Efficient non-greedy optimization of decision trees

Decision trees and randomized forests are widely used in computer vision and machine learning. Standard algorithms for decision tree induction optimize the split functions one node at a time according to some splitting criteria. This greedy procedure often leads to suboptimal trees. In this paper, we present an algorithm for optimizing the split functions at all levels of the tree jointly with the leaf parameters, based on a global objective. We show that the problem of finding optimal linear-combination (oblique) splits for decision trees is related to structured prediction with latent variables, and we formulate a convex-concave upper bound on the tree’s empirical loss. The run-time of computing the gradient of the proposed surrogate objective with respect to each training exemplar is quadratic in the the tree depth, and thus training deep trees is feasible. The use of stochastic gradient descent for optimization enables effective training with large datasets. Experiments on several classification benchmarks demonstrate that the resulting non-greedy decision trees outperform greedy decision tree baselines.

Representational Distance Learning for Deep Neural Networks

We propose representational distance learning (RDL), a technique that allows transferring knowledge from a model of arbitrary type to a deep neural network (DNN). This method seeks to maximize the similarity between the representational dissimilarity, or distance, matrices (RDMs) of a model with desired knowledge, the teacher, and a DNN currently being trained, the student. This knowledge transfer is performed using auxiliary error functions. This allows DNNs to simultaneously learn from a teacher model and learn to perform some task within the framework of backpropagation. We test the use of RDL for knowledge distillation, also known as model compression, from a large teacher DNN to a small student DNN using the MNIST and CIFAR-10 datasets. Also, we test the use of RDL for knowledge transfer between tasks using the CIFAR-10 and CIFAR-100 datasets. For each test, RDL significantly improves performance when compared to traditional backpropagation alone and performs similarly to, or better than, recently proposed methods for model compression and knowledge transfer.

Document Context Language Models

Text documents are structured on multiple levels of detail: individual words are related by syntax, and larger units of text are related by discourse structure. Existing language models generally fail to account for discourse structure, but it is crucial if we are to have language models that reward coherence and generate coherent texts. We present and empirically evaluate a set of multi-level recurrent neural network language models, called Document-Context Language Models (DCLMs), which incorporate contextual information both within and beyond the sentence. In comparison with word-level recurrent neural network language models, the DCLMs obtain slightly better predictive likelihoods, and considerably better assessments of document coherence.

Software Agents with Concerns of their Own

We claim that it is possible to have artificial software agents for which their actions and the world they inhabit have first-person or intrinsic meanings. The first-person or intrinsic meaning of an entity to a system is defined as its relation with the system’s goals and capabilities, given the properties of the environment in which it operates. Therefore, for a system to develop first-person meanings, it must see itself as a goal-directed actor, facing limitations and opportunities dictated by its own capabilities, and by the properties of the environment. The first part of the paper discusses this claim in the context of arguments against and proposals addressing the development of computer programs with first-person meanings. A set of definitions is also presented, most importantly the concepts of cold and phenomenal first-person meanings. The second part of the paper presents preliminary proposals and achievements, resulting of actual software implementations, within a research approach that aims to develop software agents that intrinsically understand their actions and what happens to them. As a result, an agent with no a priori notion of its goals and capabilities, and of the properties of its environment acquires all these notions by observing itself in action. The cold first-person meanings of the agent’s actions and of what happens to it are defined using these acquired notions. Although not solving the full problem of first-person meanings, the proposed approach and preliminary results allow us some confidence to address the problems yet to be considered, in particular the phenomenal aspect of first-person meanings.

Bayesian Analysis of Dynamic Linear Topic Models

In dynamic topic modeling, the proportional contribution of a topic to a document depends on the temporal dynamics of that topic’s overall prevalence in the corpus. We extend the Dynamic Topic Model of Blei and Lafferty (2006) by explicitly modeling document level topic proportions with covariates and dynamic structure that includes polynomial trends and periodicity. A Markov Chain Monte Carlo (MCMC) algorithm that utilizes Polya-Gamma data augmentation is developed for posterior inference. Conditional independencies in the model and sampling are made explicit, and our MCMC algorithm is parallelized where possible to allow for inference in large corpora. To address computational bottlenecks associated with Polya-Gamma sampling, we appeal to the Central Limit Theorem to develop a Gaussian approximation to the Polya-Gamma random variable. This approximation is fast and reliable for parameter values relevant in the text mining domain. Our model and inference algorithm are validated with multiple simulation examples, and we consider the application of modeling trends in PubMed abstracts. We demonstrate that sharing information across documents is critical for accurately estimating document-specific topic proportions. We also show that explicitly modeling polynomial and periodic behavior improves our ability to predict topic prevalence at future time points.

A New Framework for Random Effects Models

