Solution path for manifold regularized semisupervised classification

Traditional learning algorithms use only labeled data for training. However, labeled examples are often difficult or time consuming to obtain since they require substantial human labeling efforts. On the other hand, unlabeled data are often relatively easy to collect. Semisupervised learning addresses this problem by using large quantities of unlabeled data with labeled data to build better learning algorithms. In this paper, we use the manifold regularization approach to formulate the semisupervised learning problem where a regularization framework which balances a tradeoff between loss and penalty is established. We investigate different implementations of the loss function and identify the methods which have the least computational expense. The regularization hyperparameter, which determines the balance between loss and penalty, is crucial to model selection. Accordingly, we derive an algorithm that can fit the entire path of solutions for every value of the hyperparameter. Its computational complexity after preprocessing is quadratic only in the number of labeled examples rather than the total number of labeled and unlabeled examples.     

An efficient deconvolution algorithm for estimating oxygen consumption during muscle activities

The reconstruction of an unknown input function from noisy measurements in a biological system is an ill-posed inverse problem. Any computational algorithm for its solution must use some kind of regularization technique to neutralize the disastrous effects of amplified noise components on the computed solution. In this paper, following a hierarchical Bayesian statistical inversion approach, we seek estimates for the input function and regularization parameter (hyperparameter) that maximize the posterior probability density function. We solve the maximization problem simultaneously for all unknowns, hyperparameter included, by a suitably chosen quasi-Newton method. The optimization approach is compared to the sampling-based Bayesian approach. We demonstrate the efficiency and robustness of the deconvolution algorithm by applying it to reconstructing the time courses of mitochondrial oxygen consumption during muscle state transitions (e.g., from resting state to contraction and recovery), from the simulated noisy output of oxygen concentration dynamics on the muscle surface. The model of oxygen transport and metabolism in skeletal muscle assumes an in vitro cylindrical structure of the muscle in which the oxygen from the surrounding oxygenated solution diffuses into the muscle and is then consumed by the muscle mitochondria. The algorithm can be applied to other deconvolution problems by suitably replacing the forward model of the system.     

Maximum Penalized Likelihood Kernel Regression for Fast Adaptation

This paper proposes a nonlinear generalization of the popular maximum-likelihood linear regression (MLLR) adaptation algorithm using kernel methods. The proposed method, called maximum penalized likelihood kernel regression adaptation (MPLKR), applies kernel regression with appropriate regularization to determine the affine model transform in a kernel-induced high-dimensional feature space. Although this is not the first attempt of applying kernel methods to conventional linear adaptation algorithms, unlike most of other kernelized adaptation methods such as kernel eigenvoice or kernel eigen-MLLR, MPLKR has the advantage that it is a convex optimization and its solution is always guaranteed to be globally optimal. In fact, the adapted Gaussian means can be obtained analytically by simply solving a system of linear equations. From the Bayesian perspective, MPLKR can also be considered as the kernel version of maximum a posteriori linear regression (MAPLR) adaptation. Supervised and unsupervised speaker adaptation using MPLKR were evaluated on the Resource Management and Wall Street Journal 5K tasks, respectively, achieving a word error rate reduction of 23.6% and 15.5% respectively over the speaker-independently model.     

Recursive Bayesian Recurrent Neural Networks for Time-Series Modeling

This paper develops a probabilistic approach to recursive second-order training of recurrent neural networks (RNNs) for improved time-series modeling. A general recursive Bayesian Levenberg–Marquardt algorithm is derived to sequentially update the weights and the covariance (Hessian) matrix. The main strengths of the approach are a principled handling of the regularization hyperparameters that leads to better generalization, and stable numerical performance. The framework involves the adaptation of a noise hyperparameter and local weight prior hyperparameters, which represent the noise in the data and the uncertainties in the model parameters. Experimental investigations using artificial and real-world data sets show that RNNs equipped with the proposed approach outperform standard real-time recurrent learning and extended Kalman training algorithms for recurrent networks, as well as other contemporary nonlinear neural models, on time-series modeling.      

Nonlinear time series forecasting with Bayesian neural networks

