基于动态规划的高阶隐马氏模型推广的Viterbi算法

首先通过Hadar等价变换方法将高阶隐马氏模型转换为与之等价的一阶向量值隐马氏模型,然后利用动态规划原理建立了一阶向量值隐马氏模型的Viterbi算法,最后通过高阶隐马氏模型和一阶向量值隐马氏模型之间的等价关系建立了高阶隐马氏模型基于动态规划推广的Viterbi算法．研究结果在一定程度上推广了几乎所有隐马氏模型文献中所涉及到的解码问题的Viterbi算法,从而进一步丰富和发展了高阶隐马氏模型的算法理论．     

基于ICA的时间序列聚类方法及其在股票数据分析中的应用

时间序列聚类分析是时间序列数据挖掘中的重要任务之一，通常由于时间序列数据的特殊结构，导致一般的聚类算法不能直接应用于时间序列数据。本文提出了一种基于独立成分分析与改进^一均值算法相结合的时间序列聚类算法，该算法首先利用独立成分分析对时间序列数据进行特征提取，然后利用改进￡．均值聚类算法完成对时间序列特征数据的聚类分析，从而得到了一种新的基于特征的时间序列聚类方法。为了验证该方法的有效性和可行性，将其应用于实际的股票时间序列数据聚类分析中，取得了较好的数值结果。     

一类带随机延滞的时间序列模型的遍历性

本利用马氏化方法和一般状态空间马氏链的基本理论研究了一类带随机延滞的时间序列模型的遍历性，得到了该模型伴随几何遍历的一个判别准则．     

关于任意随机变量序列的一类强极限定理

本文的目的是建立一类任意随机变量序列的强极限定理，作为推论，得到了一类鞅差序列收敛定理，马氏过程的强极限定理和若干经典的独立随机变量序列的强大数定律，已有的若干轶差序列收敛定理和可列非齐次马氏链的一个强极限定理是本文结果的特例，本文的主要结果对随机变量序列除矩条件外没有任何要求．     

隐非齐次马尔可夫模型的强大数定律

在状态集都有限的情况下,给出了隐马尔可夫模型的一些性质定理．利用马氏链的强极限定理,得到了隐非齐次马尔可夫模型的强大数定律．     

基于二维真实隐马氏模型的手写体文字识别算法

近几年来，人们采用各种方法试图将1D隐马氏模型(HMM)^[2]推广到2D隐马氏模型。令人失望的是由于在建立合适的2D模型及其计算上的复杂度问题上存在困难，前面的尝试都没有得到一个真实的2DHMM．本文对于应用真实2D隐马氏模型(隐马氏网格随机场HMMRF)^[1,4]进行手写字符识别问题提出新的框架，针对文献[1]中的单点最优算法给出局部最优的译码算法。HMMRF模型是1D隐马氏模型到2D的扩展，能更好的描述字符的2D特性。HMMRF在字符识别中的应用具有两个相——学习相和译码相。在学习相和译码相中我们的最优标准是基于极大边缘后验概率的。不过，在涉及到2D模型中的计算问题时，对模型做出某些简单化的假设是必要的。本文用到的方法对于在合理的模型假设下解决手写字符识别问题呈现了很大的潜力。     

不同分布(φ)混合随机变量序列的强收敛性

本文研究了不同分布(φ)混合随机变量序列的强收敛性质的问题.利用(φ)混合随机变量序列的矩不等式和截尾的方法,获得了(φ)混合随机变量序列完全收敛性和几乎处处收敛性结果,所获得结果不仅推广了Baum和Katz (1965)关于独立同分布随机变量序列的结论,而且改进了Wu和Lin (2004)关于同分布(φ)混合随机变量序列的相关结论.     

基于ICA的时间序列聚类方法及其股票数据分析中的应用

时间序列聚类分析是时间序列数据挖掘中的重要任务之一,通常由于时间序列数据的特殊结构,导致一般的聚类算法不能直接应用于时间序列数据.本文提出了一种基于独立成分分析与改进K-均值算法相结合的时间序列聚类算法,该算法首先利用独立成分分析对时间序列数据进行特征提取,然后利用改进K-均值聚类算法完成对时间序列特征数据的聚类分析,从而得到了一种新的基于特征的时间序列聚类方法.为了验证该方法的有效性和可行性,将其应用于实际的股票时间序列数据聚类分析中,取得了较好的数值结果.     

Fuzzy-2D-HMMS算法及其收敛性

