Learning cellular automata rules for binary classification problem

This paper proposes a cellular automata-based solution of a binary classification problem. The proposed method is based on a two-dimensional, three-state cellular automaton (CA) with the von Neumann neighborhood. Since the number of possible CA rules (potential CA-based classifiers) is huge, searching efficient rules is conducted with use of a genetic algorithm (GA). Experiments show an excellent performance of discovered rules in solving the classification problem. The best found rules perform better than the heuristic CA rule designed by a human and also better than one of the most widely used statistical method: the k-nearest neighbors algorithm (k-NN). Experiments show that CAs rules can be successfully reused in the process of searching new rules.     

Remarks on the cellular automaton global synchronisation problem: deterministic versus stochastic models

In the global synchronisation problem, one is asked to find a cellular automaton which has the property that every initial condition evolves into a homogeneous blinking state. We study this simple inverse problem for the case of one-dimensional systems with periodic boundary conditions. Two paradoxical observations are made: (a) despite the apparent simplicity of finding rules with good statistical results, there exist no perfect deterministic solutions to this problem, (b) if we allow the use of randomness in the local rule, constructing “perfect” stochastic solutions is easy. For the stochastic case, we give some rules for which the mean time of synchronisation varies quadratically with the number of cells and ask if this result can be improved. To explore more deeply the deterministic rules, we code our problem as a SAT problem and use SAT solvers to find rules that synchronise a large set of initial conditions (in appendix).

     

On controlling stochastic sensitivity of oscillatory systems

For a nonlinear oscillatory stochastic system, we study the control problem for the variance of random trajectories around a deterministic cycle. To describe the range of random trajectories, we use the method of stochastic sensitivity functions. We consider the problem of designing a given stochastic sensitivity function, discuss problems of controllability and reachability. Complete stochastic controllability is only possible when the control’s dimension coincides with the system’s dimension. Otherwise, the design problem becomes ill-posed. To solve it, we propose a regularization method that lets us produce a given stochastic sensitivity function with any given precision. The efficiency of the proposed approach is demonstrated with the example of controlling stochastic oscillations in a brusselator model.     

一种规则集快速压缩算法

实际应用中的规则集表现出很强的聚集特性,针对这一特性提出一种规则集快速压缩算法.快速压缩算法是一个由粗到细的先分类再合并压缩的过程,首先通过使用Hash函数将提取的规则信息散列并以散列值作为查找关键字构建二叉查找树实现粗略分类,然后在树结点对应的Hash函数冲突列表中逐条比较完成精确分类,最后合并冲突列表中的规则实现压缩.实验结果表明,与逐条规则逐个域比较的简单压缩方法相比,快速压缩算法在保持较高压缩率的前提下,能够将压缩时间平均减少90%以上.     

考虑客户分类的随机时间车辆路径优化模型与算法

针对一类考虑客户分类、随机旅行时间、随机服务时间及时间窗约束的车辆路径问题构建了机会约束规划模型,该模型考虑两类客户（普通客户与优质客户）并通过添加机会约束条件确保优质客户获得准时服务的概率。同时,设计了变邻域迭代局部搜索算法,并给出了一种基于最小等待时间的初始解生成启发式规则。基于Solomon算例进行了多组仿真实验。仿真实验结果表明,所设计生成初始解的启发式规则是有效的;所给算法能够在短时间内找到确定问题和随机问题的近似最优解;客户比与车辆使用数目呈正相关关系。研究结果对解决资源有限条件下克服随机不确定性因素带来的不利影响、保证客户服务水平等问题有一定的参考意义。     

Performance evaluation of fuzzy rule-based classification systems obtained by multi-objective genetic algorithms

