Efficient morse decompositions of vector fields

Existing topology-based vector field analysis techniques rely on the ability to extract the individual trajectories such as fixed points, periodic orbits, and separatrices that are sensitive to noise and errors introduced by simulation and interpolation. This can make such vector field analysis unsuitable for rigorous interpretations. We advocate the use of Morse decompositions, which are robust with respect to perturbations, to encode the topological structures of a vector field in the form of a directed graph, called a Morse connection graph (MCG). While an MCG exists for every vector field, it need not be unique. Previous techniques for computing MCG's, while fast, are overly conservative and usually results in MCG's that are too coarse to be useful for the applications. To address this issue, we present a new technique for performing Morse decomposition based on the concept of tau-maps, which typically provides finer MCG's than existing techniques. Furthermore, the choice of tau provides a natural tradeoff between the fineness of the MCG's and the computational costs. We provide efficient implementations of Morse decomposition based on tau-maps, which include the use of forward and backward mapping techniques and an adaptive approach in constructing better approximations of the images of the triangles in the meshes used for simulation.. Furthermore, we propose the use of spatial tau-maps in addition to the original temporal tau-maps. These techniques provide additional trade-offs between the quality of the MCGs and the speed of computation. We demonstrate the utility of our technique with various examples in the plane and on surfaces including engine simulation data sets.     

Robust Morse decompositions of piecewise constant vector fields

In this paper, we introduce a new approach to computing a Morse decomposition of a vector field on a triangulated manifold surface. The basic idea is to convert the input vector field to a piecewise constant (PC) vector field, whose trajectories can be computed using simple geometric rules. To overcome the intrinsic difficulty in PC vector fields (in particular, discontinuity along mesh edges), we borrow results from the theory of differential inclusions. The input vector field and its PC variant have similar Morse decompositions. We introduce a robust and efficient algorithm to compute Morse decompositions of a PC vector field. Our approach provides subtriangle precision for Morse sets. In addition, we describe a Morse set classification framework which we use to color code the Morse sets in order to enhance the visualization. We demonstrate the benefits of our approach with three well-known simulation data sets, for which our method has produced Morse decompositions that are similar to or finer than those obtained using existing techniques, and is over an order of magnitude faster.     

On the computation of invariant sets for constrained nonlinear systems: An interval arithmetic approach

This paper deals with the computation of control invariant sets for constrained nonlinear systems. The proposed approach is based on the computation of an inner approximation of the one step set, that is, the set of states that can be steered to a given target set by an admissible control action. Based on this procedure, control invariant sets can be computed by recursion.We present a method for the computation of the one-step set using interval arithmetic. The proposed specialized branch and bound algorithm provides an inner approximation with a given bound of the error; this makes it possible to achieve a trade off between accuracy of the computed set and computational burden. Furthermore an algorithm to approximate the one step set by an inner bounded polyhedron is also presented; this allows us to relax the complexity of the obtained set, and to make easier the recursion and storage of the sets.     

Detecting critical regions in multidimensional data sets

We propose a new approach, based on the Conley index theory, for the detection and classification of critical regions in multidimensional data sets. The use of homology groups makes this method consistent and successful in all dimensions and allows us to generalize visual classification techniques based solely on the notion of connectedness which may fail in higher dimensions.     

Efficient wavelet adaptation for hybrid wavelet-large margin classifiers

Hybrid wavelet-large margin classifiers have recently proven to solve difficult signal classification problems in cases where solely using a large margin classifier like, e.g., the Support Vector Machine may fail. In this paper, we evaluate several criteria rating feature sets obtained from various orthogonal filter banks for the classification by a Support Vector Machine. Appropriate criteria may then be used for adapting the wavelet filter with respect to the subsequent support vector classification. Our results show that criteria which are computationally more efficient than the radius-margin Support Vector Machine error bound are sufficient for our filter adaptation and, hence, feature selection. Further, we propose an adaptive search algorithm that, once the criterion is fixed, efficiently finds the optimal wavelet filter. As an interesting byproduct we prove a theorem which allows the computation of the radius of a set of vectors by a standard Support Vector Machine.     

Stable Morse Decompositions for Piecewise Constant Vector Fields on Surfaces

Numerical simulations and experimental observations are inherently imprecise. Therefore, most vector fields of interest in scientific visualization are known only up to an error. In such cases, some topological features, especially those not stable enough, may be artifacts of the imprecision of the input. This paper introduces a technique to compute topological features of user‐prescribed stability with respect to perturbation of the input vector field. In order to make our approach simple and efficient, we develop our algorithms for the case of piecewise constant (PC) vector fields. Our approach is based on a super‐transition graph, a common graph representation of all PC vector fields whose vector value in a mesh triangle is contained in a convex set of vectors associated with that triangle. The graph is used to compute a Morse decomposition that is coarse enough to be correct for all vector fields satisfying the constraint. Apart from computing stable Morse decompositions, our technique can also be used to estimate the stability of Morse sets with respect to perturbation of the vector field or to compute topological features of continuous vector fields using the PC framework.     

