Random Sampling of Euler Tours

We define a Markov chain on the set of Euler tours of a given Eulerian graph based on transformations first defined by Kotzig in 1966. We prove that the chain is rapidly mixing if the maximum degree in the given graph is 6, thus obtaining an efficient algorithm for sampling and counting the set of Euler tours for such an Eulerian graph. Received October 30, 1997; revised March 12, 1999, and April 17, 2000.     

Random Sampling for Subspace Face Recognition

Subspace face recognition often suffers from two problems: (1) the training sample set is small compared with the high dimensional feature vector; (2) the performance is sensitive to the subspace dimension. Instead of pursuing a single optimal subspace, we develop an ensemble learning framework based on random sampling on all three key components of a classification system: the feature space, training samples, and subspace parameters. Fisherface and Null Space LDA (N-LDA) are two conventional approaches to address the small sample size problem. But in many cases, these LDA classifiers are overfitted to the training set and discard some useful discriminative information. By analyzing different overfitting problems for the two kinds of LDA classifiers, we use random subspace and bagging to improve them respectively. By random sampling on feature vectors and training samples, multiple stabilized Fisherface and N-LDA classifiers are constructed and the two groups of complementary classifiers are integrated using a fusion rule, so nearly all the discriminative information is preserved. In addition, we further apply random sampling on parameter selection in order to overcome the difficulty of selecting optimal parameters in our algorithms. Then, we use the developed random sampling framework for the integration of multiple features. A robust random sampling face recognition system integrating shape, texture, and Gabor responses is finally constructed.     

动态约简的抽样分析

对动态约简的思想进行了阐述．详细分析了其中子表抽取的有关问题，指出了存在的不足．给出了一种新的计算动态约简子表族大小的方法和几个评估动态约简样本族的参数．实验证明了算法的有效性．     

基于进化算法的SFSN神经网络

提出一种基于进化算法的ＳＦＳＮｔＳａｍｐｌｉｎｇＦｒｅｑｕｃｈｅｙ０ｓｅｎｓｉｔｉｖｅ Ｎｅｔｗｏｒｋ）神经网络分类量化方法,该算法把并行全局寻代的进化算法ＥＰ（Ｅｖｏｌｕｔｉｏｎａｒｙ Ｐｒｕｇｒａｍｍｉｎｇ）融合进ＳＦＳＮ神经网络,使神经网络的结构优化与参数优化同时完成。即同时解决了最佳分类数与最佳矢量量化问题。实验结果证实了算法的有效性。     

基于随机抽样的模糊粗糙约简

传统的属性约简由于其时间复杂度和空间复杂度过高,几乎无法应用到大规模的数据集中.将随机抽样引入传统的模糊粗糙集中,使得属性约简的效率大幅度提升.首先,在统计下近似的基础上提出一种统计属性约简的定义.这里的约简不是原有意义上的约简,而是保持基于统计下近似定义的统计辨识度不变的属性子集.然后,采用抽样的方法计算统计辨识度的样本估计值,基于此估计值可以对统计属性重要性进行排序,从而可以设计一种快速的适用于大规模数据的序约简算法.由于随机抽样集以及统计近似概念的引入,该算法从时间和空间上均降低了约简的计算复杂度,同时又保持了数据集中信息含量几乎不变.最后,数值实验将基于随机抽样的序约简算法和两种传统的属性约简算法从以下3个方面进行了对比：计算属性约简时间消耗、计算属性约简空间消耗、约简效果.对比实验验证了基于随机抽样的序约简算法在时间与空间上的优势.     

一种基于随机采样的SPM管理机制

嵌入式系统对于功耗和面积具有很高的要求.便签存储器(scratchpad memory,SPM)与同等容量Cache相比具有能耗低、片上面积小等优点,现已成为嵌入式处理器中广泛采用的片上存储器.高效的SPM管理策略对于降低系统功耗具有重要意义.传统的SPM管理策略通过编译器采用软件方式进行.随着移动设备及网络互联设备的发展,嵌入式程序的部署方式已趋于多样化,致使传统基于程序特征分析(profiling)的SPM管理方式在某些方面存在局限.提出了一种软硬件结合的基于随机采样(random sampling)的动态SPM管理策略,通过实时监控程序访存特征等手段在运行时动态预测核心工作集(core working set).该方法区别于传统方法之处在于无需依赖profiling信息和编译器进行SPM管理,而通过跟踪程序运行时访存动态特征指导SPM管理.实验表明,该方法可以充分发挥SPM在功耗、面积等方面的优势;通过与一种经典的SPM管理策略相比,所提出的方法在保证系统性能不降低的前提下,提高了SPM管理的灵活性、通用性.     