通过对Dat Tran和Michael Wagner等提出的FCM-FE-HMMS算法研究,并把它与2维隐马氏模型联系起来,提出了Fuzzy-2D-HMMS算法,得出在给定初值的情况下该算法将收敛到一个局部最优解.     

一种混沌多相伪随机序列

提出了一种混沌多相伪随机序列生成方法，推导出通过Logistic映射产生独立同分布多相序列的充分条件，即根据混沌轨迹的概率密度分布把混沌吸引子划分为2n个区域，对混沌轨迹进行采样间隔为n的采样，对照轨道点所处位置与相应的序列元素之间的映射关系，可以得到独立、均匀分布的2n相伪随机序列。数值统计分析支持以上研究结果并表明该序列具有较高的复杂度。此外文中给出了该序列生成的快速算法和一般表达式。该序列可用于信息安全、扩频通信等众多领域。      

Improved Approximation Algorithms for Tree Alignment

Multiple sequence alignment is a task at the heart of much of current computational biology[4]. Several different objective functions have been proposed to formalize the task of multiple sequence alignment, but efficient algorithms are lacking in each case. Thus multiple sequence alignment is one of the most critical, essentially unsolved problems in computational biology. In this paper we consider one of the more compelling objective functions for multiple sequence alignment, formalized as thetree alignment problem. Previously in[13], a ratio-two approximation method was developed for tree alignment, which ran incubictime (as a function of the number of fixed length strings to be aligned), along with a polynomial time approximation scheme (PTAS) for the problem. However, the PTAS in[13]had a running time which made it impractical to reduce the performance ratio much below two for small size biological sequences (100 characters long). In this paper we first develop a ratio-two approximation algorithm which runs inquadratictime, and then use it to develop a PTAS which has a better performance ratio and a vastly improved worst case running time compared to the scheme in[13]for the case where the given tree is a regular deg-ary tree. With the new approximation scheme, it is now practical to guarantee a ratio of 1.583 for strings of lengths 200 characters or less.     

Measuring rank correlation coefficients between financial time series: A GARCH-copula based sequence alignment algorithm

This paper presents a novel four-stage algorithm for the measurement of the rank correlation coefficients between pairwise financial time series. In first stage returns of financial time series are fitted as skewed-t distributions by the generalized autoregressive conditional heteroscedasticity model. In the second stage, the joint probability density function (PDF) of the fitted skewed-t distributions is computed using the symmetrized Joe–Clayton copula. The joint PDF is then utilized as the scoring scheme for pairwise sequence alignment in the third stage. After solving the optimal sequence alignment problem using the dynamic programming method, we obtain the aligned pairs of the series. Finally, we compute the rank correlation coefficients of the aligned pairs in the fourth stage. To the best of our knowledge, the proposed algorithm is the first to use a sequence alignment technique to pair numerical financial time series directly, without initially transforming numerical values into symbols. Using practical financial data, the experiments illustrate the method and demonstrate the advantages of the proposed algorithm.     

An optimization approach to multiple sequence alignment

The problem of multiple sequence alignment is recast as an optimization problem using Markov decision theory. One seeks to minimize the expected or average cost of alignment subject to data-derived constraints. In this setting, the problem is equivalent to a linear program which can be solved efficiently using modern interior-point methods. We present numerical results from an implementation of the algorithm for protein sequence alignment     

A convergence theorem on a kind of band-limited functions with applications

A theorem on the convergence of a particular sequence of bandlimited functions is proved. As its applications, the convergence of a speed up error energy reduction algorithm for extrapolating bandlimited functions in noiseless cases and the convergence of an iterative algorithm to obtain estimations of bandlimited functions in noise cases are derived. Both algorithms are the improved versions of the Papoulis-Gercheberg algorithm.Institute of Systems Science, Academia Sinica     

Upper and lower bounding procedures for the multiple knapsack assignment problem

We formulate the multiple knapsack assignment problem (MKAP) as an extension of the multiple knapsack problem (MKP), as well as of the assignment problem. Except for small instances, MKAP is hard to solve to optimality. We present a heuristic algorithm to solve this problem approximately but very quickly. We first discuss three approaches to evaluate its upper bound, and prove that these methods compute an identical upper bound. In this process, reference capacities are derived, which enables us to decompose the problem into mutually independent MKPs. These MKPs are solved euristically, and in total give an approximate solution to MKAP. Through numerical experiments, we evaluate the performance of our algorithm. Although the algorithm is weak for small instances, we find it prospective for large instances. Indeed, for instances with more than a few thousand items we usually obtain solutions with relative errors less than 0.1% within one CPU second.     

