An Adaptive Strategy via Reinforcement Learning for the Prisoner's Dilemma Game

The iterated prisoner's dilemma (IPD) is an ideal model for analyzing interactions between agents in complex networks. It has attracted wide interest in the development of novel strategies since the success of tit-for-tat in Axelrod's tournament. This paper studies a new adaptive strategy of IPD in different complex networks, where agents can learn and adapt their strategies through reinforcement learning method. A temporal difference learning method is applied for designing the adaptive strategy to optimize the decision making process of the agents. Previous studies indicated that mutual cooperation is hard to emerge in the IPD. Therefore, three examples which based on square lattice network and scale-free network are provided to show two features of the adaptive strategy. First, the mutual cooperation can be achieved by the group with adaptive agents under scale-free network, and once evolution has converged mutual cooperation, it is unlikely to shift. Secondly, the adaptive strategy can earn a better payoff compared with other strategies in the square network. The analytical properties are discussed for verifying evolutionary stability of the adaptive strategy.      

Fingerprint indexing with bad quality areas

Fingerprint indexing is a key technique in fingerprint identification systems. This strategy allows us to reduce the search space and the occurrences of false acceptance in databases with great size. This paper presents a new triplet based indexing algorithm which uses a new fingerprint representation, based on minutia triplets. This representation is an extension of the triangle set obtained from Delaunay triangulation. Also, a strategy is proposed in order to dismiss bad quality triplets that could affect the accuracy of the indexing process. This proposal shows a good accuracy, even when the fingerprints have bad quality areas.     

Speciation as automatic categorical modularization

Many natural and artificial systems use a modular approach to reduce the complexity of a set of subtasks while solving the overall problem satisfactorily. There are two distinct ways to do this. In functional modularization, the components perform very different tasks, such as subroutines of a large software project. In categorical modularization, the components perform different versions of basically the same task, such as antibodies in the immune system. This second aspect is the more natural for acquiring strategies in games of conflict, An evolutionary learning system is presented which follows this second approach to automatically create a repertoire of specialist strategies for a game-playing system. This relieves the human effort of deciding how to divide and specialize. The genetic algorithm speciation method used is one based on fitness sharing. The learning task is to play the iterated prisoner's dilemma. The learning system outperforms the tit-for-tat strategy against unseen test opponents. It learns using a “black box” simulation, with minimal prior knowledge of the learning task     

Wi-Fi fingerprinting based on collaborative confidence level training

Wi-Fi fingerprinting has been a popular indoor positioning technique with the advantage that infrastructures are readily available in most urban areas. However wireless signals are prone to fluctuation and noise, introducing errors in the final positioning result. This paper proposes a new fingerprint training method where a number of users train collaboratively and a confidence factor is generated for each fingerprint. Fingerprinting is carried out where potential fingerprints are extracted based on the confidence factor. Positioning accuracy improves by 40% when the new fingerprinting method is implemented and maximum error is reduced by 35%.     

基于隐马尔可夫模型的指纹分类研究

指纹分类是针对大型指纹库的一个重要的索引方式，可以有效地提高指纹匹配的效率．指纹类型的不同表现为指纹纹理结构的差异，而指纹的方向场则可以有效地描述纹理结构的差异．同一类型指纹不同区域上方向角结构的差异以及相邻区域间方向角结构的联系可以视作一个马尔可夫随机场．本文利用嵌入式隐马尔可夫模型对指纹方向场进行建模分析，通过合理地抽取指纹的类型特征，构造观察向量、进行建模训练，然后利用训练好的马尔可夫模型进行匹配，最终提出并实现了一种新的鲁棒性强且精度较高的指纹分类方法．     

Finite-state dimension

Classical Hausdorff dimension (sometimes called fractal dimension) was recently effectivized using gales (betting strategies that generalize martingales), thereby endowing various complexity classes with dimension structure and also defining the constructive dimensions of individual binary (infinite) sequences. In this paper we use gales computed by multi-account finite-state gamblers to develop the finite-state dimensions of sets of binary sequences and individual binary sequences. The theorem of Eggleston (Quart. J. Math. Oxford Ser. 20 (1949) 31–36) relating Hausdorff dimension to entropy is shown to hold for finite-state dimension, both in the space of all sequences and in the space of all rational sequences (binary expansions of rational numbers). Every rational sequence has finite-state dimension 0, but every rational number in [0,1] is the finite-state dimension of a sequence in the low-level complexity class AC₀. Our main theorem shows that the finite-state dimension of a sequence is precisely the infimum of all compression ratios achievable on the sequence by information-lossless finite-state compressors.     