VFP系统实现单纯随机抽样程序的开发及应用

单纯随机抽样是医学科研设计中最基本的抽样方法,介绍抽样程序开发过程及应用.     

ORACLE中的动态SQL编程

为了提高PL/SQL程序的性能．增加程序的灵活性，PL／SQL中增加了动态SQL。本文通过详细的例子介绍了对动态SQL编程的各种方法，并指出了在编程时应注意的问题。     

Online Dynamic Programming Speedups

Consider the dynamic program h(n)=min _1≤j≤n a(n,j), where a(n,j) is some formula that may (online) or may not (offline) depend on the previously computed h(i), for i<n. The goal is to compute all h(n), for 1≤n≤N. It is well known that, if a(n,j) satisfy the Monge property, then the SMAWK algorithm (Aggarwal et al., Algorithmica 2(1):195–208, 1987) can solve the offline problem in O(N) time; a Θ(N) speedup over the naive algorithm. In this paper we extend this speedup to the online case, that is, to compute h(n) in the order n=1,2,…,N when (i) we do not know the values of a(n′,j) for n′>n before h(n) has been computed and (ii) do not know the problem size N in advance. We show that if a(n,j) satisfy a stronger, but sometimes still natural, property than the Monge one, then each h(n) can be computed in online fashion in O(1) amortized time. This maintains the speedup online, in the sense that the total time to compute all h(n) is O(N). We also show how to compute each h(n) in the worst case O(log N) time, while maintaining the amortized time bound. For a(n,j) satisfying our stronger property, our algorithm is also simpler than the standard SMAWK algorithm for solving the offline case. We illustrate our technique on two examples from the literature; the first is the D-median problem on a line, and the second comes from mobile wireless paging. The research of the first author was partially supported by the NSF program award CNS-0626606; the research of the second and third authors was partially supported by Hong Kong RGC CERG grant HKUST6312/04E.     

A Generalized Sampling Theorem for Non-Stationary Random Processes

Abstract

Gardner [3] has proved sampling theorem for non-stationary random processes. Earlier it was known for stationary processes. Also Kramer [5], using general Kernels, has generalized the Whittaker- Shannon sampling theorem. In the present paper we use the finite Hankel-transform as it appears in the literature and extend it with the help of Kramer's theorem. Further in terms of auto-correlation functions of n-dimensional space, the sampling theorem for n-dimensional non-stationary processes is obtained. We have also extended the definition of auto-correlation function in terms of generalized Kernel in place of Fourier Kernel and then in terms of this, sampling theorem for non-stationary processes is proved. An example using Kernel in terms of Bessel functions is given.     

图像分类的随机半监督采样方法

为更好地利用大量未标注图像样本信息来提高分类器性能,提出一种半监督学习的图像分类算法--随机半监督采样(RSSS).该算法采用迭代随机采样方法,每次采样中通过谱聚类估计未标注样本的类别值,使用SVM进行模型学习,逐步优化模型;同时,使用图像的局部空间直方图特征可以有效地结合图像的统计和空间信息,以提高分类准确度.实验结果表明,RSSS算法可以充分利用未标注样本信息提高分类器的性能,并且可以有效地消除几何变换带来的影响.     

Motion Analysis by Random Sampling and Voting Process

In computer vision, motion analysis is a fundamental problem. Applying the concepts of congruence checking in computational geometry and geometric hashing, which is a technique used for the recognition of partially occluded objects from noisy data, we present a new random sampling approach for the estimation of the motion parameters in two- and three-dimensional Euclidean spaces of both a completely measured rigid object and a partially occluded rigid object. We assume that the two- and three-dimensional positions of the vertices of the object in each image frame are determined using appropriate methods such as a range sensor or stereo techniques. We also analyze the relationships between the quantization errors and the errors in the estimation of the motion parameters by random sampling, and we show that the solutions obtained using our algorithm converge to the true solutions if the resolution of the digitalization is increased.     

Random Sampling for Continuous Streams with Arbitrary Updates

The existing random sampling methods have at least one of the following disadvantages: they 1) are applicable only to certain update patterns, 2) entail large space overhead, or 3) incur prohibitive maintenance cost. These drawbacks prevent their effective application in stream environments (where a relation is updated by a large volume of insertions and deletions that may arrive in any order), despite the considerable success of random sampling in conventional databases. Motivated by this, we develop several fully dynamic algorithms for obtaining random samples from individual relations, and from the join result of two tables. Our solutions can handle any update pattern with small space and computational overhead. We also present an in-depth analysis that provides valuable insight into the characteristics of alternative sampling strategies and leads to precision guarantees. Extensive experiments validate our theoretical findings and demonstrate the efficiency of our techniques in practice     

