A robust VAR-based (vector autoregressive) model is introduced for motion prediction in 3D hand tracking. This dynamic VAR motion model is learned in an online manner. The kinematic structure of the hand is accounted for in the form of constraints when solving for the parameters of the VAR model. Also integrated into the motion prediction model are adaptive weights that are optimised according to the reliability of past predictions. Experiments on synthetic and real video sequences show a substantial improvement in tracking performance when the robust VAR motion model is used. In fact, utilising the robust VAR model allows the tracker to handle fast out-of-plane hand movement with severe self-occlusion.

We extend the well-known BFGS quasi-Newton method and its limited-memory variant LBFGS to the optimization of non-smooth convex objectives. This is done in a rigorous fashion by generalizing three components of BFGS to subdifferentials: The local quadratic model, the identification of a descent direction, and the Wolfe line search conditions. We apply the resulting subLBFGS algorithm to L2-regularized risk minimization with binary hinge loss, and its direction-finding component to L1-regularized risk minimization with logistic loss. In both settings our generic algorithms perform comparable to or better than their counterparts in specialized state-of-the-art solvers.

The mean-shift (MS) algorithm is widely used in object tracking because of its speed and simplicity. However, it assumes certain overlap of object appearance and smooth change in object scale between consecutive video frames. This assumption is usually violated in a low-frame-rate (LFR) video, which contains fast motion and scale changes. An LFR video is widely adopted in applications such as surveillance systems, where real-time object tracking is highly desirable but the traditional MS algorithm does not perform well. We addressed this problem by proposing a novel and enhanced mean-shift tracker, named SMDShift, that uses kernel prediction and stochastic meta-descent (SMD) optimization method to deal with the kernel position and scale variation when tracking objects in an LFR video. In our experiments, the SMDShift can track fast moving objects with significant scale change in an LFR video sequence on which the traditional mean-shift and Camshift algorithms fail.

Active appearance model (AAM) has been widely used in face tracking and recognition. However, accuracy and efficiency are always two main challenges with the AAM search. The paper therefore proposed a fast appearance-model based 3D face tracking algorithm to track a face appearance with significant translation, rotation, and scaling activities by using stochastic meta-descent (SMD) optimization scheme to accelerate the appearance model search and to improve the tracking efficiency and accuracy. The proposed algorithm constructs an active face appearance model by using several semantic landmark points extracted from each frame and then processes the appearance model search to approximate the model translating, rotating, and scaling by using the SMD filter to minimize the appearance difference between the current model and the new observation. We compared the results with both a conventional AAM and a Camshift filter and found that our algorithm outperforms both two in terms of efficiency and accuracy in tracking a fast moving, rotating, and scaling face object in a video sequence.

We present polynomial-time algorithms for the exact computation of lowest- energy states, worst margin violators, partition functions, and marginals in binary undirected graphical models. Our approach provides an interesting alternative to the well-known graph cut paradigm in that it does not impose any submodularity constraints; instead we require planarity to establish a correspondence with perfect matchings in an expanded dual graph. Maximum-margin parameter estimation for a boundary detection task shows our approach to be efficient and effective.

In the above titled paper (ibid., vol. 15, no. 4, pp. 828-837, Jul 04), the M-step (22) was incorrect. The corrected M-step is presented here.

We apply Stochastic Meta-Descent (SMD), a stochastic gradient optimization method with gain vector adaptation, to the training of Conditional Random Fields (CRFs). On several large data sets, the resulting optimizer converges to the same quality of solution over an order of magnitude faster than limited-memory BFGS, the leading method reported to date. We report results for both exact and inexact inference techniques.

We introduce two methods to improve convergence of the Kernel Hebbian Algorithm (KHA) for iterative kernel PCA. KHA has a scalar gain parameter which is either held constant or decreased as 1/t, leading to slow convergence. Our KHA/et algorithm accelerates KHA by incorporating the reciprocal of the current estimated eigenvalues as a gain vector. We then derive and apply Stochastic MetaDescent (SMD) to KHA/et; this further speeds convergence by performing gain adaptation in RKHS. Experimental results for kernel PCA and spectral clustering of USPS digits as well as motion capture and image de-noising problems confirm that our methods converge substantially faster than conventional KHA.

