Since the early 1960s, the paradigm of learning automata (LA) has experienced abundant interest. Arguably, it has also served as the foundation for the phenomenon and field of reinforcement learning (RL). Over the decades, new concepts and fundamental principles have been introduced to increase the LA's speed and accuracy. These include using probability updating functions, discretizing the probability space, and using the "Pursuit" concept. Very recently, the concept of incorporating "structure" into the ordering of the LA's actions has improved both the speed and accuracy of the corresponding hierarchical machines, when the number of actions is large. This has led to the ϵ -optimal hierarchical continuous pursuit LA (HCPA). This article pioneers the inclusion of all the above-mentioned phenomena into a new single LA, leading to the novel hierarchical discretized pursuit LA (HDPA). Indeed, although the previously proposed HCPA is powerful, its speed has an impediment when any action probability is close to unity, because the updates of the components of the probability vector are correspondingly smaller when any action probability becomes closer to unity. We propose here, the novel HDPA, where we infuse the phenomenon of discretization into the action probability vector's updating functionality, and which is invoked recursively at every stage of the machine's hierarchical structure. This discretized functionality does not possess the same impediment, because discretization prohibits it. We demonstrate the HDPA's robustness and validity by formally proving the ϵ -optimality by utilizing the moderation property. We also invoke the submartingale characteristic at every level, to prove that the action probability of the optimal action converges to unity as time goes to infinity. Apart from the new machine being ϵ -optimal, the numerical results demonstrate that the number of iterations required for convergence is significantly reduced for the HDPA, when compared to the state-of-the-art HCPA scheme.

Learning automata (LA) with artificially absorbing barriers was a completely new horizon of research in the 1980s (Oommen, 1986). These new machines yielded properties that were previously unknown. More recently, absorbing barriers have been introduced in continuous estimator algorithms so that the proofs could follow a martingale property, as opposed to monotonicity (Zhang et al., 2014), (Zhang et al., 2015). However, the applications of LA with artificial barriers are almost nonexistent. In that regard, this article is pioneering in that it provides effective and accurate solutions to an extremely complex application domain, namely that of solving two-person zero-sum stochastic games that are provided with incomplete information. LA have been previously used (Sastry et al., 1994) to design algorithms capable of converging to the game’s Nash equilibrium under limited information. Those algorithms have focused on the case where the saddle point of the game exists in a pure strategy. However, the majority of the LA algorithms used for games are absorbing in the probability simplex space, and thus, they converge to an exclusive choice of a single action. These LA are thus unable to converge to other mixed Nash equilibria when the game possesses no saddle point for a pure strategy. The pioneering contribution of this article is that we propose an LA solution that is able to converge to an optimal mixed Nash equilibrium even though there may be no saddle point when a pure strategy is invoked. The scheme, being of the linear reward-inaction ($L_{R-I}$) paradigm, is in and of itself, absorbing. However, by incorporating artificial barriers, we prevent it from being “stuck” or getting absorbed in pure strategies. Unlike the linear reward-$\epsilon $penalty ($L_{R-\epsilon P}$) scheme proposed by Lakshmivarahan and Narendra almost four decades ago, our new scheme achieves the same goal with much less parameter tuning and in a more elegant manner. This article includes the nontrial proofs of the theoretical results characterizing our scheme and also contains experimental verification that confirms our theoretical findings.

In this article, we consider the problem of load balancing (LB), but, unlike the approaches that have been proposed earlier, we attempt to resolve the problem in a fair manner (or rather, it would probably be more appropriate to describe it as an ϵ -fair manner because, although the LB can, probably, never be totally fair, we achieve this by being "as close to fair as possible"). The solution that we propose invokes a novel stochastic learning automaton (LA) scheme, so as to attain a distribution of the load to a number of nodes, where the performance level at the different nodes is approximately equal and each user experiences approximately the same Quality of the Service (QoS) irrespective of which node that he/she is connected to. Since the load is dynamically varying, static resource allocation schemes are doomed to underperform. This is further relevant in cloud environments, where we need dynamic approaches because the available resources are unpredictable (or rather, uncertain) by virtue of the shared nature of the resource pool. Furthermore, we prove here that there is a coupling involving LA's probabilities and the dynamics of the rewards themselves, which renders the environments to be nonstationary. This leads to the emergence of the so-called property of "stochastic diminishing rewards." Our newly proposed novel LA algorithm ϵ -optimally solves the problem, and this is done by resorting to a two-time-scale-based stochastic learning paradigm. As far as we know, the results presented here are of a pioneering sort, and we are unaware of any comparable results.

Although the field of learning automata (LA) has made significant progress in the past four decades, the LA-based methods to tackle problems involving environments with a large number of actions is, in reality, relatively unresolved. The extension of the traditional LA to problems within this domain cannot be easily established when the number of actions is very large. This is because the dimensionality of the action probability vector is correspondingly large, and so, most components of the vector will soon have values that are smaller than the machine accuracy permits, implying that they will never be chosen. This paper presents a solution that extends the continuous pursuit paradigm to such large-actioned problem domains. The beauty of the solution is that it is hierarchical, where all the actions offered by the environment reside as leaves of the hierarchy. Furthermore, at every level, we merely require a two-action LA that automatically resolves the problem of dealing with arbitrarily small action probabilities. In addition, since all the LA invoke the pursuit paradigm, the best action at every level trickles up toward the root. Thus, by invoking the property of the “max” operator, in which the maximum of numerous maxima is the overall maximum, the hierarchy of LA converges to the optimal action. This paper describes the scheme and formally proves its E-optimal convergence. The results presented here can, rather trivially, be extended for the families of discretized and Bayesian pursuit LA too. This paper also reports extensive experimental results (including for environments having 128 and 256 actions) that demonstrate the power of the scheme and its computational advantages. As far as we know, there are no comparable pursuitbased results in the field of LA. In some cases, the hierarchical continuous pursuit automaton requires less than 18% of the number of iterations than the benchmark LR-Ischeme, which is, by all metrics, phenomenal.

This paper deals with the finite-time analysis (FTA) of learning automata (LA), which is a topic for which very little work has been reported in the literature. This is as opposed to the asymptotic steady-state analysis for which there are, probably, scores of papers. As clarified later, unarguably, the FTA of Markov chains, in general, and of LA, in particular, is far more complex than the asymptotic steady-state analysis. Such an FTA provides rigid bounds for the time required for the LA to attain to a given convergence accuracy. We concentrate on the FTA of the Discretized Pursuit Automaton (DPA), which is probably one of the fastest and most accurate reported LA. Although such an analysis was carried out many years ago, we record that the previous work is flawed. More specifically, in all brevity, the flaw lies in the wrongly "derived" monotonic behavior of the LA after a certain number of iterations. Rather, we claim that the property should be invoked is the submartingale property. This renders the proof to be much more involved and deep. In this paper, we rectify the flaw and reestablish the FTA based on such a submartingale phenomenon. More importantly, from the derived analysis, we are able to discover and clarify, for the first time, the underlying dilemma between the DPA's exploitation and exploration properties. We also nontrivially confirm the existence of the optimal learning rate, which yields a better comprehension of the DPA itself.

The classification of dynamical data streams is among the most complex problems encountered in classification. This is, firstly, because the distribution of the data streams is non-stationary, and it changes without any prior “warning”. Secondly, the manner in which it changes is also unknown. Thirdly, and more interestingly, the model operates with the assumption that the correct classes of previously-classified patterns become available at a juncture after their appearance. This paper pioneers the use of unreported novel schemes that can classify such dynamical data streams by invoking the recently-introduced “Anti-Bayesian” (AB) techniques. Contrary to the Bayesian paradigm, that compare the testing sample with the distribution's central points, AB techniques are based on the information in the distant-from-the-mean samples. Most Bayesian approaches can be naturally extended to dynamical systems by dynamically tracking the mean of each class using, for example, the exponential moving average based estimator, or a sliding window estimator. The AB schemes introduced by Oommen et al., on the other hand, work with a radically different approach and with the non-central quantiles of the distributions. Surprisingly and counter-intuitively, the reported AB methods work equally or close-to-equally well to an optimal supervised Bayesian scheme on a host of accepted PR problems. This thus begs its natural extension to the unexplored arena of classification for dynamical data streams. Naturally, for such an AB classification approach, we need to track the non-stationarity of the quantiles of the classes. To achieve this, in this paper, we develop an AB approach for the online classification of data streams by applying the efficient and robust quantile estimators developed by Yazidi and Hammer [3], [13]. Apart from the methodology itself, in this paper, we compare the Bayesian and AB approaches. The results demonstrate the intriguing and counter-intuitive results that the AB approach shows competitive results to the Bayesian approach. Furthermore, the AB approach is much more robust against outliers, which is an inherent property of quantile estimators [3], [13], which is a property that the Bayesian approach cannot match, since it rather tracks the mean.

The purpose of this paper is to propose a solution to an extremely pertinent problem, namely, that of identifying unreliable sensors (in a domain of reliable and unreliable ones) without any knowledge of the ground truth. This fascinating paradox can be formulated in simple terms as trying to identify stochastic liars without any additional information about the truth. Though apparently impossible, we will show that it is feasible to solve the problem, a claim that is counter-intuitive in and of itself. One aspect of our contribution is to show how redundancy can be introduced, and how it can be effectively utilized in resolving this paradox. Legacy work and the reported literature (for example, in the so-called weighted majority algorithm) have merely addressed assessing the reliability of a sensor by comparing its reading to the ground truth either in an online or an offline manner. Unfortunately, the fundamental assumption of revealing the ground truth cannot be always guaranteed (or even expected) in many real life scenarios. While some extensions of the Condorcet jury theorem [9] can lead to a probabilistic guarantee on the quality of the fused process, they do not provide a solution to the unreliable sensor identification problem. The essence of our approach involves studying the agreement of each sensor with the rest of the sensors, and not comparing the reading of the individual sensors with the ground truth-as advocated in the literature. Under some mild conditions on the reliability of the sensors, we can prove that we can, indeed, filter out the unreliable ones. Our approach leverages the power of the theory of learning automata (LA) so as to gradually learn the identity of the reliable and unreliable sensors. To achieve this, we resort to a team of LA, where a distinct automaton is associated with each sensor. The solution provided here has been subjected to rigorous experimental tests, and the results presented are, in our opinion, both novel and conclusive.

Generally speaking, research in the field of estimation involves designing strong estimators, i.e., those which converge with probability 1, as the number of samples increases indefinitely. But when the underlying distribution is nonstationary, one should rather seek for weak estimators, i.e., those which can unlearn when the distribution has changed. One such estimator, the so-called stochastic learning weak estimator (SLWE) was based on the principles of continuous stochastic learning automata (LA). A problem that has been unsolved has been that of designing such weak estimators in the context of systems with finite memory, which is what we investigate here. In this paper, we propose a new family of stochastic discretized weak estimators which can track time-varying binomial distributions. As opposed to the SLWE, our proposed estimator is discretized, i.e., the estimate can assume only a finite number of values. By virtue of discretization, our estimator realizes extremely fast adjustments of the running estimates by executing jumps, and it is thus able to robustly, and very quickly, track changes in the parameters of the distribution after a switch has occurred. The design principle of our strategy is based on a solution for the stochastic search on the line problem. In order to achieve efficient estimation, we have to first infer (or rather simulate) an Artificial Oracle which informs the LA whether to go right or left, which is then utilized to infer whether we are to increase the current estimate or to decrease it. This paper briefly reports pioneering and conclusive experimental results that demonstrate the ability of the proposed estimator to cope with nonstationary environments.

Stochastic point location (SPL) deals with the problem of a learning mechanism (LM) determining the optimal point on the line when the only input it receives are stochastic signals about the direction in which it should move. One can differentiate the SPL from the traditional class of optimization problems by the fact that the former considers the case where the directional information, for example, as inferred from an Oracle (which possibly computes the derivatives), suffices to achieve the optimization-without actually explicitly computing any derivatives. The SPL can be described in terms of a LM (algorithm) attempting to locate a point on a line. The LM interacts with a random environment which essentially informs it, possibly erroneously, if the unknown parameter is on the left or the right of a given point. Given a current estimate of the optimal solution, all the reported solutions to this problem effectively move along the line to yield updated estimates which are in the neighborhood of the current solution(1) This paper proposes a dramatically distinct strategy, namely, that of partitioning the line in a hierarchical tree-like manner, and of moving to relatively distant points, as characterized by those along the path of the tree. We are thus attempting to merge the rich fields of stochastic optimization and data structures. Indeed, as in the original discretized solution to the SPL, in one sense, our solution utilizes the concept of discretization and operates a uni-dimensional controlled random walk (RW) in the discretized space, to locate the unknown parameter. However, by moving to nonneighbor points in the space, our newly proposed hierarchical stochastic searching on the line (HSSL) solution performs such a controlled RW on the discretized space structured on a superimposed binary tree. We demonstrate that the HSSL solution is orders of magnitude faster than the original SPL solution proposed by Oommen. By a rigorous analysis, the HSSL is shown to be optimal if the effectiveness (or credibility) of the environment, given by p , is greater than the golden ratio conjugate. The solution has been both analytically solved and simulated, and the results obtained are extremely fascinating, as this is the first reported use of time reversibility in the analysis of stochastic learning. The learning automata extensions of the scheme are currently being investigated. As we shall see later, hierarchical solutions have been proposed in the field of LA.