In this paper, we examine the classification performance of fuzzy if-then rules selected by a GA-based multi-objective rule selection method. This rule selection method can be applied to high-dimensional pattern classification problems with many continuous attributes by restricting the number of antecedent conditions of each candidate fuzzy if-then rule. As candidate rules, we only use fuzzy if-then rules with a small number of antecedent conditions. Thus it is easy for human users to understand each rule selected by our method. Our rule selection method has two objectives: to minimize the number of selected fuzzy if-then rules and to maximize the number of correctly classified patterns. In our multi-objective fuzzy rule selection problem, there exist several solutions (i.e., several rule sets) called “non-dominated solutions” because two conflicting objectives are considered. In this paper, we examine the performance of our GA-based rule selection method by computer simulations on a real-world pattern classification problem with many continuous attributes. First we examine the classification performance of our method for training patterns by computer simulations. Next we examine the generalization ability for test patterns. We show that a fuzzy rule-based classification system with an appropriate number of rules has high generalization ability.     

Mining optimized gain rules for numeric attributes

Association rules are useful for determining correlations between attributes of a relation and have applications in the marketing, financial, and retail sectors. Furthermore, optimized association rules are an effective way to focus on the most interesting characteristics involving certain attributes. Optimized association rules are permitted to contain uninstantiated attributes and the problem is to determine instantiations such that either the support, confidence, or gain of the rule is maximized. In this paper, we generalize the optimized gain association rule problem by permitting rules to contain disjunctions over uninstantiated numeric attributes. Our generalized association rules enable us to extract more useful information about seasonal and local patterns involving the uninstantiated attribute. For rules containing a single numeric attribute, we present an algorithm with linear complexity for computing optimized gain rules. Furthermore, we propose a bucketing technique that can result in a significant reduction in input size by coalescing contiguous values without sacrificing optimality. We also present an approximation algorithm based on dynamic programming for two numeric attributes. Using recent results on binary space partitioning trees, we show that the approximations are within a constant factor of the optimal optimized gain rules. Our experimental results with synthetic data sets for a single numeric attribute demonstrate that our algorithm scales up linearly with the attribute's domain size as well as the number of disjunctions. In addition, we show that applying our optimized rule framework to a population survey real-life data set enables us to discover interesting underlying correlations among the attributes.     

A cryptographic and coding-theoretic perspective on the global rules of cellular automata

Cellular Automata (CA) have widely been studied to design cryptographic primitives such as stream ciphers and pseudorandom number generators, focusing in particular on the properties of the underlying local rules. On the other hand, there have been comparatively fewer works concerning the applications of CA to the design of S-boxes and block ciphers, a task that calls for a study of CA global rules in terms of vectorial boolean functions. The aim of this paper is to analyze some of the most basic cryptographic criteria of the global rules of CA. We start by observing that the algebraic degree of a CA global rule equals the degree of its local rule. Then, we characterize the Walsh spectrum of CA induced by permutive local rules, from which we derive a formula for the nonlinearity of such CA. Additionally, we prove that the 1-resiliency property of bipermutive local rules transfers to the corresponding global rules. This result leads us to consider CA global rules from a coding-theoretic point of view: in particular, we show that linear CA are equivalent to linear cyclic codes, observing that the syndrome computation process corresponds to the application of the CA global rule, while the error-correction capability of the code is related to the resiliency order of the global rule.     

Stochastic control of two partially observed competing queues

We consider the dynamic control of two queues competing for the services of one server. The problem is to design a server time allocation strategy, when the sizes of the queues are not observable. The performance criterion used is total expected aggregate delay. The server is assumed to observe arrivals but not departures. This problem is formulated as a stochastic optimal control problem with partial observations. The framework we adopt is that of stochastic control in discrete time and countable "state space." The observations are modeled as discrete time, 0-1 point processes with rates that are influenced by a Markov chain. Examples from computer control of urban traffic are given, to illustrate the practical motivation behind the present work, and to relate to earlier work by us on the subject. A particular feature of the formulation is that the observations are influenced by transitions of the state of the Markov chain. The classical tools of simple Bayes rule and dynamic programming suffice for the analysis. In particular, we show that the "one step" predicted density for the state of the Markov chain, given the point process observations is a sufficient statistic for control. This framework is then applied to the specific problem of two queues competing for the services of one server. We obtain explicit solutions for the finite time expected aggregate delay problem. The implications of these results for practical applications as well as implementation aspects of the resulting optimal control laws are discussed.     