基于随机采样的多量测目标跟踪算法

在多目标跟踪领域,传统算法假设目标是点源辐射体,至多产生一个量测点,随着现代 传感器技术的发展,可以获得一个目标的多个量测. 本文研究当目标具有一定刚体几何形状并产生 多量测的问题,这类目标称为多量测目标.首先,通过建立目标形状的刚体参数模型,提出采用参数马 尔科夫链采样的方法,估计目标的形状参数.其次,采用等效量测方法,获得目标形心 点的运动状态. 针对目标个数未知情况,在形状目标量测满足泊松分布假设条件下,采用泊松强度比方法获得目标的个数估计. 本文定义了目标类型概率并给出 了目标类型概率的递推算法. 最后,通过三个具有不同形状和分布的多量测目标在二维平面的匀速(Constant velocity, CV)运动进行验证说明,实验表明: 所给方法在目标运动状态估计方面能够获得比较高的估计精度,目标形状估计能够比较稳定精确地估计目标形状的变化. 此外, 500次蒙特卡洛(Monte Carlo, MC)仿真实验表明,多量测目标的跟踪丢失率约为1.4%.     

Limitations of Incremental Dynamic Programming

We consider so-called “incremental” dynamic programming algorithms, and are interested in the number of subproblems produced by them. The classical dynamic programming algorithm for the Knapsack problem is incremental, produces nK subproblems and nK ² relations (wires) between the subproblems, where n is the number of items, and K is the knapsack capacity. We show that any incremental algorithm for this problem must produce about nK subproblems, and that about nKlogK wires (relations between subproblems) are necessary. This holds even for the Subset-Sum problem. We also give upper and lower bounds on the number of subproblems needed to approximate the Knapsack problem. Finally, we show that the Maximum Bipartite Matching problem and the Traveling Salesman problem require exponential number of subproblems. The goal of this paper is to leverage ideas and results of boolean circuit complexity for proving lower bounds on dynamic programming.     

面向方面程序的动态语义研究

目前,针对面向方面程序,许多研究者已定义了各种各样的形式语义。但是,没有一种语义能被软件设计者和开发者所理解。针对该问题,在已有研究的基础上,应用统一程序理论中的设计来定义面向方面的动态语义。同时,以一个例子来说明该语义的使用。     

动态规划算法解题思路

本文对近年来的信息学奥赛题的解题作总结分析.通过几道经典的动态规划题型来阐述如何应对动态规划解题过程,总结出解动态规划题型的关键是把握其"不变"和"万变"的解题技巧.     

数字前端功耗降低方法的仿真研究

数字前端是当前移动通信的研究热点,由于传送的信号是一种高频率,宽频带的动态信号,模拟前端信息处理方法不适合,且传统不均匀采样信号处理方法生成多个同频率不同相位的时钟信号,导致数字前端功率消耗较大.为了降低数字前端功率消耗,结合可编程逻辑器件(FPGA)的特有结构,设计了一种随机时钟产生模块,并利用所产生的随机时钟作为数字前端中模数转换器(ADC)的工作时钟频率,以产生不均匀采样ADC,从而有效地降低数字前端的功率消耗.仿真结果表明,所设计的FPGA模块能够产生随机性很好的时钟信号,且优于现有的设计方法,证明随机性越大的时钟信号能有效降低数字前端的功率消耗,为通信前端设计提供了依据.     

一种自适应随机反走样算法

分析了光线追踪中造成物体锯齿状边缘的原因，讨论了几种反走样方法，在此基础上设计了一个自适应随机反走样算法。实践证明该算法能有效地消除物体的锯齿状边缘。     

Dynamic Programming via Static Incrementalization

Dynamic programming is an important algorithm design technique. It is used for problems whose solutions involve recursively solving subproblems that share subsubproblems. While a straightforward recursive program solves common subsubproblems repeatedly, a dynamic programming algorithm solves every subsubproblem just once, saves the result, and reuses it when the subsubproblem is encountered again. This can reduce the time complexity from exponential to polynomial. This paper describes a systematic method for transforming programs written as straightforward recursions into programs that use dynamic programming. The method extends the original program to cache all possibly computed values, incrementalizes the extended program with respect to an input increment to use and maintain all cached results, prunes out cached results that are not used in the incremental computation, and uses the resulting incremental program to form an optimized new program. Incrementalization statically exploits semantics of both control structures and data structures and maintains as invariants equalities characterizing cached results. It provides the basis of a general method for achieving drastic program speedups. Compared with previous methods that perform memoization or tabulation, the method based on incrementalization is more powerful and systematic. It has been implemented in a prototype system CACHET and applied to numerous problems and succeeded on all of them.