Search

In this paper we discuss two modifications of the surrogate data method based on phase randomization, see [Theiler et al., 1992]. By construction, phase randomized surrogates are circular stationary. In this respect they differ from the original time series. This can cause level inaccuracies of surrogate data tests. We will illustrate this. These inaccuracies are caused by end to end mismatches of the original time series. In this paper we will discuss two approaches to remedy this problem: resampling from subsequences without end to end mismatches and data tapering. Both methods can be understood as attempts to make non-circular data approximately circular. We will show that the first method works quite well for a large range of applications whereas data tapering leads only to improvements in some examples but can be very unstable otherwise. [ABSTRACT FROM AUTHOR]

The longest common subsequence is a well known and popular method for measuring similarity between sequences. It advocates the use of information contained in the longest common subsequence as an indication of similarity. In this paper we consider the count of all common subsequences as a measure of sequence similarity with the view that all common information is captured. This measure is inspired and derived from a generic similarity measure, neighborhood counting metric. The close connection of the neighborhood counting metric with probability and the Bayes classifier helps gain an insight from the probabilistic perspective into the all-common subsequences measure. We design algorithms to calculate this measure and we also carry out an experiment in the framework of k-nearest neighbors on a gene sequence classification task. The experiment shows that the all-common subsequences measure and the longest common subsequence measure have little difference for small k values, but differ significantly for large k values. The performance of the all-common subsequences measure remains steady as k gets larger, but the performance of the longest common subsequence measure drops sharply as k gets larger. Such a property may be useful for those tasks where we are interested not only in the nearest neighbor, but also in the first k nearest neighbors. The main contribution of this paper is a suite of algorithms for finding all common subsequences. [ABSTRACT FROM AUTHOR]

For the purpose of estimating the mixing matrix under the nonstrictly sparse condition, this paper presents the algorithms to approximate the mixing matrix in two different situations in which the source vectors are 1-sparse and (m - 1)-sparse. When the source signals are 1-sparse, we use the generalized spherical coordinate transformation to convert the matrix of observation signals into the new one, which makes the process of estimating column A become the process of finding the center point of these new data. For the situation that source signals are (m - 1)-sparse, we propose a new algorithm for the underdetermined mixtures blind source separation based on hyperplane clustering. The algorithm firstly finds out the linearly independent vectors from the observations, and secondly determines all the normal vectors of hyperplanes by analyzing the number of observations that are in the same hyperplane. Finally, we identify the column vectors of the mixing matrix A by calculating the vectors which are orthogonal to the clustered normal vectors. These two new algorithms for estimating the mixing matrix are more suitable for the general cases as they have lower requirement for the sparsity of the observations. [ABSTRACT FROM AUTHOR]

This paper presents a weighted support vector machine (WSVM) to improve the outlier sensitivity problem of standard support vector machine (SVM) for two-class data classification. The basic idea is to assign different weights to different data points such that the WSVM training algorithm learns the decision surface according to the relative importance of data points in the training data set. The weights used in WSVM are generated by a robust fuzzy clustering algorithm, kernel-based possibilistic c-means (KPCM) algorithm, whose partition generates relative high values for important data points but low values for outliers. Experimental results indicate that the proposed method reduces the effect of outliers and yields higher classification rate than standard SVM does when outliers exist in the training data set. [ABSTRACT FROM AUTHOR]

A new multi-class classifier, decision tree SVM (DTSVM) which is a binary decision tree with a very simple structure is presented in this paper. In DTSVM, a problem of multi-class classification is decomposed into a series of ones of binary classification. Here, the binary decision tree is generated by using kernel clustering algorithm, and each non-leaf node represents one binary classification problem. By compared with the other multi-class classification methods based on the binary classification SVMs, the scale and the complexity of DTSVM are less, smaller number of support vectors are needed, and has faster test speed. The final simulation results confirm the feasibility and the validity of DTSVM. [ABSTRACT FROM AUTHOR]

A temporal flexible planning problem that involves contingent and requirement events can be formulated as a simple temporal network with uncertainty (STNU). An STNU is controllable when there is a strategy for executing the requirement events (or actions) in such a way that all the conditions involving contingent events can be satisfied in all situations. The most interesting and useful controllability property is dynamic controllability in which the remaining actions in an STNU can always be scheduled under all possible feasible durations of future contingent events when all the past contingent events are known. In this paper, we propose and study a novel problem of assigning bounds on the duration of each requirement link in order for the resulting STNU to be dynamically controllable and to minimize the total cost over the allowed durations of all requirement links. We first prove the NP hardness of the problem with a linear cost function. We then formulate the dynamic controllability of an STNU as the constraints in a nonlinear optimization problem. Finally, we present methods for reducing the number of constraints in order to make the problem tractable and to demonstrate the computational performance of our methods. [ABSTRACT FROM AUTHOR]