一种新型随机二进制神经网络

二进制数据表示具有简洁高效的特点,随机噪声有助于系统摆脱局部极小.新型的随 机神经网络模型采用随机加权联接,内部数据表示为随机二进制序列形式,实现十分高效.文中 分别就前馈型网络和反馈型网络进行了深入的讨论,给出了前馈型网络的梯度下降学习算法, 为反馈型网络设计了快速有效的模拟退火算法和渐进式Boltzmann学习算法.通过对PARITY 问题的测试,发现了新模型的一些有趣特征,实验结果表明梯度下降学习效果显著.利用渐进式 Boltzmann学习,反馈型网络被成功地用于带噪声人脸识别.     

Monotonic walks on a necklace and a coloured dynamic vector

Stochastic and deterministic versions of a discrete dynamical system on a necklace are investigated. This network consists of a sequence of contours NSWE with nodes, i.e. the nodes are common points at W and E. There are two cells and a particle on each contour. Each time instance, the particle occupies a cell and, at every time unit, comes to the next cell in the same direction. The particles of the neighbouring contours move in accordance with rules of stochastic or deterministic type. The behaviour of the model with the rule of the first type is stochastic only at the beginning and after a time interval becomes a pure deterministic system. The system with the second rule comes to a steady mode, which depends on the initial state. The average velocity of particles and characteristics of the system are studied.     

On multivariate binary data clustering and feature weighting

This paper presents an approach that partitions data sets of unlabeled binary vectors without a priori information about the number of clusters or the saliency of the features. The unsupervised binary feature selection problem is approached using finite mixture models of multivariate Bernoulli distributions. Using stochastic complexity, the proposed model determines simultaneously the number of clusters in a given data set composed of binary vectors and the saliency of the features used. We conduct different applications involving real data, document classification and images categorization to show the merits of the proposed approach.     

Efficient query processing for a subset of linear recursive binaryrules

We study the complexity of processing a class of rules called simple binary rule sets. The data referenced by the rules are stored in secondary memory. A necessary and sufficient condition that a simple binary rule set can be processed in a single pass of a file containing the base relations is given. Because not all simple binary rule sets can be processed in a single pass, a necessary and sufficient condition that a simple binary rule set can be processed by a constant number of passes is also given     

Development of a stochastic optimization for multireservoir scheduling

Seasonal reservoir scheduling for multireservoir hydrothermal power systems is a practical, nonlinear, stochastic problem of high dimension. Extension of an existing deterministic algorithm to handle stochastic aspects is desirable. A linear feedback rule, but with chance constraints on lower limits only, gives some promising results. Exact solution by stochastic dynamic programming is possible only for a one-reservoir model. This result is compared to the deterministic and linear feedback solutions.     

Classification based on association rules: A lattice-based approach

Classification plays an important role in decision support systems. A lot of methods for mining classification rules have been developed in recent years, such as C4.5 and ILA. These methods are, however, based on heuristics and greedy approaches to generate rule sets that are either too general or too overfitting for a given dataset. They thus often yield high error ratios. Recently, a new method for classification from data mining, called the Classification Based on Associations (CBA), has been proposed for mining class-association rules (CARs). This method has more advantages than the heuristic and greedy methods in that the former could easily remove noise, and the accuracy is thus higher. It can additionally generate a rule set that is more complete than C4.5 and ILA. One of the weaknesses of mining CARs is that it consumes more time than C4.5 and ILA because it has to check its generated rule with the set of the other rules. We thus propose an efficient pruning approach to build a classifier quickly. Firstly, we design a lattice structure and propose an algorithm for fast mining CARs using this lattice. Secondly, we develop some theorems and propose an algorithm for pruning redundant rules quickly based on these theorems. Experimental results also show that the proposed approach is more efficient than those used previously.     