Minimization of mealy finite-state machines by internal states gluing

A problem of minimization of Mealy finite-state machines that is common in synthesizing digital devices on programmable logic devices is considered. The proposed approach uses an operation of gluing two states and represents the finite-state machine as a list of transitions. Cases when gluing two states generates wait states are described. Algorithms that minimize the number of internal states, the number of transitions and input variables of Mealy finite-state machines are given. The experimental results showed that when used to implement finite-state machines on programmable logic devices, the proposed method helps decrease the implementation cost 1.31 times on average and 3 times at best. Topical directions for further study of finite-state machines minimization methods are given.     

Fingerprint classification by directional image partitioning

In this work, we introduce a new approach to automatic fingerprint classification. The directional image is partitioned into “homogeneous” connected regions according to the fingerprint topology, thus giving a synthetic representation which can be exploited as a basis for the classification. A set of dynamic masks, together with an optimization criterion, are used to guide the partitioning. The adaptation of the masks produces a numerical vector representing each fingerprint as a multidimensional point, which can be conceived as a continuous classification. Different search strategies are discussed to efficiently retrieve fingerprints both with continuous and exclusive classification. Experimental results have been given for the most commonly used fingerprint databases and the new method has been compared with other approaches known in the literature: As to fingerprint retrieval based on continuous classification, our method gives the best performance and exhibits a very high robustness     

Environmentally realistic fingerprint-image generation with evolutionary filter-bank optimization

Constructing a fingerprint database is important to evaluate the performance of an automatic fingerprint recognition system. Because of the difficulty of collecting samples, there are only few benchmark databases available. Moreover, it is hard to evaluate how robust the system is against various environments with those databases. This paper presents a novel method that generates fingerprint images automatically from only a few training samples by using the evolutionary algorithm. Fingerprints generated by the proposed method include similar characteristics of those collected from the corresponding real environment. The proposed method has been verified by comparing with real fingerprints, indicating the usefulness of the method.     

针对深度神经网络模型指纹检测的逃避算法

随着深度神经网络在不同领域的成功应用,模型的知识产权保护成为了一个备受关注的问题.由于深度神经网络的训练需要大量计算资源、人力成本和时间成本,攻击者通过窃取目标模型参数,可低成本地构建本地替代模型.为保护模型所有者的知识产权,最近提出的模型指纹比对方法,利用模型决策边界附近的指纹样本及其指纹查验模型是否被窃取,具有不影响模型自身性能的优点.针对这类基于模型指纹的保护策略,提出了一种逃避算法,可以成功绕开这类保护策略,揭示了模型指纹保护的脆弱性.该逃避算法的核心是设计了一个指纹样本检测器——Fingerprint-GAN.利用生成对抗网络(generative adversarial network,GAN)原理,学习正常样本在隐空间的特征表示及其分布,根据指纹样本与正常样本在隐空间中特征表示的差异性,检测到指纹样本,并向目标模型所有者返回有别于预测的标签,使模型所有者的指纹比对方法失效.最后通过CIFAR-10,CIFAR-100数据集评估了逃避算法的性能,实验结果表明:算法对指纹样本的检测率分别可达95%和94%,而模型所有者的指纹比对成功率最高仅为19%,证明了模型指纹比对保护方法的不可靠性.     

Extracting finite-state representations from recurrent neuralnetworks trained on chaotic symbolic sequences

Concerns neural-based modeling of symbolic chaotic time series. We investigate the knowledge induction process associated with training recurrent mural nets (RNN) on single long chaotic symbolic sequences. Even though training RNN to predict the next symbol leaves the standard performance measures such as the mean square error on the network output virtually unchanged, the nets extract a lot of knowledge. We monitor the knowledge extraction process by considering the nets stochastic sources and letting them generate sequences which are then confronted with the training sequence via information theoretic entropy and cross-entropy measures. We also study the possibility of reformulating the knowledge gained by RNN in a compact easy-to-analyze form of finite-state stochastic machines. The experiments are performed on two sequences with different complexities measured by the size and state transition structure of the induced Crutchfield's epsilon-machines (1991, 1994). The extracted machines can achieve comparable or even better entropy and cross-entropy performance. They reflect the training sequence complexity in their dynamical state representations that can be reformulated using finite-state means. The findings are confirmed by a much more detailed analysis of model generated sequences. We also introduce a visual representation of allowed block structure in the studied sequences that allows for an illustrative insight into both RNN training and finite-state stochastic machine extraction processes.     