We consider the problem of a user operating within a Cognitive Radio Network (CRN) which involves N channels each associated with a Primary User (PU). The problem consists of allocating a channel which, at any given time instant is not being used by a PU, to a Secondary User (SU). Within our study, we assume that a SU is allowed to perform “channel switching”, i.e., to choose an alternate channel S times (where S +1 ≤ N) if the previous choice does not lead to a channel which is vacant. The paper first presents a formal probabilistic model for the problem itself, referred to as the Formal Secondary Channel Selection (FSCS) problem, and the characteristics of the FSCS are then analyzed. Thereafter, the paper proposes a fascinating solution to the FSCS problem by invoking the recently devised Bayesian Learning Automaton (BLA). The crucial advantage of the BLA is that unlike traditional Learning Automata (LA), it does not involve an action probability vector, but rather relies on “sampling” as per the a posteriori Bayesian estimates of the channel occupation probabilities. However, rather than utilize the BLA in the form that was earlier proposed, we shall extend it to the so-called Switchable Bayesian Learning Automaton (SBLA), which, indeed, attains the optimal solution in the overall composite action space. Apart from proposing the solution, the paper also contains detailed simulation results which demonstrate the power of the solution proposed.

This paper deals with the problems of language detection and tracking in multilingual online short word-of-mouth (WoM) discussions. This problem is particularly unusual and difficult from a pattern recognition perspective because, in these discussions, the participants and content involve the opinions of users from all over the world. The nature of these discussions, consisting of multiple topics in different languages, presents us with a problem of finding training and classification strategies when the class-conditional distributions are nonstationary. The difficulties in solving the problem are many-fold. First of all, the analyst has no knowledge of when one language stops and when the next starts. Further, the features which one uses for any one language (for example, the n-grams) will not be valid to recognize another. Finally, and most importantly, in most real-life applications, such as in WoM, the fragments of text available before the switching, are so small that it renders any meaningful classification using traditional estimation methods almost futile. Earlier, the authors [B. J. Oommen and L. Rueda, Patt. Recogn.39(1) (2006) 328–341.] had recommended that for a variety of problems, the use of strong estimators (i.e. estimators that converge with probability 1) is sub-optimal. In this vein, we propose to solve the current problem using novel estimators that are pertinent for nonstationary environments. The classification results obtained for various data sets which involve as many as eight languages demonstrates that our proposed methodology is both powerful and efficient.

Unlike the field of tutorial systems, where a real-life student interacts and learns from a software system, our research focuses on a new philosophy in which no entity needs to be a real-life individual. Such systems are termed as tutorial-like systems, and research in this field endeavors to model every component of the system using an appropriate learning model [in our case, a learning automaton (LA)].1 While models for the student, the domain, the teacher, etc., have been presented elsewhere, the aim of this paper is to present a new approach to model how the teacher, in this paradigm, of our tutorial-like system "learns and improves his "teaching skills" while being himself an integral component of the system. We propose to model the "learning process" of the teacher by using a higher level LA, referred to as the metateacher, whose task is to assist the teacher himself. Ultimately, the intention is that the latter can communicate the teaching material to the student(s) in a manner customized to the particular student's ability and progress. In short, the teacher will infer the progress of the student and initiate a strategy by which he can "custom-communicate" the material to each individual student. The results that we present in a simulated environment validate the model for the teacher and for the metateacher. The use of the latter can be seen to significantly improve the teaching abilities of the teacher.

Discovering and tracking of spatiotemporal patterns in noisy sequences of events are difficult tasks that have become increasingly pertinent due to recent advances in ubiquitous computing, such as community-based social networking applications. The core activities for applications of this class include the sharing and notification of events, and the importance and usefulness of these functionalities increase as event sharing expands into larger areas of one's life. Ironically, instead of being helpful, an excessive number of event notifications can quickly render the functionality of event sharing to be obtrusive. Indeed, any notification of events that provides redundant information to the application/user can be seen to be an unnecessary distraction. In this paper, we introduce a new scheme for discovering and tracking noisy spatiotemporal event patterns, with the purpose of suppressing reoccurring patterns, while discerning novel events. Our scheme is based on maintaining a collection of hypotheses, each one conjecturing a specific spatiotemporal event pattern. A dedicated learning automaton (LA)--the spatiotemporal pattern LA (STPLA)--is associated with each hypothesis. By processing events as they unfold, we attempt to infer the correctness of each hypothesis through a real-time guided random walk. Consequently, the scheme that we present is computationally efficient, with a minimal memory footprint. Furthermore, it is ergodic, allowing adaptation. Empirical results involving extensive simulations demonstrate the superior convergence and adaptation speed of STPLA, as well as an ability to operate successfully with noise, including both the erroneous inclusion and omission of events. An empirical comparison study was performed and confirms the superiority of our scheme compared to a similar state-of-the-art approach. In particular, the robustness of the STPLA to inclusion as well as to omission noise constitutes a unique property compared to other related approaches. In addition, the results included, which involve the so-called " presence sharing" application, are both promising and, in our opinion, impressive. It is thus our opinion that the proposed STPLA scheme is, in general, ideal for improving the usefulness of event notification and sharing systems, since it is capable of significantly, robustly, and adaptively suppressing redundant information.

Anomaly detection involves identifying observations that deviate from the normal behavior of a system. One of the ways to achieve this is by identifying the phenomena that characterize “normal” observations. Subsequently, based on the characteristics of data learned from the “normal” observations, new observations are classified as being either “normal” or not. Most state-of-the-art approaches, especially those which belong to the family parameterized statistical schemes, work under the assumption that the underlying distributions of the observations are stationary. That is, they assume that the distributions that are learned during the training (or learning) phase, though unknown, are not time-varying. They further assume that the same distributions are relevant even as new observations are encountered. Although such a “stationarity” assumption is relevant for many applications, there are some anomaly detection problems where stationarity cannot be assumed. For example, in network monitoring, the patterns which are learned to represent normal behavior may change over time due to several factors such as network infrastructure expansion, new services, growth of user population, etc. Similarly, in meteorology, identifying anomalous temperature patterns involves taking into account seasonal changes of normal observations. Detecting anomalies or outliers under these circumstances introduces several challenges. Indeed, the ability to adapt to changes in non-stationary environments is necessary so that anomalous observations can be identified even with changes in what would otherwise be classified as “normal” behavior. In this paper, we proposed to apply weak estimation theory for anomaly detection in dynamic environments. In particular, we apply this theory to detect anomaly activities in system calls. Our experimental results demonstrate that our proposal is both feasible and effective for the detection of such anomalous activities.

Anomaly detection involves identifying observations that deviate from the normal behavior of a system. One of the ways to achieve this is by identifying the phenomena that characterize “normal” observations. Subsequently, based on the characteristics of data learned from the “normal” observations, new observations are classified as being either “normal” or not. Most state-of-the-art approaches, especially those which belong to the family of parameterized statistical schemes, work under the assumption that the underlying distributions of the observations are stationary. That is, they assume that the distributions that are learned during the training (or learning) phase, though unknown, are not time-varying. They further assume that the same distributions are relevant even as new observations are encountered. Although such a “stationarity” assumption is relevant for many applications, there are some anomaly detection problems where stationarity cannot be assumed. For example, in network monitoring, the patterns which are learned to represent normal behavior may change over time due to several factors such as network infrastructure expansion, new services, growth of user population, and so on. Similarly, in meteorology, identifying anomalous temperature patterns involves taking into account seasonal changes of normal observations. Detecting anomalies or outliers under these circumstances introduces several challenges. Indeed, the ability to adapt to changes in nonstationary environments is necessary so that anomalous observations can be identified even with changes in what would otherwise be classified as “normal” behavior. In this article we propose to apply a family of weak estimators for anomaly detection in dynamic environments. In particular, we apply this theory to spam email detection. Our experimental results demonstrate that our proposal is both feasible and effective for the detection of such anomalous emails.

Abstract This paper surveys the fields of Statistical Disclosure Control (SDC) and Micro‐Aggregation Techniques (MATs), which are both areas fundamental to the science of secure Statistical DataBases (SDBs). The paper is written from the perspective of a computer scientist with the hope that it will prove to be a source of reference material useful to researchers and practitioners in the field. The paper first introduces the concept ofSDCand describes the domain of its applications and the various data types that are currently used inSDBs. It then proceeds to focus on the family of micro‐data types inSDBs. At this juncture, we introduce the importance of the relevant measures, namely the metrics termed as the Information Loss (IL) and the Disclosure Risk (DR), after which we survey the various methods of resolving the conflicting goals that these metrics represent. Thereafter, the paper summarizes the perturbative and non‐perturbativeSDCmethods for micro‐data protection, and it focuses on the families ofMATs by formally stating the Micro‐Aggregation Problem and surveying it in a comprehensive manner. Apart from the paper including a historical view of the field ofMATs, it describes a broad selection of work that has been reported more recently. Indeed, we believe that this paper represents a complete overview of the state‐of‐the‐art techniques. Copyright © 2010 John Wiley & Sons, Ltd.

In a multitude of real-world situations, resources must be allocated based on incomplete and noisy information. However, in many cases, incomplete and noisy information render traditional resource allocation techniques ineffective. The decentralized Learning Automata Knapsack Game (LAKG) was recently proposed for solving one such class of problems, namely the class of Stochastic Nonlinear Fractional Knapsack Problems. Empirically, the LAKG was shown to yield a superior performance when compared to methods which are based on traditional parameter estimation schemes. This paper presents a completely new online Learning Automata (LA) system, namely the Hierarchy of Twofold Resource Allocation Automata (H-TRAA). In terms of contributions, we first of all, note that the primitive component of the H-TRAA is a Twofold Resource Allocation Automaton (TRAA) which possesses novelty in the field of LA. Second, the paper contains a formal analysis of the TRAA, including a rigorous proof for its convergence. Third, the paper proves the convergence of the H-TRAA itself. Finally, we demonstrate empirically that the H-TRAA provides orders of magnitude faster convergence compared to the LAKG for simulated data pertaining to two-material unit-value functions. Indeed, in contrast to the LAKG, the H-TRAA scales sublinearly. Consequently, we believe that the H-TRAA opens avenues for handling demanding real-world applications such as the allocation of sampling resources in large-scale Web accessibility assessment problems. We are currently working on applying the H-TRAA solution to the web-polling and sample-size detection problems applicable to the world wide web.

This paper considers the NP-hard problem of object assignment with respect to multiple constraints: assigning a set of elements (or objects) into mutually exclusive classes (or groups), where the elements which are "similar" to each other are hopefully located in the same class. The literature reports solutions in which the similarity constraint consists of a single index that is inappropriate for the type of multiconstraint problems considered here and where the constraints could simultaneously be contradictory. This feature, where we permit possibly contradictory constraints, distinguishes this paper from the state of the art. Indeed, we are aware of no learning automata (or other heuristic) solutions which solve this problem in its most general setting. Such a scenario is illustrated with the static mapping problem, which consists of distributing the processes of a parallel application onto a set of computing nodes. This is a classical and yet very important problem within the areas of parallel computing, grid computing, and cloud computing. We have developed four learning-automata (LA)-based algorithms to solve this problem: First, a fixed-structure stochastic automata algorithm is presented, where the processes try to form pairs to go onto the same node. This algorithm solves the problem, although it requires some centralized coordination. As it is desirable to avoid centralized control, we subsequently present three different variable-structure stochastic automata (VSSA) algorithms, which have superior partitioning properties in certain settings, although they forfeit some of the scalability features of the fixed-structure algorithm. All three VSSA algorithms model the processes as automata having first the hosting nodes as possible actions; second, the processes as possible actions; and, third, attempting to estimate the process communication digraph prior to probabilistically mapping the processes. This paper, which, we believe, comprehensively reports the pioneering LA solutions to this problem, unequivocally demonstrates that LA can play an important role in solving complex combinatorial and integer optimization problems.

In this paper, we present a learning-automata-like The reason why the mechanism is not a pure LA, but rather why it yet mimics one, will be clarified in the body of this paper. (LAL) mechanism for congestion avoidance in wired networks. Our algorithm, named as LAL Random Early Detection (LALRED), is founded on the principles of the operations of existing RED congestion-avoidance mechanisms, augmented with a LAL philosophy. The primary objective of LALRED is to optimize the value of the average size of the queue used for congestion avoidance and to consequently reduce the total loss of packets at the queue. We attempt to achieve this by stationing a LAL algorithm at the gateways and by discretizing the probabilities of the corresponding actions of the congestion-avoidance algorithm. At every time instant, the LAL scheme, in turn, chooses the action that possesses the maximal ratio between the number of times the chosen action is rewarded and the number of times that it has been chosen. In LALRED, we simultaneously increase the likelihood of the scheme converging to the action, which minimizes the number of packet drops at the gateway. Our approach helps to improve the performance of congestion avoidance by adaptively minimizing the queue-loss rate and the average queue size. Simulation results obtained using NS2 establish the improved performance of LALRED over the traditional RED methods which were chosen as the benchmarks for performance comparison purposes.

