Processing Short-Term and Long-Term Information With a Combination of Polynomial Approximation Techniques and Time-Delay Neural Networks

Neural networks are often used to process temporal information, i.e., any kind of information related to time series. In many cases, time series contain short-term and long-term trends or behavior. This paper presents a new approach to capture temporal information with various reference periods simultaneously. A least squares approximation of the time series with orthogonal polynomials will be used to describe short-term trends contained in a signal (average, increase, curvature, etc.). Long-term behavior will be modeled with the tapped delay lines of a time-delay neural network (TDNN). This network takes the coefficients of the orthogonal expansion of the approximating polynomial as inputs such considering short-term and long-term information efficiently. The advantages of the method will be demonstrated by means of artificial data and two real-world application examples, the prediction of the user number in a computer network and online tool wear classification in turning.     

On-line motif detection in time series with SwiftMotif

This article presents SwiftMotif, a novel technique for on-line motif detection in time series. With this technique, frequently occurring temporal patterns or anomalies can be discovered, for instance. The motif detection is based on a fusion of methods from two worlds: probabilistic modeling and similarity measurement techniques are combined with extremely fast polynomial least-squares approximation techniques. A time series is segmented with a data stream segmentation method, the segments are modeled by means of normal distributions with time-dependent means and constant variances, and these models are compared using a divergence measure for probability densities. Then, using suitable clustering algorithms based on these similarity measures, motifs may be defined. The fast time series segmentation and modeling techniques then allow for an on-line detection of previously defined motifs in new time series with very low run-times. SwiftMotif is suitable for real-time applications, accounts for the uncertainty associated with the occurrence of certain motifs, e.g., due to noise, and considers local variability (i.e., uniform scaling) in the time domain. This article focuses on the mathematical foundations and the demonstration of properties of SwiftMotif—in particular accuracy and run-time—using some artificial and real benchmark time series.     

Novel Online Methods for Time Series Segmentation

To efficiently and effectively mine massive amounts of data in the time series, approximate representation of the data is one of the most commonly used strategies. Piecewise Linear Approximation is such an approach, which represents a time series by dividing it into segments and approximating each segment with a straight line. In this paper, we first propose a new segmentation criterion that improves computing efficiency. Based on this criterion, two novel online piecewise linear segmentation methods are developed, the feasible space window method and the stepwise feasible space window method. The former usually produces much fewer segments and is faster and more reliable in the running time than other methods. The latter can reduce the representation error with fewer segments. It achieves the best overall performance on the segmentation results compared with other methods. Extensive experiments on a variety of real-world time series have been conducted to demonstrate the advantages of our methods.     

基于正则化的乘更新在线分类算法

大样本集上在线预测算法时间空间复杂度小、预测准确性高,与批处理学习算法相比,有明显的优势。自从Jivinen和M.Warmuth提出权衡正确性与保守性的在线学习框架后,在线学习框架已被广泛引用。但是在Jivinen和M.Warmuth提出的梯度下降和指数梯度下降算法中,对目标函数中的损失函数求导过程中使用近似步骤会引起在线学习结果恶化。运用对偶最优化理论,提出了非近似的基于不同距离和损失函数的乘更新分类算法,一系列的实验显示算法提高了预测准确率。     

A matrix-free quasi-Newton method for solving large-scale nonlinear systems

One of the widely used methods for solving a nonlinear system of equations is the quasi-Newton method. The basic idea underlining this type of method is to approximate the solution of Newton’s equation by means of approximating the Jacobian matrix via quasi-Newton update. Application of quasi-Newton methods for large scale problems requires, in principle, vast computational resource to form and store an approximation to the Jacobian matrix of the underlying problem. Hence, this paper proposes an approximation for Newton-step based on the update of approximation requiring a computational effort similar to that of matrix-free settings. It is made possible by approximating the Jacobian into a diagonal matrix using the least-change secant updating strategy, commonly employed in the development of quasi-Newton methods. Under suitable assumptions, local convergence of the proposed method is proved for nonsingular systems. Numerical experiments on popular test problems confirm the effectiveness of the approach in comparison with Newton’s, Chord Newton’s and Broyden’s methods.     

The wavelet-NARMAX representation: A hybrid model structure combining polynomial models with multiresolution wavelet decompositions

