2369815
Multiclass boosting with repartitioning
A multiclass classification problem can be reduced to a collection of binary problems with the aid of a coding matrix. The quality of the final solution, which is an ensemble of base classifiers learned on the binary problems, is affected by both the performance of the base learner and the error-correcting ability of the coding matrix. A coding matrix with strong error-correcting ability may not be overall optimal if the binary problems are too hard for the base learner. Thus a trade-off between error-correcting and base learning should be sought. In this paper, we propose a new multiclass boosting algorithm that modifies the coding matrix according to the learning ability of the base learner. We show experimentally that our algorithm is very efficient in optimizing the multiclass margin cost, and outperforms existing multiclass algorithms such as AdaBoost.ECC and one-vs-one. The improvement is especially significant when the base learner is not very powerful.
6590646
Emergent Specialization in Swarm Systems
Distributed learning is the learning process of multiple autonomous agents in a varying environment, where each agent has only partial information about the global task. In this paper, we investigate the influence of different reinforcement signals (local and global) and team diversity (homogeneous and heterogeneous agents) on the learned solutions. We compare the learned solutions with those obtained by systematic search in a simple case study in which pairs of agents have to collaborate in order to solve the task without any explicit communication. The results show that policies which allow teammates to specialize find an adequate diversity of the team and, in general, achieve similar or better performances than policies which force homogeneity. However, in this specific case study, the achieved team performances appear to be independent of the locality or globality of the reinforcement signal.
8054797
Infinite Ensemble Learning with Support Vector Machines
Ensemble learning algorithms such as boosting can achieve better performance by averaging over the predictions of base hypotheses. However, existing algorithms are limited to combining only a finite number of hypotheses, and the generated ensemble is usually sparse. It is not clear whether we should construct an ensemble classifier with a larger or even infinite number of hypotheses. In addition, constructing an infinite ensemble itself is a challenging task. In this paper, we formulate an infinite ensemble learning framework based on SVM. The framework can output an infinite and nonsparse ensemble, and can be used to construct new kernels for SVM as well as to interpret some existing ones. We demonstrate the framework with a concrete application, the stump kernel, which embodies infinitely many decision stumps. The stump kernel is simple, yet powerful. Experimental results show that SVM with the stump kernel is usually superior than boosting, even with noisy data.
14092393
Lazy Approximation for Solving Continuous Finite-Horizon MDPs
Solving Markov decision processes (MDPs) with continuous state spaces is a challenge due to, among other problems. the well-known curse of dimensionality. Nevertheless, numerous real-world applications such as transportation planning and telescope observation scheduling exhibit a critical dependence on continuous states. Current approaches to continuous-state MDPs include discretizing their transition models. In this paper, we propose and study an alternative, discretization-free approach we call lazy approximation. Empirical study shows that lazy approximation performs much better than discretization, and we successfully applied this new technique to a more realistic planetary rover planning problem.
207159693
PAC model-free reinforcement learning
For a Markov Decision Process with finite state (size S) and action spaces (size A per state), we propose a new algorithm---Delayed Q-Learning. We prove it is PAC, achieving near optimal performance except for Õ(SA) timesteps using O(SA) space, improving on the Õ(S2 A) bounds of best previous algorithms. This result proves efficient reinforcement learning is possible without learning a model of the MDP from experience. Learning takes place from a single continuous thread of experience---no resets nor parallel sampling is used. Beyond its smaller storage and experience requirements, Delayed Q-learning's per-experience computation cost is much less than that of previous PAC algorithms.
28610395
A Path-Based Approach for Efficient Structural Join with Not-Predicates
There has been much research on XML query processing. However, there has been little work on the evaluation of XML queries involving not-predicates. Such queries are useful and common in many real-life applications. In this paper, we present a model called XQuery tree to model queries involving not-predicates and describe a path-based method to evaluate such queries efficiently. A comprehensive set of experiments is carried out to demonstrate the effectiveness and efficiency of the proposed solution.
14467396
Image-based streamline generation and rendering
Seeding streamlines in 3D flow fields without considering their projections in screen space can produce visually cluttered rendering results. Streamlines will overlap or intersect with each other in the output image, which makes it difficult for the user to perceive the underlying flow structure. This paper presents a method to control the seeding and generation of streamlines in image space to avoid visual cluttering and allow a more flexible exploration of flow fields. In our algorithm, 2D images with depth maps generated by a variety of visualization techniques can be used as input from which seeds are placed and streamlines are generated. The density and rendering styles of streamlines can be flexibly controlled based on various criteria to improve visual clarity. With our image space approach, it is straightforward to implement the level of detail rendering, depth peeling, and stylized rendering of streamlines to allow for more effective visualization of 3D flow fields.
15147687
GAPWM: a genetic algorithm method for optimizing a position weight matrix
MOTIVATION
Position weight matrices (PMWs) are simple models commonly used in motif-finding algorithms to identify short functional elements, such as cis-regulatory motifs, on genes. When few experimentally verified motifs are available, estimation of the PWM may be poor. The resultant PWM may not reliably discriminate a true motif from a false one. While experimentally identifying such motifs remains time-consuming and expensive, low-resolution binding data from techniques such as ChIP-on-chip and ChIP-PET have become available. We propose a novel but simple method to improve a poorly estimated PWM using ChIP data.


METHODOLOGY
Starting from an existing PWM, a set of ChIP sequences, and a set of background sequences, our method, GAPWM, derives an improved PWM via a genetic algorithm that maximizes the area under the receiver operating characteristic (ROC) curve. GAPWM can easily incorporate prior information such as base conservation. We tested our method on two PMWs (Oct4/Sox2 and p53) using three recently published ChIP data sets (human Oct4, mouse Oct4 and human p53).


RESULTS
GAPWM substantially increased the sensitivity/specificity of a poorly estimated PWM and further improved the quality of a good PWM. Furthermore, it still functioned when the starting PWM contained a major error. The ROC performance of GAPWM compared favorably with that of MEME and others. With increasing availability of ChIP data, our method provides an alternative for obtaining high-quality PWMs for genome-wide identification of transcription factor binding sites.


AVAILABILITY
The C source code and all data used in this report are available at http://dir.niehs.nih.gov/dirbb/gapwm.


SUPPLEMENTARY INFORMATION
Supplementary data are available at Bioinformatics online.