The Bayesian learning provides a natural way to model the nonlinear structure as the artificial neural networks due to their capability to cope with the model complexity. In this paper, an evolutionary Monte Carlo (MC) algorithm is proposed to train the Bayesian neural networks (BNNs) for the time series forecasting. This approach called as Genetic MC is based on Gaussian approximation with recursive hyperparameter. Genetic MC integrates MC simulations with the genetic algorithms and the fuzzy membership functions. In the implementations, Genetic MC is compared with the traditional neural networks and time series techniques in terms of their forecasting performances over the weekly sales of a Finance Magazine.     

Gradient-based optimization of hyperparameters

Many machine learning algorithms can be formulated as the minimization of a training criterion that involves a hyperparameter. This hyperparameter is usually chosen by trial and error with a model selection criterion. In this article we present a methodology to optimize several hyperparameters, based on the computation of the gradient of a model selection criterion with respect to the hyperparameters. In the case of a quadratic training criterion, the gradient of the selection criterion with respect to the hyperparameters is efficiently computed by backpropagating through a Cholesky decomposition. In the more general case, we show that the implicit function theorem can be used to derive a formula for the hyperparameter gradient involving second derivatives of the training criterion.     

基于种群演化的超参数异步并行搜索

近年来随着深度学习尤其是深度强化学习模型的不断增大,其训练成本即超参数的搜索空间也在不断变大,然而传统超参数搜索算法大部分是基于顺序执行训练,往往需要等待数周甚至数月才有可能找到较优的超参数配置.为解决深度强化学习超参数搜索时间长和难以找到较优超参数配置问题,提出一种新的超参数搜索算法-----基于种群演化的超参数异步并行搜索(PEHS).算法结合演化算法思想,利用固定资源预算异步并行搜索种群模型及其超参数,从而提高算法性能.设计实现在Ray并行分布式框架上运行的参数搜索算法,通过实验表明在并行框架上基于种群演化的超参数异步并行搜索的效果优于传统超参数搜索算法,且性能稳定.     

Efficient and scalable quicksort on a linear array with a reconfigurable pipelined bus system

Based on the current fiber optic technology, a new computational model, called a linear array with a reconfigurable pipelined abus system (LARPBS), is proposed in this paper. A parallel quicksort algorithm is implemented on the model, and its time complexity is analyzed. For a set of N numbers, the quicksort algorithm reported in this paper runs in O(log₂ N) average time on a linear array with a reconfigurable pipelined bus system of size N. If the number of processors available is reduced to P, where P < N, the algorithm runs in O((N/P) log₂ N) average time and is still scalable. Besides proposing a new algorithm on the model, some basic data movement operations involved in the algorithm are discussed. We believe that these operations can be used to design other parallel algorithms on the same model. Future research in this area is also identified in this paper.     

Additive Regularization Trade-Off: Fusion of Training and Validation Levels in Kernel Methods

This paper presents a convex optimization perspective towards the task of tuning the regularization trade-off with validation and cross-validation criteria in the context of kernel machines. We focus on the problem of tuning the regularization trade-off in the context of Least Squares Support Vector Machines (LS-SVMs) for function approximation and classification. By adopting an additive regularization trade-off scheme, the task of tuning the regularization trade-off with respect to a validation and cross-validation criterion can be written as a convex optimization problem. The solution of this problem then contains both the optimal regularization constants with respect to the model selection criterion at hand, and the corresponding training solution. We refer to such formulations as the fusion of training with model selection. The major tool to accomplish this task is found in the primal-dual derivations as occuring in convex optimization theory. The paper advances the discussion by relating the additive regularization trade-off scheme with the classical Tikhonov scheme. Motivations are given for the usefulness of the former scheme. Furthermore, it is illustrated how to restrict the additive trade-off scheme towards the solution path corresponding with a Tikhonov scheme while retaining convexity of the overall problem of fusion of model selection and training. We relate such a scheme with an ensemble learning problem and with stability of learning machines. The approach is illustrated on a number of artificial and benchmark datasets relating the proposed method with the classical practice of tuning the Tikhonov scheme with a cross-validation measure.     

快速双非凸回归算法及其电力数据预测应用