A new hybrid model structure combing polynomial models with multiresolution wavelet decompositions is introduced for nonlinear system identification. Polynomial models play an important role in approximation theory and have been extensively used in linear and nonlinear system identification. Wavelet decompositions, in which the basis functions have the property of localization in both time and frequency, outperform many other approximation schemes and offer a flexible solution for approximating arbitrary functions. Although wavelet representations can approximate even severe nonlinearities in a given signal very well, the advantage of these representations can be lost when wavelets are used to capture linear or low-order nonlinear behaviour in a signal. In order to sufficiently utilize the global property of polynomials and the local property of wavelet representations simultaneously, in this study polynomial models and wavelet decompositions are combined together in a parallel structure to represent nonlinear input–output systems. As a special form of the NARMAX model, this hybrid model structure will be referred to as the WAvelet-NARMAX model, or simply WANARMAX. Generally, such a WANARMAX representation for an input–output system might involve a large number of basis functions and therefore a great number of model terms. Experience reveals that only a small number of these model terms are significant to the system output. A new fast orthogonal least-squares algorithm, called the matching pursuit orthogonal least squares (MPOLS) algorithm, is also introduced in this study to determine which terms should be included in the final model.     

Solution of a scaled system via generalized orthogonal polynomials

Generalized orthogonal polynomials which include all types of orthogonal polynomial are introduced first. Using the idea of orthogonal polynomials that can be expressed by a Taylor power series and vice versa, the operational matrix for the integration of the generalized orthogonal polynomials is first derived. A stretched operational matrix of diagonal form is also derived. Both the operational matrix for the integration and the stretched operational matrix of generalized orthogonal polynomials are applied to solve functional differential equations. The characteristics of each kind of orthogonal polynomial in solving the scaled system is demonstrated. The computational strategy for finding the expansion coefficients of the state variables is very simple, straightforward and easy. The inversion of only one matrix, which has the same dimension as the state variables, is required. The expansion coefficients of the state variables are obtained by the proposed recursive formula. Much computer time is thus saved and computational results are obtained that are very accurate compared with previous methods.     

噪声鲁棒的分水岭网格分割算法

提出一种对逆向工程网格噪声鲁棒的分水岭分割算法.该算法在计算网格离散曲率时,针对曲率计算对网格噪声特别敏感的问题,根据拟合曲面的曲面误差估计,动态地调整拟合曲面的顶点个数,提高了曲率计算的精确性,增强了基于曲率的分水岭算法对噪声的鲁棒性;通过后续的标识、聚类和分割后处理方法,提高了算法的分割精度和效果.该算法在大量的噪声网格模型上获得了较好的分割结果,适用于逆向工程中的二次曲面识别和NURBS曲面逼近.     

Extraction of ridge and valley lines from unorganized points

Given an unstructured point set, we use an MLS (moving least-squares) approximation to estimate the local curvatures and their derivatives at a point by means of an approximating surface. Then, we compute neighbor information using a Delaunay tessellation. Ridge and valley points can then be detected as zero-crossings, and connected using curvature directions. We demonstrate our method on several large point-sampled models, rendered by point-splatting, on which the ridge and valley lines are rendered with line width determined from curvatures.     

New results on recurrent network training: unifying the algorithmsand accelerating convergence

How to efficiently train recurrent networks remains a challenging and active research topic. Most of the proposed training approaches are based on computational ways to efficiently obtain the gradient of the error function, and can be generally grouped into five major groups. In this study we present a derivation that unifies these approaches. We demonstrate that the approaches are only five different ways of solving a particular matrix equation. The second goal of this paper is develop a new algorithm based on the insights gained from the novel formulation. The new algorithm, which is based on approximating the error gradient, has lower computational complexity in computing the weight update than the competing techniques for most typical problems. In addition, it reaches the error minimum in a much smaller number of iterations. A desirable characteristic of recurrent network training algorithms is to be able to update the weights in an online fashion. We have also developed an online version of the proposed algorithm, that is based on updating the error gradient approximation in a recursive manner.     

A method for the recovery of noisy missing data in movement analysis

A new method is proposed for the accurate recovery of missing marker data obtained from movement tracking systems. The method has the form of a least-squares cubic polynomial approximation which is realized by the recursive expansion of orthogonal polynomials.     

Solutions of linear dynamic systems by generalized orthogonal polynomials

Generalized orthogonal polynomials that represent all types of orthogonal polynomial are introduced in this paper. Using the idea of orthogonal polynomial functions that can be expressed by power series, and vice versa, the operational matrix for integration of a generalized orthogonal polynomial is first derived and then applied to solve the equations of linear dynamic systems. The characteristics of each kind of orthogonal polynomial in relation to solving linear dynamic systems is demonstrated. The computational strategy for finding the expansion coefficients of the state variables is very simple, straightforward and easy. The operational matrix is simpler than those of conventional orthogonal polynomials. Hence the expansion coefficients are more easily calculated from the proposed recursive formula when compared with those obtained from conventional orthogonal polynomial approximations.     

Online Bayesian inference for the parameters of PRISM programs