This paper presents a possibly pioneering endeavor to tackle the Microaggregation Techniques (MATs) in secure statistical databases by resorting to the principles of associative neural networks (NNs). The prior art has improved the available solutions to the MAT by incorporating proximity information, and this approach is done by recursively reducing the size of the data set by excluding points that are farthest from the centroid and points that are closest to these farthest points. Thus, although the method is extremely effective, arguably, it uses only the proximity information while ignoring the mutual interaction between the records. In this paper, we argue that interrecord relationships can be quantified in terms of the following two entities: 1) their "association" and 2) their "interaction." This case means that records that are not necessarily close to each other may still be "grouped," because their mutual interaction, which is quantified by invoking transitive-closure-like operations on the latter entity, could be significant, as suggested by the theoretically sound principles of NNs. By repeatedly invoking the interrecord associations and interactions, the records are grouped into sizes of cardinality " k," where k is the security parameter in the algorithm. Our experimental results, which are done on artificial data and benchmark real-life data sets, demonstrate that the newly proposed method is superior to the state of the art not only based on the Information Loss (IL) perspective but also when it concerns a criterion that involves a combination of the IL and the Disclosure Risk (DR).

Almost all of the learning paradigms used in machine learning, learning automata (LA), and learning theory, in general, use the philosophy of a Student (learning mechanism) attempting to learn from a teacher. This paradigm has been generalized in a myriad of ways, including the scenario when there are multiple teachers or a hierarchy of mechanisms that collectively achieve the learning. In this paper, we consider a departure from this paradigm by allowing the Student to be a member of a classroom of Students, where, for the most part, we permit each member of the classroom not only to learn from the teacher(s) but also to "extract" information from any of his fellow Students. This paper deals with issues concerning the modeling, decision-making process, and testing of such a scenario within the LA context. The main result that we show is that a weak learner can actually benefit from this capability of utilizing the information that he gets from a superior colleague-if this information transfer is done appropriately. As far as we know, the whole concept of Students learning from both a teacher and from a classroom of Students is novel and unreported in the literature. The proposed Student-classroom interaction has been tested for numerous strategies and for different environments, including the established benchmarks, and the results show that Students can improve their learning by interacting with each other. For example, for some interaction strategies, a weak Student can improve his learning by up to 73% when interacting with a classroom of Students, which includes Students of various capabilities. In these interactions, the Student does not have a priori knowledge of the identity or characteristics of the Students who offer their assistance.

This paper presents a new philosophy to model the behavior of a student in a tutorial- like system using learning automata (LAs). The model of the student in our system is inferred using a higher level LA, referred to as a meta-LA , which attempts to characterize the learning model of the students (or student simulators), while the latter use the tutorial-like system. The meta-LA , in turn, uses LAs as a learning mechanism to try to determine if the student in question is a fast, normal, or slow learner. The ultimate long-term goal of the exercise is the following: if the tutorial- like system can understand how the student perceives and processes knowledge, it will be able to customize the way by which it communicates the knowledge to the student to attain an optimal teaching strategy. The proposed meta-LA scheme has been tested for numerous environments, including the established benchmarks, and the results obtained are remarkable. Indeed, to the best of our knowledge, this is the first published result that infers the learning model of an LA when it is externally treated as a black box, whose outputs are the only observable quantities. Additionally, our paper represents a new class of multiautomata systems, where the meta-LA synchronously communicates with the students, also modeled using LAs. The meta-LA's environment "observes" the progress of the student LA, and the response of the latter to the meta-LA actions is based on these observations. This paper also discusses the learning system implications of such a meta-LA.

In this paper, we present an adaptive learning (specifically, learning automata) Like (LAL) mechanism for congestion avoidance in wired networks. Our algorithm, named as learning automata like random early detection (LALRED), is founded on the principles of operations of the existing random early detection (RED) congestion avoidance mechanisms, augmented with a LAL philosophy. Our approach helps to improve the performance of congestion avoidance by adaptively minimizing the queue loss rate and the average queue size. Simulation results obtained using NS2 establish the improved performance of LALRED over the traditional RED, which was chosen as the benchmark for performance comparison purposes.

The Adachi neural network (AdNN) is a fascinating neural network (NN) which has been shown to possess chaotic properties, and to also demonstrate associative memory (AM) and pattern recognition (PR) characteristics. Variants of the AdNN have also been used to obtain other PR phenomena, and even blurring. An unsurmountable problem associated with the AdNN and the variants referred to above is that all of them require a quadratic number of computations. This is essentially because the NNs in each case are completely connected graphs. In this paper, we consider how the computations can be significantly reduced by merely using a linear number of computations. To achieves this, we extract from the original completely connected graph one of its spanning trees. We then address the problem of computing the weights for this spanning tree. This is done in such a manner that the modified tree-based NN has approximately the same input-output characteristics, and thus the new weights are themselves calculated using a gradient-based algorithm. By a detailed experimental analysis, we show that the new linear-time AdNN-like network possesses chaotic and PR properties for different settings. As far as we know, such a tree-based AdNN has not been reported, and the results given here are novel.

We consider the microaggregation problem (MAP) that involves partitioning a set of individual records in a microdata file into a number of mutually exclusive and exhaustive groups. This problem, which seeks for the best partition of the microdata file, is known to be NP-hard and has been tackled using many heuristic solutions. In this paper, we present the first reported fixed-structure-stochastic-automata-based solution to this problem. The newly proposed method leads to a lower value of the information loss (IL), obtains a better tradeoff between the IL and the disclosure risk (DR) when compared with state-of-the-art methods, and leads to a superior value of the scoring index, which is a criterion involving a combination of the IL and the DR. The scheme has been implemented, tested, and evaluated for different real-life and simulated data sets. The results clearly demonstrate the applicability of learning automata to the MAP and its ability to yield a solution that obtains the best tradeoff between IL and DR when compared with the state of the art.

Fisher's linear discriminant analysis (LDA) is a traditional dimensionality reduction method that has been proven to be successful for decades. Numerous variants, such as the kernel-based Fisher discriminant analysis (KFDA), have been proposed to enhance the LDA's power for nonlinear discriminants. Although effective, the KFDA is computationally expensive, since the complexity increases with the size of the data set. In this correspondence, we suggest a novel strategy to enhance the computation for an entire family of the KFDAs. Rather than invoke the KFDA for the entire data set, we advocate that the data be first reduced into a smaller representative subset using a prototype reduction scheme and that the dimensionality reduction be achieved by invoking a KFDA on this reduced data set. In this way, data points that are ineffective in the dimension reduction and classification can be eliminated to obtain a significantly reduced kernel matrix K without degrading the performance. Our experimental results demonstrate that the proposed mechanism dramatically reduces the computation time without sacrificing the classification accuracy for artificial and real-life data sets.

This paper reports the first known solution to the stochastic point location (SPL) problem when the environment is nonstationary. The SPL problem involves a general learning problem in which the learning mechanism (which could be a robot, a learning automaton, or, in general, an algorithm) attempts to learn a "parameter," for example, lambda*, within a closed interval. However, unlike the earlier reported results, we consider the scenario when the learning is to be done in a nonstationary setting. For each guess, the environment essentially informs the mechanism, possibly erroneously (i.e., with probability p), which way it should move to reach the unknown point. Unlike the results available in the literature, we consider the fascinating case when the point sought for is itself stochastically moving (which is modeled as follows). The environment communicates with an intermediate entity (referred to as the teacher/oracle) about the point itself, i.e., advising where it should go. The mechanism that searches for the point in turn receives responses from the teacher/oracle, which directs how it should move. Therefore, the point itself, in the overall setting, is moving, i.e., delivering possibly incorrect information about its location to the teacher/oracle. This in turn means that the "environment" is itself nonstationary, which implies that the advice of the teacher/oracle is both uncertain and changing with time-rendering the problem extremely fascinating. The heart of the strategy we propose involves discretizing the space and performing a controlled random walk on this space. Apart from deriving some analytic results about our solution, we also report the simulation results that demonstrate the power of the scheme, and state some potential applications.

The goal of this paper is to present a novel approach to model the behavior of a Teacher in a Tutorial-like system. In this model, the Teacher is capable of presenting teaching material from a Socratic-type Domain model via multiple-choice questions. Since this knowledge is stored in the Domain model in chapters with different levels of complexity, the Teacher is able to present learning material of varying degrees of difficulty to the Students. In our model, we propose that the Teacher will be able to assist the Students to learn the more difficult material. In order to achieve this, he provides them with hints that are relative to the difficulty of the learning material presented. This enables the Students to cope with the process of handling more complex knowledge, and to be able to learn it appropriately. To our knowledge, the findings of this study are novel in the field of LA. The novelty lies in the fact that the learning system has a strategy by which it can deal with increasingly more complex/difficult Environments. In our approach, the convergence of the LA (Students) is driven not only by the response of the Environment (Teacher), but also by the hints that are provided by the latter. Our proposed Teacher model has been tested against different benchmark Environments, and the results of these simulations have demonstrated the salient aspects of our model. The main conclusion is that Normal and Below-Normal learners benefited significantly from the hints provided by the Teacher, while the benefits to (brilliant) Fast learners were marginal. This seems to be in-line with our subjective understanding of the behavior of real-life Students.

Almost all of the learning paradigms used in machine learning, learning automata (LA), and learning theory, in general, use the philosophy of a student (learning mechanism) attempting to learn from a teacher. This paradigm has been generalized in a myriad of ways including the scenario when there are multiple teachers or a hierarchy of mechanisms which collectively achieve the learning. In this paper, we consider a departure from this paradigm by allowing the student to be a member of a classroom of students, where, for the most part, we permit each member of the classroom to not only learn from the teacher(s) but also to "extract" information from any of his colleague students. This paper deals with the issues concerning the modeling, decision making process and testing of such a scenario within the LA context. The main result that we show is that a weak learner can actually benefit from this capability of utilizing the information that the gets from a superior colleague - if this information transfer is done appropriately.

We examine the problem of self-organizing linear search lists, which are lists that react to queries received from an environment by running a heuristic to reorganize the records in order to minimize the search cost. In particular, we are concerned with environments with the locality of reference phenomenon, when the queries exhibit a probabilistic dependence between themselves. We introduce a novel list organization framework that we call Lists-on-Lists (LOL), which regards the list as a set of sublists that are manageable in the same way that individual records are. An LOL organization involves a reorganization operation on the accessed record level, as well as another on the sublist which it belongs to (the record's context). We show that it is beneficial to consider the reorganization of the context together with the accessed record, since other records within the context are likely to be accessed in the near future. With the aid of a learning automaton-based partitioning algorithm, we demonstrate that we can accurately classify the different contexts of the sublist. To the best of our knowledge, both the concept of reorganizing the list ‘hierarchically’ using such a two-step LOL process, and the application of stochastic learning to this problem are new to the field. Indeed, while the costs involved to achieve these enhancements are almost of the same order as that which achieves basic list-organizing, using this framework, we were able to empirically achieve asymptotic search costs that are significantly superior to (sometimes even an order of magnitude better than) the Move-To-Front heuristic, widely acknowledged as the best algorithm for such environments.

This paper presents an efficient adaptive online routing algorithm for the computation of bandwidth-guaranteed paths in multiprotocol label switching witching (MPLS)-based networks by using a learning scheme that computes an optimal ordering of routes. The contribution of this work is twofold. The first is that we propose a new class of solutions other than those available in the literature, incorporating the family of stochastic random races (RR) algorithms. The most popular previously proposed MPLS-based traffic engineering (TE) solutions attempt to find a superior path to route an incoming setup request. Our algorithm, on the other hand, tries to learn an optimal ordering of the paths through which requests can be routed according to the rank of the paths in the order learned by the algorithm. The second contribution of our work is that we have proposed a routing algorithm that has a performance superior to the important algorithms in the literature. Our conclusions are based on three important performance criteria: 1) the rejection ratio, 2) the percentage of accepted bandwidth, and 3) the average route computation time per request. Although some of the previously proposed algorithms were designed to achieve low rejection and high throughput of route requests, they are unreasonably slow. Our algorithm, on the other hand, in general attempts to reject the least number of requests, achieves the highest throughput, and computes routes in the fastest possible time when compared to the algorithms that we used as benchmarks for comparison.

