Sporadic model building for efficiency enhancement of the hierarchical BOA

Efficiency enhancement techniques—such as parallelization and hybridization—are among the most important ingredients of practical applications of genetic and evolutionary algorithms and that is why this research area represents an important niche of evolutionary computation. This paper describes and analyzes sporadic model building, which can be used to enhance the efficiency of the hierarchical Bayesian optimization algorithm (hBOA) and other estimation of distribution algorithms (EDAs) that use complex multivariate probabilistic models. With sporadic model building, the structure of the probabilistic model is updated once in every few iterations (generations), whereas in the remaining iterations, only model parameters (conditional and marginal probabilities) are updated. Since the time complexity of updating model parameters is much lower than the time complexity of learning the model structure, sporadic model building decreases the overall time complexity of model building. The paper shows that for boundedly difficult nearly decomposable and hierarchical optimization problems, sporadic model building leads to a significant model-building speedup, which decreases the asymptotic time complexity of model building in hBOA by a factor of to where n is the problem size. On the other hand, sporadic model building also increases the number of evaluations until convergence; nonetheless, if model building is the bottleneck, the evaluation slowdown is insignificant compared to the gains in the asymptotic complexity of model building. The paper also presents a dimensional model to provide a heuristic for scaling the structure-building period, which is the only parameter of the proposed sporadic model-building approach. The paper then tests the proposed method and the rule for setting the structure-building period on the problem of finding ground states of 2D and 3D Ising spin glasses.     

Semisupervised learning of hierarchical latent trait models for data visualization

Recently, we have developed the hierarchical generative topographic mapping (HGTM), an interactive method for visualization of large high-dimensional real-valued data sets. We propose a more general visualization system by extending HGTM in three ways, which allows the user to visualize a wider range of data sets and better support the model development process. 1) We integrate HGTM with noise models from the exponential family of distributions. The basic building block is the latent trait model (LTM). This enables us to visualize data of inherently discrete nature, e.g., collections of documents, in a hierarchical manner. 2) We give the user a choice of initializing the child plots of the current plot in either interactive, or automatic mode. In the interactive mode, the user selects "regions of interest", whereas in the automatic mode, an unsupervised minimum message length (MML)-inspired construction of a mixture of LTMs is employed. The unsupervised construction is particularly useful when high-level plots are covered with dense clusters of highly overlapping data projections, making it difficult to use the interactive mode. Such a situation often arises when visualizing large data sets. 3) We derive general formulas for magnification factors in latent trait models. Magnification factors are a useful tool to improve our understanding of the visualization plots, since they can highlight the boundaries between data clusters. We illustrate our approach on a toy example and evaluate it on three more complex real data sets.     

Variational learning of hierarchical infinite generalized Dirichlet mixture models and applications

Data clustering is a fundamental unsupervised learning task in several domains such as data mining, computer vision, information retrieval, and pattern recognition. In this paper, we propose and analyze a new clustering approach based on both hierarchical Dirichlet processes and the generalized Dirichlet distribution, which leads to an interesting statistical framework for data analysis and modelling. Our approach can be viewed as a hierarchical extension of the infinite generalized Dirichlet mixture model previously proposed in Bouguila and Ziou (IEEE Trans Neural Netw 21(1):107–122, 2010). The proposed clustering approach tackles the problem of modelling grouped data where observations are organized into groups that we allow to remain statistically linked by sharing mixture components. The resulting clustering model is learned using a principled variational Bayes inference-based algorithm that we have developed. Extensive experiments and simulations, based on two challenging applications namely images categorization and web service intrusion detection, demonstrate our model usefulness and merits.     

Transfer in variable-reward hierarchical reinforcement learning