Vector field editing and periodic orbit extraction using Morse decomposition

Design and control of vector fields is critical for many visualization and graphics tasks such as vector field visualization, fluid simulation, and texture synthesis. The fundamental qualitative structures associated with vector fields are fixed points, periodic orbits, and separatrices. In this paper, we provide a new technique that allows for the systematic creation and cancellation of fixed points and periodic orbits. This technique enables vector field design and editing on the plane and surfaces with desired qualitative properties. The technique is based on Conley theory, which provides a unified framework that supports the cancellation of fixed points and periodic orbits. We also introduce a novel periodic orbit extraction and visualization algorithm that detects, for the first time, periodic orbits on surfaces. Furthermore, we describe the application of our periodic orbit detection and vector field simplification algorithms to engine simulation data demonstrating the utility of the approach. We apply our design system to vector field visualization by creating data sets containing periodic orbits. This helps us understand the effectiveness of existing visualization techniques. Finally, we propose a new streamline-based technique that allows vector field topology to be easily identified.     

An extended one-versus-rest support vector machine for multi-label classification

Hybrid strategy, which generalizes a specific single-label algorithm while one or two data decomposition tricks are applied implicitly or explicitly, has become an effective and efficient tool to design and implement various multi-label classification algorithms. In this paper, we extend traditional binary support vector machine by introducing an approximate ranking loss as its empirical loss term to build a novel support vector machine for multi-label classification, resulting into a quadratic programming problem with different upper bounds of variables to characterize label correlation of individual instance. Further, our optimization problem can be solved via combining one-versus-rest data decomposition trick with modified binary support vector machine, which dramatically reduces computational cost. Experimental study on ten multi-label data sets illustrates that our method is a powerful candidate for multi-label classification, compared with four state-of-the-art multi-label classification approaches.     

Efficient computation of 3D Morse–Smale complexes and persistent homology using discrete Morse theory

We propose an efficient algorithm that computes the Morse–Smale complex for 3D gray-scale images. This complex allows for an efficient computation of persistent homology since it is, in general, much smaller than the input data but still contains all necessary information. Our method improves a recently proposed algorithm to extract the Morse–Smale complex in terms of memory consumption and running time. It also allows for a parallel computation of the complex. The computational complexity of the Morse–Smale complex extraction solely depends on the topological complexity of the input data. The persistence is then computed using the Morse–Smale complex by applying an existing algorithm with a good practical running time. We demonstrate that our method allows for the computation of persistent homology for large data on commodity hardware.     

基于数据挖掘中文书目自动分类算法

提出一种改进的数据挖掘算法。首先采用ICTCLAS系统进行文本预处理,以词频特征构建词条向量;然后融合词频特征和词频-逆向文件频率特征,构建训练样本集的特征矩阵;接着对该矩阵进行奇异值分解变换,得到语义空间,用于对文本特征向量进行语义空间变换,得到语义向量;最后构建联合支持向量机分类器,实现中文书目所对应的语义向量的自动分类。最后做了大量的仿真实验,实验结果表明,本文方法的分类准确率高于现有方法。     

Preconditioning index set transformations for time-optimal affine scheduling

Many regular algorithms, suitable for VLSI implementation, are naturally described by sets of integer index vectors together with a rule that assigns a computation to each vector. Regular VLSI structures for such algorithms can be found by mapping the index vectors to a discrete space-time with integer coordinates. If the scope is restricted to linear or affine mappings, then the minimization of the execution time for the VLSI implementation with respect to the space-time mapping is essentially an integer linear programming (ILP) problem. If the entries in the vector describing the time function must be integers, ILP techniques can be applied directly. There are, however, index sets that allow space-time mappings with rational, nonintegral entries. In such cases, ILP will not consider all possible affine time functions and an optimal solution may go unnoticed. In this paper we give sufficient conditions on the index set for when only integer time functions are allowed. We also give a general algorithm to find a preconditioning affine transformation of the index set, such that the transformed index set allows only integer time functions. ILP methods can then be used to find time-optimal architectures for the transformed algorithm. This considerably extends the class of algorithms for which time-optimal VLSI structures can be found.Communicated by M. Snir.     

Fuzzy Regression Analysis by Support Vector Learning Approach