This paper presents a method for approximating posterior distributions over the parameters of a given PRISM program. A sequential approach is taken where the distribution is updated one datapoint at a time. This makes it applicable to online learning situations where data arrives over time. The method is applicable whenever the prior is a mixture of products of Dirichlet distributions. In this case the true posterior will be a mixture of very many such products. An approximation is effected by merging products of Dirichlet distributions. An analysis of the quality of the approximation is presented. Due to the heavy computational burden of this approach, the method has been implemented in the Mercury logic programming language. Initial results using a hidden Markov model and a probabilistic graph are presented.     

基于局部均值分解和改进小波熵的时序SAX模型

符号聚合近似表示法是提取时间序列特征的重要方式。然而,传统的符号聚合近似表示法存在平均化分段数、同等对待划分区间,以及无法准确反映非平稳序列的突变信息等多项缺陷。鉴于此,通过引入局部均值分解和改进小波熵的分段算法,建立了一种新的时序SAX模型。该模型的基本原理是采用局部均值分解技术对原始序列进行去噪处理,利用滑动窗口阈值法获取分段数,并使用SAX表示法进行符号表示,利用KNN分类器实现分类性能测试。基于这一改进模型,进行了实证检验,实验结果表明,该模型能够有效提取序列的信息特征,具有较高的拟合度,达到了降维的目的,更重要的是,提高了KNN分类算法在SAX表示法中分类的准确率。     

Finite Volterra-series realizations and input-output approximations of non-linear discrete-time systems

It is shown that a separability property of a given finite family of stationary kernels turns out to be necessary and sufficient for the realization of the associated functional by means of a polynomial affine system (i.e. a system that is polynomial in the input and affine in the state). Moreover, the discrete Volterra kernels associated with the input-output map of a non-linear analytic discrete-lime system, initialized at an equilibrium point, are shown to possess a separability property. On this basis, we state an approximation result for the given input-output map by considering the first kernels of the discrete Volterra series. Two explicit constructions of the approximating polynomial affine systems are proposed.     

Self-adaptive finite elements in fracture mechanics

A new finite element capability which permits the analyst to vary the order of polynomial approximation over each finite element is discussed with reference to its potential for application to stress intensity factor computations in linear elastic fracture mechanics. Computational experiments, in which polynomial orders ranging from 1 to 8 were used, indicated strong and monotonie convergence of the strain energy release rate even for very coarse finite element meshes as the order p of the approximating polynomial was increased. Pointwise convergence of stresses was achieved by averaging approximations of different polynomial orders. The strong and monotonie convergence of K_I factors with respect to increasing p provides a new method for computing stress intensity factors. The main advantage of this method is that the accuracy of approximation can be established without mesh refinement or the use of special procedures.     

基于分割模式的时间序列矢量符号化算法

针对符号化聚合近似算法(SAX)中时间序列必须等长分割的缺陷,提出一种基于分割模式的时间序列符号化算法(SMSAX)。利用三角阈值法对随机抽样的时间序列进行特征提取,计算时间序列最大压缩比,将其作为时间窗宽提取分割点,进而求出时间序列的分割模式。利用得到的分割模式对时间序列进行分割降维,通过均值和波动率对分割后的子序列进行向量符号化。根据时间序列特征对其进行不等长分割,并加入波动率消除奇异点的影响。实验结果表明,SMSAX能获得比SAX更精确的结果。     

Geometric selection of centers for radial basis function approximations involved in intensive computer simulations

A method for the selection of centers for radial basis function (RBF) approximation is introduced, which reduces the computational cost of the evaluation of the approximating function. The method takes into consideration:

• 1.the geometric information (arc length and curvature) of the approximating RBF expansion with all data points as centers, in order to retain as centers just those data points that have relevant geometric characteristics;
• 2.the distribution of data points in the function domain do not leave rather large regions of the function domain without centers;
• 3.the approximation error to control the number of centers in such a way that a desired fitting accuracy can be achieved.

Numerical experiments are carried out to illustrate the performance of the method on a number of test functions.     

基于矢量场在线更新的人和机器人身体交流控制

为实现人和机器人身体相互交流时的运动同步,提出基于矢量场在线更新的控制方法,并将此方法应 用于人和机器人握手的研究中．首先,对该方法中任意吸引子的矢量场进行多项式近似设计,使其具备自振动特性; 其次,通过在线更新设计,控制系统具有输入输出同步特性,并且可以通过调节系统中的忘却系数和负荷系数来改 变其同步程度;最后,基于7 自由度机器人臂,将该方法用于人和机器人握手实验中,结果表明了此方法的有效性．     

Least-Squares B-Spline Curve Approximation with Arbitary End Derivatives

An algorithm for least-squares approximation of data with end derivative constraints is presented. The approximating curve minimises the error in the least-squares sense, while at the same time assumes the derivatives specified. For degree p approximation, up to p 2 1 derivatives may be specified, resulting in C p−1 continuous curve approximants. The method is useful to piece individual curve segments together, or to create closed curves with various degrees of smoothness.