Equivalence of rational representations of behaviors

This article deals with the equivalence of representations of behaviors of linear differential systems. In general, the behavior of a given linear differential system has many different representations. In this paper we restrict ourselves to kernel and image representations. Two kernel representations are called equivalent if they represent one and the same behavior. For kernel representations defined by polynomial matrices, necessary and sufficient conditions for equivalence are well known. In this paper, we deal with the equivalence of rational representations, i. e. kernel and image representations that are defined in terms of rational matrices. As the first main result of this paper, we will derive a new condition for the equivalence of rational kernel representations of possibly noncontrollable behaviors. Secondly we will derive conditions for the equivalence of rational representations of a given behavior in terms of the polynomial modules generated by the rows of the rational matrices. We will also establish conditions for the equivalence of rational image representations. Finally, we will derive conditions under which a given rational kernel representation is equivalent to a given rational image representation.     

On the individuality of fingerprints

Fingerprint identification is based on two basic premises: (1) persistence and (2) individuality. We address the problem of fingerprint individuality by quantifying the amount of information available in minutiae features to establish a correspondence between two fingerprint images. We derive an expression which estimates the probability of a false correspondence between minutiae-based representations from two arbitrary fingerprints belonging to different fingers. Our results show that (1) contrary to the popular belief, fingerprint matching is not infallible and leads to some false associations, (2) while there is an overwhelming amount of discriminatory information present in the fingerprints, the strength of the evidence degrades drastically with noise in the sensed fingerprint images, (3) the performance of the state-of-the-art automatic fingerprint matchers is not even close to the theoretical limit, and (4) because automatic fingerprint verification systems based on minutia use only a part of the discriminatory information present in the fingerprints, it may be desirable to explore additional complementary representations of fingerprints for automatic matching.     

A novel hierarchical fingerprint matching approach

Fingerprint matching is an important and essential step in automated fingerprint recognition systems (AFRSs). The noise and distortion of captured fingerprints and the inaccurate of extracted features make fingerprint matching a very difficult problem. With the advent of high-resolution fingerprint imaging techniques and the increasing demand for high security, sweat pores have been recently attracting increasing attention in automatic fingerprint recognition. Therefore, this paper takes fingerprint pore matching as an example to show the robustness of our proposed matching method to the errors caused by the fingerprint representation. This method directly matches pores in fingerprints by adopting a coarse-to-fine strategy. In the coarse matching step, a tangent distance and sparse representation-based matching method (denoted as TD-Sparse) is proposed to compare pores in the template and test fingerprint images and establish one-to-many pore correspondences between them. The proposed TD-Sparse method is robust to noise and distortions in fingerprint images. In the fine matching step, false pore correspondences are further excluded by a weighted RANdom SAmple Consensus (WRANSAC) algorithm in which the weights of pore correspondences are determined based on the dis-similarity between the pores in the correspondences. The experimental results on two databases of high-resolution fingerprints demonstrate that the proposed method can achieve much higher recognition accuracy compared with other state-of-the-art pore matching methods.     

Stable encoding of finite-state machines in discrete-time recurrent neural nets with sigmoid units

There has been a lot of interest in the use of discrete-time recurrent neural nets (DTRNN) to learn finite-state tasks, with interesting results regarding the induction of simple finite-state machines from input-output strings. Parallel work has studied the computational power of DTRNN in connection with finite-state computation. This article describes a simple strategy to devise stable encodings of finite-state machines in computationally capable discrete-time recurrent neural architectures with sigmoid units and gives a detailed presentation on how this strategy may be applied to encode a general class of finite-state machines in a variety of commonly used first- and second-order recurrent neural networks. Unlike previous work that either imposed some restrictions to state values or used a detailed analysis based on fixed-point attractors, our approach applies to any positive, bounded, strictly growing, continuous activation function and uses simple bounding criteria based on a study of the conditions under which a proposed encoding scheme guarantees that the DTRNN is actually behaving as a finite-state machine.     

指纹图像多尺度分类字典稀疏增强