为适应产能输出、运营效益等电力数据预测应用,文中提出一种快速双非凸回归(double nonconvex regression,DNR)预测算法。首先,将经典稀疏编码分类技术解释为预测回归模型,并划分为训练阶段和测试阶段,使之适合标量预测应用;其次,针对经典Lasso模型存在的稀疏性不足以及噪声拟合单一问题,该算法通过l_p范数约束逼近原始稀疏编码问题的误差重构项和系数正则项,具有更为灵活的模型形式和应用范围。最后,通过交替方向乘子框架实现了重构系数的优化升级策略。为确保ADMM优化子问题具有快速解,提出一种改进的迭代阈值规则用于更新非凸l_p约束项,解决了原始算法陷入的局部最优问题。在电力企业实际运行产出和运营指标数据上的实验结果表明,DNR在预测效果和预测效率上均优于经典的支持向量机、BP神经网络以及非凸约束预测方法。     

TSK-fuzzy modeling based on /spl epsiv/-insensitive learning

In this paper, new learning methods tolerant to imprecision are introduced and applied to fuzzy modeling based on the Takagi-Sugeno-Kang fuzzy system. The fuzzy modeling has an intrinsic inconsistency. It may perform thinking tolerant to imprecision, but learning methods are zero-tolerant to imprecision. The proposed methods make it possible to exclude this intrinsic inconsistency of a fuzzy modeling, where zero-tolerance learning is used to obtain fuzzy model tolerant to imprecision. These new methods can be called /spl epsiv/-insensitive learning or /spl epsiv/ learning, where, in order to fit the fuzzy model to real data, the /spl epsiv/-insensitive loss function is used. This leads to a weighted or "fuzzified" version of Vapnik's support vector regression machine. This paper introduces two approaches to solving the /spl epsiv/-insensitive learning problem. The first approach leads to the quadratic programming problem with bound constraints and one linear equality constraint. The second approach leads to a problem of solving a system of linear inequalities. Two computationally efficient numerical methods for the /spl epsiv/-insensitive learning are proposed. The /spl epsiv/-insensitive learning leads to a model with the minimal Vapnik-Chervonenkis dimension, which results in an improved generalization ability of this model and its outliers robustness. Finally, numerical examples are given to demonstrate the validity of the introduced methods.     

Dynamic distributed unicast routing: optimal incremental paths

Developing new mathematical frameworks such as distributed dynamic routing algorithms for constructing optimal incremental paths from a node to another node is an important challenge in data communication networks. These new algorithms can model network resources optimally and increase network performances. A bundle of single routes in a current communication path, which starts from a source node and ends to a destination node, can consist of several successive nodes and links. The Incremental term emphasizes that the number of routes (links and nodes) in a current path can change so that achieving more data rate and optimal efficiency in the network. In this paper, our problem is to add/omit some routes consisting of some nodes and links to/from the current unicast path dynamically and optimally. We call this problem the Optimal Dynamic Distributed Unicast Routing (ODDUR) problem and it is a NP-complete problem. This problem can be formulated as a new type of Linear Programming Problem (LPP) for finding a minimum cost multichannel unicast path, which this path will minimize end-to-end delay and bandwidth consumption along the routes from the source node to the destination node. In this paper, at first a new mathematical framework will be constructed and then this framework will propose the new optimal dynamic distributed unicast routing algorithm for solving our LPP problem. This algorithm will compute an optimal solution for our LPP based on the simplex method and postoptimality computations and will reduce computations and consumed time. Simulation results will show that our new algorithm is more efficient than other available algorithms in terms of utilization of bandwidths and data rate.     

A novel solution for maze traversal problems using artificial neural networks

In this paper we have addressed the problem of finding a path through a maze of a given size. The traditional ways of finding a path through a maze employ recursive algorithms in which unwanted or non-paths are eliminated in a recursive manner. Neural networks with their parallel and distributed nature of processing seem to provide a natural solution to this problem. We present a biologically inspired solution using a two level hierarchical neural network for the mapping of the maze as also the generation of the path if it exists. For a maze of size S the amount of time it takes would be a function of S (O(S)) and a shortest path (if more than one path exists) could be found in around S cycles where each cycle involves all the neurons doing their processing in a parallel manner. The solution presented in this paper finds all valid paths and a simple technique for finding the shortest path amongst them is also given. The results are very encouraging and more applications of the network setup used in this report are currently being investigated. These include synthetic modeling of biological neural mechanisms, traversal of decision trees, modeling of associative neural networks (as in relating visual and auditory stimuli of a given phenomenon) and surgical micro-robot trajectory planning and execution.     