A different general philosophy, to be called Full Randomness (FR), for the analysis of random effects models is presented, involving a notion of reducing or preferably eliminating fixed effects, at least formally. For example, under FR applied to a repeated measures model, even the number of repetitions would be modeled as random. It is argued that in many applications such quantities really are random, and that recognizing this enables the construction of much richer, more probing analyses. Methodology for this approach will be developed here, and suggestions will be made for the broader use of the approach. It is argued that even in settings in which some factors are fixed by the experimental design, FR still ‘gives the right answers.’ In addition, computational advantages to such methods will be shown.

Online Principal Component Analysis in High Dimension: Which Algorithm to Choose?

In the current context of data explosion, online techniques that do not require storing all data in memory are indispensable to routinely perform tasks like principal component analysis (PCA). Recursive algorithms that update the PCA with each new observation have been studied in various fields of research and found wide applications in industrial monitoring, computer vision, astronomy, and latent semantic indexing, among others. This work provides guidance for selecting an online PCA algorithm in practice. We present the main approaches to online PCA, namely, perturbation techniques, incremental methods, and stochastic optimization, and compare their statistical accuracy, computation time, and memory requirements using artificial and real data. Extensions to missing data and to functional data are discussed. All studied algorithms are available in the R package onlinePCA on CRAN.

Bipolar orientations on planar maps and SLE$_{12}$

Properly Learning Poisson Binomial Distributions in Almost Polynomial Time

Deformation of Quintic Threefolds to the Chordal Variety

Generalized Goncarov polynomials

NIM with Cash

Block-diagonal covariance selection for high-dimensional Gaussian graphical models

Multimodal Skipgram Using Convolutional Pseudowords

Dating structural breaks in functional data without dimension reduction

RasBhari: optimizing spaced seeds for database searching, read mapping and alignment-free sequence comparison

Automatic Inference of the Quantile Parameter

Prediction of the Yield of Enzymatic Synthesis of Betulinic Acid Ester Using Artificial Neural Networks and Support Vector Machine

Dynamic coloring parameters for graphs with given genus

Mean Square Error bounds for parameter estimation under model misspecification

Convergence of the risk for nonparametric IV quantile regression and nonparametric IV regression with full independence

Refracted Continuous-State Branching Processes: Auto-regulating populations

A High Accuracy Stochastic Estimation of a Nonlinear Deterministic Model

Find Your Place: Simple Distributed Algorithms for Community Detection

The scalability of the matrices in direct Trefftz method in 2D Laplace problem

A Multilingual FrameNet-based Grammar and Lexicon for Controlled Natural Language

Mod-$φ$ convergence: Approximation of discrete measures and harmonic analysis on the torus

We Found the Smallest Non-Autograph

Learning Human Identity from Motion Patterns

IfcWoD, Semantically Adapting IFC Model Relations into OWL Properties

Sequential estimation of intrinsic activity and synaptic input in single neurons by particle filtering with optimal importance density

Performance analysis and Optimisation of the Met Unified Model on a Cray XC30

Extremal line configurations on the projective plane, Kummer extensions, asymptotic Chern slopes and singular surfaces

Flexible premium computation principles to manage prior information

Smoothing parameter and model selection for general smooth models

Preemptive Investment under Uncertainty

Feature Learning based Deep Supervised Hashing with Pairwise Labels

Estimation of entropy for Poisson marked point processes

Multiply union families in $\mathbb{N}^n$

Coloring non-crossing strings

Characterizing Concept Drift

Private False Discovery Rate Control

Nonparametric Estimation of Scale-Free Graphical Models

Towards Vision-Based Deep Reinforcement Learning for Robotic Motion Control

A User’s Guide to CARSKit

On the Optimal Sample Complexity for Best Arm Identification

Bose-Einstein Hypernetworks

Improving performance of recurrent neural network with relu nonlinearity

The Hadamard product and the free convolutions

Sparse Learning for Large-scale and High-dimensional Data: A Randomized Convex-concave Optimization Approach

Random Multi-Constraint Projection: Stochastic Gradient Methods for Convex Optimization with Many Constraints

Integrating Heterogeneous Information via Flexible Regularization Framework for Recommendation

Complexity of the Description Logic ALCM

Grounding of Textual Phrases in Images by Reconstruction

Sums of sets of lattice points and unimodular coverings of polytopes

Degree switching and partitioning for enumerating graphs to arbitrary orders of accuracy

On the Dual Ramsey Property for Finite Distributive Lattices

Instability and Information

Larger-Context Language Modelling

An Analysis of How Spatiotemporal Dynamic Models of Brain Activity Could Improve MEG/EEG Inverse Solutions

Doubly Robust Off-policy Evaluation for Reinforcement Learning

Universum Prescription: Regularization using Unlabeled Data

Cayley graphs of diameter two with order greater than 0.684 of the Moore bound for any degree

Optimal bounds for convergence of expected spectral distributions to the semi-circular law for the $4+ε$ moment ensemble

Deep Multimodal Semantic Embeddings for Speech and Images

Capturing Meaning in Product Reviews with Character-Level Generative Text Models

Abelian Girth and Girth

Learning to Diagnose with LSTM Recurrent Neural Networks

Variable-range hopping through marginally localized phonons

Around Sylvester’s question in the plane