Search

Brain atlases enable the mapping of labeled cells and newly defined projections from different brains onto a standard coordinate system. We address two fundamental issues in the construction and use of atlases. First, expert neuroanatomists ascertain the fine-scale structure of brain tissue, the ”texture” formed by cell structure and organization, to define cytoarchitectural borders. Can this approach be automated, so that a machine can locate landmark structures and automatically align new brains to a reference atlas? We achieve this goal with a robust procedure that is driven by machine learning and bootstrapped from brains annotated by experts. Second, can one construct a brain atlas that is active, i.e., augmented and improved with each use? We show that the alignment of new brains to a reference atlas can continuously refine the coordinate system and associated variance. We apply this approach to the adult murine brainstem and achieve a precise alignment of projections in cytoarchitecturally ill-defined regions across brains from different animals.

We present a system for localizing sound sources in a room with several ad-hoc microphone arrays. Each circular array performs direction of arrival (DOA) estimation independently using commercial software. The DOAs are fed to a fusion center, concatenated, and used to perform the localization based on two proposed methods, which require only few labeled source locations (anchor points) for training. The first proposed method is based on principal component analysis (PCA) of the observed DOA and does not require any knowledge of anchor points. The array cluster can then perform localization on a manifold defined by the PCA of concatenated DOAs over time. The second proposed method performs localization using an affine transformation between the DOA vectors and the room manifold. The PCA has fewer requirements on the training sequence, but is less robust to missing DOAs from one of the arrays. The methods are demonstrated with five IoT 8-microphone circular arrays, placed at unspecified fixed locations in an office. Both the PCA and the affine method can easily map out a rectangle based on a few anchor points with similar accuracy. The proposed methods provide a step towards monitoring activities in a smart home and require little installation effort as the array locations are not needed., Comment: IN press, IEEE Internet of Things Journal

The objective of this paper is to demonstrate how the boosting approach can be used to define a data-driven board Balanced Scorecard (BSC) with applications to S&P 500 companies. Using Adaboost, we can generate alternating decision trees (ADTs) that explain the relationship between corporate governance variables, and firm performance. We also propose an algorithm to build a representative ADT based on cross-validation experiments. The representative ADT selects the most important indicators for the board BSC. As a final result, we propose a partially automated strategic planning system combining Adaboost with the board BSC for board-level or investment decisions.

This article describes an algorithm for short-term technical trading. The algorithm was tested in the context of the Penn-Lehman Automated Trading (PLAT) competition. The algorithm is based on three main ideas. The first idea is to use a combination of technical indicators to predict the daily trend of the stock, the combination is optimized using a boosting algorithm. The second idea is to use the constant rebalanced portfolios within the day in order to take advantage of market volatility without increasing risk. The third idea is to use limit orders rather than market orders in order to minimize transaction costs.

The traditional k-NN classification rule predicts a label based on the most common label of the k nearest neighbors (the plurality rule). It is known that the plurality rule is optimal when the number of examples tends to infinity. In this paper we show that the plurality rule is sub-optimal when the number of labels is large and the number of examples is small. We propose a simple k-NN rule that takes into account the labels of all of the neighbors, rather than just the most common label. We present a number of experiments on both synthetic datasets and real-world datasets, including MNIST and SVHN. We show that our new rule can achieve lower error rates compared to the majority rule in many cases.

Robust real time tracking is a requirement for many emerging applications. Many of these applications must track objects even as their appearance changes. Training classifiers online has become an effective approach for dealing with variability in object appearance. Classifiers can learn and adapt to changes online at the cost of additional runtime computation. In this paper, we propose a FPGA accelerated design of an online boosting algorithm that uses multiple classifiers to track and recover objects in real time. Our algorithm uses a novel method for training and comparing pose-specific classifiers along with adaptive tracking classifiers. Our FPGA accelerated design is able to track at 60 frames per second while concurrently evaluating 11 classifiers. This represents a 30× speed up over a CPU based software implementation. It also demonstrates tracking accuracy at state of the art levels on a standard set of videos.

