Achieving Intelligent Traffic-aware Consolidation of Virtual Machines in a Data Center Using Learning Automata

Cloud Computing (CC) is becoming increasingly pertinent and popular. A natural consequence of this is that many modern-day data centers experience very high internal traffic within the data centers themselves. The VMs with high mutual traffic often end up being far apart in the data center network, forcing them to communicate over unnecessarily long distances. The consequent traffic bottlenecks negatively affect both the performance of the application and the network in its entirety, posing nontrivial challenges for the administrators of these cloudbased data centers. The problem can, quite naturally, be compartmentalized into two phases which follow each other. First of all, the VMs are co…

On Utilizing Association and Interaction Concepts for Enhancing Microaggregation in Secure Statistical Databases

Published version of an article in the journal: IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics. Personal use of this material is permitted. Permission from IEEE must be obtained for all other users, including reprinting/ republishing this material for advertising or promotional purposes, creating new collective works for resale or redistribution to servers or lists, or reuse of any copyrighted components of this work in other works 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 availa…

Networking logistic neurons can yield chaotic and pattern recognition properties

Accepted version of an article the book: 2011 IEEE International Conference on Computational Intelligence for Measurement Systems and Applications (CIMSA) Proceedings. Published version available from IEEE: http://dx.doi.org/10.1109/CIMSA.2011.6059914 Over the last few years, the field of Chaotic Neural Networks (CNNs) has been extensively studied because of their potential applications in the understanding/recognition of patterns and images, their associative memory properties, their relationship to complex dynamic system control, and their capabilities in the modeling and analysis of other measurement systems. However, the results concerning CNNs which can demonstrate chaos, quasi-chaos, …

On achieving intelligent traffic-aware consolidation of virtual machines in a data center using Learning Automata

Unlike the computational mechanisms of the past many decades, that involved individual (extremely powerful) computers or clusters of machines, cloud computing (CC) is becoming increasingly pertinent and popular. Computing resources such as CPU and storage are becoming cheaper, and the servers themselves are becoming more powerful. This enables clouds to host more virtual machines (VMs). A natural consequence ofthis is that many modern-day data centers experience very high internaltraffic within the data centers themselves. This is, of course, due to the occurrence of servers that belong to the same tenant, communicating between themselves. The problem is accentuated when the VM deployment t…

Higher-Fidelity Frugal and Accurate Quantile Estimation Using a Novel Incremental <italic>Discretized</italic> Paradigm

Traditional pattern classification works with the moments of the distributions of the features and involves the estimation of the means and variances. As opposed to this, more recently, research has indicated the power of using the quantiles of the distributions because they are more robust and applicable for non-parametric methods. The estimation of the quantiles is even more pertinent when one is mining data streams. However, the complexity of quantile estimation is much higher than the corresponding estimation of the mean and variance, and this increased complexity is more relevant as the size of the data increases. Clearly, in the context of infinite data streams, a computational and sp…

Scheduling Domestic Shiftable Loads in Smart Grids: A Learning Automata-Based Scheme

In this paper, we consider the problem of scheduling shiftable loads, over multiple users, in smart grids. We approach the problem, which is becoming increasingly pertinent in our present energy-thirsty society, using a novel distributed game-theoretic framework. From a modeling perspective, the distributed scheduling problem is formulated as a game, and in particular, a so-called “Potential” game. This game has at least one pure strategy Nash Equilibrium (NE), and we demonstrate that the NE point is a global optimal point. The solution that we propose, which is the pioneering solution that incorporates the theory of Learning Automata (LA), permits the total supplied loads to approach the p…

Solving Multiconstraint Assignment Problems Using Learning Automata

Published version of an article in the journal: IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics. Personal use of this material is permitted. Permission from IEEE must be obtained for all other users, including reprinting/ republishing this material for advertising or promotional purposes, creating new collective works for resale or redistribution to servers or lists, or reuse of any copyrighted components of this work in other works 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 ldquosimilarrdquo to ea…

A User-Centric Approach for Personalized Service Provisioning in Pervasive Environments

Published version of an article published in Wireless Personal Communications (2011). Also available from the publisher at http://dx.doi.org/10.1007/s11277-011-0387-3 The vision of pervasive environments is being realized more than ever with the proliferation of services and computing resources located in our surrounding environments. Identifying those services that deserve the attention of the user is becoming an increasingly-challenging task. In this paper, we present an adaptive multi-criteria decision making mechanism for recommending relevant services to the mobile user. In this context, "Relevance" is determined based on a user-centric approach that combines both the reputation of the…

Concept Drift Detection Using Online Histogram-Based Bayesian Classifiers

In this paper, we present a novel algorithm that performs online histogram-based classification, i.e., specifically designed for the case when the data is dynamic and its distribution is non-stationary. Our method, called the Online Histogram-based Naïve Bayes Classifier (OHNBC) involves a statistical classifier based on the well-established Bayesian theory, but which makes some assumptions with respect to the independence of the attributes. Moreover, this classifier generates a prediction model using uni-dimensional histograms, whose segments or buckets are fixed in terms of their cardinalities but dynamic in terms of their widths. Additionally, our algorithm invokes the principles of info…

Learning Automata-Based Solutions to the Multi-Elevator Problem

In the last century, AI has been the topic of interest in many areas, where the focus was on mimicking human behaviour. It has been researched to be incorporated into different domains, such as security, diagnosis, autonomous driving, financial prediction analysis and playing games such as chess and Go. They also worked on different subfields of AI such as machine learning, deep learning, pattern recognition and other relevant subfields. Our work in a previous paper [1] focused on a problem that has not been tackled using AI before, which is the elevator-problem. In which we try to find the optimal parking floor for the elevator for the single elevator problem. In this paper, our work exten…

The Bayesian Pursuit Algorithm: A New Family of Estimator Learning Automata

Published version of a chapter in the book: Modern Approaches in Applied Intelligence. Also available from the publisher at http://dx.doi.org/10.1007/978-3-642-21827-9_53 The fastest Learning Automata (LA) algorithms currently available come from the family of estimator algorithms. The Pursuit algorithm (PST), a pioneering scheme in the estimator family, obtains its superior learning speed by using Maximum Likelihood (ML) estimates to pursue the action currently perceived as being optimal. Recently, a Bayesian LA (BLA) was introduced, and empirical results that demonstrated its advantages over established top performers, including the PST scheme, were reported. The BLA scheme is inherently …

Optimizing channel selection for cognitive radio networks using a distributed Bayesian learning automata-based approach

Consider a multi-channel Cognitive Radio Network (CRN) with multiple Primary Users (PUs), and multiple Secondary Users (SUs) competing for access to the channels. In this scenario, it is essential for SUs to avoid collision among one another while maintaining efficient usage of the available transmission opportunities. We investigate two channel access schemes. In the first model, an SU selects a channel and sends a packet directly without Carrier Sensing (CS) whenever the PU is absent on this channel. In the second model, an SU invokes CS in order to avoid collision among co-channel SUs. For each model, we analyze the channel selection problem and prove that it is a so-called "Exact Potent…

Solving Two-Person Zero-Sum Stochastic Games With Incomplete Information Using Learning Automata With Artificial Barriers

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…

On the Cryptanalysis of Two Cryptographic Algorithms That Utilize Chaotic Neural Networks

This paper deals with the security and efficiency issues of two cipher algorithms which utilize the principles of Chaotic Neural Networks (CNNs). The two algorithms that we consider are (1) the CNN-Hash, which is a one-way hash function based on the Piece-Wise Linear Chaotic Map (PWLCM) and the One-Way Coupled Map Lattice (OCML), and (2) the Delayed CNN-Based Encryption (DCBE), which is an encryption algorithm based on the delayed CNN. Although both of these cipher algorithms have their own salient characteristics, our analysis shows that, unfortunately, the CNN-Hash is not secure because it is neither Second-Preimage resistant nor collision resistant. Indeed, one can find a collision with …

A Stochastic Search on the Line-Based Solution to Discretized Estimation