Support vector machines (SVMs) have been very successful in pattern classification and function approximation problems for crisp data. In this paper, we incorporate the concept of fuzzy set theory into the support vector regression machine. The parameters to be estimated in the SVM regression, such as the components within the weight vector and the bias term, are set to be the fuzzy numbers. This integration preserves the benefits of SVM regression model and fuzzy regression model and has been attempted to treat fuzzy nonlinear regression analysis. In contrast to previous fuzzy nonlinear regression models, the proposed algorithm is a model-free method in the sense that we do not have to assume the underlying model function. By using different kernel functions, we can construct different learning machines with arbitrary types of nonlinear regression functions. Moreover, the proposed method can achieve automatic accuracy control in the fuzzy regression analysis task. The upper bound on number of errors is controlled by the user-predefined parameters. Experimental results are then presented that indicate the performance of the proposed approach.     

Dynamic Force Distribution in Multifingered Grasping by Decomposition and Positive Combination

This paper presents a general algorithm for computing the optimal dynamic force distribution in multifingered grasping. It consists of two phases. In the offline phase, we select a spanning set for the required dynamic resultant wrench and find a corresponding spanning set for the total contact force. Then, in the online phase, the total contact force is obtained by decomposition of the resultant wrench into the former spanning set and a coefficient vector followed by positive combination of the latter spanning set with the vector. To make the online computation as simple as possible, iterative operation is executed offline and only arithmetic operation is employed online. To improve the grasping quality, the two spanning sets are selected elaborately.     

A note on the decomposition methods for support vector regression

The dual formulation of support vector regression involves two closely related sets of variables. When the decomposition method is used, many existing approaches use pairs of indices from these two sets as the working set. Basically, they select a base set first and then expand it so all indices are pairs. This makes the implementation different from that for support vector classification. In addition, a larger optimization subproblem has to be solved in each iteration. We provide theoretical proofs and conduct experiments to show that using the base set as the working set leads to similar convergence (number of iterations). Therefore, by using a smaller working set while keeping a similar number of iterations, the program can be simpler and more efficient.     

基于WordNet概念向量空间模型的文本分类

文章提出了一种文本特征提取方法,以WordNet语言本体库为基础,以同义词集合概念代替词条,同时考虑同义词集合间的上下位关系,建立文本的概念向量空间模型作为文本特征向量,使得在训练过程中能够提取出代表类别的高层次信息。实验结果表明,当训练文本集合很小时,方法能够较大地提高文本的分类准确率。     

Bayesian Classifiers Programmed in SQL

The Bayesian classifier is a fundamental classification technique. In this work, we focus on programming Bayesian classifiers in SQL. We introduce two classifiers: Naive Bayes and a classifier based on class decomposition using K-means clustering. We consider two complementary tasks: model computation and scoring a data set. We study several layouts for tables and several indexing alternatives. We analyze how to transform equations into efficient SQL queries and introduce several query optimizations. We conduct experiments with real and synthetic data sets to evaluate classification accuracy, query optimizations, and scalability. Our Bayesian classifier is more accurate than Naive Bayes and decision trees. Distance computation is significantly accelerated with horizontal layout for tables, denormalization, and pivoting. We also compare Naive Bayes implementations in SQL and C++: SQL is about four times slower. Our Bayesian classifier in SQL achieves high classification accuracy, can efficiently analyze large data sets, and has linear scalability.     

Multiclass classifier based on boundary complexity

This paper presents several criteria for partition of classes for the support vector machine based hierarchical classification. Our clustering algorithm combines support vector machine and binary tree, it is a divisive (top-down) approach in which a set of classes is automatically separated into two smaller groups at each node of the hierarchy, it splits the classes based on the normalized cuts clustering algorithm. Our clustering algorithm considers the involved classes rather than the individual data samples. In the new proposed measures, similarity between classes is determined based on boundary complexity. In these measures, concepts such as the upper bound of error and Kolmogorov complexity are used. We reported results on several data sets and five distance/similarity measures. Experimental results demonstrate the superiority of the proposed measures compared to other measures; even when applied to nonlinearly separable data, the new criteria perform well.     

Density-induced margin support vector machines

This paper proposes a new classifier called density-induced margin support vector machines (DMSVMs). DMSVMs belong to a family of SVM-like classifiers. Thus, DMSVMs inherit good properties from support vector machines (SVMs), e.g., unique and global solution, and sparse representation for the decision function. For a given data set, DMSVMs require to extract relative density degrees for all training data points. These density degrees can be taken as relative margins of corresponding training data points. Moreover, we propose a method for estimating relative density degrees by using the K nearest neighbor method. We also show the upper bound on the leave-out-one error of DMSVMs for a binary classification problem and prove it. Promising results are obtained on toy as well as real-world data sets.