Finite state automata representing two-dimensional subshifts

A new type of two-dimensional automaton has been defined to recognize a class of two-dimensional shifts of finite type having the property that every admissible block found within the related local picture language can be extended to a point of the subshift. Here it is shown that this automaton accurately represents the image of the represented two-dimensional shift of finite type under a block code. It is then shown that these automata can be used to check for a certain type of two-dimensional transitivity in the factor language of the corresponding shift space and how this relates to periodicity in the two-dimensional case. The paper closes with a notion of “follower sets” that are used to reduce the size of the automata representing two-dimensional sofic shifts.     

Minimum positive influence dominating set and its application in influence maximization: a learning automata approach

In recent years, with the rapid development of online social networks, an enormous amount of information has been generated and diffused by human interactions through online social networks. The availability of information diffused by users of online social networks has facilitated the investigation of information diffusion and influence maximization. In this paper, we focus on the influence maximization problem in social networks, which refers to the identification of a small subset of target nodes for maximizing the spread of influence under a given diffusion model. We first propose a learning automaton-based algorithm for solving the minimum positive influence dominating set (MPIDS) problem, and then use the MPIDS for influence maximization in online social networks. We also prove that by proper choice of the parameters of the algorithm, the probability of finding the MPIDS can be made as close to unity as possible. Experimental simulations on real and synthetic networks confirm the superiority of the algorithm for finding the MPIDS Experimental results also show that finding initial target seeds for influence maximization using the MPIDS outperforms well-known existing algorithms.     

Finite time analysis of the pursuit algorithm for learning automata

The problem of analyzing the finite time behavior of learning automata is considered. This problem involves the finite time analysis of the learning algorithm used by the learning automaton and is important in determining the rate of convergence of the automaton. In this paper, a general framework for analyzing the finite time behavior of the automaton learning algorithms is proposed. Using this framework, the finite time analysis of the Pursuit Algorithm is presented. We have considered both continuous and discretized forms of the pursuit algorithm. Based on the results of the analysis, we compare the rates of convergence of these two versions of the pursuit algorithm. At the end of the paper, we also compare our framework with that of Probably Approximately Correct (PAC) learning.     

On a family of L languages resulting from systolic tree automata

Recent work on systolic tree automata has given rise to a rather natural subfamily of EOL languages, referred to as systolic EOL languages in this paper. Systolic EOL languages possess some remarkable properties. While their family contains (because of its closure under Boolean operations) intuitively quite complicated languages, it still has decidable equivalence problem. Especially interesting is the fact that similar decision problems for slightly more general families lead to the celebrated open problems concerning Z-rational power series.     

Joint maximization of accuracy and information for learning the structure of a Bayesian network classifier

Machine Learning - Although recent studies have shown that a Bayesian network classifier (BNC) that maximizes the classification accuracy (i.e., minimizes the 0/1 loss function) is a powerful tool...     

Adaptively learning probabilistic deterministic automata from data streams

Markovian models with hidden state are widely-used formalisms for modeling sequential phenomena. Learnability of these models has been well studied when the sample is given in batch mode, and algorithms with PAC-like learning guarantees exist for specific classes of models such as Probabilistic Deterministic Finite Automata (PDFA). Here we focus on PDFA and give an algorithm for inferring models in this class in the restrictive data stream scenario: Unlike existing methods, our algorithm works incrementally and in one pass, uses memory sublinear in the stream length, and processes input items in amortized constant time. We also present extensions of the algorithm that (1) reduce to a minimum the need for guessing parameters of the target distribution and (2) are able to adapt to changes in the input distribution, relearning new models when needed. We provide rigorous PAC-like bounds for all of the above. Our algorithm makes a key usage of stream sketching techniques for reducing memory and processing time, and is modular in that it can use different tests for state equivalence and for change detection in the stream.     

基于规则约束的深度学习网络用于文本信息抽取

针对文本信息抽取中由于训练样本不足导致性能下降的问题,提出一种基于规矩约束的深度学习网络模型.模型分为深度学习模块、逻辑规则库和差异单元3个部分.将文本句子作为输入数据馈送到学习模块中,基于Bi-GRU网络和多头自注意力机制在多个维度上为每个单词生成一个预测向量;规则库采用带权重的逻辑规则对深度学习进行约束;差异单元利用损失函数协调学习模块与规则库之间的一致性.实验结果表明,所提模型比其它算法具有更好的性能,能够高效精确处理复杂文本.     

Spike-timing-dependent plasticity and relevant mutual information maximization

Synaptic plasticity was recently shown to depend on the relative timing of the pre- and postsynaptic spikes. This article analytically derives a spike-dependent learning rule based on the principle of information maximization for a single neuron with spiking inputs. This rule is then transformed into a biologically feasible rule, which is compared to the experimentally observed plasticity. This comparison reveals that the biological rule increases information to a near-optimal level and provides insights into the structure of biological plasticity. It shows that the time dependency of synaptic potentiation should be determined by the synaptic transfer function and membrane leak. Potentiation consists of weight-dependent and weight-independent components whose weights are of the same order of magnitude. It further suggests that synaptic depression should be triggered by rare and relevant inputs but at the same time serves to unlearn the baseline statistics of the network's inputs. The optimal depression curve is uniformly extended in time, but biological constraints that cause the cell to forget past events may lead to a different shape, which is not specified by our current model. The structure of the optimal rule thus suggests a computational account for several temporal characteristics of the biological spike-timing-dependent rules.     

基于CRF和半监督学习的中文时间信息抽取