Published version of a chapter in the book: Advanced Research in Applied Artificial Intelligence. Also available from the publisher at: http://dx.doi.org/10.1007/978-3-642-31087-4_77 Recently, Oommen and Rueda [11] presented a strategy by which the parameters of a binomial/multinomial distribution can be estimated when the underlying distribution is nonstationary. The method has been referred to as the Stochastic Learning Weak Estimator (SLWE), and is based on the principles of continuous stochastic Learning Automata (LA). In this paper, we consider a new family of stochastic discretized weak estimators pertinent to tracking time-varying binomial distributions. As opposed to the SLWE, our p…

On enhancing the object migration automaton using the Pursuit paradigm

Abstract One of the most difficult problems that is all-pervasive in computing is that of partitioning. It has applications in the partitioning of databases into relations, the realization of the relations themselves into sub-relations based on the partitioning of the attributes, the assignment of processes to processors, graph partitioning, and the task assignment problem, etc. The problem is known to be NP-hard. The benchmark solution for this for the Equi-Partitioning Problem (EPP) has involved the classic field of Learning Automata (LA), and the corresponding algorithm, the Object Migrating Automata (OMA) has been used in all of these application domains. While the OMA is a fixed struct…

User Grouping and Power Allocation in NOMA Systems: A Reinforcement Learning-Based Solution

In this paper, we present a pioneering solution to the problem of user grouping and power allocation in Non-Orthogonal Multiple Access (NOMA) systems. There are two fundamentally salient and difficult issues associated with NOMA systems. The first involves the task of grouping users together into the pre-specified time slots. The subsequent second phase augments this with the solution of determining how much power should be allocated to the respective users. We resolve this with the first reported Reinforcement Learning (RL)-based solution, which attempts to solve the partitioning phase of this issue. In particular, we invoke the Object Migration Automata (OMA) and one of its variants to re…

An intelligent architecture for service provisioning in pervasive environments

Accepted version of an article from the conference: 2011 International Symposium on Innovations in Intelligent Systems and Applications (INISTA). Definitive published version available from IEEE: http://dx.doi.org/10.1109/INISTA.2011.5946134 The vision of pervasive environments is being realized more than ever with the proliferation of services and computing resources located in our surrounding environments. Identifying those services that deserve the attention of the user is becoming an increasingly-challenging task. In this paper, we present an adaptive multi-criteria decision making mechanism for recommending relevant services to the mobile user. In this context Relevance is determined b…

A Bayesian Learning Automata-Based Distributed Channel Selection Scheme for Cognitive Radio Networks

We consider a scenario where multiple Secondary Users SUs operate within a Cognitive Radio Network CRN which involves a set of channels, where each channel is associated with a Primary User PU. We investigate two channel access strategies for SU transmissions. In the first strategy, the SUs will send a packet directly without operating Carrier Sensing Medium Access/Collision Avoidance CSMA/CA whenever a PU is absent in the selected channel. In the second strategy, the SUs implement CSMA/CA to further reduce the probability of collisions among co-channel SUs. For each strategy, the channel selection problem is formulated and demonstrated to be a so-called "Potential" game, and a Bayesian Lea…

A Cluster Analysis of Stock Market Data Using Hierarchical SOMs

The analysis of stock markets has become relevant mainly because of its financial implications. In this paper, we propose a novel methodology for performing a structured cluster analysis of stock market data. Our proposed method uses a tree-based neural network called the TTOSOM. The TTOSOM performs self-organization to construct tree-based clusters of vector data in the multi-dimensional space. The resultant tree possesses interesting mathematical properties such as a succinct representation of the original data distribution, and a preservation of the underlying topology. In order to demonstrate the capabilities of our method, we analyze 206 assets of the Italian stock market. We were able…

A Novel Border Identification Algorithm Based on an “Anti-Bayesian” Paradigm

Published version of a chapter in the book: Computer Analysis of Images and Patterns. Also available from the publisher at: http://dx.doi.org/10.1007/978-3-642-40261-6_23 Border Identification (BI) algorithms, a subset of Prototype Reduction Schemes (PRS) aim to reduce the number of training vectors so that the reduced set (the border set) contains only those patterns which lie near the border of the classes, and have sufficient information to perform a meaningful classification. However, one can see that the true border patterns (“near” border) are not able to perform the task independently as they are not able to always distinguish the testing samples. Thus, researchers have worked on thi…

Novel threat-based AI strategies that incorporate adaptive data structures for multi-player board games

This paper considers the problem of designing novel techniques for multi-player game playing, in a range of board games and configurations. Compared to the well-known case of two-player game playing, multi-player game playing is a more complex problem with unique requirements. To address the unique challenges of this domain, we examine the potential of employing techniques inspired by Adaptive Data Structures (ADSs) to rank opponents based on their relative threats, and using this information to achieve gains in move ordering and tree pruning. We name our new technique the Threat-ADS heuristic. We examine the Threat-ADS’ performance within a range of game models, employing a number of diffe…

On merging the fields of neural networks and adaptive data structures to yield new pattern recognition methodologies

Published version of a chapter from the book Pattern Recognition and Machine Intelligence. Also available from the publisher at http://dx.doi.org/10.1007/978-3-642-21786-9_3 The aim of this talk is to explain a pioneering exploratory research endeavour that attempts to merge two completely different fields in Computer Science so as to yield very fascinating results. These are the well-established fields of Neural Networks (NNs) and Adaptive Data Structures (ADS) respectively. The field of NNs deals with the training and learning capabilities of a large number of neurons, each possessing minimal computational properties. On the other hand, the field of ADS concerns designing, implementing an…

Learning Automata-Based Solutions to Stochastic Nonlinear Resource Allocation Problems

“Computational Intelligence” is an extremely wide-ranging and all-encompassing area. However, it is fair to say that the strength of a system that possesses “Computational Intelligence” can be quantified by its ability to solve problems that are intrinsically hard. One such class of NP-Hard problems concerns the so-called family of Knapsack Problems, and in this Chapter, we shall explain how a sub-field of Artificial Intelligence, namely that which involves “Learning Automata”, can be used to produce fast and accurate solutions to “difficult” and randomized versions of the Knapsack problem (KP).

Modeling a teacher in a tutorial-like system using Learning Automata

Published version of a chapter in the book: Transactions on Computational Collective Intelligence VIII. Also available from the publisher at: http://dx.doi.org/10.1007/978-3-642-34645-3_2 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 as…

Occlusion-based estimation of independent multinomial random variables using occurrence and sequential information

Abstract This paper deals with the relatively new field of sequence-based estimation in which the goal is to estimate the parameters of a distribution by utilizing both the information in the observations and in their sequence of appearance. Traditionally, the Maximum Likelihood (ML) and Bayesian estimation paradigms work within the model that the data, from which the parameters are to be estimated, is known, and that it is treated as a set rather than as a sequence. The position that we take is that these methods ignore, and thus discard, valuable sequence -based information, and our intention is to obtain ML estimates by “extracting” the information contained in the observations when perc…

On the pattern recognition and classification of stochastically episodic events

Published version of a chapter published in the book: Transactions on Compuational Collective Intelligence VI. Also available from the publisher at: http://dx.doi.org/10.1007/978-3-642-29356-6_1 Researchers in the field of Pattern Recognition (PR) have traditionally presumed the availability of a representative set of data drawn from the classes of interest, say ω 1 and ω 2 in a 2-class problem. These samples are typically utilized in the development of the system’s discriminant function. It is, however, widely recognized that there exists a particularly challenging class of PR problems for which a representative set is not available for the second class, which has motivated a great deal of…

A new paradigm for pattern classification: Nearest Border Techniques

Published version of a chapter in the book: AI 2013: Advances in Artificial Intelligence. Also available from the publisher at: http://dx.doi.org/10.1007/978-3-319-03680-9_44 There are many paradigms for pattern classification. As opposed to these, this paper introduces a paradigm that has not been reported in the literature earlier, which we shall refer to as the Nearest Border (NB) paradigm. The philosophy for developing such a NB strategy is as follows: Given the training data set for each class, we shall first attempt to create borders for each individual class. After that, we advocate that testing is accomplished by assigning the test sample to the class whose border it lies closest to…