Symmetric recursive algorithms for surfaces: B-patches and the de boor algorithm for polynomials over triangles

Using the concept of a symmetric recursive algorithm, we construct a new patch representation for bivariate polynomials: the B-patch. B-patches share many properties with B-spline segments: they are characterized by their control points and by a three-parameter family of knots. If the knots in each family coincide, we obtain the Bézier representation of a bivariate polynomial over a triangle. Therefore B-patches are a generalization of Bézier patches. B-patches have a de Boor-like evaluation algorithm, and, as in the case of B-spline curves, the control points of a B-patch can be expressed by simply inserting a sequence of knots into the corresponding polar form. In particular, this implies linear independence of the blending functions. B-patches can be joined smoothly and they have an algorithm for knot insertion that is completely similar to Boehm's algorithm for curves.     

Novel evolutionary models and applications to sequence alignment problems

In this paper, we present a novel graph-theoretical approach for representing a wide variety of sequence analysis problems within a single model. The model allows incorporation of the operations “insertion”, “deletion”, and “substitution”, and various parameters such as relative distances and weights. Conceptually, we refer the problem as the minimum weight common mutated sequence (MWCMS) problem. The MWCMS model has many applications including multiple sequence alignment problem, the phylogenetic analysis, the DNA sequencing problem, and sequence comparison problem, which encompass a core set of very difficult problems in computational biology. Thus the model presented in this paper lays out a mathematical modeling framework that allows one to investigate theoretical and computational issues, and to forge new advances for these distinct, but related problems. Through the introduction of supernodes, and the multi-layer supergraph, we proved that MWCMS is -complete. Furthermore, it was shown that a conflict graph derived from the multi-layer supergraph has the property that a solution to the associated node-packing problem of the conflict graph corresponds to a solution of the MWCMS problem. In this case, we proved that when the number of input sequences is a constant, MWCMS is polynomial-time solvable. We also demonstrated that some well-known combinatorial problems can be viewed as special cases of the MWCMS problem. In particular, we presented theoretical results implied by the MWCMS theory for the minimum weight supersequence problem, the minimum weight superstring problem, and the longest common subsequence problem. Two integer programming formulations were presented and a simple yet elegant decomposition heuristic was introduced. The integer programming instances have proven to be computationally intensive. Consequently, research involving simultaneous column and row generation and parallel computing will be explored. The heuristic algorithm, introduced herein for multiple sequence alignment, overcomes the order-dependent drawbacks of many of the existing algorithms, and is capable of returning good sequence alignments within reasonable computational time. It is able to return the optimal alignment for multiple sequences of length less than 1500 base pairs within 30 minutes. Its algorithmic decomposition nature lends itself naturally for parallel distributed computing, and we continue to explore its flexibility and scalability in a massive parallel environment.     

Sensitivity analysis incorporating fuzzy evaluation for scaling constants of multiattribute utility functions

A multiattribute utility function can be represented by a function of single-attribute utility functions if the decision maker’s preference satisfies additive independence or mutually utility independence. Additive independence is a preference condition stronger than mutually utility independence, and the multiattribute utility function is in the additive form if the former condition is satisfied, otherwise it is in the multiplicative form. In this paper, we propose a method for sensitivity analysis of multiattribute utility functions in multiplicative form, taking into account the imprecision of the decision maker’s judgment in the procedures for determining scaling constants (attribute weights).     

An Apéry-like continued fraction for π coth π

We consider the number π coth π which is transcendental in view of algebraic independence of π and e^π (due to Nesterenko's work in 1996). Studying certain nearly-poised hypergeometric series with complex parameters, which give us linear forms in π coth π and 1 with rational coefficients and applying Zeilberger's algorithm of creative telescoping we obtain a second order difference equation for these forms and their coefficients. As a consequence, we find a new decomposition of π coth π into a continued fraction, which produces a rapidly convergent sequence of rational approximations to this number.     

Nonmonotone BFGS-trained recurrent neural networks for temporal sequence processing

In this paper we propose a nonmonotone approach to recurrent neural networks training for temporal sequence processing applications. This approach allows learning performance to deteriorate in some iterations, nevertheless the network’s performance is improved over time. A self-scaling BFGS is equipped with an adaptive nonmonotone technique that employs approximations of the Lipschitz constant and is tested on a set of sequence processing problems. Simulation results show that the proposed algorithm outperforms the BFGS as well as other methods previously applied to these sequences, providing an effective modification that is capable of training recurrent networks of various architectures.