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

Extension of Stochastic Point Location for Multimodal Problems

Stochastic point location (SPL) involves a learning mechanism (LM) determining an optimal point on the line when the only inputs LM receives are stochastic information about the direction in which LM should move. The complexity of SPL comes from the stochastic responses of the environment, which may lead LM completely astray. SPL is a fundamental problem in optimization and was studied by many researchers during the last two decades, including improvement of its solution and all-pervasive applications. However, all existing SPL studies assume that the whole search space contains only one optimal point. Since a multimodal optimization problem (MMOP) contains multiple optimal solutions, it is significant to develop SPL's multimodal version. This article extends it from a unimodal problem to a multimodal one and proposes a parallel partition search (PPS) solution to address this issue. The heart of the proposed solution involves extracting the feature of the historical sampling information to distinguish the subintervals that contain the optimal points or not. Specifically, it divides the whole search space into multiple subintervals and samples them parallelly, then utilizes the feature of the historical sampling information to adjust the subintervals adaptively and to find the subintervals containing the optimal points. Finally, the optimal points are located within these subintervals according to their respective sampling statistics. The proof of the ϵ -optimal property for the proposed solution is presented. The numerical testing results demonstrate the power of the scheme.

Weak Estimator-Based Stochastic Searching on the Line in Dynamic Dual Environments

Stochastic point location deals with the problem of finding a target point on a real line through a learning mechanism (LM) with the stochastic environment (SE) offering directional information. The SE can be further categorized into an informative or deceptive one, according to whether p is above 0.5 or not, where p is the probability of providing a correct suggestion of a direction to LM. Several attempts have been made for LM to work in both types of environments, but none of them considers a dynamically changing environment where p varies with time. A dynamic dual environment involves fierce changes that frequently cause its environment to switch from an informative one to a deceptive one, or vice versa. This article presents a novel weak estimator-based adaptive step search solution, to enable LM to track the target in a dynamic dual environment, with the help of a weak estimator. The experimental results show that the proposed solution is feasible and efficient.

Balanced difficulty task finder: an adaptive recommendation method for learning tasks based on the concept of state of flow

An adaptive task difficulty assignment method which we reckon as balanced difficulty task finder (BDTF) is proposed in this paper. The aim is to recommend tasks to a learner using a trade-off between skills of the learner and difficulty of the tasks such that the learner experiences a state of flow during the learning. Flow is a mental state that psychologists refer to when someone is completely immersed in an activity. Flow state is a multidisciplinary field of research and has been studied not only in psychology, but also neuroscience, education, sport, and games. The idea behind this paper is to try to achieve a flow state in a similar way as Elo’s chess skill rating (Glickman in Am Chess J 3:59–102) and TrueSkill (Herbrich et al. in Advances in neural information processing systems, 2006) for matching game players, where “matched players” should possess similar capabilities and skills in order to maintain the level of motivation and involvement in the game. The BDTF draws analogy between choosing an appropriate opponent or appropriate game level and automatically choosing an appropriate difficulty level of a learning task. This method, as an intelligent tutoring system, could be used in a wide range of applications from online learning environments and e-learning, to learning and remembering techniques in traditional methods such as adjusting delayed matching to sample and spaced retrieval training that can be used for people with memory problems such as people with dementia.

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 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 ϵ -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 pursuit-based 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 L_R-I scheme, which is, by all metrics, phenomenal.

Symmetrical Hierarchical Stochastic Searching on the Line in Informative and Deceptive Environments

A stochastic point location (SPL) problem aims to find a target parameter on a 1-D line by operating a controlled random walk and receiving information from a stochastic environment (SE). If the target parameter changes randomly, we call the parameter dynamic; otherwise static. SE can be 1) informative (p > 0.5 where p represents the probability for an environment providing a correct suggestion) and 2) deceptive (p <; 0.5). Up till now, hierarchical stochastic searching on the line (HSSL) is the most efficient algorithms to catch static or dynamic parameter in an informative environment, but unable to locate the target parameter in a deceptive environment and to recognize an environment's type (informative or deceptive). This paper presents a novel solution, named symmetrical HSSL, by extending an HSSL binary tree-based search structure to a symmetrical form. By means of this innovative way, the proposed learning mechanism is able to converge to a static or dynamic target parameter in the range of not only 0.6181 <; p <; 1, but also 0 <; p <; 0.382. Finally, the experimental results show that our scheme is efficient and feasible to solve the SPL problem in any SE.

Novel Discretized Weak Estimators Based on the Principles of the Stochastic Search on the Line Problem

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.

Random Walk-Based Solution to Triple Level Stochastic Point Location Problem

This paper considers the stochastic point location (SPL) problem as a learning mechanism trying to locate a point on a real line via interacting with a random environment. Compared to the stochastic environment in the literatures that confines the learning mechanism to moving in two directions, i.e., left or right, this paper introduces a general triple level stochastic environment which not only tells the learning mechanism to go left or right, but also informs it to stay unmoved. It is easy to understand, as we will prove in this paper, that the environment reported in the previous literatures is just a special case of the triple level environment. And a new learning algorithm, named as random walk-based triple level learning algorithm, is proposed to locate an unknown point under this new type of environment. In order to examine the performance of this algorithm, we divided the triple level SPL problems into four distinguished scenarios by the properties of the unknown point and the stochastic environment, and proved that even under the triple level nonstationary environment and the convergence condition having not being satisfied for some time, which are rarely considered in existing SPL problems, the proposed learning algorithm is still working properly whenever the unknown point is static or evolving with time. Extensive experiments validate our theoretical analyses and demonstrate that the proposed learning algorithms are quite effective and efficient.