MultiETSC: automated machine learning for early time series classification

Early time series classification (EarlyTSC) involves the prediction of a class label based on partial observation of a given time series. Most EarlyTSC algorithms consider the trade-off between accuracy and earliness as two competing objectives, using a single dedicated hyperparameter. To obtain insights into this trade-off requires finding a set of non-dominated (Pareto efficient) classifiers. So far, this has been approached through manual hyperparameter tuning. Since the trade-off hyperparameters only provide indirect control over the earliness-accuracy trade-off, manual tuning is tedious and tends to result in many sub-optimal hyperparameter settings. This complicates the search for optimal hyperparameter settings and forms a hurdle for the application of EarlyTSC to real-world problems. To address these issues, we propose an automated approach to hyperparameter tuning and algorithm selection for EarlyTSC, building on developments in the fast-moving research area known as automated machine learning (AutoML). To deal with the challenging task of optimising two conflicting objectives in early time series classification, we propose MultiETSC, a system for multi-objective algorithm selection and hyperparameter optimisation (MO-CASH) for EarlyTSC. MultiETSC can potentially leverage any existing or future EarlyTSC algorithm and produces a set of Pareto optimal algorithm configurations from which a user can choose a posteriori. As an additional benefit, our proposed framework can incorporate and leverage time-series classification algorithms not originally designed for EarlyTSC for improving performance on EarlyTSC; we demonstrate this property using a newly defined, “naïve” fixed-time algorithm. In an extensive empirical evaluation of our new approach on a benchmark of 115 data sets, we show that MultiETSC performs substantially better than baseline methods, ranking highest (avg. rank 1.98) compared to conceptually simpler single-algorithm (2.98) and single-objective alternatives (4.36).

     

基于L1/2正则化的三维人体姿态重构

针对从给定2D特征点的单目图像中重构对象的3D形状问题,本文在形状空间模型的基础上,结合L_1/2正则化和谱范数的性质提出一种基于L_1/2正则化的凸松弛方法,将形状空间模型的非凸求解问题通过凸松弛方法转化为凸规划问题;在采用ADMM算法对凸规划问题进行优化求解过程中,提出谱范数近端梯度算法保证解的正交性与稀疏性.利用所提的优化方法,基于形状空间模型和3D可变形状模型在卡内基梅隆大学运动捕获数据库上进行3D人体姿态重构,定性和定量对比实验结果表明本文方法均优于现有的优化方法,验证了所提方法的有效性.     

Benchmarking Least Squares Support Vector Machine Classifiers

In Support Vector Machines (SVMs), the solution of the classification problem is characterized by a (convex) quadratic programming (QP) problem. In a modified version of SVMs, called Least Squares SVM classifiers (LS-SVMs), a least squares cost function is proposed so as to obtain a linear set of equations in the dual space. While the SVM classifier has a large margin interpretation, the LS-SVM formulation is related in this paper to a ridge regression approach for classification with binary targets and to Fisher's linear discriminant analysis in the feature space. Multiclass categorization problems are represented by a set of binary classifiers using different output coding schemes. While regularization is used to control the effective number of parameters of the LS-SVM classifier, the sparseness property of SVMs is lost due to the choice of the 2-norm. Sparseness can be imposed in a second stage by gradually pruning the support value spectrum and optimizing the hyperparameters during the sparse approximation procedure. In this paper, twenty public domain benchmark datasets are used to evaluate the test set performance of LS-SVM classifiers with linear, polynomial and radial basis function (RBF) kernels. Both the SVM and LS-SVM classifier with RBF kernel in combination with standard cross-validation procedures for hyperparameter selection achieve comparable test set performances. These SVM and LS-SVM performances are consistently very good when compared to a variety of methods described in the literature including decision tree based algorithms, statistical algorithms and instance based learning methods. We show on ten UCI datasets that the LS-SVM sparse approximation procedure can be successfully applied.     

求解大规模问题的多核学习正则化路径算法