A multimedia analysis system utilizes a set of correlated media streams, each of which, we assume, has a confidence level and a cost associated with it, and each of which partially helps in achieving the system goal. However, the fact that at any instant, not all of the media streams contribute towards a system goal brings up the issue of finding the best subset from the available set of media streams. For example, a subset of two video cameras and two microphones could be better than any other subset of sensors at some time instance to achieve a surveillance goal (e.g. event detection). This article presents a novel framework that finds the optimal subset of media streams so as to achieve the system goal under specified constraints. The proposed framework uses a dynamic programming approach to find the optimal subset of media streams based on three different criteria: first, by maximizing the probability of achieving the goal under the specified cost and confidence; second, by maximizing the confidence in the achieved goal under the specified cost and probability with which the goal is achieved; and third, by minimizing the cost to achieve the goal with a specified probability and confidence. Each of these problems is proven to be NP-Complete. From an AI point of view, the solution we propose is heuristic-based, and for each criterion, utilizes a heuristic function which for a given problem, combines optimal solutions of small-sized subproblems to yield a potential near-optimal solution to the original problem. The proposed framework allows for a tradeoff among the aforementioned three criteria, and offers the flexibility to compare whether any one set of media streams of low cost would be better than any other set of higher cost, or whether any one set of media streams of high confidence would be better than any other set of low confidence. To show the utility of our framework, we provide the experimental results for event detection in a surveillance scenario.

The usual goal of modeling natural and artificial perception involves determining how a system can extract the object that it perceives from an image that is noisy. The "inverse" of this problem is one of modeling how even a clear image can be perceived to be blurred in certain contexts. To our knowledge, there is no solution to this in the literature other than for an oversimplified model in which the true image is garbled with noise by the perceiver himself. In this paper, we propose a chaotic model of pattern recognition (PR) for the theory of "blurring." This paper, which is an extension to a companion paper demonstrates how one can model blurring from the view point of a chaotic PR system. Unlike the companion paper in which a chaotic PR system extracts the pattern from the input, in this case, we show that even without the inclusion of additional noise, perception of an object can be "blurred" if the dynamics of the chaotic system are modified. We thus propose a formal model and present an analysis using the Lyapunov exponents and the Routh-Hurwitz criterion. We also demonstrate experimentally the validity of our model by using a numeral data set. A byproduct of this model is the theoretical possibility of desynchronization of the periodic behavior of the brain (as a chaotic system), rendering us the possibility of predicting, controlling, and annulling epileptic behavior.

This paper considers the nonlinear fractional knapsack problem and demonstrates how its solution can be effectively applied to two resource allocation problems dealing with the World Wide Web. The novel solution involves a "team" of deterministic learning automata (LA). The first real-life problem relates to resource allocation in web monitoring so as to "optimize" information discovery when the polling capacity is constrained. The disadvantages of the currently reported solutions are explained in this paper. The second problem concerns allocating limited sampling resources in a "real-time" manner with the purpose of estimating multiple binomial proportions. This is the scenario encountered when the user has to evaluate multiple web sites by accessing a limited number of web pages, and the proportions of interest are the fraction of each web site that is successfully validated by an HTML validator. Using the general LA paradigm to tackle both of the real-life problems, the proposed scheme improves a current solution in an online manner through a series of informed guesses that move toward the optimal solution. At the heart of the scheme, a team of deterministic LA performs a controlled random walk on a discretized solution space. Comprehensive experimental results demonstrate that the discretization resolution determines the precision of the scheme, and that for a given precision, the current solution (to both problems) is consistently improved until a nearly optimal solution is found--even for switching environments. Thus, the scheme, while being novel to the entire field of LA, also efficiently handles a class of resource allocation problems previously not addressed in the literature.

This paper presents a Learning Automaton (LA) solution to the Multi-Constrained Mapping problem, which has its applications in the allocation of processes on processors so as to satisfy multiple (possibly conflicting) constraints. Mathematically, it considers the problem of partitioning a set of elements (or objects) into mutually exclusive classes (or groups), where elements which are "similar" to each other are, hopefully, located in the same class. This problem has been shown to be NP-Hard, and the literature reports solutions in which the similarity constraint consists of a single index. For example, typical "similarity" conditions that have been used in the literature include those in which "similar" objects are accessed together (as in the context of query systems), or when they communicate (as processes do) with each other. The application at hand is the static mapping problem (SMP) of distributing the processes of a parallel application onto a set of computing nodes. Such an application may run on multiple GRID sites where it is desirable avoid centralised control and mapping. This paper proposes a solution to this combinatorial optimization problem resulting from the collective behaviour of independent Discrete General Pursuit Automata (DGPA) that tries to learn the digraph of the communication among the processes of the application, and group together processes with strong mutual dependencies. Earlier learning solutions to the problem were either based on centralised mapping with full system knowledge. In this paper, we attempt to relax this assumptions, thus rendering the problem more complex. The present solution performs very well when the system size is small. However, the simulated results demonstrate that the quality of the final solution decreases with the number of elements. Thus, although this is the first reported solution to the problem which incorporates the specific digraph properties of the objects, the scalability of the solution to the problem which incorporates the specific digraph properties of the objects, the scalability of the solution remains open.

Designing routing schemes that would successfully operate in the presence of adversarial environments in mobile ad hoc networks (MANETs) is a challenging issue. In this paper we discuss fault-tolerant routing schemes where there are malfunctioning nodes in the network. Most existing MANET protocols were postulated considering scenarios where all the mobile nodes in the ad hoc network function properly, and in an idealistic manner. However, adversarial environments are common in MANET environments, and there are misbehaving nodes that degrade the performance of these routing protocols. The need for fault tolerant routing protocols was identified to address routing in adversarial environments in the presence of faulty nodes by exploring network redundancies in networks. In this paper, we present a new fault-tolerant routing scheme using a stochastic learning-based weak estimation procedure. The superiority of our algorithm, as compared to the existing algorithms, was experimentally established

This paper presents a new solution to the dynamic all-pairs shortest path routing problem, using a linear reinforcement learning scheme. The particular instance of the problem that we have investigated concerns finding the all-pairs shortest paths in a stochastic graph, where there are continuous probabilistically-based updates in edge-weights. We present the details of the algorithm with an illustrative example. The algorithm can be used to find the all-pairs shortest paths for the "statistical" average graph, and the solution converges irrespective of whether there are new changes in edge-weights or not. On the other hand, the existing algorithms will fail to exhibit such a behavior and would recalculate the affected shortest paths after each edge-weight update. There are two important contributions of the proposed algorithm. The first contribution is that not all the edges in a stochastic graph are probed and, even if they are, they are not all probed equally often. Indeed, the algorithm attempts to almost always probe only those edges that will be included in the final list involving all pairs of nodes in the graph, while probing the other edges minimally. This increases the performance of the proposed algorithm. The second contribution is designing a data-structure, the elements of which represent the probability that a particular edge in the graph lies in the shortest path between a pair of nodes in the graph. All the algorithms were tested in environments where edge-weights change stochastically and where the graph topologies undergo multiple simultaneous edge-weight updates. Its superiority in terms of the average number of processed nodes, scanned edges, and the time per update operation, when compared with the existing algorithms, was experimentally established.

This paper deals with the problem of estimating, using enhanced artificial-intelligence (AI) techniques, a transmitted string X* by processing the corresponding string Y, which is a noisy version of X*. It is assumed that Y contains substitution, insertion, and deletion (SID) errors. The best estimate X+ of X* is defined as that element of a dictionary H that minimizes the generalized Levenshtein distance (GLD) D (X, Y) between X and Y, for all X epsilon H. In this paper, it is shown how to evaluate D (X, Y) for every X epsilon H simultaneously, when the edit distances are general and the maximum number of errors is not given a priori, and when H is stored as a trie. A new scheme called clustered beam search (CBS) is first introduced, which is a heuristic-based search approach that enhances the well-known beam-search (BS) techniques used in AI. The new scheme is then applied to the approximate string-matching problem when the dictionary is stored as a trie. The new technique is compared with the benchmark depth-first search (DFS) trie-based technique (with respect to time and accuracy) using large and small dictionaries. The results demonstrate a marked improvement of up to 75% with respect to the total number of operations needed on three benchmark dictionaries, while yielding an accuracy comparable to the optimal. Experiments are also done to show the benefits of the CBS over the BS when the search is done on the trie. The results also demonstrate a marked improvement (more than 91%) for large dictionaries.

This paper considers a general learning problem akin to the field of learning automata (LA) in which the learning mechanism attempts to learn from a stochastic teacher or a stochastic compulsive liar. More specifically, unlike the traditional LA model in which LA attempts to learn the optimal action offered by the Environment (also here called the "Oracle"), this paper considers the problem of the learning mechanism (robot, an LA, or in general, an algorithm) attempting to learn a "parameter" within a closed interval. The problem is modeled as follows: The learning mechanism is trying to locate an unknown point on a real interval by interacting with a stochastic Environment through a series of informed guesses. For each guess, the Environment essentially informs the mechanism, possibly erroneously (i.e., with probability p), which way it should move to reach the unknown point. When the probability of a correct response is p > 0.5, the Environment is said to be informative, and thus the case of learning from a stochastic teacher. When this probability p < 0.5, the Environment is deemed deceptive, and is called a stochastic compulsive liar. This paper describes a novel learning strategy by which the unknown parameter can be learned in both environments. These results are the first reported results, which are applicable to the latter scenario. The most significant contribution of this paper is that the proposed scheme is shown to operate equally well, even when the learning mechanism is unaware of whether the Environment ("Oracle") is informative or deceptive. The learning strategy proposed herein, called CPL-AdS, partitions the search interval into d subintervals, evaluates the location of the unknown point with respect to these subintervals using fast-converging E-optimal LRI LA, and prunes the search space in each iteration by eliminating at least one partition. The CPL-AdS algorithm is shown to provably converge to the unknown point with an arbitrary degree of accuracy with probability as close to unity as desired. Comprehensive experimental results confirm the fast and accurate convergence of the search for a wide range of values for the Environment's feedback accuracy parameter p, and thus has numerous potential applications.

This correspondence shows that learning automata techniques, which have been useful in developing weak estimators, can be applied to data compression applications in which the data distributions are nonstationary. The adaptive coding scheme utilizes stochastic learning-based weak estimation techniques to adaptively update the probabilities of the source symbols, and this is done without resorting to either maximum likelihood, Bayesian, or sliding-window methods. The authors have incorporated the estimator in the adaptive Fano coding scheme and in an adaptive entropy-based scheme that "resembles" the well-known arithmetic coding. The empirical results obtained for both of these adaptive methods are obtained on real-life files that possess a fair degree of nonstationarity. From these results, it can be seen that the proposed schemes compress nearly 10% more than their respective adaptive methods that use maximum-likelihood estimator-based estimates.

This paper presents a new solution to the dynamic all-pairs shortest path routing problem, using a linear reinforcement learning scheme. It involves finding the shortest path in a stochastic network, where there are continuous probabilistically-based updates in link-costs. In this paper we present the details of the algorithm and also provide an example to illustrate how the algorithm would function. The initial experimental results of the algorithm show that the algorithm is few orders of magnitude superior to the algorithms available in the literature. It can be used to find the shortest path (between all pairs of nodes in a network) within the "statistical" average network, which converges irrespective of whether there are new changes in link-costs or not. On the other hand, the existing algorithms fails to exhibit such a behavior and would recalculate the affected shortest paths after each link-cost update.

A ternary search trie (TST) is a highly efficient dynamic dictionary structure applicable for strings and textual data. The strings are accessed based on a set of access probabilities and are to be arranged using a TST. We consider the scenario where the probabilities are not known a priori and is time-invariant. Our aim is to adaptively restructure the TST so as to yield the best access or retrieval time. Unlike the case of lists and binary search trees where numerous methods have been proposed, in the case of the TST, currently, the number of reported adaptive schemes are few. In this paper we consider various self-organizing schemes that were applied to binary search trees and apply them to TSTs. Three new schemes, which are the splaying, the conditional rotation and the randomization heuristics, have been proposed, tested and comparatively presented. The results demonstrate that the conditional rotation heuristic is the best when compared with other heuristics that are considered in the paper.

In Kernel-based Nonlinear Subspace (KNS) methods, the subspace dimensions have a strong influence on the performance of the subspace classifier. In order to get a high classification accuracy, a large dimension is generally required. However, if the chosen subspace dimension is too large, it leads to a low performance due to the overlapping of the resultant subspaces and, if it is too small, it increases the classification error due to the poor resulting approximation. The most common approach is of an ad hoc nature, which selects the dimensions based on the so-called cumulative proportion computed from the kernel matrix for each class. In this paper, we propose a new method of systematically and efficiently selecting optimal or near-optimal subspace dimensions for KNS classifiers using a search strategy and a heuristic function termed the Overlapping criterion. The rationale for this function has been motivated in the body of the paper. The task of selecting optimal subspace dimensions is reduced to finding the best ones from a given problem-domain solution space using this criterion as a heuristic function. Thus, the search space can be pruned to very efficiently find the best solution. Our experimental results demonstrate that the proposed mechanism selects the dimensions efficiently without sacrificing the classification accuracy.

