6920854
Chaos inducement and Enhancement in Two Particular Nonlinear Maps Using Weak Periodic/quasiperiodic Perturbations
Weak periodic perturbation has long been used to suppress chaos in dynamical systems. In this paper, however, we demonstrate that weak periodic or quasiperiodic perturbation can also be used to induce chaos in nonchaotic parameter ranges of chaotic maps, or to enhance the already existing chaotic state. Two kinds of chaotic maps, the period doubling system and the Hopf bifurcation system, are employed as basic models to analyze and compare in detail the different mechanisms of inducing and enhancing chaos in them. In addition, a special kind of intermittency characterized by its periodicity is found for the first time in periodically perturbed Henon map, and reasonable speculations are presented to explain its complicated dynamics.
10651609
Improved Nyström low-rank approximation and error analysis
Low-rank matrix approximation is an effective tool in alleviating the memory and computational burdens of kernel methods and sampling, as the mainstream of such algorithms, has drawn considerable attention in both theory and practice. This paper presents detailed studies on the Nyström sampling scheme and in particular, an error analysis that directly relates the Nyström approximation quality with the encoding powers of the landmark points in summarizing the data. The resultant error bound suggests a simple and efficient sampling scheme, the k-means clustering algorithm, for Nyström low-rank approximation. We compare it with state-of-the-art approaches that range from greedy schemes to probabilistic sampling. Our algorithm achieves significant performance gains in a number of supervised/unsupervised learning tasks including kernel PCA and least squares SVM.
14078787
Maximum Margin Clustering Made Practical
Motivated by the success of large margin methods in supervised learning, maximum margin clustering (MMC) is a recent approach that aims at extending large margin methods to unsupervised learning. However, its optimization problem is nonconvex and existing MMC methods all rely on reformulating and relaxing the nonconvex optimization problem as semidefinite programs (SDP). Though SDP is convex and standard solvers are available, they are computationally very expensive and only small data sets can be handled. To make MMC more practical, we avoid SDP relaxations and propose in this paper an efficient approach that performs alternating optimization directly on the original nonconvex problem. A key step to avoid premature convergence in the resultant iterative procedure is to change the loss function from the hinge loss to the Laplacian/square loss so that overconfident predictions are penalized. Experiments on a number of synthetic and real-world data sets demonstrate that the proposed approach is more accurate, much faster (hundreds to tens of thousands of times faster), and can handle data sets that are hundreds of times larger than the largest data set reported in the MMC literature.
1966273
Block-quantized kernel matrix for fast spectral embedding
Eigendecomposition of kernel matrix is an indispensable procedure in many learning and vision tasks. However, the cubic complexity <i>O</i>(<i>N</i><sup>3</sup>) is impractical for large problem, where <i>N</i> is the data size. In this paper, we propose an efficient approach to solve the eigendecomposition of the kernel matrix <i>W</i>. The idea is to approximate <i>W</i> with <i>W</i> that is composed of <i>m</i><sup>2</sup> constant blocks. The eigenvectors of <i>W</i>, which can be solved in <i>O</i>(<i>m</i><sup>3</sup>) time, is then used to recover the eigenvectors of the original kernel matrix. The complexity of our method is only <i>O</i>(<i>mN</i> + <i>m</i><sup>3</sup>), which scales more favorably than state-of-the-art low rank approximation and sampling based approaches (<i>O</i>(<i>m</i><sup>2</sup><i>N</i> + <i>m</i><sup>3</sup>)), and the approximation quality can be controlled conveniently. Our method demonstrates encouraging scaling behaviors in experiments of image segmentation (by spectral clustering) and kernel principal component analysis.
2257586
Applying neighborhood consistency for fast clustering and kernel density estimation
Nearest neighborhood consistency is an important concept in statistical pattern recognition, which underlies the well-known k-nearest neighbor method. In this paper, we combine this idea with kernel density estimation based clustering, and derive the fast mean shift algorithm (FMS). FMS greatly reduces the complexity of feature space analysis, resulting satisfactory precision of classification. More importantly, we show that with FMS algorithm, we are in fact relying on a conceptually novel approach of density estimation, the fast kernel density estimation (FKDE) for clustering. The FKDE combines smooth and non-smooth estimators and thus inherits advantages from both. Asymptotic analysis reveals the approximation of the FKDE to standard kernel density estimator. Data clustering and image segmentation experiments demonstrate the efficiency of FMS.
5858271
Prototype vector machine for large scale semi-supervised learning
Practical data mining rarely falls exactly into the supervised learning scenario. Rather, the growing amount of unlabeled data poses a big challenge to large-scale semi-supervised learning (SSL). We note that the computational intensiveness of graph-based SSL arises largely from the manifold or graph regularization, which in turn lead to large models that are difficult to handle. To alleviate this, we proposed the prototype vector machine (PVM), a highly scalable, graph-based algorithm for large-scale SSL. Our key innovation is the use of "prototypes vectors" for efficient approximation on both the graph-based regularizer and model representation. The choice of prototypes are grounded upon two important criteria: they not only perform effective low-rank approximation of the kernel matrix, but also span a model suffering the minimum information loss compared with the complete model. We demonstrate encouraging performance and appealing scaling properties of the PVM on a number of machine learning benchmark data sets.
16395477
Extending Metadata with Scenarios in Adaptive Distributed System
The traditional metadata cannot provide enough support for the adaptive distributed systems. In this paper, we propose a metadata extension that uses the scenarios as semantic aspect, describing the expected interaction sequence based on XML schema. With such constraints, resource waste and further damages can be avoided by preventing the illegal interactions at runtime. This extension is more valid and user-friendly than the majority of the existing proposals, avoiding the potential inconsistency. A prototype has been developed to illustrate the applicability of the extended metadata. The experiments demonstrate that the prototype introduces an average overhead ratio of 6.4% in the inter-process interactions and only 0.27% in the remote interactions. The approach presented in this paper is suitable for the adaptive distributed systems and affords more guarantee of reliability
18767470
New event detection based on indexing-tree and named entity
New Event Detection (NED) aims at detecting from one or multiple streams of news stories that which one is reported on a new event (i.e. not reported previously). With the overwhelming volume of news available today, there is an increasing need for a NED system which is able to detect new events more efficiently and accurately. In this paper we propose a new NED model to speed up the NED task by using news indexing-tree dynamically. Moreover, based on the observation that terms of different types have different effects for NED task, two term reweighting approaches are proposed to improve NED accuracy. In the first approach, we propose to adjust term weights dynamically based on previous story clusters and in the second approach, we propose to employ statistics on training data to learn the named entity reweighting model for each class of stories. Experimental results on two Linguistic Data Consortium (LDC) datasets TDT2 and TDT3 show that the proposed model can improve both efficiency and accuracy of NED task significantly, compared to the baseline system and other existing systems.
12863588
Studies on some perfectly matched layers for one-dimensional time-dependent systems
We will analyze some perfectly matched layers (PMLs) for the one-dimensional time-dependent Maxwell system, acoustic equations and hyperbolic systems in unbounded domains. The exponential decays and convergence of the PML solutions are studied. Some finite difference schemes are proposed for the PML equations and their stability and convergence are established.
225470
A 3D Self-Adjust Region Growing Method for Axon Extraction
Neuron axon analysis is an important means to investigate disease mechanisms and signaling pathways in neurobiology and often requires collecting a great amount of statistical information and phenomena. Automated extraction of axons in 3D microscopic images posts a key problem in the field of neuron axon analysis. To address tortuous axons in 3D volumes, a self-adjust region growing approach referring to surface modeling and self-adjustment which takes advantage of the nature of axon (e.g., continuity), is presented. Experimental results on axon volumes show that the proposed scheme provides a reliable solution to axon retrieving and overcomes several common drawbacks from other existing methods.
42520367
Extending metadata with scenarios in adaptive distributed system
The traditional metadata cannot provide enough support for the adaptive distributed systems. In this paper, we propose a metadata extension that uses the scenarios as semantic aspect, describing the expected interaction sequence based on XML Schema. With such constraints, resource waste and further damages can be avoided by preventing the illegal interactions at runtime. This extension is more valid and user-friendly than the majority of the existing proposals, avoiding the potential inconsistency. A prototype has been developed to illustrate the applicability of the extended metadata. The experiments demonstrate that the prototype introduces an average overhead ratio of 6.4% in the inter-process interactions and only 0.27% in the remote interactions. The approach presented in this paper is suitable for the adaptive distributed systems and affords more guarantee of reliability.