Discretized Bayesian Pursuit – A New Scheme for Reinforcement Learning

Published version of a chapter in the book: Advanced Research in Applied Artificial Intelligence. Also available from the publisher at: http://dx.doi.org/10.1007/978-3-642-31087-4_79 The success of Learning Automata (LA)-based estimator algorithms over the classical, Linear Reward-Inaction ( L RI )-like schemes, can be explained by their ability to pursue the actions with the highest reward probability estimates. Without access to reward probability estimates, it makes sense for schemes like the L RI to first make large exploring steps, and then to gradually turn exploration into exploitation by making progressively smaller learning steps. However, this behavior becomes counter-intuitive wh…

A formal proof of the ε-optimality of absorbing continuous pursuit algorithms using the theory of regular functions

Published version of an article from the journal: Applied Intelligence. Also available on Springerlink: http://dx.doi.org/10.1007/s10489-014-0541-1 The most difficult part in the design and analysis of Learning Automata (LA) consists of the formal proofs of their convergence accuracies. The mathematical techniques used for the different families (Fixed Structure, Variable Structure, Discretized etc.) are quite distinct. Among the families of LA, Estimator Algorithms (EAs) are certainly the fastest, and within this family, the set of Pursuit algorithms have been considered to be the pioneering schemes. Informally, if the environment is stationary, their ε-optimality is defined as their abili…

On achieving near-optimal “Anti-Bayesian” Order Statistics-Based classification fora asymmetric exponential distributions

Published version of a Chapter in the book: Computer Analysis of Images and Patterns. Also available from the publisher at: http://dx.doi.org/10.1007/978-3-642-40261-6_44 This paper considers the use of Order Statistics (OS) in the theory of Pattern Recognition (PR). The pioneering work on using OS for classification was presented in [1] for the Uniform distribution, where it was shown that optimal PR can be achieved in a counter-intuitive manner, diametrically opposed to the Bayesian paradigm, i.e., by comparing the testing sample to a few samples distant from the mean - which is distinct from the optimal Bayesian paradigm. In [2], we showed that the results could be extended for a few sym…

Learning Automaton Based On-Line Discovery and Tracking of Spatio-temporal Event Patterns

Published version of an article from the book: Lecture Notes in Computer Science, 2010, Volume 6230/2010, 327-338. The original publication is available at Springerlink. http://dx.doi.org/10.1007/978-3-642-15246-7_31 Discovering and tracking of spatio-temporal patterns in noisy sequences of events is a difficult task that has 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 functionalites increases as event-sharing expands into larger areas of one’s life. Ironically, …

A novel Stochastic Discretized Weak Estimator operating in non-stationary environments

The task of designing estimators that are able to track time-varying distributions has found promising applications in many real-life problems. A particularly interesting family of distributions are the binomial/multiomial distributions. Existing approaches resort to sliding windows that track changes by discarding old observations. In this paper, we report a novel estimator referred to as the Stochastic Discretized Weak Estimator (SDWE), that is based on the principles of Learning Automata (LA). In brief, the estimator is able to estimate the parameters of a time varying binomial distribution using finite memory. The estimator tracks changes in the distribution by operating on a controlled…

Learning automata-based solutions to the optimal web polling problem modelled as a nonlinear fractional knapsack problem

We consider the problem of polling web pages as a strategy for monitoring the world wide web. The problem consists of repeatedly polling a selection of web pages so that changes that occur over time are detected. In particular, we consider the case where we are constrained to poll a maximum number of web pages per unit of time, and this constraint is typically dictated by the governing communication bandwidth, and by the speed limitations associated with the processing. Since only a fraction of the web pages can be polled within a given unit of time, the issue at stake is one of determining which web pages are to be polled, and we attempt to do it in a manner that maximizes the number of ch…

On the analysis of a new Markov chain which has applications in AI and machine learning

Accepted version of an article from the conference: 2011 24th Canadian Conference on Electrical and Computer Engineering. Published version available from IEEE: http://dx.doi.org/10.1109/CCECE.2011.6030727 In this paper, we consider the analysis of a fascinating Random Walk (RW) that contains interleaving random steps and random "jumps". The characterizing aspect of such a chain is that every step is paired with its counterpart random jump. RWs of this sort have applications in testing of entities, where the entity is never allowed to make more than a pre-specified number of consecutive failures. This paper contains the analysis of the chain, some fascinating limiting properties, and some i…

Tracking the Preferences of Users Using Weak Estimators

Published version of am article from the book:AI 2011: Advances in Artificial Intelligence. Also available from the publisher on SpringerLink:http://dx.doi.org/10.1007/978-3-642-25832-9_81 Since a social network, by definition, is so diverse, the problem of estimating the preferences of its users is becoming increasingly essential for personalized applications which range from service recommender systems to the targeted advertising of services. However, unlike traditional estimation problems where the underlying target distribution is stationary, estimating a user’s interests, typically, involves non-stationary distributions. The consequent time varying nature of the distribution to be trac…

On using prototype reduction schemes to optimize locally linear reconstruction methods

Authors version of an article published in the journal: Pattern Recognition. Also available from the publisher at: http://dx.doi.org/10.1016/j.patcog.2011.06.021 This paper concerns the use of prototype reduction schemes (PRS) to optimize the computations involved in typical k-nearest neighbor (k-NN) rules. These rules have been successfully used for decades in statistical pattern recognition (PR) [1,15] applications and are particularly effective for density estimation, classification, and regression because of the known error bounds that they possess. For a given data point of unknown identity, the k-NN possesses the phenomenon that it combines the information about the samples from a pri…

Optimal sampling for estimation with constrained resources using a learning automaton-based solution for the nonlinear fractional knapsack problem

Published version of an article from the journal: Applied intelligence. The original publication is available at Springerlink. http://dx.doi.org/10.1007/s10489-010-0228-1 While training and estimation for Pattern Recognition (PR) have been extensively studied, the question of achieving these when the resources are both limited and constrained is relatively open. This is the focus of this paper. We consider the problem of allocating limited sampling resources in a “real-time” manner, with the explicit purpose of estimating multiple binomial proportions (the extension of these results to non-binomial proportions is, in our opinion, rather straightforward). More specifically, the user is prese…

On Using a Hierarchy of Twofold Resource Allocation Automata to Solve Stochastic Nonlinear Resource Allocation Problems

Recent trends in AI attempt to solve difficult NP-hard problems using intelligent techniques so as to obtain approximately-optimal solutions. In this paper, we consider a family of such problems which fall under the general umbrella of "knapsack-like" problems, and demonstrate how we can solve all of them fast and accurately using a hierarchy of Learning Automata (LA). In a multitude of real-world situations, resources must be allocated based on incomplete and noisy information, which often renders traditional resource allocation techniques ineffective. This paper addresses one such class of problems, namely, Stochastic Non-linear Fractional Knapsack Problems. We first present a completely …

Identifying Unreliable Sensors Without a Knowledge of the Ground Truth in Deceptive Environments