Transfer learning seeks to leverage previously learned tasks to achieve faster learning in a new task. In this paper, we consider transfer learning in the context of related but distinct Reinforcement Learning (RL) problems. In particular, our RL problems are derived from Semi-Markov Decision Processes (SMDPs) that share the same transition dynamics but have different reward functions that are linear in a set of reward features. We formally define the transfer learning problem in the context of RL as learning an efficient algorithm to solve any SMDP drawn from a fixed distribution after experiencing a finite number of them. Furthermore, we introduce an online algorithm to solve this problem, Variable-Reward Reinforcement Learning (VRRL), that compactly stores the optimal value functions for several SMDPs, and uses them to optimally initialize the value function for a new SMDP. We generalize our method to a hierarchical RL setting where the different SMDPs share the same task hierarchy. Our experimental results in a simplified real-time strategy domain show that significant transfer learning occurs in both flat and hierarchical settings. Transfer is especially effective in the hierarchical setting where the overall value functions are decomposed into subtask value functions which are more widely amenable to transfer across different SMDPs.     

Applying semi-supervised learning in hierarchical multi-label classification

In classification problems with hierarchical structures of labels, the target function must assign labels that are hierarchically organized and it can be used either for single-label (one label per instance) or multi-label classification problems (more than one label per instance). In parallel to these developments, the idea of semi-supervised learning has emerged as a solution to the problems found in a standard supervised learning procedure (used in most classification algorithms). It combines labelled and unlabelled data during the training phase. Some semi-supervised methods have been proposed for single-label classification methods. However, very little effort has been done in the context of multi-label hierarchical classification. Therefore, this paper proposes a new method for supervised hierarchical multi-label classification, called HMC-RAkEL. Additionally, we propose the use of semi-supervised learning, self-training, in hierarchical multi-label classification, leading to three new methods, called HMC-SSBR, HMC-SSLP and HMC-SSRAkEL. In order to validate the feasibility of these methods, an empirical analysis will be conducted, comparing the proposed methods with their corresponding supervised versions. The main aim of this analysis is to observe whether the semi-supervised methods proposed in this paper have similar performance of the corresponding supervised versions.     

分层强化学习中的并行自动分层方法研究

为加快分层强化学习中任务层次结构的自动生成速度,提出了一种基于多智能体系统的并行自动分层方法,该方法以Sutton提出的Option分层强化学习方法为理论框架,首先由多智能体合作对状态空间进行并行探测并集中聚类产生状态子空间,然后多智能体并行学习生成各子空间上内部策略,最终生成Option.以二维有障碍栅格空间内两点间最短路径规划为任务背景给出了算法并进行了仿真实验和分析,结果表明,并行自动分层方法生成任务层次结构的速度明显快于以往的串行自动分层方法.本文的方法适用于空间探测、路径规划、追逃等类问题领域.     

Using localizing learning to improve supervised learning algorithms

Slow learning of neural-network function approximators can frequently be attributed to interference, which occurs when learning in one area of the input space causes unlearning in another area. To mitigate the effect of unlearning, this paper develops an algorithm that adjusts the weights of an arbitrary, nonlinearly parameterized network such that the potential for future interference during learning is reduced. This is accomplished by the reduction of a biobjective cost function that combines the approximation error and a term that measures interference. An analysis of the algorithm's convergence properties shows that learning with this algorithm reduces future unlearning. The algorithm can be used either during online learning or can be used to condition a network to have immunity from interference during a future learning stage. A simple example demonstrates how interference manifests itself in a network and how less interference can lead to more efficient learning. Simulations demonstrate how this new learning algorithm speeds up the training in various situations due to the extra cost function term.     

Using machine learning to support pedagogy in the arts

Teaching artistic skills to children presents a unique challenge: High-level creative and social elements of an artistic discipline are often the most engaging and the most likely to sustain student enthusiasm, but these skills rely on low-level sensorimotor capabilities, and in some cases rote knowledge, which are often tedious to develop. We hypothesize that computer-based learning can play a critical role in connecting “bottom-up” (sensorimotor-first) learning in the arts to “top-down” (creativity-first) learning, by employing machine learning and artificial intelligence techniques that can play the role of the sensorimotor expert. This approach allows learners to experience components of higher-level creativity and social interaction even before developing the prerequisite sensorimotor skills or academic knowledge.     