Hints are sometimes used in online learning system to help students when they are having difficulties. However, in all of the systems we are aware of, the hints are fixed ahead of time and do not depend on the unsuccessful attempts the student has already made. This severely limits the effectiveness of the hints.We have developed an alternative system for giving hints to students. The main difference is that the system allows an instructor to send a hint to a student after the student has made several attempts to solve the problem and failed. After analyzing the student's mistakes, the instructor is better able to understand the problem in the student's thinking and send them a more helpful hint.We have deployed this system in a probability and statistics course with 176 students. We have demonstrated the superiority of the new hints methodology over the traditional one.The limiting factor on the effectiveness of our system is the amount of manual labor required to send each hint. This is the main obstacle we see in scaling this approach to larger classes and to MOOCs. We are currently exploring several approaches for addressing this problem: 1) Letting students send hints to their peers. 2) Creating hint libraries. 3) Using machine learning methods to automate the process of mapping student mistakes to the most relevant hint.

In the first part of the paper we consider the problem of dynamically apportioning resources among a set of options in a worst-case on-line framework. The model we study can be interpreted as a broad, abstract extension of the well-studied on-line prediction model to a general decision-theoretic setting. We show that the multiplicative weight-update Littlestone–Warmuth rule can be adapted to this model, yielding bounds that are slightly weaker in some cases, but applicable to a considerably more general class of learning problems. We show how the resulting learning algorithm can be applied to a variety of problems, including gambling, multiple-outcome prediction, repeated games, and prediction of points in Rn. In the second part of the paper we apply the multiplicative weight-update technique to derive a new boosting algorithm. This boosting algorithm does not require any prior knowledge about the performance of the weak learning algorithm. We also study generalizations of the new boosting algorithm to the problem of learning functions whose range, rather than being binary, is an arbitrary finite set or a bounded segment of the real line.

We analyze the “query by committee” algorithm, a method for filtering informative queries from a random stream of inputs. We show that if the two-member committee algorithm achieves information gain with positive lower bound, then the prediction error decreases exponentially with the number of queries. We show that, in particular, this exponential decrease holds for query learning of perceptrons.

We present an algorithm for improving the accuracy of algorithms for learning binary concepts. The improvement is achieved by combining a large number of hypotheses, each of which is generated by training the given learning algorithm on a different set of examples. Our algorithm is based on ideas presented by Schapire and represents an improvement over his results, The analysis of our algorithm provides general upper bounds on the resources required for learning in Valiant′s polynomial PAC learning framework, which are the best general upper bounds known today. We show that the number of hypotheses that are combined by our algorithm is the smallest number possible. Other outcomes of our analysis are results regarding the representational power of threshold circuits, the relation between learnability and compression, and a method for parallelizing PAC learning algorithms. We provide extensions of our algorithms to cases in which the concepts are not binary and to the case where the accuracy of the learning algorithm depends on the distribution of the instances.

We present RIFFA, a reusable integration framework for FPGA accelerators. RIFFA provides communication and synchronization for FPGA accelerated software using a standard interface. Our goal is to expand the use of FPGAs as an acceleration platform by releasing, as open source, a no cost framework that easily integrates software on traditional CPUs with FPGA based IP cores, over PCIe, with minimal custom configuration. RIFFA requires no specialized hardware or fee licensed IP cores. It can be deployed on common Linux workstations with a PCIe bus and has been tested on two different Linux distributions using Xilinx FPGAs.

In this work, a novel occlusion detection algorithm using online learning is proposed for video applications. Each frame of a video is considered as a time-step for which pixels are classified as being either occluded or non-occluded. The Hedge algorithm is employed to determine weights for a set of experts, each of which is tuned to detect a specific type of occlusion boundary. In contrast to previous training-based methods, the proposed algorithm does not require any training, and has a runtime linear with respect to the number of experts considered. Detection performance is excellent on novel video sequences for which training data does not exist. In addition, the proposed algorithm is easily extended to provide classification results supplementary to detection. We demonstrate results on a series of challenging video sequences including a dataset of hand-labelled occlusion boundaries.