This paper deals with the extremely fascinating area of “fusing” the outputs of sensors without any knowledge of the ground truth. In an earlier paper, the present authors had recently pioneered a solution, by mapping it onto the fascinating paradox of trying to identify stochastic liars without any additional information about the truth. Even though that work was significant, it was constrained by the model in which we are living in a world where “the truth prevails over lying”. Couched in the terminology of Learning Automata (LA), this corresponds to the Environment (Since the Environment is treated as an entity in its own right, we choose to capitalize it, rather than refer to it as an “…

A novel abstraction for swarm intelligence: particle field optimization

Particle swarm optimization (PSO) is a popular meta-heuristic for black-box optimization. In essence, within this paradigm, the system is fully defined by a swarm of "particles" each characterized by a set of features such as its position, velocity and acceleration. The consequent optimized global best solution is obtained by comparing the personal best solutions of the entire swarm. Many variations and extensions of PSO have been developed since its creation in 1995, and the algorithm remains a popular topic of research. In this work we submit a new, abstracted perspective of the PSO system, where we attempt to move away from the swarm of individual particles, but rather characterize each …

An adaptive approach to learning the preferences of users in a social network using weak estimators

Published version of an article in the journal: Journal of Information Processing Systems. Also available from the publisher at: http://dx.doi.org/10.3745/JIPS.2012.8.2.191 - Open Access Since a social network by definition is so diverse, the problem of estimating the preferences of its users is becoming increasingly essential for personalized applications, which range from service recommender systems to the targeted advertising of services. However, unlike traditional estimation problems where the underlying target distribution is stationary; estimating a user's interests typically involves non-stationary distributions. The consequent time varying nature of the distribution to be tracked i…

The Power of the “Pursuit” Learning Paradigm in the Partitioning of Data

Traditional Learning Automata (LA) work with the understanding that the actions are chosen purely based on the “state” in which the machine is. This modus operandus completely ignores any estimation of the Random Environment’s (RE’s) (specified as \(\mathbb {E}\)) reward/penalty probabilities. To take these into consideration, Estimator/Pursuit LA utilize “cheap” estimates of the Environment’s reward probabilities to make them converge by an order of magnitude faster. This concept is quite simply the following: Inexpensive estimates of the reward probabilities can be used to rank the actions. Thereafter, when the action probability vector has to be updated, it is done not on the basis of th…

A new frontier in novelty detection: Pattern recognition of stochastically episodic events

Published version of an article from the book: Intelligent Information and Database Systems, Lecture Notes in Computer Science. Also available from the publisher on SpringerLink:http://dx.doi.org/10.1007/978-3-642-20039-7_44 A particularly challenging class of PR problems in which the, generally required, representative set of data drawn from the second class is unavailable, has recently received much consideration under the guise of One-Class (OC) classification. In this paper, we extend the frontiers of OC classification by the introduction of a new field of problems open for analysis. In particular, we note that this new realm deviates from the standard set of OC problems based on the fo…

Solving Stochastic Nonlinear Resource Allocation Problems Using a Hierarchy of Twofold Resource Allocation Automata.

Published version of an article in the journal: IEEE Transactions on Computers. Personal use of this material is permitted. Permission from IEEE must be obtained for all other users, including reprinting/ republishing this material for advertising or promotional purposes, creating new collective works for resale or redistribution to servers or lists, or reuse of any copyrighted components of this work in other works 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 Ga…

Imposing tree-based topologies onto self organizing maps

Accepted version of an article from the journal Information Sciences. Definitive published version available on Elsevier Science Direct: http://dx.doi.org/10.1016/j.ins.2011.04.038 The beauty of the Kohonen map is that it has the property of organizing the codebook vectors, which represent the data points, both with respect to the underlying distribution and topologically. This topology is traditionally linear, even though the underlying lattice could be a grid, and this has been used in a variety of applications [23,35,40]. The most prominent efforts to render the topology to be structured involves the Evolving Tree (ET) due to Pakkanen et al. [36], and the Self-Organizing Tree Maps (SOTM)…

The design of absorbing Bayesian pursuit algorithms and the formal analyses of their ε-optimality

The fundamental phenomenon that has been used to enhance the convergence speed of learning automata (LA) is that of incorporating the running maximum likelihood (ML) estimates of the action reward probabilities into the probability updating rules for selecting the actions. The frontiers of this field have been recently expanded by replacing the ML estimates with their corresponding Bayesian counterparts that incorporate the properties of the conjugate priors. These constitute the Bayesian pursuit algorithm (BPA), and the discretized Bayesian pursuit algorithm. Although these algorithms have been designed and efficiently implemented, and are, arguably, the fastest and most accurate LA report…

Ultimate Order Statistics-Based Prototype Reduction Schemes

Published version of a chapter in the book: AI 2013: Advances in Artificial Intelligence. Also available from the publisher at: http://dx.doi.org/10.1007/978-3-319-03680-9_42 The objective of Prototype Reduction Schemes (PRSs) and Border Identification (BI) algorithms is to reduce the number of training vectors, while simultaneously attempting to guarantee that the classifier built on the reduced design set performs as well, or nearly as well, as the classifier built on the original design set. In this paper, we shall push the limit on the field of PRSs to see if we can obtain a classification accuracy comparable to the optimal, by condensing the information in the data set into a single tr…

Learning automata-based solutions to the optimal web polling problem modelled as a nonlinear fractional knapsack problem

Accepted version of an article from the journal: Engineering Applications of Artificial Intelligence. Definitive published version on Elsevier Science Direct: http://dx.doi.org/10.1016/j.engappai.2011.05.018 We consider the problem of polling web pages as a strategy for monitoring the world wide web. The problem consists of repeatedly polling a selection of web pages so that changes that occur over time are detected. In particular, we consider the case where we are constrained to poll a maximum number of web pages per unit of time, and this constraint is typically dictated by the governing communication bandwidth, and by the speed limitations associated with the processing. Since only a fra…

On the classification of dynamical data streams using novel “Anti-Bayesian” techniques

Abstract 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, tha…

“Anti-Bayesian” parametric pattern classification using order statistics criteria for some members of the exponential family

This paper submits a comprehensive report of the use of order statistics (OS) for parametric pattern recognition (PR) for various distributions within the exponential family. Although the field of parametric PR has been thoroughly studied for over five decades, the use of the OS of the distributions to achieve this has not been reported. The pioneering work on using OS for classification was presented earlier for the uniform distribution and for some members of the exponential family, where it was shown that optimal PR can be achieved in a counter-intuitive manner, diametrically opposed to the Bayesian paradigm, i.e., by comparing the testing sample to a few samples distant from the mean. A…

Using artificial intelligence techniques for strategy generation in the Commons game

Published version of a chapter in the book: Hybrid Artificial Intelligent Systems. Also available from the publisher on SpringerLink: http://dx.doi.org/10.1007/978-3-642-21219-2_7 In this paper, we consider the use of artificial intelligence techniques to aid in discovery of winning strategies for the Commons Game (CG). The game represents a common scenario in which multiple parties share the use of a self-replenishing resource. The resource deteriorates quickly if used indiscriminately. If used responsibly, however, the resource thrives. We consider the scenario one player uses hill climbing or particle swarm optimization to select the course of action, while the remaining N − 1 players us…

A Conclusive Analysis of the Finite-Time Behavior of the Discretized Pursuit Learning Automaton

Author's accepted version (post-print). © 20XX IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. Available from 20/03/2021. 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, probabl…

Multi-class pairwise linear dimensionality reduction using heteroscedastic schemes

Accepted version of an article published in the journal: Pattern Recognition. Published version on Sciverse: http://dx.doi.org/10.1016/j.patcog.2010.01.018 Linear dimensionality reduction (LDR) techniques have been increasingly important in pattern recognition (PR) due to the fact that they permit a relatively simple mapping of the problem onto a lower-dimensional subspace, leading to simple and computationally efficient classification strategies. Although the field has been well developed for the two-class problem, the corresponding issues encountered when dealing with multiple classes are far from trivial. In this paper, we argue that, as opposed to the traditional LDR multi-class schemes…

A New Tool for the Modeling of AI and Machine Learning Applications: Random Walk-Jump Processes

Published version of an article from the book: Hybrid artificial intelligent systems, Lecture notes in computer science. The original publication is available at www.springerlink.com, http://dx.doi.org/10.1007/978-3-642-21219-2_2 There are numerous applications in Artificial Intelligence (AI) and Machine Learning (ML) where the criteria for decisions are based on testing procedures. The most common tools used in such random phenomena involve Random Walks (RWs). The theory of RWs and its applications have gained an increasing research interest since the start of the last century. [1]. In this context, we note that a RW is, usually, defined as a trajectory involving a series of successive ran…

On solving single elevator-like problems using a learning automata-based paradigm

This paper concentrates on a host of problems with characteristics similar to those that are related to moving elevators within a building. These are referred to as Elevator-like problems (ELPs), and their common phenomena will be expanded on in the body of the paper. We shall resolve ELPs using a subfield of AI, namely the field of learning automata (LA). Rather than working with the well-established mathematical formulations of the field, our intention is to use these tools to tackle ELPs, and in particular, those that deal with single “elevators” moving between “floors”. ELPs have not been tackled before using AI. In a simplified domain, the ELP involves the problem of optimizing the sch…

On Distinguishing between Reliable and Unreliable Sensors Without a Knowledge of the Ground Truth

In many applications, data from different sensors are aggregated in order to obtain more reliable information about the process that the sensors are monitoring. However, the quality of the aggregated information is intricately dependent on the reliability of the individual sensors. In fact, unreliable sensors will tend to report erroneous values of the ground truth, and thus degrade the quality of the fused information. Finding strategies to identify unreliable sensors can assist in having a counter-effect on their respective detrimental influences on the fusion process, and this has has been a focal concern in the literature. The purpose of this paper is to propose a solution to an extreme…

On Using “Stochastic Learning on the Line” to Design Novel Distance Estimation Methods

In this paper, we consider the problem of Distance Estimation (DE) when the inputs are the x and y coordinates of the points under consideration. The aim of the problem is to yield an accurate value for the real (road) distance between the points specified by the latter coordinates. This problem has, typically, been tackled by utilizing parametric functions called Distance Estimation Functions (DEFs). The parameters are learned from the training data (i.e., the true road distances) between a subset of the points under consideration. We propose to use Learning Automata (LA)-based strategies to solve the problem. In particular, we resort to the Adaptive Tertiary Search (ATS) strategy, propose…

Fault-tolerant routing in adversarial mobile ad hoc networks: an efficient route estimation scheme for non-stationary environments

Published version of an article from the journal: Telecommunication systems. The original publication is available at Spingerlink. http://dx.doi.org/DOI: 10.1007/s11235-009-9215-4 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 operating in a network with malfunctioning nodes. 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 misbehaving no…

On Solving the Problem of Identifying Unreliable Sensors Without a Knowledge of the Ground Truth: The Case of Stochastic Environments.

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 counterintuitive 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 exam…

THE USE OF WEAK ESTIMATORS TO ACHIEVE LANGUAGE DETECTION AND TRACKING IN MULTILINGUAL DOCUMENTS

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…

Achieving Unbounded Resolution inFinitePlayer Goore Games Using Stochastic Automata, and Its Applications

Abstract This article concerns the sequential solution to a distributed stochastic optimization problem using learning automata and the Goore game (also referred to as the Gur game in the related literature). The amazing thing about our solution is that, unlike traditional methods, which need N automata (where N determines the degree of accuracy), in this article, we show that we can obtain arbitrary accuracy by recursively using only three automata. To be more specific, the Goore game (GG) introduced in Tsetlin (1973) has the fascinating property that it can be resolved in a completely distributed manner with no inter-communication between the players. The game has recently found applicati…

Using the Theory of Regular Functions to Formally Prove the ε-Optimality of Discretized Pursuit Learning Algorithms

Learning Automata LA can be reckoned to be the founding algorithms on which the field of Reinforcement Learning has been built. Among the families of LA, Estimator Algorithms EAs are certainly the fastest, and of these, the family of Pursuit Algorithms PAs are the pioneering work. It has recently been reported that the previous proofs for e-optimality for all the reported algorithms in the family of PAs have been flawed. We applaud the researchers who discovered this flaw, and who further proceeded to rectify the proof for the Continuous Pursuit Algorithm CPA. The latter proof, though requires the learning parameter to be continuously changing, is, to the best of our knowledge, the current …

A Hierarchy of Twofold Resource Allocation Automata Supporting Optimal Sampling

We consider the problem of allocating limited sampling resources in a "real-time" manner with the purpose of estimating multiple binomial proportions. More specifically, the user is presented with `n ' sets of data points, S 1 , S 2 , ..., S n , where the set S i has N i points drawn from two classes {*** 1 , *** 2 }. A random sample in set S i belongs to *** 1 with probability u i and to *** 2 with probability 1 *** u i , with {u i }. i = 1, 2, ...n , being the quantities to be learnt. The problem is both interesting and non-trivial because while both n and each N i are large, the number of samples that can be drawn is bounded by a constant, c . We solve the problem by first modelling it a…

Generalized Bayesian pursuit: A novel scheme for multi-armed Bernoulli bandit problems

Published version of a chapter in the book: IFIP Advances in Information and Communication Technology. Also available from the publisher at: http;//dx.doi.org/10.1007/978-3-642-23960-1_16 In the last decades, a myriad of approaches to the multi-armed bandit problem have appeared in several different fields. The current top performing algorithms from the field of Learning Automata reside in the Pursuit family, while UCB-Tuned and the ε -greedy class of algorithms can be seen as state-of-the-art regret minimizing algorithms. Recently, however, the Bayesian Learning Automaton (BLA) outperformed all of these, and other schemes, in a wide range of experiments. Although seemingly incompatible, in…

User grouping and power allocation in NOMA systems: a novel semi-supervised reinforcement learning-based solution

Author's accepted manuscript In this paper, we present a pioneering solution to the problem of user grouping and power allocation in non-orthogonal multiple access (NOMA) systems. The problem is highly pertinent because NOMA is a well-recognized technique for future mobile radio systems. The salient and difcult issues associated with NOMA systems involve the task of grouping users together into the prespecifed time slots, which are augmented with the question of determining how much power should be allocated to the respective users. This problem is, in and of itself, NP-hard. Our solution is the frst reported reinforcement learning (RL)-based solution, which attempts to resolve parts of thi…

On utilizing dependence-based information to enhance micro-aggregation for secure statistical databases

Published version of an article in the journal: Pattern Analysis and Applications. Also available from the publisher at: http://dx.doi.org/10.1007/s10044-011-0199-9 We consider the micro-aggregation problem which involves partitioning a set of individual records in a micro-data file into a number of mutually exclusive and exhaustive groups. This problem, which seeks for the best partition of the micro-data file, is known to be NP-hard, and has been tackled using many heuristic solutions. In this paper, we would like to demonstrate that in the process of developing micro-aggregation techniques (MATs), it is expedient to incorporate information about the dependence between the random variable…

On Optimizing Locally Linear Nearest Neighbour Reconstructions Using Prototype Reduction Schemes

Published version of an article from the Book: AI 2010: Advances in Artificial Intelligence, Spinger. Also available on Springerlink: http://dx.doi.org/10.1007/978-3-642-17432-2_16 This paper concerns the use of Prototype Reduction Schemes (PRS) to optimize the computations involved in typical k-Nearest Neighbor (k-NN) rules. These rules have been successfully used for decades in statistical Pattern Recognition (PR) applications, and have numerous applications because of their known error bounds. For a given data point of unknown identity, the k-NN possesses the phenomenon that it combines the information about the samples from a priori target classes (values) of selected neighbors to, for …

On the Analysis of a Random Interleaving Walk–Jump Process with Applications to Testing

Abstract Although random walks (RWs) with single-step transitions have been extensively studied for almost a century as seen in Feller (1968), problems involving the analysis of RWs that contain interleaving random steps and random “jumps” are intrinsically hard. In this article, we consider the analysis of one such fascinating RW, where every step is paired with its counterpart random jump. In addition to this RW being conceptually interesting, it has applications in testing of entities (components or personnel), where the entity is never allowed to make more than a prespecified number of consecutive failures. The article contains the analysis of the chain, some fascinating limiting proper…

Stochastic discretized learning-based weak estimation: a novel estimation method for non-stationary environments

The task of designing estimators that are able to track time-varying distributions has found promising applications in many real-life problems.Existing approaches resort to sliding windows that track changes by discarding old observations. In this paper, we report a novel estimator referred to as the Stochastic Discretized Weak Estimator (SDWE), that is based on the principles of discretized Learning Automata (LA). In brief, the estimator is able to estimate the parameters of a time varying binomial distribution using finite memory. The estimator tracks changes in the distribution by operating a controlled random walk in a discretized probability space. The steps of the estimator are discre…

On Optimizing Locally Linear Nearest Neighbour Reconstructions Using Prototype Reduction Schemes

This paper concerns the use of Prototype Reduction Schemes (PRS) to optimize the computations involved in typical k-Nearest Neighbor (k-NN) rules. These rules have been successfully used for decades in statistical Pattern Recognition (PR) applications, and have numerous applications because of their known error bounds. For a given data point of unknown identity, the k-NN possesses the phenomenon that it combines the information about the samples from a priori target classes (values) of selected neighbors to, for example, predict the target class of the tested sample. Recently, an implementation of the k-NN, named as the Locally Linear Reconstruction (LLR) [11], has been proposed. The salien…

On utilizing an enhanced object partitioning scheme to optimize self-organizing lists-on-lists

With the advent of “Big Data” as a field, in and of itself, there are at least three fundamentally new questions that have emerged, namely the Artificially Intelligence (AI)-based algorithms required, the hardware to process the data, and the methods to store and access the data efficiently. This paper (The work of the second author was partially supported by NSERC, the Natural Sciences and Engineering Council of Canada. We are very grateful for the feedback from the anonymous Referees of the original submission. Their input significantly improved the quality of this final version.) presents some novel schemes for the last of the three areas. There have been thousands of papers written rega…

On the analysis of a random walk-jump chain with tree-based transitions and its applications to faulty dichotomous search

Random Walks (RWs) have been extensively studied for more than a century [1]. These walks have traditionally been on a line, and the generalizations for two and three dimensions, have been by extending the random steps to the corresponding neighboring positions in one or many of the dimensions. Among the most popular RWs on a line are the various models for birth and death processes, renewal processes and the gambler’s ruin problem. All of these RWs operate “on a discretized line”, and the walk is achieved by performing small steps to the current-state’s neighbor states. Indeed, it is this neighbor-step motion that renders their analyses tractable. When some of the transitions are to non-ne…

A Novel Clustering Algorithm based on a Non-parametric "Anti-Bayesian" Paradigm

The problem of clustering, or unsupervised classification, has been solved by a myriad of techniques, all of which depend, either directly or implicitly, on the Bayesian principle of optimal classification. To be more specific, within a Bayesian paradigm, if one is to compare the testing sample with only a single point in the feature space from each class, the optimal Bayesian strategy would be to achieve this based on the distance from the corresponding means or central points in the respective distributions. When this principle is applied in clustering, one would assign an unassigned sample into the cluster whose mean is the closest, and this can be done in either a bottom-up or a top-dow…

Corrigendum to three papers that deal with “Anti”-Bayesian Pattern Recognition [Pattern Recognition]

In the papers 1 (Thomas and Oommen, 2013), 2 (Oommen and Thomas, 2014) and 3 (Thomas and Oommen, 2013), and their associated conference versions cited in those papers, we had introduced a new method of so-called "Anti"-Bayesian Pattern Recognition (PR) which achieved the classification using only a few (sometimes as few as two) points distant from the mean. While the PR strategy, in and of itself, is accurate, the claim that it was based on the Order Statistics (OS) of the distributions of the features is not. The PR and classification results are rather founded on the symmetric quantiles and not on the symmetric OSs. This brief paper corrects the flawed claim presented in those papers. Hig…

Service selection in stochastic environments: a learning-automaton based solution

Published version of an article from the journal: Applied Intelligence. Also available from the publisher on SpringerLink: http://dx.doi.org/10.1007/s10489-011-0280-5 In this paper, we propose a novel solution to the problem of identifying services of high quality. The reported solutions to this problem have, in one way or the other, resorted to using so-called “Reputation Systems” (RSs). Although these systems can offer generic recommendations by aggregating user-provided opinions about the quality of the services under consideration, they are, understandably, prone to “ballot stuffing” and “badmouthing” in a competitive marketplace. In general, unfair ratings may degrade the trustworthine…

The Hierarchical Discrete Pursuit Learning Automaton: A Novel Scheme With Fast Convergence and Epsilon-Optimality

Author's accepted manuscript © 2022 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting /republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. 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 t…

Fault-Tolerant Routing in Mobile Ad Hoc Networks

On Addressing the Challenges of Complex Stochastic Games Using “Representative” Moves

The problem of achieving competitive game play in a board game, against an intelligent opponent, is a well-known and studied field of Artificial Intelligence (AI). This area of research has seen major breakthroughs in recent years, particularly in the game of Go. However, popular hobby board games, and particularly Trading Card Games, have unique qualities that make them very challenging to existing game playing techniques, partly due to enormous branching factors. This remains a largely unexamined domain and is the arena we operate in. To attempt to tackle some of these daunting requirements, we introduce the novel concept of “Representative” Moves (RMs). Rather than examine the complete l…

Text Classification Using Novel “Anti-Bayesian” Techniques

This paper presents a non-traditional “Anti-Bayesian” solution for the traditional Text Classification (TC) problem. Historically, all the recorded TC schemes work using the fundamental paradigm that once the statistical features are inferred from the syntactic/semantic indicators, the classifiers themselves are the well-established statistical ones. In this paper, we shall demonstrate that by virtue of the skewed distributions of the features, one could advantageously work with information latent in certain “non-central” quantiles (i.e., those distant from the mean) of the distributions. We, indeed, demonstrate that such classifiers exist and are attainable, and show that the design and im…

Modeling a Student's Behavior in a Tutorial-Like System Using Learning Automata

Published version of an article in the journal: IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics. Personal use of this material is permitted. Permission from IEEE must be obtained for all other users, including reprinting/ republishing this material for advertising or promotional purposes, creating new collective works for resale or redistribution to servers or lists, or reuse of any copyrighted components of this work in other works 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…

Anomaly Detection in Dynamic Social Systems Using Weak Estimators

Anomaly detection involves identifying observationsthat deviate from the normal behavior of a system. One ofthe ways to achieve this is by identifying the phenomena thatcharacterize “normal” observations. Subsequently, based on thecharacteristics 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 belongto the family parameterized statistical schemes, work under theassumption that the underlying distributions of the observationsare stationary. That is, they assume that the distributions thatare learned during the training (or learning) phase, thoughunknown, are not time-varyin…

On using novel “Anti-Bayesian” techniques for the classification of dynamical data streams

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…

On Utilizing Stochastic Non-linear Fractional Bin Packing to Resolve Distributed Web Crawling

This paper deals with the extremely pertinent problem of web crawling, which is far from trivial considering the magnitude and all-pervasive nature of the World-Wide Web. While numerous AI tools can be used to deal with this task, in this paper we map the problem onto the combinatorially-hard stochastic non-linear fractional knapsack problem, which, in turn, is then solved using Learning Automata (LA). Such LA-based solutions have been recently shown to outperform previous state-of-the-art approaches to resource allocation in Web monitoring. However, the ever growing deployment of distributed systems raises the need for solutions that cope with a distributed setting. In this paper, we prese…

A Learning Automata Based Solution to Service Selection in Stochastic Environments

Published version of a paper published in the book: Trends in Applied Intelligent Systems. Also available on SpringerLink: http://dx.doi.org/10.1007/978-3-642-13033-5_22 With the abundance of services available in today’s world, identifying those of high quality is becoming increasingly difficult. Reputation systems can offer generic recommendations by aggregating user provided opinions about service quality, however, are prone to ballot stuffing and badmouthing . In general, unfair ratings may degrade the trustworthiness of reputation systems, and changes in service quality over time render previous ratings unreliable. In this paper, we provide a novel solution to the above problems based …

Generalized Bayesian Pursuit: A Novel Scheme for Multi-Armed Bernoulli Bandit Problems

In the last decades, a myriad of approaches to the multi-armed bandit problem have appeared in several different fields. The current top performing algorithms from the field of Learning Automata reside in the Pursuit family, while UCB-Tuned and the e-greedy class of algorithms can be seen as state-of-the-art regret minimizing algorithms. Recently, however, the Bayesian Learning Automaton (BLA) outperformed all of these, and other schemes, in a wide range of experiments. Although seemingly incompatible, in this paper we integrate the foundational learning principles motivating the design of the BLA, with the principles of the so-called Generalized Pursuit algorithm (GPST), leading to the Gen…

Potential AI Strategies to Solve the Commons Game: A Position Paper

Published version of an article from the book: Advances in Artificial Intelligence : 23rd Canadian Conference on Artificial Intelligence. The original publication is available at Springerlink. http://dx.doi.org/10.1007/978-3-642-13059-5_45 In this paper, we propose the use of hill climbing and particle swarm optimization to find strategies in order to play the Commons Game (CG). The game, which is a non-trivial N-person non-zero-sum game, presents a simple mechanism to formulate how different parties can use shared resources. If the parties cooperate, the resources are sustainable. However, the resources get depleted if used indiscriminately. We consider the case when a single player has to…

On Applying Adaptive Data Structures to Multi-Player Game Playing

In the field of game playing, the focus has been on two-player games, such as Chess and Go, rather than on multi-player games, with dominant multi-player techniques largely being an extension of two-player techniques to an \(N\)-player environment. To address the problem of multiple opponents, we propose the merging of two previously unrelated fields, namely those of multi-player game playing and Adaptive Data Structures (ADS). We present here a novel move-ordering heuristic for a dominant multi-player game playing algorithm, namely the Best-Reply Search (BRS). Our enhancement uses an ADS to rank the opponents in terms of their respective threat levels to the player modeled by the AI algori…

Achieving Fair Load Balancing by Invoking a Learning Automata-Based Two-Time-Scale Separation Paradigm.

Author's accepted manuscript. © 2020 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. 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…

A formal proof of the e-optimality of discretized pursuit algorithms

Learning Automata (LA) can be reckoned to be the founding algorithms on which the field of Reinforcement Learning has been built. Among the families of LA, Estimator Algorithms (EAs) are certainly the fastest, and of these, the family of discretized algorithms are proven to converge even faster than their continuous counterparts. However, it has recently been reported that the previous proofs for ??-optimality for all the reported algorithms for the past three decades have been flawed. We applaud the researchers who discovered this flaw, and who further proceeded to rectify the proof for the Continuous Pursuit Algorithm (CPA). The latter proof examines the monotonicity property of the proba…

Optimal “anti-Bayesian” parametric pattern classification for the exponential family using Order Statistics criteria

Published version of a chapter in the book: Image Analysis and Recognition. Also available from the publisher at: http://dx.doi.org/10.1007/978-3-642-31295-3_2 This paper reports some pioneering results in which optimal parametric classification is achieved in a counter-intuitive manner, quite opposed to the Bayesian paradigm. The paper, which builds on the results of [1], demonstrates (with both theoretical and experimental results) how this can be done for some distributions within the exponential family. To be more specific, within a Bayesian paradigm, if we are allowed to compare the testing sample with only a single point in the feature space from each class, the optimal Bayesian strat…

Semi-supervised classification using tree-based self-organizing maps

Published version of an article from the following onference prodeedings: AI 2011: Advances in Artificial Intelligence. Also available from the publisher on SpringerLink: http://dx.doi.org/10.1007/978-3-642-25832-9_3 This paper presents a classifier which uses a tree-based Neural Network (NN), and uses both, unlabeled and labeled instances. First, we learn the structure of the data distribution in an unsupervised manner. After convergence, and once labeled data become available, our strategy tags each of the clusters according to the evidence provided by the instances. Unlike other neighborhood-based schemes, our classifier uses only a small set of representatives whose cardinality can be m…

“Anti-Bayesian” flat and hierarchical clustering using symmetric quantiloids

A myriad of works has been published for achieving data clustering based on the Bayesian paradigm, where the clustering sometimes resorts to Naive-Bayes decisions. Within the domain of clustering, the Bayesian principle corresponds to assigning the unlabelled samples to the cluster whose mean (or centroid) is the closest. Recently, Oommen and his co-authors have proposed a novel, counter-intuitive and pioneering PR scheme that is radically opposed to the Bayesian principle. The rational for this paradigm, referred to as the “Anti-Bayesian” (AB) paradigm, involves classification based on the non-central quantiles of the distributions. The first-reported work to achieve clustering using the A…

The Hierarchical Continuous Pursuit Learning Automation for Large Numbers of Actions

Part 10: Learning - Intelligence; International audience; Although the field of Learning Automata (LA) has made significant progress in the last four decades, the LA-based methods to tackle problems involving environments with a large number of actions are, in reality, relatively unresolved. The extension of the traditional LA (fixed structure, variable structure, discretized, and pursuit) 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 consequently, most components of the vector will, after a relatively short time, have values that are smal…

The fundamental theory of optimal "Anti-Bayesian" parametric pattern classification using order statistics criteria

Author's version of an article in the journal: Pattern Recognition. Also available from the publisher at: http://dx.doi.org/10.1016/j.patcog.2012.07.004 The gold standard for a classifier is the condition of optimality attained by the Bayesian classifier. Within a Bayesian paradigm, if we are allowed to compare the testing sample with only a single point in the feature space from each class, the optimal Bayesian strategy would be to achieve this based on the (Mahalanobis) distance from the corresponding means. The reader should observe that, in this context, the mean, in one sense, is the most central point in the respective distribution. In this paper, we shall show that we can obtain opti…

On Using “Stochastic Learning on the Line” to Design Novel Distance Estimation Methods for Three-Dimensional Environments

We consider the unsolved problem of Distance Estimation (DE) when the inputs are the x and y coordinates (i.e., the latitudinal and longitudinal positions) of the points under consideration, and the elevation/altitudes of the points specified, for example, in terms of their z coordinates (3DDE). The aim of the problem is to yield an accurate value for the real (road) distance between the points specified by all the three coordinates of the cities in question (This is a typical problem encountered in a GISs and GPSs.). In our setting, the distance between any pair of cities is assumed to be computed by merely having access to the coordinates and known inter-city distances of a small subset o…

Object Migration Automata for Non-equal Partitioning Problems with Known Partition Sizes

Part 4: Automated Machine Learning; International audience; Solving partitioning problems in random environments is a classic and challenging task, and has numerous applications. The existing Object Migration Automaton (OMA) and its proposed enhancements, which include the Pursuit and Transitivity phenomena, can solve problems with equi-sized partitions. Currently, these solutions also include one where the partition sizes possess a Greatest Common Divisor (GCD). In this paper, we propose an OMA-based solution that can solve problems with both equally and non-equally-sized groups, without restrictions on their sizes. More specifically, our proposed approach, referred to as the Partition Siz…

Anomaly detection in dynamic systems using weak estimators

Accepted version of an article from the journal: ACM transactions on internet technology. Published version available from the ACM: http://dx.doi.org/10.1145/1993083.1993086 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…

A Learning-Automata Based Solution for Non-equal Partitioning: Partitions with Common GCD Sizes

The Object Migration Automata (OMA) has been used as a powerful tool to resolve real-life partitioning problems in random Environments. The virgin OMA has also been enhanced by incorporating the latest strategies in Learning Automata (LA), namely the Pursuit and Transitivity phenomena. However, the single major handicap that it possesses is the fact that the number of objects in each partition must be equal. Obviously, one does not always encounter problems with equally-sized groups (When the true underlying problem has non-equally-sized groups, the OMA reports the best equally-sized solution as the recommended partition.). This paper is the pioneering attempt to relax this constraint. It p…

Channel selection in Cognitive Radio Networks: A Switchable Bayesian Learning Automata approach

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. Ther…

Dynamic Ordering of Firewall Rules Using a Novel Swapping Window-based Paradigm

Designing and implementing efficient firewall strategies in the age of the Internet of Things (IoT) is far from trivial. This is because, as time proceeds, an increasing number of devices will be connected, accessed and controlled on the Internet. Additionally, an ever-increasingly amount of sensitive information will be stored on various networks. A good and effi- cient firewall strategy will attempt to secure this information, and to also manage the large amount of inevitable network traffic that these devices create. The goal of this paper is to propose a framework for designing optimized firewalls for the IoT. This paper deals with two fundamental challenges/problems encountered in such…

Pattern classification using a new border identification paradigm: The nearest border technique

Abstract There are many paradigms for pattern classification such as the optimal Bayesian, kernel-based methods, inter-class border identification schemes, nearest neighbor methods, nearest centroid methods, among others. As opposed to these, this paper pioneers a new paradigm, which we shall refer to as the nearest border (NB) paradigm. The philosophy for developing such a NB strategy is as follows: given the training data set for each class, we shall attempt to create borders for each individual class. However, unlike the traditional border identification (BI) methods, we do not undertake this by using inter-class criteria; rather, we attempt to obtain the border for a specific class in t…

On the Online Classification of Data Streams Using Weak Estimators

In this paper, we propose a novel online classifier for complex data streams which are generated from non-stationary stochastic properties. Instead of using a single training model and counters to keep important data statistics, the introduced online classifier scheme provides a real-time self-adjusting learning model. The learning model utilizes the multiplication-based update algorithm of the Stochastic Learning Weak Estimator (SLWE) at each time instant as a new labeled instance arrives. In this way, the data statistics are updated every time a new element is inserted, without requiring that we have to rebuild its model when changes occur in the data distributions. Finally, and most impo…

A novel strategy for solving the stochastic point location problem using a hierarchical searching scheme

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 environme…

Order statistics-based parametric classification for multi-dimensional distributions

Traditionally, in the field of Pattern Recognition (PR), the moments of the class-conditional densities of the respective classes have been used to perform classification. However, the use of phenomena that utilized the properties of the Order Statistics (OS) were not reported. Recently, in [10,8], we proposed a new paradigm named CMOS, Classification by the Moments of Order Statistics, which specifically used these quantifiers. It is fascinating that CMOS is essentially ''anti''-Bayesian in its nature because the classification is performed in a counter-intuitive manner, i.e., by comparing the testing sample to a few samples distant from the mean, as opposed to the Bayesian approach in whi…

On Using the Theory of Regular Functions to Prove the ε-Optimality of the Continuous Pursuit Learning Automaton

Published version of a chapter in the book: Recent Trends in Applied Artificial Intelligence. Also available from the publisher at: http://dx.doi.org/10.1007/978-3-642-38577-3_27 There are various families of Learning Automata (LA) such as Fixed Structure, Variable Structure, Discretized etc. Informally, if the environment is stationary, their ε-optimality is defined as their ability to converge to the optimal action with an arbitrarily large probability, if the learning parameter is sufficiently small/large. Of these LA families, Estimator Algorithms (EAs) are certainly the fastest, and within this family, the set of Pursuit algorithms have been considered to be the pioneering schemes. The…

The Hierarchical Continuous Pursuit Learning Automation: A Novel Scheme for Environments With Large Numbers of Actions.

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 …

Language Detection and Tracking in Multilingual Documents Using Weak Estimators

Published version of an article from the book: Structural, Syntactic, and Statistical Pattern Recognition . The original publication is available at Spingerlink. http://dx.doi.org/DOI: 10.1007/978-3-642-14980-1_59 This paper deals with the extremely complicated problem of language detection and tracking in real-life electronic (for example, in Word-of-Mouth (WoM)) applications, where various segments of the text are written in different languages. 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…

A Novel Multidimensional Scaling Technique for Mapping Word-Of-Mouth Discussions

The techniques which utilize Multidimensional Scaling (MDS) as a fundamental statistical tool have been well developed since the late 1970’s. In this paper we show how anMDS scheme can be enhanced by incorporating into it a Stochastic Point Location (SPL) strategy (one which optimizes the former’s gradient descent learning phase) and a new Stress function. The enhanced method, referred to as MDS SPL, has been used in conjunction with a combination of the TF-IDF and Cosine Similarities on a very noisy Word-Of-Mouth (WoM) discussion set consisting of postings concerning mobile phones, yielding extremely satisfying results.

A Learning Automaton-based Scheme for Scheduling Domestic Shiftable Loads in Smart Grids

In this paper, we consider the problem of scheduling shiftable loads, over multiple users, in smart electrical grids. We approach the problem, which is becoming increasingly pertinent in our present energy-thirsty society, using a novel distributed game-theoretic framework. In our specific instantiation, we consider the scenario when the power system has a local-area Smart Grid subnet comprising of a single power source and multiple customers. The objective of the exercise is to tacitly control the total power consumption of the customers’ shiftable loads, so to approach the rigid power budget determined by the power source, but to simultaneously not exceed this threshold. As opposed to the…

Optimal “anti-Bayesian” parametric pattern classification using Order Statistics criteria

Published version of a chapter in the book: Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications. Also available from the publisher at: http://dx.doi.org/10.1007/978-3-642-33275-3_1 The gold standard for a classifier is the condition of optimality attained by the Bayesian classifier. Within a Bayesian paradigm, if we are allowed to compare the testing sample with only a single point in the feature space from each class, the optimal Bayesian strategy would be to achieve this based on the (Mahalanobis) distance from the corresponding means. The reader should observe that, in this context, the mean, in one sense, is the most central point in the respective distrib…

A novel technique for stochastic root-finding: Enhancing the search with adaptive d-ary search

The most fundamental problem encountered in the field of stochastic optimization, is the Stochastic Root Finding (SRF) problem where the task is to locate an unknown point x∗ for which g(x∗) = 0 for a given function g that can only be observed in the presence of noise [15]. The vast majority of the state-of-the-art solutions to the SRF problem involve the theory of stochastic approximation. The premise of the latter family of algorithms is to oper ate by means of so-called “small-step”processesthat explorethe search space in a conservative manner. Using this paradigm, the point investigated at any time instant is in the proximity of the point investigated at the previous time instant, render…

A Hierarchical Learning Scheme for Solving the Stochastic Point Location Problem

Published version of a chapter in the book: Advanced Research in Applied Artificial Intelligence. Also available from the publisher at: http://dx.doi.org/10.1007/978-3-642-31087-4_78 This paper deals with the Stochastic-Point Location (SPL) problem. It presents a solution which is novel in both philosophy and strategy to all the reported related learning algorithms. The SPL problem concerns the task of a Learning Mechanism attempting to locate a point on a line. The mechanism 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 which also is the current guess. The first pioneering work […

On incorporating the paradigms of discretization and Bayesian estimation to create a new family of pursuit learning automata

Published version of an article in the journal: Applied Intelligence. Also available from the publisher at: http://dx.doi.org/10.1007/s10489-013-0424-x There are currently two fundamental paradigms that have been used to enhance the convergence speed of Learning Automata (LA). The first involves the concept of utilizing the estimates of the reward probabilities, while the second involves discretizing the probability space in which the LA operates. This paper demonstrates how both of these can be simultaneously utilized, and in particular, by using the family of Bayesian estimates that have been proven to have distinct advantages over their maximum likelihood counterparts. The success of LA-…

Ideal Chaotic Pattern Recognition is achievable: The Ideal-M-AdNN - its design and properties

Published version of a chapter in the book: Transactions on Computational Collective Intelligence XI. Also available from the publisher at: http://dx.doi.org/10.1007/978-3-642-41776-4_2 This paper deals with the relatively new field of designing a Chaotic Pattern Recognition (PR) system. The benchmark of such a system is the following: First of all, one must be able to train the system with a set of “training” patterns. Subsequently, as long as there is no testing pattern, the system must be chaotic. However, if the system is, thereafter, presented with an unknown testing pattern, the behavior must ideally be as follows. If the testing pattern is not one of the trained patterns, the system …