In Kernel-based Nonlinear Subspace (KNS) methods, the length of the projections onto the principal component directions in the feature space, is computed using a kernel matrix, K, whose dimension is equivalent to the number of sample data points. Clearly this is problematic, especially, for large data sets. In this paper, we solve this problem by subdividing the data into smaller subsets, and utilizing a Prototype Reduction Scheme (PRS) as a preprocessing module, to yield more refined representative prototypes. Thereafter, a Classifier Fusion Strategy (CFS) is invoked as a postprocessing module, to combine the individual KNS classification results to derive a consensus decision. Essentially, the PRS is used to yield computational advantage, and the CFS, in turn, is used to compensate for the decreased efficiency caused by the data set division. Our experimental results demonstrate that the proposed mechanism significantly reduces the prototype extraction time as well as the computation time without sacrificing the classification accuracy. The results especially demonstrate a significant computational advantage for large data sets within a parallel processing philosophy.

This paper presents the first Learning Automaton-based solution to the dynamic single source shortest path problem. It involves finding the shortest path in a single-source stochastic graph topology where there are continuous probabilistic updates in the edge-weights. The algorithm is significantly more efficient than the existing solutions, and can be used to find the "statistical" shortest path tree in the "average" graph topology. It converges to this solution irrespective of whether there are new changes in edge-weights taking place or not. In such random settings, the proposed learning automata solution converges to the set of shortest paths. On the other hand, the existing algorithms will fail to exhibit such a behavior, and would recalculate the affected shortest paths after each weight-change. The important contribution of the proposed algorithm is that all the edges in a stochastic graph are not probed, and even if they are, they are not all probed equally often. Indeed, the algorithm attempts to almost always probe only those edges that will be included in the shortest path graph, while probing the other edges minimally. This increases the performance of the proposed algorithm. All the algorithms were tested in environments where edge-weights change stochastically, and where the graph topologies undergo multiple simultaneous edge-weight updates. Its superiority in terms of the average number of processed nodes, scanned edges and the time per update operation, when compared with the existing algorithms, was experimentally established. The algorithm can be applicable in domains ranging from ground transportation to aerospace, from civilian applications to military, from spatial database applications to telecommunications networking.

This paper presents a new efficient solution to the dynamic single source shortest path routing problem, using the principles of generalized pursuit learning. It involves finding the shortest path in a stochastic network, where there are continuous probabilistically based updates in link-costs. The algorithm has been rigorously experimentally evaluated and has been found to be a few orders of magnitude superior to the algorithms available in the literature. It can be used to find the shortest path within the "statistical" average network, which converges irrespective of whether there are new changes in link-costs or not. On the other hand, the existing algorithms would fail to exhibit such a behavior and would recalculate the affected shortest paths after each link-cost update.

Most of the prototype reduction schemes (PRS), which have been reported in the literature, process the data in its entirety to yield a subset of prototypes that are useful in nearest-neighbor-like classification. Foremost among these are the prototypes for nearest neighbor classifiers, the vector quantization technique, and the support vector machines. These methods suffer from a major disadvantage, namely, that of the excessive computational burden encountered by processing all the data. In this paper, we suggest a recursive and computationally superior mechanism referred to as adaptive recursive partitioning (ARP)_PRS. Rather than process all the data using a PRS, we propose that the data be recursively subdivided into smaller subsets. This recursive subdivision can be arbitrary, and need not utilize any underlying clustering philosophy. The advantage of ARP_PRS is that the PRS processes subsets of data points that effectively sample the entire space to yield smaller subsets of prototypes. These prototypes are then, in turn, gathered and processed by the PRS to yield more refined prototypes. In this manner, prototypes which are in the interior of the Voronoi spaces, and thus ineffective in the classification, are eliminated at the subsequent invocations of the PRS. We are unaware of any PRS that employs such a recursive philosophy. Although we marginally forfeit accuracy in return for computational efficiency, our experimental results demonstrate that the proposed recursive mechanism yields classification comparable to the best reported prototype condensation schemes reported to-date. Indeed, this is true for both artificial data sets and for samples involving real-life data sets. The results especially demonstrate that a fair computational advantage can be obtained by using such a recursive strategy for "large" data sets, such as those involved in data mining and text categorization applications.

In addition to the classical heuristic algorithms of operations research, there have also been several approaches based on artificial neural networks for solving the traveling salesman problem. Their efficiency, however, decreases as the problem size (number of cities) increases. A technique to reduce the complexity of a large-scale traveling salesman problem (TSP) instance is to decompose or partition it into smaller subproblems. We introduce an all-neural decomposition heuristic that is based on a recent self-organizing map called KNIES, which has been successfully implemented for solving both the Euclidean traveling salesman problem and the Euclidean Hamiltonian path problem. Our solution for the Euclidean TSP proceeds by solving the Euclidean HPP for the subproblems, and then patching these solutions together. No such all-neural solution has ever been reported.

Benchmarking is an important phase in developing any new software technique because it helps to validate the underlying theory in the specific problem domain. But benchmarking of new software strategies is a very complex problem, because it is difficult (if not impossible) to test, validate and verify the results of the various schemes in completely different settings. This is even more true in the case of database systems because the benchmarking also depends on the types of queries presented to the databases used in the benchmarking experiments. Query optimization strategies in relational database systems rely on approximately estimating the query result sizes to minimize the response time for user-queries. Among the many query result size estimation techniques, the histogram-based techniques are by far the most commonly used ones in modern-day database systems. These techniques estimate the query result sizes by approximating the underlying data distributions, and, thus, are prone to estimation errors. In two recent works , we proposed (and thoroughly analyzed) two new forms of histogram-like techniques called the rectangular and trapezoidal attribute cardinality maps (ACM), respectively, that give much smaller estimation errors than the traditional equi-width and equi-depth histograms currently being used by many commercial database systems. This paper reports how the benchmarking of the Rectangular-ACM (R-ACM) and the Trapezoidal-ACM (T-ACM) for query optimization can be achieved. By conducting an extensive set of experiments using the acclaimed TPC-D benchmark queries and database , we demonstrate that these new ACM schemes are much more accurate than the traditional histograms for query result size estimation. Apart from demonstrating the power of the ACMs, this paper also shows how the TPC-D benchmarking can be achieved using a large synthetic database with many different patterns of synthetic queries, which are representative of a real-world business environment.

Various prototype reduction schemes (PRS) have been reported in the literature. Based on their operating characteristics, these schemes fall into two fairly distinct categories-those which are of a creative sort, and those which are essentially selective. The norms for evaluating these methods are typically, the reduction rate and the classification accuracy. It is generally believed that the former class of methods is superior to the latter. We report the results of executing various creative PRS and attempt to comparatively quantity their capabilities. The paper presents a brief taxonomy of the various reported PRS schemes. Our experimental results for three artificial data sets, and for samples involving real-life data sets, demonstrate that no single method is uniformly superior to the others for all kinds of applications. The conclusion of this study is that the question of determining when one method is superior to another remains open, and depends on the specific characteristics of the data that they are studying. The paper also suggests answers to various hypotheses that relate to the accuracies and reduction rates of families of PRS.

In this paper we have solved the open problem of generating random vectors when the underlying structure obeyed by the dependence graph is a Directed Acyclic Graph (DAG). To the best of our knowledge, our work is of a pioneering sort. We present a formal strategy for the case when the DAG structure and the marginals are given. The paper presents the formal algorithm, proves its correctness, derives its complexity, and presents examples for both artificial data, and for date that is intended to artificially populate a medical database. The method has also been used for testing the ALARM network.

One of the most difficult tasks in modern day database management systems is information retrieval. Basically, this task involves a user query, written in a high-level language such as the Structured Query Language, and some internal operations, which are transparent to the user. The internal operations are carried out through very complex modules that decompose, optimize and execute the different operations. We consider the problem of Query Optimization which consists of the system choosing, among many different query evaluation plans (QEPs), the most economical one. Since the number of QEPs increases exponentially as the number of relations involving the query increases, query optimization is a very complex problem. Many estimation techniques have been developed in order to approximate the cost of a QEP. Histogram-based techniques are the most used methods in this context. In this paper, we discuss the efficiency of some of these methods: Equi-width, Equi-depth, the Rectangular Attribute Cardinality Map (R-ACM) and the Trapezoidal Attribute Cardinality Map (T-ACM). These methods are used to estimate the cost of the different QEP, whence they attempt to determine the optimal one. It has been shown that the errors of the estimates from R-ACM and T-ACM are significantly less than the corresponding errors obtained from Equi-width and Equi-depth. This fact has been formally demonstrated using reasonable statistical distributions for the cost of a QEP, the doubly exponential distribution and the normal distribution. For the empirical analysis, we have developed a formal, rigorous prototype model used to analyze these methods on random databases. Our empirical results demonstrate that R-ACM chooses a superior QEP more than two times as often as Equi-width and Equi-depth. Similar results have been obtained for T-ACM when compared to the traditional methods. Indeed, in the most general scenario, we analytically prove that under certain models the better the accuracy of an estimation technique, the greater the probability of choosing the most efficient QEP.

Optimal Bayesian linear classifiers have been studied in the literature for many decades. We demonstrate that all the known results consider only the scenario when the quadratic polynomial has coincident roots. Indeed, we present a complete analysis of the case when the optimal classifier between two normally distributed classes is pairwise and linear. We focus on some special cases of the normal distribution with nonequal covariance matrices. We determine the conditions that the mean vectors and covariance matrices have to satisfy in order to obtain the optimal pairwise linear classifier. As opposed to the state of the art, in all the cases discussed here, the linear classifier is given by a pair of straight lines, which is a particular case of the general equation of second degree. We also provide some empirical results, using synthetic data for the Minsky's paradox case, and demonstrated that the linear classifier achieves very good performance. Finally, we have tested our approach on real life data obtained from the UCI machine learning repository. The empirical results that we obtained show the superiority of our scheme over the traditional Fisher's discriminant classifier.

The fastest learning automata (LA) algorithms currently available fall in the family of estimator algorithms introduced by Thathachar and Sastry (1986). The pioneering work of these authors was the pursuit algorithm, which pursues only the current estimated optimal action. If this action is not the one with the minimum penalty probability, this algorithm pursues a wrong action. In this paper, we argue that a pursuit scheme that generalizes the traditional pursuit algorithm by pursuing all the actions with higher reward estimates than the chosen action, minimizes the probability of pursuing a wrong action, and is a faster converging scheme. To attest this, we present two new generalized pursuit algorithms (GPAs) and also present a quantitative comparison of their performance against the existing pursuit algorithms. Empirically, the algorithms proposed here are among the fastest reported LA to date.

We present a discretized learning automaton (LA) solution to the capacity assignment (CA) problem which focuses on finding the best possible set of capacities for the links that satisfy the traffic requirements in a prioritized network while minimizing the cost. Most approaches consider a single class of packets flowing through the network, but in reality, different classes of packets with different average packet lengths and different priorities are transmitted over the networks. This generalized model is the focus of this paper. Although the problem is inherently NP-hard, a few approximate solutions have been proposed in the literature. Marayuma and Tang (1977) proposed a single algorithm composed of several elementary heuristic procedures. Other solutions tackle the problem by using modern-day artificial intelligence (AI) paradigms such as simulated annealing and genetic algorithms (GAs). In 2000, we introduced a new method, superior to these, that uses continuous LA. In this paper, we present a discretized LA solution to the problem. This solution uses a meta-action philosophy new to the field of LA, and is probably the best available solution to this extremely complex problem.

We have solved the following problem using pattern classification techniques (PCT): given two histogram methods, M/sub 1/ and M/sub 2/, used in query optimization, if the estimation accuracy of M/sub 1/ is greater than that of M/sub 2/, then M/sub 1/ has a higher probability of leading to the optimal query evaluation plan (QEP) than M/sub 2/. To the best of our knowledge, this problem has been open for at least two decades, the difficulty of the problem partially being due to the hurdles involved in the formulation itself. By formulating the problem from a pattern recognition perspective, we use PCT to present a rigorous mathematical proof of this fact, and show some uniqueness results. We also report empirical results demonstrating the power of these theoretical results on well-known histogram estimation methods.

Statistical coding techniques have been used for a long time in lossless data compression, using methods such as Huffman's algorithm, arithmetic coding, Shannon's method, Fano's method, etc. Most of these methods can be implemented either statically or adaptively. Canonical codes, in which the code words are arranged in a lexicographical order, are advantageous because they can be decoded extremely expediently. Although Huffman's algorithm is optimal, the generation of a canonical Huffman code is not straightforward. Conversely, while the Fano coding is sub-optimal, it can lead to canonical codes. In this paper, we resolve the dilemma by focusing on the static implementation of Fano's method. By taking advantage of the properties of the encoding schemes generated by this method, and the concept of "code word arrangement", we present an enhanced version of the static Fano's method, namely Fano/sup +/. We formally analyze Fanol by presenting some properties of Fano trees, and the theory of list rearrangements. Our enhanced algorithm achieves compression ratios arbitrarily close to those of Huffman's algorithm. Empirical results on files of the Canterbury corpus corroborate the almost-optimal efficiency of our enhanced algorithm and its canonical nature. We believe that the compression efficiency of Fano+ can be made to attain the compression ratios of the best known schemes if a structure model of the data is also incorporated.