A complex model for evolving the update strategy of a Particle Swarm Optimisation (PSO) algorithm is described in this paper. The model is a hybrid technique that combines a Genetic Algorithm (GA) and a PSO algorithm. Each GA chromosome is an array encoding a meaning for updating the particles of the PSO algorithm. The Evolved PSO algorithm is compared to several human-designed PSO algorithms by using ten artificially constructed functions and one real-world problem. Numerical experiments show that the Evolved PSO algorithm performs similarly and sometimes even better than the Standard approaches for the considered problems. The Evolved PSO is highly scalable (regarding the size of the problem's input), being able to solve problems having different dimensions. [ABSTRACT FROM AUTHOR]

This paper addresses a novel sentence reduction algorithm based on a decision tree model in which semantic information is used to enhance the accuracy of sentence reduction. The proposed algorithm is able to deal with the changeable order problem in sentence reduction. Furthermore, the use of decision list to solve the fragment problem in sentence reduction based decision tree model is also discussed. Our experimental results show an improvement when compared with earlier methods. [ABSTRACT FROM AUTHOR]

Propositional satisfiability (SAT) problem is fundamental to the theory of NP-completeness. Indeed, using the concept of "polynomial-time reducibility" all NP-complete problems can be polynomially reduced to SAT. Thus, any new technique for satisfiability problems will lead to general approaches for thousands of hard combinatorial problems. In this paper, we introduce the incremental propositional satisfiability problem that consists of maintaining the satisfiability of a propositional formula anytime a conjunction of new clauses is added. More precisely, the goal here is to check whether a solution to a SAT problem continues to be a solution anytime a new set of clauses is added and if not, whether the solution can be modified efficiently to satisfy the old formula and the new clauses. We will study the applicability of systematic and approximation methods for solving incremental SAT problems. The systematic method is based on the branch and bound technique while the approximation methods rely on stochastic local search and genetic algorithms. Experimental tests, conducted on randomly generated SAT instances, demonstrate the efficiency in time of the approximation methods over the branch and bound algorithm. However these approximation methods do not always guarantee the completeness of the solution returned. We show that a method we propose that uses non systematic search in a limited form together with branch and bound has the best compromise, in practice, between time and quality of the solution returned (success ratio). [ABSTRACT FROM AUTHOR]

Inference problems are one of the main research topics in the artificial intellect field. So far there have been various inference systems, some of them have been applied in fuzzy control according to their feature. In 1989, the concept of truth-valued flow inference was introduced by Wang1, and its mathematical theory of truth-valued flow inference was set up by Wang2 in 1995. In this paper, aimed at the real meaning of the truth-valued in the truth-valued flow inference, we introduce the concepts of the inner product truth-valued and inner product truth-valued flow inference, and analyze some inference algorithms of fuzzy control at present in detail. We reveal that the fuzzy inference algorithms in fuzzy control at present are all regarded as inner product truth-valued flow inference algorithm. Finally, inner product truth-valued flow inference approach is generalized in the multiple inputs and single output. [ABSTRACT FROM AUTHOR]

In Global Positioning System (GPS), receivers use FFT-based convolvers to acquire the signals. This paper shows a robust substitute algorithm for calculating the convolution that is less sensitive to additive noise. [ABSTRACT FROM AUTHOR]

This paper presents a fast algorithm for solving the n-queens problem. The basic idea of this algorithm is to use pre-computed solutions in 75% of the cases, while the remaining cases are solved by calling the Sosic's algorithm. The novelty of this algorithm is in the observation that these pre-computable cases exhibit a modular nature. In addition, the pre-computed solutions run 100 times faster than Sosic's algorithm in most cases. [ABSTRACT FROM AUTHOR]

The Multi-Tier (M-Tier) algorithm proposed in [1], has enabled an enhanced correlation between dynamic resource utilization and QoS guarantees. The algorithm favored the delay sensitive applications. Indirectly, this infers that the assignment of priorities practiced in the algorithm is static. In redesigning the algorithm, priority assignments should be able to be implemented dynamically. Thus, enabling an embedded element to provide implementation mobility. This would depend upon the current status of the classified buffers and the tolerance level of the delay sensitive traffic. Integrating control parameters to enable alternation in scheduling priorities is an option to resolve the element of partiality present in the M-Tier algorithm. Thereafter, the proposed algorithm will be denoted as the M-Tier(T) algorithm [2]. The paper proposes a detailed mathematical model for the analysis of dynamic resource reservation algorithms implemented in IP switches. The semi-markov process (SMP) approach utilized provides an accurate performance prediction and representation of resource reservation mechanisms. The algorithm correlates the average packet delay and packet loss ratio parameters to activate the dynamic resource reservation mechanism in a hierarchical manner. The developed models are validated through discrete-event simulation. The performance of the algorithm is studied in terms of average packet delay and network throughput. [ABSTRACT FROM AUTHOR]

This paper describes an efficient and adaptive method of threshold estimation for removing impulse noise from images, based on Double Density Wavelet Transform (DDWT). The performance of image de-noising algorithms using wavelet transforms can be improved significantly by fixing an optimum threshold value, based on the analysis of the statistical parameters of subband coefficients. In this proposed method, the choice of the threshold estimation is carried out by analyzing the statistical parameters of the wavelet subband coefficients like standard deviation, arithmetic mean and geometrical mean. Here the noisy image is first decomposed into many levels to obtain different frequency bands using DDWT. Then soft thresholding method is used to remove the noisy coefficients, by fixing the optimum threshold value by the proposed method. Experimental results on several test images by using the proposed method show that, the proposed method yields significantly superior image quality and better Peak Signal-to-Noise Ratio (PSNR). Some comparisons with the best available results will be given in order to illustrate the effectiveness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

By analyzing the dynamic behaviors of the transiently chaotic neural network and greedy heuristic for the maximum independent set (MIS) problem, we present an improved transiently chaotic neural network for the MIS problem in this paper. Extensive simulations are performed and the results show that this proposed transiently chaotic neural network can yield better solutions to p-random graphs than other existing algorithms. The efficiency of the new model is also confirmed by the results on the complement graphs of some DIMACS clique instances in the second DIMACS challenge. Moreover, the improved model uses fewer steps to converge to stable state in comparison with the original transiently chaotic neural network. [ABSTRACT FROM AUTHOR]

A fuzzy variable is a function from a possibility space to the set of real numbers, while a bifuzzy variable is a function from a possibility space to the set of fuzzy variables. In this paper, a concept of chance distribution is originally presented for bifuzzy variable, and the linearity of expected value operator of bifuzzy variable is proved. Furthermore, bifuzzy simulations are designed and illustrated by some numerical experiments. [ABSTRACT FROM AUTHOR]

In this paper, we apply OPCL control to discrete system, and based on relative nonlinear measure, give an algorithm for estimating the radius of stable basin. We rigorously prove that this basin is bound to be of existence for nonlinear discrete system, whose goal dynamics is either periodic orbits or fixed point. We also, in particular, investigate the stable basin in a quadratic polynomial map system, and present that the stable basin is irrelevant to the goal orbits with a negative Jacobian gain matrix. Furthermore, we take the well-known Hénon system and Ikeda system as examples to illustrate the implementation of our theory, and give the corresponding simulations to reinforce our method. [ABSTRACT FROM AUTHOR]

An algorithm is proposed in this paper that finds exact exclusive-or sum-of-products of an arbitrary function, provided the number of product terms is less than eight. If the number of product terms in the minimal expression is more than seven, then the algorithm detects it and heuristically returns near-optimal expressions. The algorithm is time and space efficient even for functions with many input variables. [ABSTRACT FROM AUTHOR]

This paper introduces an automatic robust nonlinear identification algorithm using the leave-one-out test score also known as the PRESS (Predicted REsidual Sums of Squares) statistic and regularised orthogonal least squares. The proposed algorithm aims to achieve maximised model robustness via two effective and complementary approaches, parameter regularisation via ridge regression and model optimal generalisation structure selection. The major contributions are to derive the PRESS error in a regularised orthogonal weight model, develop an efficient recursive computation formula for PRESS errors in the regularised orthogonal least squares forward regression framework and hence construct a model with a good generalisation property. Based on the properties of the PRESS statistic the proposed algorithm can achieve a fully automated model construction procedure without resort to any other validation data set for model evaluation. [ABSTRACT FROM AUTHOR]

We are watching the news on TV: the change of the background tells us when a new story begins. A glance at the clock and we can clearly see what time it is. These are special spatial-temporal episodes caused by ballistic eye movements and sudden optical changes. In this paper we give a useful definition for generalized sudden global change events, present its main properties and give an algorithm to recognize them in any video-flow. The proposed algorithm is implemented on a standard Cellular Nonlinear Network Universal Machine (CNN-UM). The processing time of the detection is roughly one millisecond on the ACE4k CNN-UM chip in the Aladdin environment. Therefore it can serve as a common function in any online, real-time spatial-temporal algorithm. The sudden global change event can be used to define the instant when the time-dependent part of that algorithm, e.g., homotopy, has to be initialized. The first steps of the multimedia processing, such as searching for key frames — for compression, browsing or indexing — can be helped by the proposed algorithm as a robust video shot change detection method. [ABSTRACT FROM AUTHOR]

This paper treats a problem of reconstructing ordinary differential equation from a single analytic time series with observational noise. We suppose that the noise is Gaussian (white). The investigation is presented in terms of classical theory of dynamical systems and modern time series analysis. We restrict our considerations on time series obtained as a numerical analytic solution of autonomous ordinary differential equation, solved with respect to the highest derivative and with polynomial right-hand side. In case of an approximate numerical solution with a rather small error, we propose a geometrical basis and a mathematical algorithm to reconstruct a low-order and low-power polynomial differential equation. To reduce the noise the given time series is smoothed at every point by moving polynomial averages using the least-squares method. Then a specific form of the least-squares method is applied to reconstruct the polynomial right-hand side of the unknown equation. We demonstrate for monotonous, periodic and chaotic solutions that this technique is very efficient. [ABSTRACT FROM AUTHOR]