目的 自动指纹识别系统大多是基于细节点匹配的,系统性能依赖于输入指纹质量。输入指纹质量差是目前自动指纹识别系统面临的主要问题。为了提高系统性能,实现对低质量指纹的增强,提出了一种基于多尺度分类字典稀疏表示的指纹增强方法。方法 首先,构建高质量指纹训练样本集,基于高质量训练样本学习得到多尺度分类字典;其次,使用线性对比度拉伸方法对指纹图像进行预增强,得到预增强指纹;然后,在空域对预增强指纹进行分块,基于块内点方向一致性对块质量进行评价和分级;最后,在频域构建基于分类字典稀疏表示的指纹块频谱增强模型,基于块质量分级机制和复合窗口策略,结合频谱扩散,基于多尺度分类字典对块频谱进行增强。结果 在指纹数据库FVC2004上将提出算法与两种传统指纹增强算法进行了对比实验。可视化和量化实验结果均表明,相比于传统指纹增强算法,提出的方法具有更好的鲁棒性,能有效改善低质量输入指纹质量。结论 通过将指纹脊线模式先验引入分类字典学习,为拥有不同方向类别的指纹块分别学习一个更为可靠的字典,使得学习到的分类字典拥有更可靠的脊线模式信息。块质量分级机制和复合窗口策略不仅有助于频谱扩散,改善低质量块的频谱质量,而且使得多尺度分类字典能够成功应用,克服了增强准确性和抗噪性之间的矛盾,使得块增强结果更具稳定性和可靠性,显著提升了低质量指纹图像的增强质量。     

Combining multiple matchers for a high security fingerprint verification system

Integration of various fingerprint matching algorithms is a viable method to improve the performance of a fingerprint verification system. Different fingerprint matching algorithms are often based on different representations of the input fingerprints and hence complement each other. We use the logistic transform to integrate the output scores from three different fingerprint matching algorithms. Experiments conducted on a large fingerprint database confirm the effectiveness of the proposed integration scheme.     

Combining flat and structured representations for fingerprint classification with recursive neural networks and support vector machines

We present new fingerprint classification algorithms based on two machine learning approaches: support vector machines (SVMs) and recursive neural networks (RNNs). RNNs are trained on a structured representation of the fingerprint image. They are also used to extract a set of distributed features of the fingerprint which can be integrated in the SVM. SVMs are combined with a new error-correcting code scheme. This approach has two main advantages: (a) It can tolerate the presence of ambiguous fingerprint images in the training set and (b) it can effectively identify the most difficult fingerprint images in the test set. By rejecting these images the accuracy of the system improves significantly. We report experiments on the fingerprint database NIST-4. Our best classification accuracy is of 95.6 percent at 20 percent rejection rate and is obtained by training SVMs on both FingerCode and RNN-extracted features. This result indicates the benefit of integrating global and structured representations and suggests that SVMs are a promising approach for fingerprint classification.     

Deep learning compact binary codes for fingerprint indexing

With the rapid growth in fingerprint databases, it has become necessary to develop excellent fingerprint indexing to achieve efficiency and accuracy. Fingerprint indexing has been widely studied with real-valued features, but few studies focus on binary feature representation, which is more suitable to identify fingerprints efficiently in large-scale fingerprint databases. In this study, we propose a deep compact binary minutia cylinder code (DCBMCC) as an effective and discriminative feature representation for fingerprint indexing. Specifically, the minutia cylinder code (MCC), as the state-of-the-art fingerprint representation, is analyzed and its shortcomings are revealed. Accordingly, we propose a novel fingerprint indexing method based on deep neural networks to learn DCBMCC. Our novel network restricts the penultimate layer to directly output binary codes. Moreover, we incorporate independence, balance, quantization-loss-minimum, and similarity-preservation properties in this learning process. Eventually, a multi-index hashing (MIH) based fingerprint indexing scheme further speeds up the exact search in the Hamming space by building multiple hash tables on binary code substrings. Furthermore, numerous experiments on public databases show that the proposed approach is an outstanding fingerprint indexing method since it has an extremely small error rate with a very low penetration rate.     

A combination fingerprint classifier

Fingerprint classification is an important indexing method for any large scale fingerprint recognition system or database as a method for reducing the number of fingerprints that need to be searched when looking for a matching print. Fingerprints are generally classified into broad categories based on global characteristics. This paper describes novel methods of classification using hidden Markov models and decision trees to recognize the ridge structure of the print, without needing to detect singular points. The methods are compared and combined with a standard fingerprint classification algorithm and results for the combination are presented using a standard database of fingerprint images. The paper also describes a method for achieving any level of accuracy required of the system by sacrificing the efficiency of the classifier. The accuracy of the combination classifier is shown to be higher than that of the two state-of-the-art systems tested under the same conditions