Many real-life dynamical systems change abruptly followed by almost stationary periods. In this paper, we consider streams of data with such abrupt behavior and investigate the problem of tracking their statistical properties in an online manner. We devise a tracking procedure where an estimator that is suitable for a stationary environment is combined together with an event detection method such that the estimator rapidly can jump to a more suitable value if an event is detected. Combining an estimation procedure with detection procedure is commonly known idea in the literature. However, our contribution lies in building the detection procedure based on the difference between the stationary estimator and a Stochastic Learning Weak Estimator (SLWE). The SLWE estimator is known to be the state-of-the art approach to tracking properties of non-stationary environments and thus should be a better choice to detect changes in abruptly changing environments than the far more common sliding window based approaches. To the best of our knowledge, the event detection procedure suggested by (2012) is the only procedure in the literature taking advantage of the powerful tracking properties of the SLWE estimator. The procedure in is however quite complex and not well founded theoretically compared to the procedures in this paper. In this paper, we focus on estimation procedure for the binomial and multinomial distributions, but our approach can be easily generalized to cover other distributions as well. Extensive simulation results based on both synthetic and real-life data related to news classification demonstrate that our estimation procedure is easy to tune and performs well.
In this paper, we formally present a novel estimation method, referred to as the Stochastic Learning Weak Estimator (SLWE), which yields the estimate of the parameters of a binomial distribution, where the convergence of the estimate is weak, i.e. with regard to the first and second moments. The estimation is based on the principles of stochastic learning. The mean of the final estimate is independent of the scheme's learning coefficient, @l, and both the variance of the final distribution and the speed decrease with @l. Similar results are true for the multinomial case, except that the equations transform from being of a scalar type to be of a vector type. Amazingly enough, the speed of the latter only depends on the same parameter, @l, which turns out to be the only non-unity eigenvalue of the underlying stochastic matrix that determines the time-dependence of the estimates. An empirical analysis on synthetic data shows the advantages of the scheme for non-stationary distributions. The paper also briefly reports (without detailed explanation) conclusive results that demonstrate the superiority of SLWE in pattern-recognition-based data compression, where the underlying data distribution is non-stationary. Finally, and more importantly, the paper includes the results of two pattern recognition exercises, the first of which involves artificial data, and the second which involves the recognition of the types of data that are present in news reports of the Canadian Broadcasting Corporation (CBC). The superiority of the SLWE in both these cases is demonstrated. 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 discretized so that the updates are done in jumps, and thus the convergence speed is increased. Further, the state transitions are both state-dependent and randomized. As far as we know, such a scheme is both novel and pioneering. The results which have first been proven for binomial distributions have subsequently been extended for the multinomial case, using which they can be applied to any univariate distribution using a histogram-based scheme. The most outstanding and pioneering contribution of our work is that of achieving multinomial estimation without relying on a set of binomial estimators, and where the underlying strategy is truly randomized. Interestingly, the estimator possesses a low computational complexity that is independent of the number of parameters of the multinomial distribution. The generalization of these results for other distributions has also been alluded to. The paper briefly reports conclusive experimental results that prove the ability of the SDWE to cope with non-stationary environments with high adaptation and accuracy. HighlightsWe present finite-memory estimation techniques for non-stationary environments.These new techniques use the principles of discretized Learning Automata.The results have been tested for many time-varying problems and applications. 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 1 distributions. As opposed to the SLWE, our proposed estimator is discretized, 2 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. 1 The extension to multinomial and to other distributions is straightforward. 