The solution of sparse linear systems, a fundamental and resource-intensive task in scientific computing, can be approached through multiple algorithms. Using an algorithm well adapted to characteristics of the task can significantly enhance the performance, such as reducing the time required for the operation, without compromising the quality of the result. However, the “best” solution method can vary even across linear systems generated in course of the same PDE-based simulation, thereby making solver selection a very challenging problem. In this paper, we use a machine learning technique, Alternating Decision Trees (ADT), to select efficient solvers based on the properties of sparse linear systems and runtime-dependent features, such as the stages of simulation. We demonstrate the effectiveness of this method through empirical results over linear systems drawn from computational fluid dynamics and magnetohydrodynamics applications. The results also demonstrate that using ADT can resolve the problem of “over-fitting”, which occurs when limited amount of data is available.

Massive quantities of digital data are being collected in every aspect of modern life. Examples include Personal photos and videos, biological and medical images and recordings from sensor arrays. To transform these massive data streams into useful information we use a sequence of "winnowing" stages. Each step reduces the size of the data by an order of magnitude; extracting the wheat form the chaff. In this talk I will describe this approach in a variety of contexts, ranging from the analysis of genetic pathways in fruit-fly embryos and C-Elegans worms to counting birds and helping elderly people living alone keep in touch with their family and caregivers.

We have built a system that engages naive users in an audio-visual interaction with a computer in an unconstrained public space. We combine audio source localization techniques with face detection algorithms to detect and track the user throughout a large lobby. The sensors we use are an ad-hoc microphone array and a PTZ camera. To engage the user, the PTZ camera turns and points at sounds made by people passing by. From this simple pointing of a camera, the user is made aware that the system has acknowledged their presence. To further engage the user, we develop a face classification method that identifies and then greets previously seen users. The user can interact with the system through a simple hot-spot based gesture interface. To make the user interactions with the system feel natural, we utilize reconfigurable hardware, achieving a visual response time of less than 100ms. We rely heavily on machine learning methods to make our system self-calibrating and adaptive.

Background Identifying the catalytic residues in enzymes can aid in understanding the molecular basis of an enzyme's function and has significant implications for designing new drugs, identifying genetic disorders, and engineering proteins with novel functions. Since experimentally determining catalytic sites is expensive, better computational methods for identifying catalytic residues are needed. Results We propose ResBoost, a new computational method to learn characteristics of catalytic residues. The method effectively selects and combines rules of thumb into a simple, easily interpretable logical expression that can be used for prediction. We formally define the rules of thumb that are often used to narrow the list of candidate residues, including residue evolutionary conservation, 3D clustering, solvent accessibility, and hydrophilicity. ResBoost builds on two methods from machine learning, the AdaBoost algorithm and Alternating Decision Trees, and provides precise control over the inherent trade-off between sensitivity and specificity. We evaluated ResBoost using cross-validation on a dataset of 100 enzymes from the hand-curated Catalytic Site Atlas (CSA). Conclusion ResBoost achieved 85% sensitivity for a 9.8% false positive rate and 73% sensitivity for a 5.7% false positive rate. ResBoost reduces the number of false positives by up to 56% compared to the use of evolutionary conservation scoring alone. We also illustrate the ability of ResBoost to identify recently validated catalytic residues not listed in the CSA.

We present a camera pointing system controlled by real-time calculations of sound source locations from a microphone array. Traditional audio localization techniques require explicit estimates of the spatial coordinates for each microphone in the array. In addition, positional information for the camera is needed to use such techniques to drive a camera pointing system. Sometimes this positioning can be done by hand, but for large aperture microphone arrays with many elements this is impractical. We show that in this setting, where elements are placed in an ad-hoc manner, explicitly learning the microphone positions is an unnecessary step. We give a calibration method whose focus is learning the mapping from time delays between pairs of microphones to the associated pan and tilt a PTZ-camera should be given to point at. This curtails the need to explicitly learn the microphone and camera positions. We use this method to calibrate a real-time camera pointing system used by the UCSD interactive display.