We consider the problem of recognizing ordered labeled trees by processing their noisy subsequence-trees which are "patched-up" noisy portions of their fragments. We assume that H, a finite dictionary of ordered labeled trees, is given. X* is an unknown element of H, and U is any arbitrary subsequence-tree of X*. We consider the problem of estimating X* by processing Y, which is a noisy version of U. The solution which we present is, to our knowledge, the first reported solution to the problem. We solve the problem by sequentially comparing Y with every element X of H, the basis of comparison being a new dissimilarity measure between two trees, which implicitly captures the properties of the corrupting mechanism that noisily garbles U into Y. The algorithm which incorporates this constraint has been used to test our pattern recognition system, and the experimental results obtained demonstrate good accuracy.

A learning automaton (LA) is an automaton that interacts with a random environment, having as its goal the task of learning the optimal action based on its acquired experience. Many learning automata (LAs) have been proposed, with the class of estimator algorithms being among the fastest ones, Thathachar and Sastry, through the pursuit algorithm, introduced the concept of learning algorithms that pursue the current optimal action, following a reward-penalty learning philosophy. Later, Oommen and Lanctot extended the pursuit algorithm into the discretized world by presenting the discretized pursuit algorithm, based on a reward-inaction learning philosophy. In this paper we argue that the reward-penalty and reward-inaction learning paradigms in conjunction with the continuous and discrete models of computation, lead to four versions of pursuit learning automata. We contend that a scheme that merges the pursuit concept with the most recent response of the environment, permits the algorithm to utilize the LAs long-term and short-term perspectives of the environment. In this paper, we present all four resultant pursuit algorithms, prove the E-optimality of the newly introduced algorithms, and present a quantitative comparison between them.

Histogram techniques are used to efficiently estimate query result sizes in most of the modern-day database systems. In a recent work (Oommen and Thiyagarajah, 1999), we introduced a new histogram-like approximation strategy, called the Rectangular Attribute Cardinality Map (R-ACM), which approximates the density function within a given sector by a rectangular cell. In this paper, we introduce another histogram-like approximation strategy, called the Trapezoidal Attribute Cardinality Map (T-ACM) that approximates the density function within a given sector by a trapezoidal cell, where the slope of the trapezoid is obtained so as to fix the actual probability mass within the cell. We present numerous analytic and experimental results concerning the T-ACM demonstrating its superiority over the traditional equi-width and equi-depth histograms for query result size estimation. We hope that with the R-ACM introduced in (Oommen and Thiyagarajah, 1999), the T-ACM could become an invaluable tool for query optimization in the future database systems.

The Capacity Assignment (CA) problem focuses on finding the best possible set of capacities for the links that satisfies the traffic requirements in a prioritized network while minimizing the cost. Most approaches consider a single class of packets flowing through the network, but, in reality, different classes of packets with different packet lengths and priorities are transmitted over the networks. In this paper, we assume that the traffic consists of different classes of packets with different average packet lengths and priorities. We shall look at three different solutions to this problem. K. Marayuma and D.T. Tang (1977) proposed a single algorithm composed of several elementary heuristic procedures. A. Levi and C. Ersoy (1994) introduced a simulated annealing approach that produced substantially better results. In this paper, we introduce a new method which uses continuous learning automata to solve the problem. Our new schemes produce superior results when compared with either of the previous solutions and is, to our knowledge, currently the best known solution.

Current database systems utilize histograms to approximate frequency distributions of attribute values of relations. These are used to efficiently estimate query result sizes and access plan costs. Even though they have been in use for nearly two decades, there has been no significant mathematical techniques (other than those used in statistics for traditional histogram approximations) to study them. We introduce a new histogram-like approximation strategy called the Rectangular Attribute Cardinality Map (R-ACM), that aims to approximate the density of the underlying attribute values using the philosophies of numerical integration. In this new histogram-like approximation method, the density function within a given sector is approximated by a rectangular cell, where the height of the cell is obtained so as to guarantee that the actual probability density differs from the approximated one by a maximum of a user specified tolerance, /spl tau/. Furthermore, unlike the two traditional histogram types, namely equi-width and equi-depth, the R-ACM is neither equi-width nor equi-depth. Analytically, we show that for the R-ACM, the distribution of an attribute value within the sector is binomially distributed. This permits us to derive worst-case and average case results for the estimation errors of the probability mass itself. Our theoretical results, which include a rigorous maximum likelihood and expected case analyses, and an extensive set of experiments demonstrate that the R-ACM scheme (which is essentially histogram-like) is much more accurate than the traditional histograms for query result size estimation. Due to its high accuracy and low construction costs, we hope that it could become an invaluable tool for query optimization in the future database systems.

We consider a fundamental inference problem in syntactic pattern recognition (PR). We assume that the system has a dictionary which is a collection of all the ideal representations of the objects in question. To recognize a noisy sample, the system compares it with every element in the dictionary based on a nearest-neighbor philosophy, using three standard edit operations: substitution, insertion, and deletion, and the associated primitive elementary edit distances d(.,.). In this paper, we consider the assignment of the inter-symbol distances using the parametric distances. We show how the classifier can be trained to get the optimal parametric distance using vector quantization in the meta-space. In all our experiments, the training was typically achieved in a very few iterations. The subsequent classification accuracy we obtained using this single-parameter scheme was 96.13%. The power of the scheme is evident if we compare it to 96.67%, which is the accuracy of the scheme which uses the complete array of inter-symbol distances derived from a knowledge of all the confusion probabilities.

There are currently many vastly different areas of research involving adaptive learning. Among them are the two areas that concern neural networks and learning automata. This paper develops a method by which the general philosophies of vector quantization (VQ) and discretized automata learning can be incorporated for the computation of arbitrary distance functions. The latter is a problem which has important applications in logistics and location analysis. The input to our problem is the set of coordinates of a large number of nodes whose internode arbitrary "distances" have to be estimated. To render the problem interesting, nontrivial, and realistic, we assume that the explicit form of this distance function is both unknown and uncomputable. Unlike traditional operations research methods, which use optimized parametric functional estimators, we have utilized discretized VQ principles to first adaptively polarize the nodes into subregions. Subsequently, the parameters characterizing the subregions are learned by using a variety of methods (including, for academic purposes, a VQ strategy in the meta-domain). After an initial training phase, a system which achieves distance estimation attempts to yield an estimate of any node-pair distance without actually deriving an explicit form for the unknown function. The algorithms have been rigorously tested for the actual road-travel distances involving cities in Turkey and the results obtained are conclusive. Indeed, these present results are the best currently available from any single or hybrid strategy.

Consider the problem of a robot (learning mechanism or algorithm) attempting to locate a point on a line. The mechanism interacts with a random environment which essentially informs it, possibly erroneously, which way it should move. The first reported paper to solve this problem (Oommen 1997) presented a solution which operated in a discretized space. In this paper we present a new scheme by which the point can be learnt using a combination of various learning principles. The heart of the strategy involves performing a controlled random walk on the underlying space and then intelligently pruning the space using an adaptive tertiary search. The overall learning scheme is shown to be epsilon-optimal. Just as in the case of the results presented in Oommen (1997) the application of the solution in nonlinear optimization has been alluded to. In a typical optimization process the algorithm has to work its way toward the maximum (minimum) using local information. However, the crucial issue in these strategies is that of determining the parameter to be used in the optimization itself. If the parameter is too small the convergence is sluggish. On the other hand, if the parameter is too large, the system could erroneously converge or even oscillate. The strategy presented here can be utilized to determine the best parameter to be used in the optimization.

In this article we apply the concepts of vector quantization for the evaluation of arbitrary distance functions—a problem which has important applications in logistics and location analysis. The input to our problem is the set of coordinates of a large number of nodes whose internode arbitrary “distances” have to be estimated. To render the problem interesting, nontrivial and realistic, we assume that the explicit form of this distance function is both unknown and uncomputable. Unlike traditional operations research methods, which compute aggregate parameters of functional estimators according to certain goodness-of-fit criteria, we have utilized vector quantization principles to first adaptively polarize the nodes into subregions. Subsequently, the parameters characterizing the subregions are learned by using a variety of methods (including, for academic purposes a vector quantization strategy in the metadomain). The algorithms have been rigorously tested for the actual roadtravel distances involving cities in Turkey. The results obtained are not only conclusive, but also the best currently available from any single or hybrid strategy.

Approximation techniques are an important aspect of digital signal and image processing. Many lossy signal compression procedures such as the Fourier transform and discrete cosine transform are based on the idea that a signal can be represented by a small number of transformed coefficients which are an approximation of the original. Existing approximation techniques approach this problem in either a time/spatial domain or transform domain, but not both. This paper briefly reviews various existing approximation techniques. Subsequently, we present a new strategy to obtain an approximation f/spl circ/(x) of f(x) in such a way that it is reasonably close to the original function in the domain of the variable x, and exactly preserves some properties of the transformed domain. In this particular case, the properties of the transformed values that are preserved are geometric moments of the original function. The proposed technique has been applied to single-variable functions, two-dimensional planar curves, and two-dimensional images, and the results obtained are demonstrative.

We consider the problem of a learning mechanism (for example, a robot) locating a point on a line when it is interacting with a random environment which essentially informs it, possibly erroneously, which way it should move. In this paper we present a novel scheme by which the point can he learned using some recently devised learning principles. The heart of the strategy involves discretizing the space and performing a controlled random walk on this space. The scheme is shown to be epsilon-optimal and to converge with probability 1. Although the problem is solved in its generality, its application in nonlinear optimization has also been suggested. Typically, an optimization process involves working one's way toward the maximum (minimum) using the local information that is available. However, the crucial issue in these strategies is that of determining the parameter to be used in the optimization itself. If the parameter is too small the convergence is sluggish. On the other hand, if the parameter is too large, the system could erroneously converge or even oscillate. Our strategy can be used to determine the best parameter to be used in the optimization.

A typical syntactic pattern recognition (PR) problem involves comparing a noisy string with every element of a dictionary, X. The problem of classification can be greatly simplified if the dictionary is partitioned into a set of subdictionaries. In this case, the classification can be hierarchical-the noisy string is first compared to a representative element of each subdictionary and the closest match within the subdictionary is subsequently located. Indeed, the entire problem of subdividing a set of string into subsets where each subset contains "similar" strings has been referred to as the "String Taxonomy Problem". To our knowledge there is no reported solution to this problem. In this paper we present a learning-automaton based solution to string taxonomy. The solution utilizes the Object Migrating Automaton the power of which in clustering objects and images has been reported. The power of the scheme for string taxonomy has been demonstrated using random string and garbled versions of string representations of fragments of macromolecules.

We present experimental results that demonstrate that we can develop a foundational basis for probabilistic syntactic pattern recognition (PR). The patterns are "linearly" represented as strings. In an earlier paper Oommen and Kashyap (1996) had presented a formal basis for designing such systems when the errors involved were arbitrarily distributed substitution, insertion and deletion (SID) syntactic errors. In this paper we show that we can generalize the framework and permit these traditional errors and generalized transposition (GT) errors. We do this by developing a rigorous model, MG*, for channels which permit all these errors in an arbitrarily distributed manner. We also show how we can compute Pr[Y/U] the probability of receiving Y given that U was transmitted, can be computed in quartic time using dynamic programming. Experimental results which involve dictionaries with strings of lengths between 7 and 14 with an overall average noise of 70.5% demonstrate the superiority of our system over existing methods.

Marzal and Vidal (1993) considered the problem of computing the normalized edit distance between two strings, and reported experimental results which demonstrated the use of the measure to recognize hand-written characters. Their paper formulated the theoretical properties of the measure and developed two algorithms to compute it. In this short communication the authors demonstrate how this measure is related to an auxiliary measure already defined in the literature-the inter-string constrained edit distance. Since the normalized edit distance can be computed efficiently using the latter, the analytic and experimental results reported in the above paper can be obtained just as accurately, but more efficiently, using the strategies presented here.

Given a graph G, we intend to partition its nodes into two sets of equal size so as to minimize the sum of the cost of the edges having end points in different sets. This problem, called the uniform graph partitioning problem, is known to be NP complete. We propose the first reported learning automaton based solution to the problem. We compare this new solution to various reported schemes such as the B.W. Kernighan and S. Lin's (1970) algorithm, and two excellent recent heuristic methods proposed by E. Rolland et al. (1994; 1992)-an extended local search algorithm and a genetic algorithm. The current automaton based algorithm outperforms all the other schemes. We believe that it is the fastest algorithm reported to date. Additionally, our solution can also be adapted for the GPP in which the edge costs are not constant but random variables whose distributions are unknown.

