Feature selection via sensitivity analysis of SVM probabilistic outputs

Feature selection is an important aspect of solving data-mining and machine-learning problems. This paper proposes a feature-selection method for the Support Vector Machine (SVM) learning. Like most feature-selection methods, the proposed method ranks all features in decreasing order of importance so that more relevant features can be identified. It uses a novel criterion based on the probabilistic outputs of SVM. This criterion, termed Feature-based Sensitivity of Posterior Probabilities (FSPP), evaluates the importance of a specific feature by computing the aggregate value, over the feature space, of the absolute difference of the probabilistic outputs of SVM with and without the feature. The exact form of this criterion is not easily computable and approximation is needed. Four approximations, FSPP1-FSPP4, are proposed for this purpose. The first two approximations evaluate the criterion by randomly permuting the values of the feature among samples of the training data. They differ in their choices of the mapping function from standard SVM output to its probabilistic output: FSPP1 uses a simple threshold function while FSPP2 uses a sigmoid function. The second two directly approximate the criterion but differ in the smoothness assumptions of criterion with respect to the features. The performance of these approximations, used in an overall feature-selection scheme, is then evaluated on various artificial problems and real-world problems, including datasets from the recent Neural Information Processing Systems (NIPS) feature selection competition. FSPP1-3 show good performance consistently with FSPP2 being the best overall by a slight margin. The performance of FSPP2 is competitive with some of the best performing feature-selection methods in the literature on the datasets that we have tested. Its associated computations are modest and hence it is suitable as a feature-selection method for SVM applications. Editor: Risto Miikkulainen.     

Theory and implementation of path planning by negotiation for decentralized agents

This paper presents a cooperative decentralized path-planning algorithm for a group of autonomous agents that provides guaranteed collision-free trajectories in real-time. The algorithm is robust with respect to arbitrary delays in the wireless traffic, possible sources being transmission time and error correction. Agents move on reserved areas which are guaranteed not to intersect, therefore ensuring safety. A handshaking procedure guarantees recent information states for the agents. Conflicts between agents are resolved by a cost-based negotiation process. The basic algorithm is augmented by the introduction of waypoints, which increase performance at the cost of additional wireless traffic. An implementation of the algorithm is tested in simulation and successfully applied to a real system of autonomous robots. The results are presented and discussed.     

A constant-time dynamic storage allocator for real-time systems

Dynamic memory allocation has been used for decades. However, it has seldom been used in real-time systems since the worst case of spatial and temporal requirements for allocation and deallocation operations is either unbounded or bounded but with a very large bound. In this paper, a new allocator called TLSF (Two Level Segregated Fit) is presented. TLSF is designed and implemented to accommodate real-time constraints. The proposed allocator exhibits time-bounded behaviour, O(1), and maintains a very good execution time. This paper describes in detail the data structures and functions provided by TLSF. We also compare TLSF with a representative set of allocators regarding their temporal cost and fragmentation. Although the paper is mainly focused on timing analysis, a brief study and comparative analysis of fragmentation incurred by the allocators has been also included in order to provide a global view of the behaviour of the allocators. The temporal and spatial results showed that TLSF is also a fast allocator and produces a fragmentation close to that caused by the best existing allocators.

A novel fault-tolerant sensor system for sensor drift compensation

The conventional fault-tolerant sensor systems would fail when outputs from incorporated sensors are either noisy or drifting. This paper presents a novel real-time fault compensation method, which uses state estimation and compensation techniques, that the sensor system can perform robust measurements even when outputs from every incorporated sensor are noisy and drifting. In a simulation example, the proposed design can detect and correct the sensor errors (dc bias and drift) in real time. For the dc bias, the minimum detectable offset value is 0.1, which is the same as the standard deviation of the sensor noise. The compensated sensor output is biased at values smaller than 0.02. For the sensor drifts, the proposed method can compensate drifts for the change rate of drifts up to four times faster than that of the signal to be measured. The highest change rate of drifts, that can be compensated by this method, is determined by the standard deviation of the sensor noise.     

Network invariants for real-time systems

We extend the approach of model checking parameterized networks of processes by means of network invariants to the setting of real-time systems. We introduce timed transition structures (which are similar in spirit to timed automata) and define a notion of abstraction that is safe with respect to linear temporal properties. We strengthen the notion of abstraction to allow a finite system, then called network invariant, to be an abstraction of networks of real-time systems. In general the problem of checking abstraction of real-time systems is undecidable. Hence, we provide sufficient criteria, which can be checked automatically, to conclude that one system is an abstraction of a concrete one. Our method is based on timed superposition and discretization of timed systems. We exemplify our approach by proving mutual exclusion of a simple protocol inspired by Fischer’s protocol, using the model checker TLV. Part of this work was done during O. Grinchtein’s stay at Weizmann Institute. This author was supported by the European Research Training Network “Games”.     

An efficient bit-based feature selection method

Feature selection is about finding useful (relevant) features to describe an application domain. Selecting relevant and enough features to effectively represent and index the given dataset is an important task to solve the classification and clustering problems intelligently. This task is, however, quite difficult to carry out since it usually needs a very time-consuming search to get the features desired. This paper proposes a bit-based feature selection method to find the smallest feature set to represent the indexes of a given dataset. The proposed approach originates from the bitmap indexing and rough set techniques. It consists of two-phases. In the first phase, the given dataset is transformed into a bitmap indexing matrix with some additional data information. In the second phase, a set of relevant and enough features are selected and used to represent the classification indexes of the given dataset. After the relevant and enough features are selected, they can be judged by the domain expertise and the final feature set of the given dataset is thus proposed. Finally, the experimental results on different data sets also show the efficiency and accuracy of the proposed approach.     

基于合一的链接文法

以词汇主义形式语法为基础,建立了链接文法与合一理论相结合的句法分析新方法.在封闭测试中,基于合一的链接文法句法分析精确率和召回率相比传统链接文法分别提高了9.6%和14.1%.实验表明方法具有一定独创性和高效性.     

一种改进的支持向量机降维方法

提出了一种基于支持向量机的改进的降维方法.在输入和特征空间中,特征子集的选取分别根据原始特征每一维对分类的贡献来获得.最后,通过将输入和特征空间中的特征选取联合起来,得到了一种改进的降维方法.实验表明:使用这种方法,在保持对分类准确率不受明显的影响的同时,能大大地提高训练和预测的速度.     

基于文字下划线特征变化的脆弱型文本水印

根据特征编码的思想,首次提出了一种基于文字下划线特征变化的脆弱型文本水印算法.该算法利用字符的内码特征信息生成水印,然后按照特定的顺序插入水印或检测水印.理论分析和实验表明,算法具有良好的不可感知性,能准确地检测各类水印攻击,在大部分情况下能对篡改进行精确定位.     

基于最大熵模型的中文名词短语识别

中文名词短语识别在自然语言处理已经得到了广泛应用。该文首先对名词短语识别问题进行描述,然后利用最大熵模型建立名词短语识别系统,通过实验选取最大熵模型的特征,最后利用选取的特征进行名词短语识别,实验结果表明系统达到了较高的准确率和召回率。