The advance of fluorescent tagging and of confocal microscopy is allowing biologists to image biochemical processes at a level of detail that was unimaginable just a few years ago. However, as the analysis of these images is done mostly by hand, there is a severe bottleneck in transforming these images into useful quantitative data that can be used to evaluate mathematical models. One of the inherent challenges involved in automating this transformation is that image data is highly variable. This requires a recalibration of the image processing algorithms for each experiment. We use machine learning methods to enable the experimentalist to calibrate the image processing methods without having any knowledge of how these methods work. This, we believe, will allow the rapid integration of computer vision methods with confocal microscopy and open the way to the development of quantitative spatial models of cellular processes. For more information, see http://seed.ucsd.edu/ yfreund/NewHomePage/ Applications/Biomedical Imaging.html

A system for scoring images based on the likelihood of containing crystalline material is described. A simulation carried out on a real set of crystallization images demonstrates the utility of such a system in high-throughput environments by substantially reducing the manual workload necessary to detect crystals for X-ray screening., The ability of computers to learn from and annotate large databases of crystallization-trial images provides not only the ability to reduce the workload of crystallization studies, but also an opportunity to annotate crystallization trials as part of a framework for improving screening methods. Here, a system is presented that scores sets of images based on the likelihood of containing crystalline material as perceived by a machine-learning algorithm. The system can be incorporated into existing crystallization-analysis pipelines, whereby specialists examine images as they normally would with the exception that the images appear in rank order according to a simple real-valued score. Promising results are shown for 319 112 images associated with 150 structures solved by the Joint Center for Structural Genomics pipeline during the 2006–2007 year. Overall, the algorithm achieves a mean receiver opera­ting characteristic score of 0.919 and a 78% reduction in human effort per set when considering an absolute score cutoff for screening images, while incurring a loss of five out of 150 structures.

Combinatorial transcriptional fluorescent in situ hybridization (CT-FLSH) is a confocal fluorescence imaging technique enabling the detection of multiple active transcription units in individual interphase diploid nuclei. As improved combinatorial labeling methods allow simultaneous measurement of gene activities to expand from five genes in a single embryo or tissue section to upward of twenty genes, transforming image stacks into usable data becomes an increasingly labor in tensive task, in this paper we describe our progress towards a method for the computational analysis of confocal images from Drosophila melanogastar that involves the segmentation of the cell nuclei and of nascent transcription sites of specific genes. Using image processing and machine learning algorithms, we allow experimentalists to reiteratively tune and improve the analysis system to reflect biological reality

We present a novel classification-based method for learning to predict gene regulatory response. Our approach is motivated by the hypothesis that in simple organisms such as Saccharomyces cerevisiae, we can learn a decision rule for predicting whether a gene is up- or down-regulated in a particular experiment based on (1) the presence of binding site subsequences (``motifs'') in the gene's regulatory region and (2) the expression levels of regulators such as transcription factors in the experiment (``parents''). Thus our learning task integrates two qualitatively different data sources: genome-wide cDNA microarray data across multiple perturbation and mutant experiments along with motif profile data from regulatory sequences. We convert the regression task of predicting real-valued gene expression measurement to a classification task of predicting +1 and -1 labels, corresponding to up- and down-regulation beyond the levels of biological and measurement noise in microarray measurements. The learning algorithm employed is boosting with a margin-based generalization of decision trees, alternating decision trees. This large-margin classifier is sufficiently flexible to allow complex logical functions, yet sufficiently simple to give insight into the combinatorial mechanisms of gene regulation. We observe encouraging prediction accuracy on experiments based on the Gasch S. cerevisiae dataset, and we show that we can accurately predict up- and down-regulation on held-out experiments. Our method thus provides predictive hypotheses, suggests biological experiments, and provides interpretable insight into the structure of genetic regulatory networks., 8 pages, 4 figures, presented at Twelfth International Conference on Intelligent Systems for Molecular Biology (ISMB 2004), supplemental website: http://www.cs.columbia.edu/compbio/geneclass