A spectral approach to learning structural variations in graphs

This paper shows how to construct a linear deformable model for graph structure by performing principal components analysis (PCA) on the vectorised adjacency matrix. We commence by using correspondence information to place the nodes of each of a set of graphs in a standard reference order. Using the correspondences order, we convert the adjacency matrices to long-vectors and compute the long-vector covariance matrix. By projecting the vectorised adjacency matrices onto the leading eigenvectors of the covariance matrix, we embed the graphs in a pattern-space. We illustrate the utility of the resulting method for shape-analysis.     

Automatic approximation of the marginal likelihood in non-Gaussian hierarchical models

Fitting of non-Gaussian hierarchical random effects models by approximate maximum likelihood can be made automatic to the same extent that Bayesian model fitting can be automated by the program BUGS. The word “automatic” means that the technical details of computation are made transparent to the user. This is achieved by combining a technique from computer science known as “automatic differentiation” with the Laplace approximation for calculating the marginal likelihood. Automatic differentiation, which should not be confused with symbolic differentiation, is mostly unknown to statisticians, and hence basic ideas and results are reviewed. The computational performance of the approach is compared to that of existing mixed-model software on a suite of datasets selected from the mixed-model literature.     

Inference in HIV dynamics models via hierarchical likelihood

HIV dynamical models are often based on non-linear systems of ordinary differential equations (ODE), which do not have an analytical solution. Introducing random effects in such models leads to very challenging non-linear mixed-effects models. To avoid the numerical computation of multiple integrals involved in the likelihood, a hierarchical likelihood (h-likelihood) approach, treated in the spirit of a penalized likelihood is proposed. The asymptotic distribution of the maximum h-likelihood estimators (MHLE) for fixed effects is given. The MHLE are slightly biased but the bias can be made negligible by using a parametric bootstrap procedure. An efficient algorithm for maximizing the h-likelihood is proposed. A simulation study, based on a classical HIV dynamical model, confirms the good properties of the MHLE. The method is applied to the analysis of a clinical trial.     

Learning and approximate inference in dynamic hierarchical models

A new variant of the dynamic hierarchical model (DHM) that describes a large number of parallel time series is presented. The separate series, which may be interdependent, are modeled through dynamic linear models (DLMs). This interdependence is included in the model through the definition of a ‘top-level’ or ‘average’ DLM. The model features explicit dependences between the latent states of the parallel DLMs and the states of the average model, and thus the many parallel time series are linked to each other. The combination of dependences within each time series and dependences between the different DLMs makes the computation time that is required for exact inference cubic in the number of parallel time series, however, which is unacceptable for practical tasks that involve large numbers of parallel time series. Therefore, two methods for fast, approximate inference are proposed: a variational approximation and a factorial approach. Under these approximations, inference can be performed in linear time, and it still features exact means. Learning is implemented through a maximum likelihood (ML) estimation of the model parameters. This estimation is realized through an expectation maximization (EM) algorithm with approximate inference in the E-step. Examples of learning and forecasting on two data sets show that the addition of direct dependences has a ‘smoothing’ effect on the evolution of the states of the individual time series, and leads to better prediction results. The use of approximate instead of exact inference is further shown not to lead to inferior results on either data set.     

Using computers to teach structural analysis

Structural analysis has been radically affected by the advent of computers over the last 25 years. The need to update teaching methods and the opportunities to do so have accelerated with the now widespread availability of cheap microcimputers. Theory of structures, as taught at the Unoversity of Bristol, is based upon fundamental energy theorems, in particular the principle of virtual work, and leads to matrix structural analysis and finite element methods. Computer programming is an integral part of the course together with an introduction to the use of standard structural analysis programs. A structures teaching program, with interactive graphics facilities, is used to develop skill at qualitative understanding of structural behaviour. Experience of employing these teaching methods is discussed in the paper.     

Using narratives in conferences to improve the CMC learning environment