Quantifying the measure of similarity between two trees is a problem of intrinsic importance in the study of algorithms and data structures and has applications in computational molecular biology, structural/syntactic pattern recognition and in data management. In this paper we define and formulate an abstract measure of comparison, /spl Omega/(T/sub 1/, T/sub 2/), between two trees T/sub 1/ and T/sub 2/ presented in terms of a set of elementary intersymbol measures /spl omega/(.,.) and two abstract operators /spl oplus/ and /spl otimes/. By appropriately choosing the concrete values for these two operators and for /spl omega/(.,.), this measure can be used to define various quantities including: (1) the edit distance between two trees, (2) the size of their largest common subtree, (3) Prob(T/sub 2/|T/sub 1/), the probability of receiving T/sub 2/ given that T/sub 1/ was transmitted across a channel causing independent substitution and deletion errors, and (4) the a posteriori probability of T/sub 1/ being the transmitted tree given that T/sub 2/ is the received tree containing independent substitution, insertion and deletion errors. The recursive properties of /spl Omega/(T/sub 1/, T/sub 2/) have been derived and a single generic iterative dynamic programming scheme to compute all the above quantities has been developed. The time and space complexities of the algorithm have been analyzed and the implications of our results in both theoretical and applied fields has been discussed.

Learning automata are stochastic finite state machines that attempt to learn the characteristic of an unknown random environment with which they interact. The fundamental problem is that of learning, through feedback, the action which has the highest probability of being rewarded by the environment. The problem of designing automata for stationary environments has been extensively studied. When the environment is nonstationary, the question of modeling the nonstationarity is, in itself, a very interesting problem. In this paper, the authors generalize the model used in Tsetlin (1971, 1973) to present three models of nonstationarity. In the first two cases, the nonstationarity is modeled by a homogeneous Markov chain governing the way in which the characteristics change. The final model considers the more general case when the transition matrix of this chain itself changes with time in a geometric manner. In each case the authors analyze the stochastic properties of the resultant switching environment. The question of analyzing the various learning machines when interacting with these environments introduces an entire new avenue of open research problems.>

A finite mixture distribution consists of the superposition of a finite number of component probability densities, and is typically used to model a population composed of two or more subpopulations. Mixture models find utility in situations where there is a difficulty in directly observing the underlying components of the population of interest. This paper examines the method of moments as a general estimation technique for estimating the parameters of the component distributions and their mixing proportions. It is shown that the same basic solution can be applied to any continuous or discrete density from the exponential family with a known common shape parameter. Results of an empirical study of the method are also presented.>

Let R = {R1, R2, …, RN} be a set of data elements. The elements of R are accessed by the users of the system according to a fixed but unknown distribution S = {s1, s2, …, sN}, referred to as the users' query distribution. In this paper we consider the problem of organizing data so as to optimize its retrieval. However, rather than organize the data according to Q, the stream of queries presented by the user, we suggest a scheme by which the data is organised based on a synthesized query stream Q′. This synthesized stream possesses an underlying distribution, S′. Thus, in effect, the data organization is achieved according to the distribution S′ and so, in one sense, the user's query distribution is modified without his knowing it. Furthermore, we show how this transformation can be done in such a way that the data storage achieved according to S′ will be superior to that achieved if the data was stored according to the distribution S. The module which achieves this transformation is called a Distribution Changing Technique (DCT) Filter. In this paper we shall present the theory of DCT filters in its mathematical generality. We shall show that a DCT filter can be represented as Stochastic Mealy Automation. Various DCT filters will be catalogued and, in particular, a filter F* will be presented. It has been shown that this filter transforms the original distribution expediently, and thus accentuates the information contained in the user's distribution. The problem of cascading DCT filtes has also been studied, and extensive computational and simulation results have been included which justify the theoretical results which have been presented.

Presents SEATER/spl minus/an object-oriented environment in which any general telephone traffic routing problem can be set up, tested, and simulated using a variety of routing methods. The routing methods available are the fixed rule, random routing, and routing utilizing a complete assortment of different learning automata. The paper first describes the general telephone traffic routing problem, and various existing fixed rule routing schemes supported by the system are explained. This is followed by a brief motivation and description of learning automata routing techniques, and a survey of those schemes which are supported by the prototype system implemented. The paper then highlights the considerations that were taken in the design and implementation of the object-oriented prototype, SEATER. These automata schemes supported by SEATER are compared to the existing fixed rule algorithms in terms of minimizing the blocking probability of the network. The simulations show that the former solutions are far superior to any fixed rule solutions. The advantage of the former lies in their adaptability to changes in telephone traffic. The system is written in SMALLTALK V and runs on a MAC II.>

In this short note we consider the general problem of solving certain ill-continued constraint problems. We propose a strategy of transforming the original problem by projecting the constraint onto an auxiliary surface (e.g. a hyperplane) in such a way that the transformed problem possesses a well-defined solution. The technique has been utilized to tackle two ill-conditioned problems - the Constrained Angle Bisector Problem and a Constrained Location Problem. The former problem, which has applications in image processing, involves bisecting an arbitrary angle subject to a simple quadratic constraint. The latter problem involves a location assignment problem in which the locations are external to the boundary from which services are provided.

In this paper we study the Image Examination and Retrieval Problem (IERP). Consider the scenario in which a user wants to browse through a database of images so as to retrieve a particular image which he/she is interested in. Rather than specifying the target image textually, we instead permit the user to access the image by using his/her subjective discrimination of how it resembles other images that are presented by the system. The IERP is not merely viewed as one involving recognition or classification, but instead as one that falls in the domain of classifying and partitioning the set of images in terms of their ‘visual’ resemblances. In the process, we intend to not merely find images that match other images, but, in fact, to group all similar images together so that subsequent searches will be enhanced. The intelligent partitioning of the image database is done adaptively on the basis of the statistical properties of the user's query patterns. This is achieved using learning automata and does not involve the evaluation of any statistics.

Let Lambda be a finite plaintext alphabet and V be a cypher alphabet with the same cardinality as Lambda . In all one-to-one substitution cyphers, there exists the property that each element in V maps onto exactly one element in Lambda and vice versa. This mapping of V onto Lambda is represented by a function T*, which maps any v in V onto some lambda in Lambda (i.e., T*(v)= lambda ). The problem of learning the mapping of T* (or its inverse (T*)/sup -1/) by processing a sequence of cypher text is discussed. The fastest reported method to achieve this is a relaxation scheme that utilizes the statistical information contained in the unigrams and trigrams of the plaintext language. A new learning automaton solution to the problem called the cypher learning automaton (CLA) is given. The proposed scheme is fast, and the advantages of the scheme in terms of time and space requirements over the relaxation method have been listed. Simulation results comparing both cypher-breaking techniques are presented.>

Consider a set A=(A/sub 1/,A/sub 2/,. . ., A/sub n/) of records, where each record is identified by a unique key. The records are accessed based on a set of access probabilities S=(s/sub 1/,s/sub 2/,. . ., s/sub N/) and are to be arranged lexicographically using a binary search tree (BST). If S is known a priori, it is well known that an optimal BST may be constructed using A and S. The case when S is not known a priori is considered. A new restructuring heuristic is introduced that requires three extra integer memory locations per record. In this scheme, the restructuring is performed only if it decreases the weighted path length (WPL) of the overall resultant tree. An optimized version of the latter method, which requires only one extra integer field per record has, is presented. Initial simulation results comparing this algorithm with various other static and dynamic schemes indicates that this scheme asymptotically produces trees which are an order of magnitude closer to the optimal one than those produced by many of the other BST schemes reported in the literature.>

Consider a learning machine (LM) interacting with an environment epsilon . The environment offers the machine M actions. Traditionally, learning systems endeavor to compute the best action that the environment offers, and this is done without any estimation procedure. In this paper, we consider the problem of the LM computing not only the optimal action offered but also the ordering of the actions in terms of their optimality. The problem is posed in its generality and various norms of learning in this setting are formalized. Also various learning strategies are presented that use a new mathematical model called the random race. In this model the learning is modeled using M racers that are running toward a goal. At each instant, racer R/sub i/ moves toward the goal with a probability of s/sub i/ and stays where he is with a probability of (1-s/sub i/). In the simplest learning model, the learning multiple race track (LMRT) model, the racers run on multiple tracks, and in this scenario, each racer has his own track, thus disallowing interference between the racers. However, in a more general setting, the learning single race track (LSRT) model, the racers run on a single track, and in this case, interferences between racers are specified in terms of overtaking rules. In this paper, we first examine the learning multiple race track (LMRT) model, and we have shown that in the absence of a priori information the LMRT is permutationally epsilon -optimal in all suggestive random environments. Other results are proven or conjectured.>

The class of memoryless heuristics for maintaining a Doubly-Linked List in an approximately optimal order is studied. Two mappings that relate Singly-Linked List and Doubly-Linked List heuristics are defined, and theorems involving these mappings are presented. A new heuristic referred to as the Swap heuristic for the Doubly-Linked List is introduced, and its asymptotic distribution has been derived.

The improvements gained by rendering the various estimator learning algorithms discrete are investigated. This is done by restricting the probability of selecting an action to a finite discrete subset of (0, 1). This modification is proven to be epsilon -optimal in all stationary environments. Various discretized estimator algorithms (DEAs) are constructed. Subsequently, members of the family of DEAs are shown to be epsilon -optimal by deriving two sufficient conditions required for the epsilon -optimality-the properties of monotonicity and moderation. A conjecture about the necessity of these conditions for epsilon -optimality is presented. Experimental results indicate that the discrete modifications improve the performance of the algorithms so that the automata constitute fast-converging and accurate learning automata.>

The identification of a source given a sequence of random strings is discussed. Two modes of random string generation are analyzed. In the first mode, arbitrary strings are generated in which the individual symbols occur exactly once in each random string. The latter case corresponds to the situation in which the sources generate random permutations. In both cases, the best match to the distribution being used by each source can be obtained by maintaining an exponential number of statistics. This being infeasible, a simple parameterization of the distributions is proposed. For arbitrary strings, the simple unigram-based model (U-model) is proposed. For the case of permutations, a new model called the S-model is proposed, and it is used to analyze and/or approximate unknown distributions of permutations. The relevant estimation procedures, together with the applications to source recognition, are presented. The method presents a unique blend of syntactic and statistical pattern recognition.>

The authors consider the problem of assigning more than one symbol of a finite alphabet A to the same key on a keyboard. Since multiple symbols of the alphabet A reside on the same key, the representations of all the words in a finite dictionary H need not be unique. The problem is one of optimally assigning the symbols of the alphabet to the keys of a given keyboard with a view to minimize the total number of words that have ambiguous representation. The problem is proven to be NP-hard. After presenting the only reported solution to the problem, a fast learning-automaton-based solution to this problem is reported. Experimental results demonstrating the power of this solution are presented.>

Let R = {R1, R2, …, RM} be an ordered set of M elements where Ri < Rj whenever i < j. Let π be the set of permutations of R. We consider the problem of randomly generating the elements of π according to a distribution G(π). Various algorithms including those due to Durstenfeld3,5 and Moses et al7 are available for the case when the distribution G(π) is a uniform distribution (i.e., where all the elements of π are generated with equal probability). In this paper we consider the case when the distribution G(π) is not necessarily uniform. We present a strategy for specifying the distribution G(π) and propose a technique for generating the elements of π according to the distribution G(π). Applications of the technique to generate ‘almost sorted lists’ and in the Travelling Salesman Problem have been presented. Finally, simulation results have been included which demonstrate the power of the Random Permutation Generation (RPG) technique.

The learning machine presented is an automaton whose structure changes with time and is assumed to be interacting with a random environment. The machine is essentially a stubborn machine, i.e. once the machine has chosen a particular action it increases the probability of choosing the action irrespective of whether the response from the environment was favorable or unfavorable. However, this increase in the action probability takes place in a systematic and methodical way, so that the machine ultimately learns the best action that the environment offers. It is shown that the learning mechanism is epsilon -optimal and that the probability that it will choose the optimal action converges uniformly to unity. The mathematical tools used in the proof are quite novel to the field of learning. Various simulation results that demonstrate the properties of stubbornly learning mechanisms are also presented. Such mechanisms are shown to be inferior to learning machines that merely ignore the penalty responses of the environment. Some open problems are also presented.>

The problem of a stochastic learning automaton interacting with an unknown random environment is considered. The fundamental problem is that of learning, through interaction, the best action allowed by the environment (i.e. the action that is rewarded optimally). By using running estimates of reward probabilities to learn the optimal action, an extremely efficient pursuit algorithm (PA), which is presently among the fastest algorithms known, was reported in earlier works. The improvements gained by rendering the PA discrete are investigated. This is done by restricting the probability of selecting an action to a finite and, hence, discrete subset of (0, 1). This improved scheme is proven to be epsilon -optimal in all stationary environments. Furthermore, the experimental results seem to indicate that the algorithm presented is faster than the fastest nonestimator learning automata reported to date, and also faster than the continuous pursuit automaton.>