Background. One of the best known results in information theory says that a data sequence x 1,x 2,...,x n produced by independent random draws from a fixed distribution P over a discrete domain can be compressed into a binary sequence, or code whose expected length is at most nH(P)+1 bits, where H(P) = − ∑ i P i logP i is the entropy of P. It is also known that this compression is near optimal as nH(P) is the smallest achievable expected number of code bits.

We consider the following setting of the (supervised) learning problem. A sequence of input data x/sub 1/,...,x/sub t/,..., is given, one by one, and the goal is to predict the corresponding outputs y/sub 1/,...,y/sub t/,.... Our proposed solution for the supervised learning problem is Bayesian, and the contribution of this work lies in determining the optimal way to choose the Bayesian "prior" for the supervised learning problem, and observing the strong sequential, non-anticipating, structure of the resulting universal predictor.

We propose a new boosting algorithm. This boosting algorithm is an adaptive version of the boost by majority algorithm and combines bounded goals of the boost by majority algorithm with the adaptivity of AdaBoost.

We study online learning algorithms that predict by com- bining the predictions of several subordinate prediction a lgorithms, sometimes called "experts." These simple algorithms belon g to the multiplicative weights family of algorithms. The performance of these algorithms degrades only logarithmically with the number of experts, making them particularly useful in applications where the number of experts is very large. However, in applications such as text categorization, it is often natural for some of the ex perts to abstain from making predictions on some of the instances. We show how to transform algorithms that assume that all experts are always awake to algorithms that do not require this assumption. We also show how to derive corresponding loss bounds. Our method is very general, and can be applied to a large family of online learning algorithms. We also give applications to various prediction models including decision graphs and "switching" experts.

In this paper we study learning algorithms for environments which are changing over time. Unlike most previous work, we are interested in the case where the changes might be rapid but their “direction” is relatively constant. We model this type of change by assuming that the target distribution is changing continuously at a constant rate from one extreme distribution to another. We show in this case how to use a simple weighting scheme to estimate the error of an hypothesis, and using this estimate, to minimize the error of the prediction.

This paper describes new and efficient algorithms for learning deterministic finite automata. Our approach is primarily distinguished by two features: (1) the adoption of an average-case setting to model the “typical” labeling of a finite automaton, while retaining a worst-case model for the underlying graph of the automaton, along with (2) a learning model in which the learner is not provided with the means to experiment with the machine, but rather must learn solely by observing the automaton's output behavior on a random input sequence. The main contribution of this paper is in presenting the first efficient algorithms for learning non-trivial classes of automata in an entirely passive learning model. We adopt an on-line learning model in which the learner is asked to predict the output of the next state, given the next symbol of the random input sequence; the goal of the learner is to make as few prediction mistakes as possible. Assuming the learner has a means of resetting the target machine to a fixed start state, we first present an efficient algorithm that makes an expected polynomial number of mistakes in this model. Next, we show how this first algorithm can be used as a subroutine by a second algorithm that also makes a polynomial number of mistakes even in the absence of a reset. Along the way, we prove a number of combinatorial results for randomly labeled automata. We also show that the labeling of the states and the bits of the input sequence need not be truly random, but merely semi - random . Finally, we discuss an extension of our results to a model in which automata are used to represent distributions over binary strings.

We study efficient algorithms for solving the following problem, which we call the switching distributions learning problem. A sequence S = 1 2 : : : n, over a finite alphabet Σ is generated in the following way. The sequence is a concatenation of K runs, each of which is a consecutive subsequence. Each run is generated by independent random draws from a distribution ~pi over Σ, where ~ pi is an element in a set of distributions f~p1; : : : ; ~pNg. The learning algorithm is given this sequence and its goal is to find approximations of the distributions ~p1; : : : ; ~pN , and give an approximate segmentation of the sequence into its constituting runs. We give an efficient algorithm for solving this problem and show conditions under which the algorithm is guaranteed to work with high probability.