Abstract This paper reports on the use of short stories in Internet discussions to promote student learning. It describes off-campus teacher education students CMC discussions of short stories concerning issues in human development. The content of students' discussions is analysed, as is their perceptions of the value of the discussion stories. The results indicate that the use of narratives can improve the social environment of online conferences and contribute to collaborative student learning.     

Control models in computer-assisted learning

Abstract: This paper is concerned with structural models of what have come to be called Intelligent CAL systems. It proposes and examines such models in the light of the needs of different types of CAL systems, particularly those systems which offer learner control. Based on the five-circle model proposed by Tim O' Shea and others, a more general 'figure of eight' model is put forward which accords with certain of the ideas suggested by Gordon Pask concerning the architecture of learning systems.     

A new learning algorithm for the hierarchical structure learning automata operating in the nonstationary S-model random environment

An extended algorithm of the relative reward strength algorithm is proposed. It is shown that the proposed algorithm ensures the convergence with probability I to the optimal path under the certain type of nonstationary environment. Several computer simulation results confirm the effectiveness of the proposed algorithm.     

Using models to improve stereo reconstruction

The authors propose the combination of photometric and stereometric information to solve the stereo vision problem in the case of a man-made environment. A method to introduce geometrical models in the stereo process in order to improve the accuracy of the depth measurement and to extend the depth map to points where no measurements have been made is presented. This method is based on a parameterization of the object surfaces and relies on a systematic comparison of the result of a stereo process with the photometric (or gray-level) image. The proposed approach improves the accuracy of the stereo information and its density by introducing a hypothesis on the object surfaces. Two kinds of hypothesis are developed: planar and quadratic objects. Reconstructions of complex scenes are given     

Application of a Bayesian hierarchical model to system identification of structural parameters

System identification (SI) is a key step in the process of evaluating the status or condition of physical structures and of devising a scheme to sustain their structural integrity. SI is typically carried out by updating the current structural parameters used in a computational model based on the measured responses of the structure. In the deterministic approach, SI has been conducted by minimizing the error between calculated responses (using the computational model) and measured responses. However, this brought about unexpected numerical issues such as the ill-posedness of the inverse problem, which likely results in non-uniqueness of the solutions or non-stability of the optimization operation. To address this issue, Bayesian updating enhanced with an advanced modeling technique such as a Bayesian network (BN) was introduced. However, it remained challenging to construct the quantitative relations between structural parameters and responses (which are placed in conditional probability tables: CPTs) in a BN setting. Therefore, this paper presented a novel approach for conducting the SI of structural parameters using a Bayesian hierarchical model (BHM) technique. Specifically, the BHM was integrated into the Bayesian updating framework instead of utilizing a BN. The primary advantage of the proposed approach is that it enables use of the existing relations between structural parameters and responses. This can save the computational effort needed to construct CPTs to relate the parameter and response nodes. The proposed approach was applied to two experimental structures and a realistic soil-slope structure. The results showed that the proposed SI approach provided good agreement with actual measurements and also gave relatively robust estimation results compared to the traditional approach of maximum likelihood estimation. Hence, the proposed approach is expected to be utilized to address SI problems for complex structural systems and its computational model when integrated with a statistical regression approach or with various machine learning algorithms.     

Compiler support for task scheduling in hierarchical execution models

Algorithms from scientific computing often exhibit a two-level parallelism based on potential method parallelism and potential system parallelism. We consider the parallel implementation of those algorithms on distributed memory machines. The two-level potential parallelism of algorithms is expressed in a specification consisting of an upper level hierarchy of multiprocessor tasks each of which has an internal structure of uniprocessor tasks. To achieve an optimal parallel execution time, the parallel execution of such a program requires an optimal scheduling of the multiprocessor tasks and an appropriate treatment of uniprocessor tasks. For an important subclass of structured method parallelism we present a scheduling methodology which takes data redistributions between multiprocessor tasks into account. As costs we use realistic parallel runtimes. The scheduling methodology is designed for an integration into a parallel compiler tool. We illustrate the multitask scheduling by several examples from numerical analysis.