The authors consider the problem of a learning mechanism learning the optimal action offered by a random environment. The mechanism presented can be defined as an action probability updating rule and thus a variable-structure stochastic automaton. The machine is essentially a stubborn machine; in other words, once the machine has chosen a particular action it increases the probability of choosing the action irrespective of whether the response from the environment was favorable or unfavorable. However, this increase in the action probability is done in a systematic and methodical way so that the machine learns, in an epsilon -optimal fashion, the best action which the environment offers. The proposed mechanism forms an excellent model for an epsilon -optimal stubbornly learning system. Apart from the fact that the machine is shown to be epsilon -optimal, a major contribution of the present work is that the mathematical tools used in this proof (namely the theory of distributions, kernels, and topological spaces) are quite distinct from those which are currently used in the field of learning. Also presented are simulation results which demonstrate the properties of the mechanism and which compare it to the traditional L/sub RI/ scheme.>

The authors consider the problem of a stochastic learning automaton interacting with an unknown random environment. The fundamental problem is that of learning, through interaction, the best action (that is, the action which is rewarded optimally) allowed by the environment. By using running estimates of reward probabilities to learn the optimal action, an extremely efficient pursuit algorithm was obtained by M.A.L. Thathachar et al. (1986, 1989) which is presently among the fastest-growing algorithms known. In the present work, the authors investigate the improvements gained by rendering the pursuit algorithm discrete. This is done by restricting the probability of selecting an action to a finite and, hence, discrete subset of

Three deterministic learning automata solutions to the problem of equipartitioning are presented. Although the first two are epsilon -optimal, they seem to be practically feasible only when a set of W objects is small. The last solution, which uses a novel learning automaton, demonstrates an excellent partitioning capability. Experimentally, this solution converges an order of magnitude faster than the best known algorithm in the literature.>

The authors consider the problem of terrain model acquisition by a roving point placed in an unknown terrain populated by stationary polyhedral obstacles in two/three dimensions. The motivation for this problem is that after the terrain model is completely acquired, navigation from a source point to a destination point can be achieved along the collision-free paths. This can be done without the usage of sensors by applying the existing techniques for the find-path problem. In the paper, the point robot autonomous machine (PRAM) is used as a simplified abstract model for real-life roving robots. An algorithm is presented that enables PRAM to autonomously acquire the model of an unexplored obstacle terrain composed of an unknown number of polyhedral obstacles in two/three dimensions. In this method, PRAM undertakes a systematic exploration of the obstacle terrain with its sensor that detects all the edges and vertices visible from the present location, and builds the complete obstacle terrain model.>

Variable-structure stochastic automata (VSSA) are considered which interact with an environment and which dynamically learn the optimal action that the environment offers. Like all VSSA the automata are fully defined by a set of action-probability updating rules. However, to minimize the requirements on the random-number generator used to implement the VSSA, and to increase the speed of convergence of the automation, the case in which the probability-updating functions can assume only a finite number of values. These values discretize the probability space (0, 1) and hence they are called discretized learning automata. The discretized automata are linear because the subintervals of (0, 1) are of equal length. The authors prove the following results: (a) two-action discretized linear reward-penalty automata are ergodic and epsilon -optimal in all environments whose minimum penalty probability is less than 0.5; (b) there exist discretized two-action linear reward-penalty automata that are ergodic and epsilon -optimal in all random environments, and (c) discretized two-action linear reward-penalty automata with artificially created absorbing barriers are epsilon -optimal in all random environments.>

Let Ω = {A1, …, AW} be a set of W objects to be partitioned into R classes {P1, …, PR}. The objects are accessed in groups of unknown size and the size of these groups need not be equal. Additionally, the joint access probabilities of the objects are unknown. The intention is that the objects accessed more frequently together are located in the same class. This problem has been shown to be NP-hard [15, 16]. In this paper, we propose two stochastic learning automata solutions to the problem. Although the first one is relatively fast, its accuracy is not so remarkable in some environments. The second solution, which uses a new variable structure stochastic automation, demonstrates an excellent partitioning capability. Experimentally, this solution converges an order of magnitude faster than the best known algorithm in the literature [15, 16].

Let X* be any unknown word from a finite dictionary H. Let U be any arbitrary subsequence of X*. We consider the problem of estimating X* by processing Y, which is a noisy version of U. We do this by defining the constrained edit distance between XH and Y subject to any arbitrary edit constraint involving the number and type of edit operations to be performed. An algorithm to compute this constrained edit distance has been presented. Although in general the algorithm has a cubic time complexity, within the framework of our solution the algorithm possesses a quadratic time complexity. Recognition using the constrained edit distance as a criterion demonstrates remarkable accuracy. Experimental results which involve strings of lengths between 40 and 80 and which contain an average of 26.547 errors per string demonstrate that the scheme has about 99.5 percent accuracy.

Consider a list of elements $\{ R_1 , \cdots ,R_N \} $ in which the element $R_1 $ is accessed with an (unknown) probability $s_i $. If the cost of accessing $R_i $ is proportional to i (as in sequential search) then it is advantageous if each access is accompanied by a simple reordering operation. This operation is chosen so that ultimately the list will be sorted in the descending order of the access probabilities. In this paper we present two list organizing schemes, the first of which uses bounded memory and the second of which uses memory proportional to the number of elements in the list. Both of the schemes reorder the list by moving only the accessed element. However, as opposed to the schemes discussed in the literature the move operation is performed stochastically in such a way that ultimately no more move operations are performed. When this occurs we say that the scheme has converged. We shall show that: (i) The bounded memory stochastic move-to-front algorithm is expedient, but is always worse than the deterministic move-to-front algorithm. (ii) The linear memory stochastic move-to-rear scheme is optimal, independent of the distribution of the access probabilities. By this we mean that although the list could converge to one of its N! configurations, by suitably updating the probability of performing the move-to-rear operation, the probability of converging to the right arrangement can be made as close to unity as desired.

The problem of navigating an autonomous mobile robot through unexplored terrain of obstacles is discussed. The case when the obstacles are "known" has been extensively studied in literature. Completely unexplored obstacle terrain is considered. In this case, the process of navigation involves both learning the information about the obstacle terrain and path planning. An algorithm is presented to navigate a robot in an unexplored terrain that is arbitrarily populated with disjoint convex polygonal obstacles in the plane. The navigation process is constituted by a number of traversals; each traversal is from an arbitrary source point to an arbitrary destination point. The proposed algorithm is proven to yield a convergent solution to each path of traversal. Initially, the terrain is explored using a rather primitive sensor, and the paths of traversal made may be suboptimal. The visibility graph that models the obstacle terrain is incrementally constructed by integrating the information about the paths traversed so far. At any stage of learning, the partially learned terrain model is represented as a learned visibility graph, and it is updated after each traversal. It is proven that the learned visibility graph converges to the visibility graph with probability one when the source and destination points are chosen randomly. Ultimately, the availability of the complete visibility graph enables the robot to plan globally optimal paths and also obviates the further usage of sensors.

Learning automata are considered which update their action probabilities on the basis of the responses they get from a random environment. The automata update the probabilities whether the environment responds with a reward or a penalty. Learning automata are said to be ergodic if the distribution of the limiting action probability vector is independent of the initial distribution. An ergodic scheme is presented which can take into consideration a priori information about the action probabilities. This is the only reported scheme in the literature capable of achieving this. The mean and the variance of the limiting distribution of the automaton is derived, and it is shown that the mean is not independent of the a priori information. Further, it is shown that the expressions for the foregoing quantities are general cases of the corresponding quantities derived for the familiar LRP scheme. Finally, it is shown that by constantly updating the parameter quantifying the a priori information, a resultant linear scheme can be obtained. This scheme is of a reward-reward flavor and yet is absolutely expedient. It falls within the class of absolutely expedient schemes presented by Aso and Kimura.

We consider the problem of moving an elliptic object A, surrounded by a set of elliptic obstacles {Bj}. The initial and final positions of the object are known and the intention is to move A solely by performing translations in the plane. The motion must be performed in such a way that A does not collide with any of the obstacles. We present the following algorithms: (i) An algorithm, of complexity O(N log N), where N is the number of obstacles, which yields the set of all directions along which the object is separable from the obstacles by a single translation. (ii) An algorithm, quadratic in the number of obstacles, which yields a path for A to be moved from its starting configuration to its final configuration. The technique we propose first transforms the ellipse A into a circle A'. This same transformation changes each ellipse Bjinto another figure Bj', which is also elliptic. The algorithms then compute the path of translation by processing the configuration obstacle space of {Bj'} with respect to the circle A'.

A learning automaton is a machine that interacts with a random environment and that simultaneously learns the optimal action that the environment offers to it. Learning automata with variable structure are considered. Such automata are completely defined by a set of probability updating rules. Contrary to all the variable-structure stochastic automata (VSSA) discussed in the literature, which update the probabilities in such a way that an action probability can take any real value in the interval [0,1], the probability space is discretized so as to permit the action probability to assume one of a finite number of distinct values in [0,1]. The discretized automaton is termed linear or nonlinear depending on whether the subintervals of [0,1] are of equal length. It is proven that 1) discretized two-action linear reward-inaction automata are absorbing and ϵ-optimal in all environments; 2) discretized two-action linear inaction-penalty automata are ergodic and expedient in all environments; 3) discretized two-action linear inaction-penalty learning automata with artificially created absorbing barriers are ϵ-optimal in all random environments; and 4) there exist nonlinear discretized reward-inaction automata that are ϵ-optimal in all random environments. The maximum advantage gained by rendering any finite-state discretized automaton nonlinear has also been derived.

The minimum-spanning circle (MSC) of N points in the plane is the smalest circle that encloses these points. The problem of computing the MSC of N stochastically varying points in the plane is considered. We propose a solution to the problem that involves a heirarchy of learning automata. The automata used in this solution are the Absorbing discretized linear Inaction-Penalty (ADLIP) automata, which are the only known linear automata which are of an inaction-penalty type and yet asymptotically optimal.

The automata considered have a variable structure and hence are completely described by action probability updating functions. The action probabilities can take only a finite number of prespecified values. These values linearly increase and the interval [0, 1] is divided into a number of equal length subintervals. The probability is updated by the automata only if the environment responds with a reward and hence they are called discretized linear reward-inaction automata. The asymptotic optimality of this family of automata is proved for all environments.

A smoother version of a polygon ¿ is defined as a polygon which approximates ¿ according to a given criterion and which simultaneously has no more edges than ¿ itself. In this paper, a scale preserving smoothing algorithm is presented. The input to the algorithm is a polygon ¿ and the output is its smoothed version ¿. ¿, which contains all the scale information that ¿ contains, is called the linear minimum perimeter polygon (LMPP) of ¿ within a tolerance of. Using the quantity the degree of with ¿ approximates ¿ can be controlled. From the LMPP a representation for a polygon approximating ¿ can be procured, which is invariant to scale and translation changes. Examples of smoothing maps and characters have been presented.

Let T(U) be the set of words in the dictionary H which contains U as a substring. The problem considered here is the estimation of the set T(U) when U is not known, but Y, a noisy version of U is available. The suggested set estimate S*(Y) of T(U) is a proper subset of H such that its every element contains at least one substring which resembles Y most according to the Levenshtein metric. The proposed algorithm for-the computation of S*(Y) requires cubic time. The algorithm uses the recursively computable dissimilarity measure Dk(X, Y), termed as the kth distance between two strings X and Y which is a dissimilarity measure between Y and a certain subset of the set of contiguous substrings of X. Another estimate of T(U), namely SM(Y) is also suggested. The accuracy of SM(Y) is only slightly less than that of S*(Y), but the computation time of SM(Y) is substantially less than that of S*(Y). Experimental results involving 1900 noisy substrings and dictionaries which are subsets of 1023 most common English words [11] indicate that the accuracy of the estimate S*(Y) is around 99 percent and that of SM(Y) is about 98 percent.

Learning automata which update their action probabilities on the basis of the responses they get from an environment are considered. The automata update the probabilities whether the environment responds with a reward or a penalty. An automation is said to possess ergodicity of the mean (EM) if the mean action probability is the total state probability of an ergodic Markov chain. The only known EM algorithm is the linear reward-penalty (LRP) scheme. For the two-action case, necessary and sufficient conditions have been derived for nonlinear updating schemes to be EM. The method of controlling the rate of convergence of this scheme is presented. In particular, a generalized linear algorithm has been proposed which is superior to the LRPscheme. The expression for the variance of the limiting action probabilities of this scheme is derived.

Two geometrical measures have been proposed to quantify the dissimilarity between two irregular polygons. These measures capture the intuitive notion of the dissimilarity between shapes and are related to the minimum value of the intersecting area of the polygons on superposing one on the other in various configurations. A more easily computable measure of dissimilarity, referred to as the minimum integral square error between the polygons, has also been proposed, and using the latter measure pattern classification, has been performed. Experimental results involving the classification of the noisy boundaries of the four Great Lakes, Erie, Huron, Michigan, and Superior, using this measure, have been presented.