多核学习在处理异构、不规则和分布不平坦的样本数据时表现出良好的灵活性和可解释性.针对精确正则化路径算法难以处理大规模样本数据的问题,文中提出正则化路径近似算法.根据采样分布函数进行抽样,在原始核矩阵的基础上生成近似矩阵,同时在拉格朗日乘子向量中抽取对应行,实现矩阵乘积的近似计算,提高多核学习正则化路径的求解效率.最后分析多核学习正则化路径近似算法的近似误差界和计算复杂性.在标准数据集上的实验验证文中算法的合理性和计算效率.     

Active learning SVM with regularization path for image classification

In classification problems, many different active learning techniques are often adopted to find the most informative samples for labeling in order to save human labors. Among them, active learning support vector machine (SVM) is one of the most representative approaches, in which model parameter is usually set as a fixed default value during the whole learning process. Note that model parameter is closely related to the training set. Hence dynamic parameter is desirable to make a satisfactory learning performance. To target this issue, we proposed a novel algorithm, called active learning SVM with regularization path, which can fit the entire solution path of SVM for every value of model parameters. In this algorithm, we first traced the entire solution path of the current classifier to find a series of candidate model parameters, and then used unlabeled samples to select the best model parameter. Besides, in the initial phase of training, we constructed a training sample sets by using an improved K-medoids cluster algorithm. Experimental results conducted from real-world data sets showed the effectiveness of the proposed algorithm for image classification problems.     

基于海图和改进粒子群优化算法的AUV全局路径规划

针对AUV（自主水下机器人）在复杂条件海域做全局路径规划时面临的环境信息缺少,环境建模困难和常规算法复杂、求解能力弱等问题,提出一种基于海图和改进粒子群优化算法的全局路径规划方法．首先利用电子海图的先验知识建立3维静态环境模型,并构造路径航程、危险度和平滑函数;在粒子群优化算法中引入搜索因子和同性因子自适应地调整参数,并结合鱼群算法的“跳跃”过程提升算法的求解能力．同时建立安全违背度和选优规则以提高所规划路径的安全性．仿真实验结果表明,本文方法与传统粒子群算法和蚁群算法相比,规划出短航程、安全性高的全局路径的能力更强,可满足AUV在复杂海域航行时的全局路径规划需求．     

Enhanced A algorithms for multiple alignments: optimal alignments for several sequences and k-opt approximate alignments for large cases

The multiple alignment of the sequences of DNA and proteins is applicable to various important fields in molecular biology. Although the approach based on Dynamic Programming is well-known for this problem, it requires enormous time and space to obtain the optimal alignment. On the other hand, this problem corresponds to the shortest path problem and the A^* algorithm, which can efficiently find the shortest path with an estimator, is usable.

First, this paper directly applies the A^* algorithm to multiple sequence alignment problem with more powerful estimator in more than two-dimensional case and discusses the extensions of this approach utilizing an upper bound of the shortest path length and of modification of network structure. The algorithm to provide the upper bound is also proposed in this paper. The basic part of these results was originally shown in Ikeda and Imai [11]. This part is similar to the branch-and-bound techniques implemented in MSA program in Gupta et al. [6]. Our framework is based on the edge length transformation to reduce the problem to the shortest path problem, which is more suitable to generalizations to enumerating suboptimal alignments and parametric analysis as done in Shibuya and Imai [15–17]. By this enhanced A^* algorithm, optimal multiple alignments of several long sequences can be computed in practice, which is shown by computational results.

Second, this paper proposes a k-group alignment algorithm for multiple alignment as a practical method for much larger-size problem of, say multiple alignments of 50–100 sequences. A basic part of these results were originally presented in Imai and Ikeda [13]. In existing iterative improvement methods for multiple alignment, the so-called group-to-group two-dimensional dynamic programming has been used, and in this respect our proposal is to extend the ordinary two-group dynamic programming to a k-group alignment programming. This extension is conceptually straightforward, and here our contribution is to demonstrate that the k-group alignment can be implemented so as to run in a reasonable time and space under standard computing environments. This is established by generalizing the above A^* search approach. The k-group alignment method can be directly incorporated in existing methods such as iterative improvement algorithms [2, 5] and tree-based (iterative) algorithms [9]. This paper performs computational experiments by applying the k-group method to iterative improvement algorithms, and shows that our approach can find better alignments in reasonable time. For example, through larger-scale computational experiments here, 34 protein sequences with very high homology can be optimally 10-group aligned, and 64 sequences with high homology can be optimally 5-group aligned.