Using extensions of linear algebra concepts to Reproducing Kernel Hilbert Spaces (RKHS), we define a unifying framework for random walk kernels on graphs. Re- duction to a Sylvester equation allows us to compute many of these kernels in O(n3) worst-case time. This includes kernels whose previous worst-case time complexity was O(n6), such as the geometric kernels of G¨artner et al. [1] and the marginal graph kernels of Kashima et al. [2]. Our algebra in RKHS allow us to exploit sparsity in directed and undirected graphs more effectively than previ- ous methods, yielding sub-cubic computational complexity when combined with conjugate gradient solvers or fixed-point iterations. Experiments on graphs from bioinformatics and other application domains show that our algorithms are often more than 1000 times faster than existing approaches.

This paper presents an online support vector machine (SVM) that uses the stochastic meta-descent (SMD) algorithm to adapt its step size automatically. We formulate the online learning problem as a stochastic gradient descent in reproducing kernel Hilbert space (RKHS) and translate SMD to the nonparametric setting, where its gradient trace parameter is no longer a coefficient vector but an element of the RKHS. We derive efficient updates that allow us to perform the step size adaptation in linear time. We apply the online SVM framework to a variety of loss functions, and in particular show how to handle structured output spaces and achieve efficient online multiclass classification. Experiments show that our algorithm outperforms more primitive methods for setting the gradient step size.

Reinforcement learning by direct policy gradient estimation is attractive in theory but in practice leads to notoriously ill-behaved optimization problems. We improve its robustness and speed of convergence with stochastic meta-descent, a gain vector adaptation method that employs fast Hessian-vector products. In our experiments the resulting algorithms outperform previously employed online stochastic, offline conjugate, and natural policy gradient methods.

We present an overview of evolutionary algorithms that use empirical models of the fitness function to accelerate convergence, distinguishing between evolution control and the surrogate approach. We describe the Gaussian process model and propose using it as an inexpensive fitness function surrogate. Implementation issues such as efficient and numerically stable computation, exploration versus exploitation, local modeling, multiple objectives and constraints, and failed evaluations are addressed. Our resulting Gaussian process optimization procedure clearly outperforms other evolutionary strategies on standard test functions as well as on a real-world problem: the optimization of stationary gas turbine compressor profiles.

This paper derives a family of differential learning rules that optimize the Shannon entropy at the output of an adaptive system via kernel density estimation. In contrast to parametric formulations of entropy, this nonparametric approach assumes no particular functional form of the output density. We address problems associated with quantized data and finite sample size, and implement efficient maximum likelihood techniques for optimizing the regularizer. We also develop a normalized entropy estimate that is invariant with respect to affine transformations, facilitating optimization of the shape, rather than the scale, of the output density. Kernel density estimates are smooth and differentiable; this makes the derived entropy estimates amenable to manipulation by gradient descent. The resulting weight updates are surprisingly simple and efficient learning rules that operate on pairs of input samples. They can be tuned for data-limited or memory-limited situations, or modified to give a fully online implementation.

We discuss the implementation of a learning algorithm for determining adaptation parameters in evolution strategies. As an initial test case, we consider the application of reinforcement learning for determining the relationship between success rates and the adaptation of step sizes in the (1+1)-evolution strategy. The results from the new adaptive scheme when applied to several test functions are compared with those obtained from the (1+1)-evolution strategy with a priori selected parameters. Our results indicate that assigning good reward measures seems to be crucial to the performance of the combined strategy.

We propose a generic method for iteratively approximating various second-order gradient steps - Newton, Gauss-Newton, Levenberg-Marquardt, and natural gradient - in linear time per iteration, using special curvature matrix-vector products that can be computed in O(n). Two recent acceleration techniques for on-line learning, matrix momentum and stochastic meta-descent (SMD), implement this approach. Since both were originally derived by very different routes, this offers fresh insight into their operation, resulting in further improvements to SMD.

Neural network simulations often spend a large proportion of their time computing exponential functions. Since the exponentiation routines of typical math libraries are rather slow, their replacement with a fast approximation can greatly reduce the overall computation time. This article describes how exponentiation can be approximated by manipulating the components of a standard (IEEE-754) floating-point representation. This models the exponential function as well as a lookup table with linear interpolation, but is significantly faster and more compact.

Differentiation between the nodes of a competitive learning net(cid:173) work is conventionally achieved through competition on the ba(cid:173) sis of neural activity. Simple inhibitory mechanisms are limited to sparse representations, while decorrelation and factorization schemes that support distributed representations are computation(cid:173) ally unattractive. By letting neural plasticity mediate the compet(cid:173) itive interaction instead, we obtain diffuse, nonadaptive alterna(cid:173) tives for fully distributed representations. We use this technique to Simplify and improve our binary information gain optimiza(cid:173) tion algorithm for feature extraction (Schraudolph and Sejnowski, 1993); the same approach could be used to improve other learning algorithms.