为提高文本中时间信息识别和抽取的效率,提出一种基于CRF （条件随机场）的方法。根据时间信息表现出的一般特点,采用机器学习的方法,通过分析文本中相关词性、短语结构和上下文信息等,提取时间信息的外部特征,采用一种自训练的半监督方法,使用CRF进行识别和抽取。实验结果表明,该方法有效提升了时间识别的性能,在显性时间、隐性时间和总体时间上分别取得了96?25％、88?65％和93?97％的 F1值。     

Biased sampling from facebook multilayer activity network using learning automata

Although much research has been devoted to unbiased sampling of various networks, bias is not always disadvantageous, but sometimes useful. Especially for many real-world applications such as detecting influential nodes, spam users, and the most trustful people, it is preferred to sample users with special properties. Since sampling from friendship network alone cannot collect these important nodes appropriately, one may use interactions occurred among users. This paper deals with biased sampling of multilayer activity network. The proposed method initially learns the transition probabilities according to the considered application using learning automata. Then we sample the graph by running an application-based random walk following the learnt probabilities, in order to be guided to suitable nodes and collect their information. At last, the performance of the proposed method in terms of different applications such as fame, spam, and trust is evaluated and compared with those of common sampling algorithms. According to the experiments done, biased sampling method based on learning automata outperforms all other sampling approaches including simple random walk, Metropolis-Hastings random walk, BFS, forest fire, degree, and uniform sampling in terms of all the evaluation measures. To the best of our knowledge, our method is the first and only biased sampling method which can be used in a multilayer activity network.     

Extracting state information from a quantized output record

We consider the problem of manipulating the input to a discrete-time state space linear system with the goal of obtaining information at each time about the system's current state from a record of past quantized measurements of the system's output. We find that if the system is not excessively unstable, there exist feedback control strategies that allow one to make an asymtotically perfect determination of the current stage based on the output records that result. Even if the system is too unstable to apply such strategies, there are feedback control laws that make the system's output record more informative about the system's state evolution than one might expect. In deriving these control laws, we regard quantized measurements of real numbers more as partial observations than as strict approximations, and employ techniques from information theory and the theory of Markov chains with countable state spaces.     

A cooperative game of a pair of learning automata

A cooperative game played in a sequential manner by a pair of learning automata is investigated in this paper. The automata operate in an unknown random environment which gives a common pay-off to the automata. Necessary and sufficient conditions on the functions in the reinforcement scheme are given for absolute monotonicity which enables the expected pay-off to be monotonically increasing in any arbitrary environment. As each participating automaton operates with no information regarding the other partner, the results of the paper are relevant to decentralized control.     

Asymptotic behavior of a hierarchical system of learning automata

Learning automata arranged in a two-level hierarchy are considered. The automata operate in a stationary random environment and update their action probabilities according to the linear-reward-ε-penalty algorithm at each level. Unlike some hierarchical systems previously proposed, no information transfer exists from one level to another, and yet the hierarchy possesses good convergence properties. Using weak-convergence concepts it is shown that for large time and small values of parameters in the algorithm, the evolution of the optimal path probability can be represented by a diffusion whose parameters can be computed explicitly.     

Mathematical logic and quantum finite state automata

This paper is a review of the connection between formulas of logic and quantum finite-state automata in respect to the language recognition and acceptance probability of quantum finite-state automata. As is well known, logic has had a great impact on classical computation, it is promising to study the relation between quantum finite-state automata and mathematical logic. After a brief introduction to the connection between classical computation and logic, the required background of the logic and quantum finite-state automata is provided and the results of the connection between quantum finite-state automata and logic are presented.     

Finite automata over a direct product of free semigroups and groups and languages

A finite-automaton-algebraic model of formal languages is described. It is shown how particular cases of this model characterize the classes of recursively enumerable and context-free languages.Translated from Kibernetika, No. 4, pp. 16–20, July–August, 1990.     

Convergence theorems for stochastic automata and learning systems

It is shown that every stochastic automaton generates a semigroup of continuous linear operators in order to give conditions for the convergence of certain operators connected with infinite input sequences. The main results of this note are conditions for the infinitesimal stability of stochastic automata. Since under suitable conditions the behaviour of a learning system can be represented by a stochastic automaton, these results apply to the asymptotic stability of learning.     

Semisupervised learning from different information sources

This paper studies the use of a semisupervised learning algorithm from different information sources. We first offer a theoretical explanation as to why minimising the disagreement between individual models could lead to the performance improvement. Based on the observation, this paper proposes a semisupervised learning approach that attempts to minimise this disagreement by employing a co-updating method and making use of both labeled and unlabeled data. Three experiments to test the effectiveness of the approach are presented in this paper: (i) webpage classification from both content and hyperlinks; (ii) functional classification of gene using gene expression data and phylogenetic data and (iii) machine self-maintaining from both sensory and image data. The results show the effectiveness and efficiency of our approach and suggest its application potentials.     

BNC-VLA: bayesian network structure learning using a team of variable-action set learning automata

Bayesian Network (BN) is a probabilistic graphical model which describes the joint probability distribution over a set of random variables. One of the most important challenges in the field of BNs is to find an optimal network structure based on an available training dataset. Since the problem of searching the optimal BN structure belongs to the class of NP-hard problems, typically greedy algorithms are used to solve it. In this paper a learning automata-based algorithm has been proposed to solve the BNs structure learning problem. There is a learning automaton corresponding with each random variable and at each stage of the proposed algorithm, named BNC-VLA, a set of learning automata is randomly activated and determined the graph edges that must be appeared in that stage. Finally, the constructed network is evaluated using a scoring function. As BNC-VLA algorithm proceeds, the learning process focuses on the BN structure with higher scores. The convergence of this algorithm is theoretically proved; and also some experiments are designed to evaluate the performance of it. Experimental results show that BNC-VLA is capable of finding the optimal structure of BN in an acceptable execution time; and comparing against other search-based methods, it outperforms them.