CARR: a scalable solution for network packet classification

Modern Internet routers have to handle a large number of packet classification rules, which requires classification schemes to be scalable both in time and space. In this paper, we present a scalable packet classification algorithm that is developed by combining two new concepts to the well‐known bit vector (BV) scheme. We propose a range search method based on a cache‐aware tree (CATree) which makes full use of processor's cache line to reduce the number of dynamic random access memory (DRAM) accesses. Theoretically, the number of DRAM accesses of CATree is about log(m+1) times lower than that of the widely used binary search algorithm, where m is the number of keys in a single cache line. Based on our computational results on a set of 1024 keys, the CATree algorithm is 36% faster than binary search algorithm and the performance is better when applied to a larger set of keys. In addition, we develop a rule re‐arrangement algorithm to reduce the bitmap space of BV. With this re‐arrangement, the rules for the same action may be assigned an identical priority. This reduces the number of priorities as well as the memory space of the bitmap. Furthermore, this also reduces the number of memory accesses and hence, increases the CPU cache utilization. With CATree and rule re‐arrangement, the cache‐aware bit vector with rule re‐arrangement algorithm achieves better performance in comparison with the regular BV scheme, both in space and time. In our experiments, the proposed algorithm reduces the bitmap memory space of a practical set of firewall rules by two orders of magnitude and is 91% faster than the regular BV.     

Modelling IEEE 802.11 CSMA/CA RTS/CTS with stochastic bigraphs with sharing

Stochastic bigraphical reactive systems (SBRS) is a recent formalism for modelling systems that evolve in time and space. However, the underlying spatial model is based on sets of trees and thus cannot represent spatial locations that are shared among several entities in a simple or intuitive way. We adopt an extension of the formalism, SBRS with sharing, in which the topology is modelled by a directed acyclic graph structure. We give an overview of SBRS with sharing, we extend it with rule priorities, and then use it to develop a model of the 802.11 CSMA/CA RTS/CTS protocol with exponential backoff, for an arbitrary network topology with possibly overlapping signals. The model uses sharing to model overlapping connectedness areas, instantaneous prioritised rules for deterministic computations, and stochastic rules with exponential reaction rates to model constant and uniformly distributed timeouts and constant transmission times. Equivalence classes of model states modulo instantaneous reactions yield states in a CTMC that can be analysed using the model checker PRISM. We illustrate the model on a simple example wireless network with three overlapping signals and we present some example quantitative properties.     

Adaptive management of natural systems using fuzzy logic

Hypotheses about how management practices influence ecosystem services can be tested using a crisp, probability-based, or fuzzy decision rule. The correct decision rule depends on whether: (1) the observed state of an ecosystem service (x) is non-stochastic or stochastic; (2) the true state of the ecosystem service (y) is non-stochastic or stochastic; and (3) the relationship between x and y is deterministic, stochastic, or uncertain. Crisp and probability-based decision rules are not appropriate when the relationship between y and x is uncertain in the sense that the decision maker is unable or unwilling to specify conditional probabilities of y given x. Under these conditions, a fuzzy decision rule is appropriate. A hypothetical case study is used to illustrate how a fuzzy decision rule is used to test hypotheses about whether selective cutting of timber provides greater or less forest biodiversity than clearcutting of timber. The case study describes how to incorporate the decision rule in an active adaptive management framework to sequentially test the extent to which changes over time in other factors influencing ecosystem services, such as greater spread of invasive species due to global warming, alter the efficacy of timber management practices. The fuzzy adaptive management decision rule can be generalized to account for the effects of management practices on multiple ecosystem services.