title: A Convex Feature Learning Formulation for Latent Task Structure Discovery

abstract: This paper considers the multi-task learning problem and in the setting where some relevant features could be shared across few related tasks. Most of the existing methods assume the extent to which the given tasks are related or share a common feature space to be known apriori. In real-world applications however, it is desirable to automatically discover the groups of related tasks that share a feature space. In this paper we aim at searching the exponentially large space of all possible groups of tasks that may share a feature space. The main contribution is a convex formulation that employs a graph-based regularizer and simultaneously discovers few groups of related tasks, having close-by task parameters, as well as the feature space shared within each group. The regularizer encodes an important structure among the groups of tasks leading to an efficient algorithm for solving it: if there is no feature space under which a group of tasks has close-by task parameters, then there does not exist such a feature space for any of its supersets. An efficient active set algorithm that exploits this simplification and performs a clever search in the exponentially large space is presented. The algorithm is guaranteed to solve the proposed formulation (within some precision) in a time polynomial in the number of groups of related tasks discovered. Empirical results on benchmark datasets show that the proposed formulation achieves good generalization and outperforms state-of-the-art multi-task learning algorithms in some cases.


title: Exact Soft Confidence-Weighted Learning

abstract: In this paper, we propose a new Soft Confidence-Weighted (SCW) online learning scheme, which enables the conventional confidence-weighted learning method to handle non-separable cases. Unlike the previous confidence-weighted learning algorithms, the proposed soft confidence-weighted learning method enjoys all the four salient properties: (i) large margin training, (ii) confidence weighting, (iii) capability to handle non-separable data, and (iv) adaptive margin. Our experimental results show that the proposed SCW algorithms significantly outperform the original CW algorithm. When comparing with a variety of state-of-the-art algorithms (including AROW, NAROW and NHERD), we found that SCW generally achieves better or at least comparable predictive accuracy, but enjoys significant advantage of computational efficiency (i.e., smaller number of updates and lower time cost).


title: Near-Optimal BRL using Optimistic Local Transitions

abstract: Model-based Bayesian Reinforcement Learning (BRL) allows a found formalization of the problem of acting optimally while facing an unknown environment, i.e., avoiding the exploration-exploitation dilemma. However, algorithms explicitly addressing BRL suffer from such a combinatorial explosion that a large body of work relies on heuristic algorithms. This paper introduces BOLT, a simple and (almost) deterministic heuristic algorithm for BRL which is optimistic about the transition function. We analyze BOLT's sample complexity, and show that under certain parameters, the algorithm is near-optimal in the Bayesian sense with high probability. Then, experimental results highlight the key differences of this method compared to previous work.


title: Information-theoretic Semi-supervised Metric Learning via Entropy Regularization

abstract: We propose a general information-theoretic approach called Seraph (SEmi-supervised metRic leArning Paradigm with Hyper-sparsity) for metric learning that does not rely upon the manifold assumption. Given the probability parameterized by a Mahalanobis distance, we maximize the entropy of that probability on labeled data and minimize it on unlabeled data following entropy regularization, which allows the supervised and unsupervised parts to be integrated in a natural and meaningful way. Furthermore, Seraph is regularized by encouraging a low-rank projection induced from the metric. The optimization of Seraph is solved efficiently and stably by an EM-like scheme with the analytical E-Step and convex M-Step. Experiments demonstrate that Seraph compares favorably with many well-known global and local metric learning methods.


title: Levy Measure Decompositions for the Beta and Gamma Processes

abstract: We develop new representations for the Levy measures of the beta and gamma processes. These representations are manifested in terms of an infinite sum of well-behaved (proper) beta and gamma distributions. Further, we demonstrate how these infinite sums may be truncated in practice, and explicitly characterize truncation errors. We also perform an analysis of the characteristics of posterior distributions, based on the proposed decompositions. The decompositions provide new insights into the beta and gamma processes (and their generalizations), and we demonstrate how the proposed representation unifies some properties of the two. This paper is meant to provide a rigorous foundation for and new perspectives on Levy processes, as these are of increasing importance in machine learning.


title: A Hierarchical Dirichlet Process Model with Multiple Levels of Clustering for Human EEG Seizure Modeling

abstract: Driven by the multi-level structure of human intracranial electroencephalogram (iEEG) recordings of epileptic seizures, we introduce a new variant of a hierarchical Dirichlet Process---the multi-level clustering hierarchical Dirichlet Process (MLC-HDP)---that simultaneously clusters datasets on multiple levels. Our seizure dataset contains brain activity recorded in typically more than a hundred individual channels for each seizure of each patient. The MLC-HDP model clusters over channels-types, seizure-types, and patient-types simultaneously. We describe this model and its implementation in detail. We also present the results of a simulation study comparing the MLC-HDP to a similar model, the Nested Dirichlet Process and finally demonstrate the MLC-HDP's use in modeling seizures across multiple patients. We find the MLC-HDP's clustering to be comparable to independent human physician clusterings. To our knowledge, the MLC-HDP model is the first in the epilepsy literature capable of clustering seizures within and between patients.


title: Continuous Inverse Optimal Control with Locally Optimal Examples

abstract: Inverse optimal control, also known as inverse reinforcement learning, is the problem of recovering an unknown reward function in a Markov decision process from expert demonstrations of the optimal policy. We introduce a probabilistic inverse optimal control algorithm that scales gracefully with task dimensionality, and is suitable for large, continuous domains where even computing a full policy is impractical. By using a local approximation of the reward function, our method can also drop the assumption that the demonstrations are globally optimal, requiring only local optimality. This allows it to learn from examples that are unsuitable for prior methods.


title: Compact Hyperplane Hashing with Bilinear Functions

abstract: Hyperplane hashing aims at rapidly searching nearest points to a hyperplane, and has shown practical impact in scaling up active learning with SVMs. Unfortunately, the existing randomized methods need long hash codes to achieve reasonable search accuracy and thus suffer from reduced search speed and large memory overhead. To this end, this paper proposes a novel hyperplane hashing technique which yields compact hash codes. The key idea is the bilinear form of the proposed hash functions, which leads to higher collision probability than the existing hyperplane hash functions when using random projections. To further increase the performance, we propose a learning based framework in which the bilinear functions are directly learned from the data. This results in short yet discriminative codes, and also boosts the search performance over the random projection based solutions. Large-scale active learning experiments carried out on two datasets with up to one million samples demonstrate the overall superiority of the proposed approach.


title: Inductive Kernel Low-rank Decomposition with Priors: A Generalized Nystrom Method

abstract: Low-rank matrix decomposition has gained great popularity recently in scaling up kernel methods to large amounts of data. However, some limitations could prevent them from working effectively in certain domains. For example, many existing approaches are intrinsically unsupervised, which does not incorporate side information (e.g., class labels) to produce task specific decompositions; also, they typically work "transductively", i.e., the factorization does not generalize to new samples, so the complete factorization needs to be recomputed when new samples become available. To solve these problems, in this paper we propose an"inductive"-flavored method for low-rank kernel decomposition with priors. We achieve this by generalizing the Nystr\"om method in a novel way. On the one hand, our approach employs a highly flexible, nonparametric structure that allows us to generalize the low-rank factors to arbitrarily new samples; on the other hand, it has linear time and space complexities, which can be orders of magnitudes faster than existing approaches and renders great efficiency in learning a low-rank kernel decomposition. Empirical results demonstrate the efficacy and efficiency of the proposed method.


title: Improved Information Gain Estimates for Decision Tree Induction

abstract: Ensembles of classification and regression trees remain popular machine learning methods because they define flexible non-parametric models that predict well and are computationally efficient both during training and testing. During induction of decision trees one aims to find predicates that are maximally informative about the prediction target. To select good predicates most approaches estimate an information-theoretic scoring function, the information gain, both for classification and regression problems. We point out that the common estimation procedures are biased and show that by replacing them with improved estimators of the discrete and the differential entropy we can obtain better decision trees. In effect our modifications yield improved predictive performance and are simple to implement in any decision tree code.


abstract: There has been a recent focus in reinforcement learning on addressing continuous state and action problems by optimizing parameterized policies. PI2 is a recent example of this approach. It combines a derivation from first principles of stochastic optimal control with tools from statistical estimation theory. In this paper, we consider PI2 as a member of the wider family of methods which share the concept of probability-weighted averaging to iteratively update parameters to optimize a cost function. We compare PI2 to other members of the same family - Cross-Entropy Methods and CMAES - at the conceptual level and in terms of performance. The comparison suggests the derivation of a novel algorithm which we call PI2-CMA for "Path Integral Policy Improvement with Covariance Matrix Adaptation". PI2-CMA's main advantage is that it determines the magnitude of the exploration noise automatically.


title: A Graphical Model Formulation of Collaborative Filtering Neighbourhood Methods with Fast Maximum Entropy Training

abstract: Item neighbourhood methods for collaborative filtering learn a weighted graph over the set of items, where each item is connected to those it is most similar to. The prediction of a user's rating on an item is then given by that rating of neighbouring items, weighted by their similarity. This paper presents a new neighbourhood approach which we call item fields, whereby an undirected graphical model is formed over the item graph. The resulting prediction rule is a simple generalization of the classical approaches, which takes into account non-local information in the graph, allowing its best results to be obtained when using drastically fewer edges than other neighbourhood approaches. A fast approximate maximum entropy training method based on the Bethe approximation is presented, which uses a simple gradient ascent procedure. When using precomputed sufficient statistics on the Movielens datasets, our method is faster than maximum likelihood approaches by two orders of magnitude.


title: On the Size of the Online Kernel Sparsification Dictionary

abstract: We analyze the size of the dictionary constructed from online kernel sparsification, using a novel formula that expresses the expected determinant of the kernel Gram matrix in terms of the eigenvalues of the covariance operator. Using this formula, we are able to connect the cardinality of the dictionary with the eigen-decay of the covariance operator. In particular, we show that under certain technical conditions, the size of the dictionary will always grow sub-linearly in the number of data points, and, as a consequence, the kernel linear regressor constructed from the resulting dictionary is consistent.


title: Robust Multiple Manifolds Structure Learning

abstract: We present a robust multiple manifolds structure learning (RMMSL) scheme to robustly estimate data structures under the multiple low intrinsic dimensional manifolds assumption. In the local learning stage, RMMSL efficiently estimates local tangent space by weighted low-rank matrix factorization. In the global learning stage, we propose a robust manifold clustering method based on local structure learning results. The proposed clustering method is designed to get the flattest manifolds clusters by introducing a novel curved-level similarity function. Our approach is evaluated and compared to state-of-the-art methods on synthetic data, handwritten digit images, human motion capture data and motorbike videos. We demonstrate the effectiveness of the proposed approach, which yields higher clustering accuracy, and produces promising results for challenging tasks of human motion segmentation and motion flow learning from videos.


title: Optimizing F-measure: A Tale of Two Approaches

abstract: F-measures are popular performance metrics, particularly for tasks with imbalanced data sets. Algorithms for learning to maximize F-measures follow two approaches: the empirical utility maximization (EUM) approach learns a classifier having optimal performance on training data, while the decision-theoretic approach learns a probabilistic model and then predicts labels with maximum expected F-measure. In this paper, we investigate the theoretical justifications and connections for these two approaches, and we study the conditions under which one approach is preferable to the other using synthetic and real datasets. Given accurate models, our results suggest that the two approaches are asymptotically equivalent given large training and test sets. Nevertheless, empirically, the EUM approach appears to be more robust against model misspecification, and given a good model, the decision-theoretic approach appears to be better for handling rare classes and a common domain adaptation scenario.


title: On-Line Portfolio Selection with Moving Average Reversion

abstract: On-line portfolio selection has attracted increasing interests in machine learning and AI communities recently. Empirical evidences show that stock's high and low prices are temporary and stock price relatives are likely to follow the mean reversion phenomenon. While the existing mean reversion strategies are shown to achieve good empirical performance on many real datasets, they often make the single-period mean reversion assumption, which is not always satisfied in some real datasets, leading to poor performance when the assumption does not hold. To overcome the limitation, this article proposes a multiple-period mean reversion, or so-called Moving Average Reversion (MAR), and a new on-line portfolio selection strategy named "On-Line Moving Average Reversion" (OLMAR), which exploits MAR by applying powerful online learning techniques. From our empirical results, we found that OLMAR can overcome the drawback of existing mean reversion algorithms and achieve significantly better results, especially on the datasets where the existing mean reversion algorithms failed. In addition to superior trading performance, OLMAR also runs extremely fast, further supporting its practical applicability to a wide range of applications.


title: Convergence Rates of Biased Stochastic Optimization for Learning Sparse Ising Models

abstract: We study the convergence rate of stochastic optimization of exact (NP-hard) objectives, for which only biased estimates of the gradient are available. We motivate this problem in the context of learning the structure and parameters of Ising models. We first provide a convergence-rate analysis of deterministic errors for forward-backward splitting (FBS). We then extend our analysis to biased stochastic errors, by first characterizing a family of samplers and providing a high probability bound that allows understanding not only FBS, but also proximal gradient (PG) methods. We derive some interesting conclusions: FBS requires only a logarithmically increasing number of random samples in order to converge (although at a very low rate); the required number of random samples is the same for the deterministic and the biased stochastic setting for FBS and basic PG; accelerated PG is not guaranteed to converge in the biased stochastic setting.


title: Robust PCA in High-dimension: A Deterministic Approach

abstract: We consider principal component analysis for contaminated data-set in the high dimensional regime, where the dimensionality of each observation is comparable or even more than the number of observations. We propose a deterministic high-dimensional robust PCA algorithm which inherits all theoretical properties of its randomized counterpart, i.e., it is tractable, robust to contaminated points, easily kernelizable, asymptotic consistent and achieves maximal robustness -- a breakdown point of 50%. More importantly, the proposed method exhibits significantly better computational efficiency, which makes it suitable for large-scale real applications.


title: Multiple Kernel Learning from Noisy Labels by Stochastic Programming

abstract: We study the problem of multiple kernel learning from noisy labels. This is in contrast to most of the previous studies on multiple kernel learning that mainly focus on developing efficient algorithms and assume perfectly labeled training examples. Directly applying the existing multiple kernel learning algorithms to noisily labeled examples often leads to suboptimal performance due to the incorrect class assignments. We address this challenge by casting multiple kernel learning from noisy labels into a stochastic programming problem, and presenting a minimax formulation. We develop an efficient algorithm for solving the related convex-concave optimization problem with a fast convergence rate of $O(1/T)$ where $T$ is the number of iterations. Empirical studies on UCI data sets verify both the effectiveness of the proposed framework and the efficiency of the proposed optimization algorithm.


title: Efficient Decomposed Learning for Structured Prediction

abstract: Structured prediction is the cornerstone of several machine learning applications. Unfortunately, in structured prediction settings with expressive inter-variable interactions, exact inference-based learning algorithms, e.g. Structural SVM, are often intractable. We present a new way, Decomposed Learning (DecL), which performs efficient learning by restricting the inference step to a limited part of the structured spaces. We provide characterizations based on the structure, target parameters, and gold labels, under which DecL is equivalent to exact learning. We then show that in real world settings, where our theoretical assumptions may not completely hold, DecL-based algorithms are significantly more efficient and as accurate as exact learning.


title: A Poisson convolution model for characterizing topical content with word frequency and exclusivity

abstract: An ongoing challenge in the analysis of document collections is how to summarize content in terms of a set of inferred themes that can be interpreted substantively in terms of topics. The current practice of parametrizing the themes in terms of most frequent words limits interpretability by ignoring the differential use of words across topics. We argue that words that are both common and exclusive to a theme are more effective at characterizing topical content. We consider a setting where professional editors have annotated documents to a collection of topic categories, organized into a tree, in which leaf-nodes correspond to the most specific topics. Each document is annotated to multiple categories, at different levels of the tree. We introduce a hierarchical Poisson convolution model to analyze annotated documents in this setting. The model leverages the structure among categories defined by professional editors to infer a clear semantic description for each topic in terms of words that are both frequent and exclusive. We carry out a large randomized experiment on Amazon Turk to demonstrate that topic summaries based on the FREX score are more interpretable than currently established frequency based summaries, and that the proposed model produces more efficient estimates of exclusivity than with currently models. We also develop a parallelized Hamiltonian Monte Carlo sampler that allows the inference to scale to millions of documents.


title: A Complete Analysis of the l_1,p Group-Lasso

abstract: The Group-Lasso is a well-known tool for joint regularization in machine learning methods. While the l_{1,2} and the l_{1,\infty} version have been studied in detail and efficient algorithms exist, there are still open questions regarding other l_{1,p} variants. We characterize conditions for solutions of the l_{1,p} Group-Lasso for all p-norms with 1 <= p <= \infty, and we present a unified active set algorithm. For all p-norms, a highly efficient projected gradient algorithm is presented. This new algorithm enables us to compare the prediction performance of many variants of the Group-Lasso in a multi-task learning setting, where the aim is to solve many learning problems in parallel which are coupled via the Group-Lasso constraint. We conduct large-scale experiments on synthetic data and on two real-world data sets. In accordance with theoretical characterizations of the different norms we observe that the weak-coupling norms with p between 1.5 and 2 consistently outperform the strong-coupling norms with p >> 2.


title: Fast Bounded Online Gradient Descent Algorithms for Scalable Kernel-Based Online Learning

abstract: Kernel-based online learning has often shown state-of-the-art performance for many online learning tasks. It, however, suffers from a major shortcoming, that is, the unbounded number of support vectors, making it non-scalable and unsuitable for applications with large-scale datasets. In this work, we study the problem of bounded kernel-based online learning that aims to constrain the number of support vectors by a predefined budget. Although several algorithms have been proposed in literature, they are neither computationally efficient due to their intensive budget maintenance strategy nor effective due to the use of simple Perceptron algorithm. To overcome these limitations, we propose a framework for bounded kernel-based online learning based on an online gradient descent approach. We propose two efficient algorithms of bounded online gradient descent (BOGD) for scalable kernel-based online learning: (i) BOGD by maintaining support vectors using uniform sampling, and (ii) BOGD++ by maintaining support vectors using non-uniform sampling. We present theoretical analysis of regret bound for both algorithms, and found promising empirical performance in terms of both efficacy and efficiency by comparing them to several well-known algorithms for bounded kernel-based online learning on large-scale datasets.


title: Artist Agent: A Reinforcement Learning Approach to Automatic Stroke Generation in Oriental Ink Painting

abstract: Oriental ink painting, called Sumi-e, is one of the most appealing painting styles that has attracted artists around the world. Major challenges in computer-based Sumi-e simulation are to abstract complex scene information and draw smooth and natural brush strokes. To automatically find such strokes, we propose to model the brush as a reinforcement learning agent, and learn desired brush-trajectories by maximizing the sum of rewards in the policy search framework. We also provide elaborate design of actions, states, and rewards tailored for a Sumi-e agent. The effectiveness of our proposed approach is demonstrated through simulated Sumi-e experiments.


title: Deep Mixtures of Factor Analysers

abstract: An efficient way to learn deep density models that have many layers of latent variables is to learn one layer at a time using a model that has only one layer of latent variables. After learning each layer, samples from the posterior distributions for that layer are used as training data for learning the next layer. This approach is commonly used with Restricted Boltzmann Machines, which are undirected graphical models with a single hidden layer, but it can also be used with Mixtures of Factor Analysers (MFAs) which are directed graphical models. In this paper, we present a greedy layer-wise learning algorithm for Deep Mixtures of Factor Analysers (DMFAs). Even though a DMFA can be converted to an equivalent shallow MFA by multiplying together the factor loading matrices at different levels, learning and inference are much more efficient in a DMFA and the sharing of each lower-level factor loading matrix by many different higher level MFAs prevents overfitting. We demonstrate empirically that DMFAs learn better density models than both MFAs and two types of Restricted Boltzmann Machine on a wide variety of datasets.


title: Modeling Latent Variable Uncertainty for Loss-based Learning

abstract: We consider the problem of parameter estimation using weakly supervised datasets, where a training sample consists of the input and a partially specified annotation, which we refer to as the output. The missing information in the annotation is modeled using latent variables. Previous methods overburden a single distribution with two separate tasks: (i) modeling the uncertainty in the latent variables during training; and (ii) making accurate predictions for the output and the latent variables during testing. We propose a novel framework that separates the demands of the two tasks using two distributions: (i) a conditional distribution to model the uncertainty of the latent variables for a given input-output pair; and (ii) a delta distribution to predict the output and the latent variables for a given input. During learning, we encourage agreement between the two distributions by minimizing a loss-based dissimilarity coefficient. Our approach generalizes latent SVM in two important ways: (i) it models the uncertainty over latent variables instead of relying on a pointwise estimate; and (ii) it allows the use of loss functions that depend on latent variables, which greatly increases its applicability. We demonstrate the efficacy of our approach on two challenging problems---object detection and action detection---using publicly available datasets.


title: Learning to Identify Regular Expressions that Describe Email Campaigns

abstract: This paper addresses the problem of inferring a regular expression from a given set of strings that resembles, as closely as possible, the regular expression that a human expert would have written to identify the language. This is motivated by our goal of automating the task of postmasters of an email service who use regular expressions to describe and blacklist email spam campaigns. Training data contains batches of messages and corresponding regular expressions that an expert postmaster feels confident to blacklist. We model this task as a learning problem with structured output spaces and an appropriate loss function, derive a decoder and the resulting optimization problem, and a report on a case study conducted with an email service.


title: Efficient Euclidean Projections onto the Intersection of Norm Balls

abstract: Using sparse-inducing norms to learn robust models has received increasing attention from many fields for its attractive properties. Projection-based methods have been widely applied to learning tasks constrained by such norms. As a key building block of these methods, an efficient operator for Euclidean projection onto the intersection of $\ell_1$ and $\ell_{1,q}$ norm balls $(q=2\text{or}\infty)$ is proposed in this paper. We prove that the projection can be reduced to finding the root of an auxiliary function which is piecewise smooth and monotonic. Hence, a bisection algorithm is sufficient to solve the problem. We show that the time complexity of our solution is $O(n+g\log g)$ for $q=2$ and $O(n\log n)$ for $q=\infty$, where $n$ is the dimensionality of the vector to be projected and $g$ is the number of disjoint groups; we confirm this complexity by experimentation. Empirical study reveals that our method achieves significantly better performance than classical methods in terms of running time and memory usage. We further show that embedded with our efficient projection operator, projection-based algorithms can solve regression problems with composite norm constraints more efficiently than other methods and give superior accuracy.


title: Adaptive Regularization for Weight Matrices

abstract: Algorithms for learning distributions over weight-vectors, such as AROW were recently shown empirically to achieve state-of-the-art performance at various problems, with strong theoretical guaranties. Extending these algorithms to matrix models pose challenges since the number of free parameters in the covariance of the distribution scales as $n^4$ with the dimension $n$ of the matrix, and $n$ tends to be large in real applications. We describe, analyze and experiment with two new algorithms for learning distribution of matrix models. Our first algorithm maintains a diagonal covariance over the parameters and can handle large covariance matrices. The second algorithm factors the covariance to capture inter-features correlation while keeping the number of parameters linear in the size of the original matrix. We analyze both algorithms in the mistake bound model and show a superior precision performance of our approach over other algorithms in two tasks: retrieving similar images, and ranking similar documents. The factored algorithm is shown to attain faster convergence rate.


title: Stability of matrix factorization for collaborative filtering

abstract: We study the stability vis a vis adversarial noise of matrix factorization algorithm for matrix completion. In particular, our results include: (I) we bound the gap between the solution matrix of the factorization method and the ground truth in terms of root mean square error; (II) we treat the matrix factorization as a subspace fitting problem and analyze the difference between the solution subspace and the ground truth; (III) we analyze the prediction error of individual users based on the subspace stability. We apply these results to the problem of collaborative filtering under manipulator attack, which leads to useful insights and guidelines for collaborative filtering system design.


title: Total Variation and Euler's Elastica for Supervised Learning

abstract: In recent years, total variation (TV) and Euler's elastica (EE) have been successfully applied to image processing tasks such as denoising and inpainting. This paper investigates how to extend TV and EE to the supervised learning settings on high dimensional data. The supervised learning problem can be formulated as an energy functional minimization under Tikhonov regularization scheme, where the energy is composed of a squared loss and a total variation smoothing (or Euler's elastica smoothing). Its solution via variational principles leads to an Euler-Lagrange PDE. However, the PDE is always high-dimensional and cannot be directly solved by common methods. Instead, radial basis functions are utilized to approximate the target function, reducing the problem to finding the linear coefficients of basis functions. We apply the proposed methods to supervised learning tasks (including binary classification, multi-class classification, and regression) on benchmark data sets. Extensive experiments have demonstrated promising results of the proposed methods.


title: Fast Computation of Subpath Kernel for Trees

abstract: The kernel method is a potential approach to analyzing structured data such as sequences, trees, and graphs; however, unordered trees have not been investigated extensively. Kimura et al. (2011) proposed a kernel function for unordered trees on the basis of their subpaths, which are vertical substructures of trees responsible for hierarchical information in them. Their kernel exhibits practically good performance in terms of accuracy and speed; however, linear-time computation is not guaranteed theoretically, unlike the case of the other unordered tree kernel proposed by Vishwanathan and Smola (2003). In this paper, we propose a theoretically guaranteed linear-time kernel computation algorithm that is practically fast, and we present an efficient prediction algorithm whose running time depends only on the size of the input tree. Experimental results show that the proposed algorithms are quite efficient in practice.


title: Lightning Does Not Strike Twice: Robust MDPs with Coupled Uncertainty

abstract: We consider Markov decision processes under parameter uncertainty. Previous studies all restrict to the case that uncertainties among different states are uncoupled, which leads to conservative solutions. In contrast, we introduce an intuitive concept, termed "Lightning Does not Strike Twice," to model coupled uncertain parameters. Specifically, we require that the system can deviate from its nominal parameters only a bounded number of times. We give probabilistic guarantees indicating that this model represents real life situations and devise tractable algorithms for computing optimal control policies using this concept.


title: Groupwise Constrained Reconstruction for Subspace Clustering

abstract: Reconstruction based subspace clustering methods compute a self reconstruction matrix over the samples and use it for spectral clustering to obtain the final clustering result. Their success largely relies on the assumption that the underlying subspaces are independent, which, however, does not always hold in the applications with increasing number of subspaces. In this paper, we propose a novel reconstruction based subspace clustering model without making the subspace independence assumption. In our model, certain properties of the reconstruction matrix are explicitly characterized using the latent cluster indicators, and the affinity matrix used for spectral clustering can be directly built from the posterior of the latent cluster indicators instead of the reconstruction matrix. Experimental results on both synthetic and real-world datasets show that the proposed model can outperform the state-of-the-art methods.


title: Ensemble Methods for Convex Regression with Applications to Geometric Programming Based Circuit Design

abstract: Convex regression is a promising area for bridging statistical estimation and deterministic convex optimization. New piecewise linear convex regression methods are fast and scalable, but can have instability when used to approximate constraints or objective functions for optimization. Ensemble methods, like bagging, smearing and random partitioning, can alleviate this problem and maintain the theoretical properties of the underlying estimator. We empirically examine the performance of ensemble methods for prediction and optimization, and then apply them to device modeling and constraint approximation for geometric programming based circuit design.


title: Partial-Hessian Strategies for Fast Learning of Nonlinear Embeddings

abstract: Stochastic neighbor embedding (SNE) and related nonlinear manifold learning algorithms achieve high-quality low-dimensional representations of similarity data, but are notoriously slow to train. We propose a generic formulation of embedding algorithms that includes SNE and other existing algorithms, and study their relation with spectral methods and graph Laplacians. This allows us to define several partial-Hessian optimization strategies, characterize their global and local convergence, and evaluate them empirically. We achieve up to two orders of magnitude speedup over existing training methods with a strategy (which we call the spectral direction) that adds nearly no overhead to the gradient and yet is simple, scalable and applicable to several existing and future embedding algorithms.


title: Active Learning for Matching Problems

abstract: Effective learning of user preferences is critical to easing user burden in various types of matching problems. Equally important is active query selection to further reduce the amount of preference information users must provide. We address the problem of active learning of user preferences for matching problems, introducing a novel method for determining probabilistic matchings, and developing several new active learning strategies that are sensitive to the specific matching objective. Experiments with real-world data sets spanning diverse domains demonstrate that matching-sensitive active learning


title: Two-Manifold Problems with Applications to Nonlinear System Identification

abstract: Recently, there has been much interest in spectral approaches to learning manifolds---so-called kernel eigenmap methods. These methods have had some successes, but their applicability is limited because they are not robust to noise. To address this limitation, we look at two-manifold problems, in which we simultaneously reconstruct two related manifolds, each representing a different view of the same data. By solving these interconnected learning problems together, two-manifold algorithms are able to succeed where a non-integrated approach would fail: each view allows us to suppress noise in the other, reducing bias. We propose a class of algorithms for two-manifold problems, based on spectral decomposition of cross-covariance operators in Hilbert space, and discuss when two-manifold problems are useful. Finally, we demonstrate that solving a two-manifold problem can aid in learning a nonlinear dynamical system from limited data.


title: Learning Efficient Structured Sparse Models

abstract: We present a comprehensive framework for structured sparse coding and modeling extending the recent ideas of using learnable fast regressors to approximate exact sparse codes. For this purpose, we develop a novel block-coordinate proximal splitting method for the iterative solution of hierarchical sparse coding problems, and show an efficient feed forward architecture derived from its iteration. This architecture faithfully approximates the exact structured sparse codes with a fraction of the complexity of the standard optimization methods. We also show that by using different training objective functions, learnable sparse encoders are no longer restricted to be mere approximants of the exact sparse code for a pre-given dictionary, as in earlier formulations, but can be rather used as full-featured sparse encoders or even modelers. A simple implementation shows several orders of magnitude speedup compared to the state-of-the-art at minimal performance degradation, making the proposed framework suitable for real time and large-scale applications.


title: Analysis of Kernel Mean Matching under Covariate Shift

abstract: In real supervised learning scenarios, it is not uncommon that the training and test sample follow different probability distributions, thus rendering the necessity to correct the sampling bias. Focusing on a particular covariate shift problem, we derive high probability confidence bounds for the kernel mean matching (KMM) estimator, whose convergence rate turns out to depend on some regularity measure of the regression function and also on some capacity measure of the kernel. By comparing KMM with the natural plug-in estimator, we establish the superiority of the former hence provide concrete evidence/understanding to the effectiveness of KMM under covariate shift.


title: Is margin preserved after random projection?

abstract: Random projections have been applied in many machine learning algorithms. However, whether margin is preserved after random projection is non-trivial and not well studied. In this paper we analyse margin distortion after random projection, and give the conditions of margin preservation for binary classification problems. We also extend our analysis to margin for multiclass problems, and provide theoretical bounds on multiclass margin on the projected data.


title: The Most Persistent Soft-Clique in a Set of Sampled Graphs

abstract: When searching for characteristic subpatterns in potentially noisy graph data, it appears self-evident that having multiple observations would be better than having just one. However, it turns out that the inconsistencies introduced when different graph instances have different edge sets pose a serious challenge. In this work we address this challenge for the problem of finding maximum weighted cliques. We introduce the concept of most persistent soft-clique. This is subset of vertices, that 1) is almost fully or at least densely connected, 2) occurs in all or almost all graph instances, and 3) has the maximum weight. We present a measure of clique-ness, that essentially counts the number of edge missing to make a subset of vertices into a clique. With this measure, we show that the problem of finding the most persistent soft-clique problem can be cast either as: a) a max-min two person game optimization problem, or b) a min-min soft margin optimization problem. Both formulations lead to the same solution when using a partial Lagrangian method to solve the optimization problems. By experiments on synthetic data and on real social network data, we show that the proposed method is able to reliably find soft cliques in graph data, even if that is distorted by random noise or unreliable observations.


title: Dimensionality Reduction by Local Discriminative Gaussians

abstract: We present local discriminative Gaussian (LDG) dimensionality reduction, a supervised dimensionality reduction technique for classification. The LDG objective function is an approximation to the leave-one-out training error of a local quadratic discriminant analysis classifier, and thus acts locally to each training point in order to find a mapping where similar data can be discriminated from dissimilar data. While other state-of-the-art linear dimensionality reduction methods require gradient descent or iterative solution approaches, LDG is solved with a single eigen-decomposition. Thus, it scales better for datasets with a large number of feature dimensions or training examples. We also adapt LDG to the transfer learning setting, and show that it achieves good performance when the test data distribution differs from that of the training data.


title: A Generalized Loop Correction Method for Approximate Inference in Graphical Models

abstract: Belief Propagation (BP) is one of the most popular methods for inference in probabilistic graphical models. BP is guaranteed to return the correct answer for tree structures, but can be incorrect or non-convergent for loopy graphical models. Recently, several new approximate inference algorithms based on cavity distribution have been proposed. These methods can account for the effect of loops by incorporating the dependency between BP messages. Alternatively, region-based approximations (that lead to methods such as Generalized Belief Propagation) improve upon BP by considering interactions within small clusters of variables, thus taking small loops within these clusters into account. This paper introduces an approach, Generalized Loop Correction (GLC), that benefits from both of these types of loop correction. We show how GLC relates to these two families of inference methods, then provide empirical evidence that GLC works effectively in general, and can be significantly more accurate than both correction schemes.


title: Modelling transition dynamics in MDPs with RKHS embeddings

abstract: We propose a new, nonparametric approach to learning and representing transition dynamics in Markov decision processes (MDPs), which can be combined easily with dynamic programming methods for policy optimisation and value estimation. This approach makes use of a recently developed representation of conditional distributions as \emph{embeddings} in a reproducing kernel Hilbert space (RKHS). Such representations bypass the need for estimating transition probabilities or densities, and apply to any domain on which kernels can be defined. This avoids the need to calculate intractable integrals, since expectations are represented as RKHS inner products whose computation has linear complexity in the number of points used to represent the embedding. We provide guarantees for the proposed applications in MDPs: in the context of a value iteration algorithm, we prove convergence to either the optimal policy, or to the closest projection of the optimal policy in our model class (an RKHS), under reasonable assumptions. In experiments, we investigate a learning task in a typical classical control setting (the under-actuated pendulum), and on a navigation problem where only images from a sensor are observed. For policy optimisation we compare with least-squares policy iteration where a Gaussian process is used for value function estimation. For value estimation we also compare to the NPDP method. Our approach achieves better performance in all experiments.


title: Machine Learning that Matters

abstract: Much of current machine learning (ML) research has lost its connection to problems of import to the larger world of science and society. From this perspective, there exist glaring limitations in the data sets we investigate, the metrics we employ for evaluation, and the degree to which results are communicated back to their originating domains. What changes are needed to how we conduct research to increase the impact that ML has? We present six Impact Challenges to explicitly focus the field?s energy and attention, and we discuss existing obstacles that must be addressed. We aim to inspire ongoing discussion and focus on ML that matters.


title: Projection-free Online Learning

abstract: The computational bottleneck in applying online learning to massive data sets is usually the projection step. We present efficient online learning algorithms that eschew projections in favor of much more efficient linear optimization steps using the Frank-Wolfe technique. We obtain a range of regret bounds for online convex optimization, with better bounds for specific cases such as stochastic online smooth convex optimization. Besides the computational advantage, other desirable features of our algorithms are that they are parameter-free in the stochastic case and produce sparse decisions. We apply our algorithms to computationally intensive applications of collaborative filtering, and show the theoretical improvements to be clearly visible on standard datasets.


title: Dirichlet Process with Mixed Random Measures: A Nonparametric Topic Model for Labeled Data

abstract: We describe a nonparametric topic model for labeled data. The model uses a mixture of random measures (MRM) as a base distribution of the Dirichlet process (DP) of the HDP framework, so we call it the DP-MRM. To model labeled data, we define a DP distributed random measure for each label, and the resulting model generates an unbounded number of topics for each label. We apply DP-MRM on single-labeled and multi-labeled corpora of documents and compare the performance on label prediction with MedLDA, LDA-SVM, and Labeled-LDA. We further enhance the model by incorporating ddCRP and modeling multi-labeled images for image segmentation and object labeling, comparing the performance with nCuts and rddCRP.


title: Max-Margin Nonparametric Latent Feature Models for Link Prediction

abstract: We present a max-margin nonparametric latent feature model, which unites the ideas of max-margin learning and Bayesian nonparametrics to discover discriminative latent features for link prediction and automatically infer the unknown latent social dimension. By minimizing a hinge-loss using the linear expectation operator, we can perform posterior inference efficiently without dealing with a highly nonlinear link likelihood function; by using a fully-Bayesian formulation, we can avoid tuning regularization constants. Experimental results on real datasets appear to demonstrate the benefits inherited from max-margin learning and fully-Bayesian nonparametric inference.


title: Learning with Augmented Features for Heterogeneous Domain Adaptation

abstract: We propose a new learning method for heterogeneous domain adaptation (HDA), in which the data from the source domain and the target domain are represented by heterogeneous features with different dimensions. Using two different projection matrices, we first transform the data from two domains into a common subspace in order to measure the similarity between the data from two domains. We then propose two new feature mapping functions to augment the transformed data with their original features and zeros. The existing learning methods (e.g., SVM and SVR) can be readily incorporated with our newly proposed augmented feature representations to effectively utilize the data from both domains for HDA. Using the hinge loss function in SVM as an example, we introduce the detailed objective function in our method called Heterogeneous Feature Augmentation (HFA) for a linear case and also describe its kernelization in order to efficiently cope with the data with very high dimensions. Moreover, we also develop an alternating optimization algorithm to effectively solve the nontrivial optimization problem in our HFA method. Comprehensive experiments on two benchmark datasets clearly demonstrate that HFA outperforms the existing HDA methods.


title: Predicting accurate probabilities with a ranking loss

abstract: In many real-world applications of machine learning classifiers, it is essential to predict the probability of an example belonging to a particular class. This paper proposes a simple technique for predicting probabilities based on optimizing a ranking loss, followed by isotonic regression. This semi-parametric technique offers both good ranking and regression performance, and models a richer set of probability distributions than statistical workhorses such as logistic regression. We provide experimental results that show the effectiveness of this technique on real-world applications of probability prediction.


title: Bayesian Watermark Attacks

abstract: This paper presents an application of statistical machine learning to the field of watermarking. We propose a new attack model on additive spread-spectrum watermarking systems. The proposed attack is based on Bayesian statistics. We consider the scenario in which a watermark signal is repeatedly embedded in specific, possibly chosen based on a secret message bitstream, segments (signals) of the host data. The host signal can represent a patch of pixels from an image or a video frame. We propose a probabilistic model that infers the embedded message bitstream and watermark signal, directly from the watermarked data, without access to the decoder. We develop an efficient Markov chain Monte Carlo sampler for updating the model parameters from their conjugate full conditional posteriors. We also provide a variational Bayesian solution, which further increases the convergence speed of the algorithm. Experiments with synthetic and real image signals demonstrate that the attack model is able to correctly infer a large part of the message bitstream and obtain a very accurate estimate of the watermark signal.


title: The Convexity and Design of Composite Multiclass Losses

abstract: We consider composite loss functions for multiclass prediction comprising a proper (i.e., Fisher-consistent) loss over probability distributions and an inverse link function. We establish conditions for their (strong) convexity and explore the implications. We also show how the separation of concerns afforded by using this composite representation allows for the design of families of losses with the same Bayes risk.


title: Tighter Variational Representations of f-Divergences via Restriction to Probability Measures

abstract: We show that the variational representations for f-divergences currently used in the literature can be tightened. This has implications to a number of methods recently proposed based on this representation. As an example application we use our tighter representation to derive a general f-divergence estimator based on two i.i.d. samples and derive the dual program for this estimator that performs well empirically. We also point out a connection between our estimator and MMD.


title: Nonparametric variational inference

abstract: Variational methods are widely used for approximate posterior inference. However, their use is typically limited to families of distributions that enjoy particular conjugacy properties. To circumvent this limitation, we propose a family of variational approximations inspired by nonparametric kernel density estimation. The locations of these kernels and their bandwidth are treated as variational parameters and optimized to improve an approximate lower bound on the marginal likelihood of the data. Using multiple kernels allows the approximation to capture multiple modes of the posterior, unlike most other variational approximations. We demonstrate the efficacy of the nonparametric approximation with a hierarchical logistic regression model and a nonlinear matrix factorization model. We obtain predictive performance as good as or better than more specialized variational methods and sample-based approximations. The method is easy to apply to more general graphical models for which standard variational methods are difficult to derive.


title: A Bayesian Approach to Approximate Joint Diagonalization of Square Matrices

abstract: We present a Bayesian scheme for the approximate diagonalisation of several square matrices which are not necessarily symmetric. A Gibbs sampler is derived to simulate samples of the common eigenvectors and the eigenvalues for these matrices. Several synthetic examples are used to illustrate the performance of the proposed Gibbs sampler and we then provide comparisons to several other joint diagonalization algorithms, which shows that the Gibbs sampler achieves the state-of-the-art performance on the examples considered. As a byproduct, the output of the Gibbs sampler could be used to estimate the log marginal likelihood, however we employ the approximation based on the Bayesian information criterion (BIC) which in the synthetic examples considered correctly located the number of common eigenvectors. We then succesfully applied the sampler to the source separation problem as well as the common principal component analysis and the common spatial pattern analysis problems.


title: Unachievable Region in Precision-Recall Space and Its Effect on Empirical Evaluation

abstract: Precision-recall (PR) curves and the areas under them are widely used to summarize machine learning results, especially for data sets exhibiting class skew. They are often used analogously to ROC curves and the area under ROC curves. It is known that PR curves vary as class skew changes. What was not recognized before this paper is that there is a region of PR space that is completely unachievable, and the size of this region depends only on the skew. This paper precisely characterizes the size of that region and discusses its implications for empirical evaluation methodology in machine learning.


title: Approximate Principal Direction Trees

abstract: We introduce a new spatial data structure for high dimensional data called the \emph{approximate principal direction tree} (APD tree) that adapts to the intrinsic dimension of the data. Our algorithm ensures vector-quantization accuracy similar to that of computationally-expensive PCA trees with similar time-complexity to that of lower-accuracy RP trees. APD trees use a small number of power-method iterations to find splitting planes for recursively partitioning the data. As such they provide a natural trade-off between the running-time and accuracy achieved by RP and PCA trees. Our theoretical results establish a) strong performance guarantees regardless of the convergence rate of the power-method and b) that $O(\log d)$ iterations suffice to establish the guarantee of PCA trees when the intrinsic dimension is $d$. We demonstrate this trade-off and the efficacy of our data structure on both the CPU and GPU.


title: Sparse Additive Functional and Kernel CCA

abstract: Canonical Correlation Analysis (CCA) is a classical tool for finding correlations among the components of two random vectors. In recent years, CCA has been widely applied to the analysis of genomic data, where it is common for researchers to perform multiple assays on a single set of patient samples. Recent work has proposed sparse variants of CCA to address the high dimensionality of such data. However, classical and sparse CCA are based on linear models, and are thus limited in their ability to find general correlations. In this paper, we present two approaches to high-dimensional nonparametric CCA, building on recent developments in high-dimensional nonparametric regression. We present estimation procedures for both approaches, and analyze their theoretical properties in the high-dimensional setting. We demonstrate the effectiveness of these procedures in discovering nonlinear correlations via extensive simulations, as well as through experiments with genomic data.


title: State-Space Inference for Non-Linear Latent Force Models with Application to Satellite Orbit Prediction

abstract: Latent force models (LFMs) are flexible models that combine mechanistic modelling principles (i.e., physical models) with non-parametric data-driven components. Several key applications of LFMs need non-linearities, which results in analytically intractable inference. In this work we show how non-linear LFMs can be represented as non-linear white noise driven state-space models and present an efficient non-linear Kalman filtering and smoothing based method for approximate state and parameter inference. We illustrate the performance of the proposed methodology via two simulated examples, and apply it to a real-world problem of long-term prediction of GPS satellite orbits.

categories: cs.IT astro-ph.EP cs.LG math.IT physics.data-an


title: Dependent Hierarchical Normalized Random Measures for Dynamic Topic Modeling

abstract: We develop dependent hierarchical normalized random measures and apply them to dynamic topic modeling. The dependency arises via superposition, subsampling and point transition on the underlying Poisson processes of these measures. The measures used include normalised generalised Gamma processes that demonstrate power law properties, unlike Dirichlet processes used previously in dynamic topic modeling. Inference for the model includes adapting a recently developed slice sampler to directly manipulate the underlying Poisson process. Experiments performed on news, blogs, academic and Twitter collections demonstrate the technique gives superior perplexity over a number of previous models.


title: Efficient Active Algorithms for Hierarchical Clustering

abstract: Advances in sensing technologies and the growth of the internet have resulted in an explosion in the size of modern datasets, while storage and processing power continue to lag behind. This motivates the need for algorithms that are efficient, both in terms of the number of measurements needed and running time. To combat the challenges associated with large datasets, we propose a general framework for active hierarchical clustering that repeatedly runs an off-the-shelf clustering algorithm on small subsets of the data and comes with guarantees on performance, measurement complexity and runtime complexity. We instantiate this framework with a simple spectral clustering algorithm and provide concrete results on its performance, showing that, under some assumptions, this algorithm recovers all clusters of size ?(log n) using O(n log^2 n) similarities and runs in O(n log^3 n) time for a dataset of n objects. Through extensive experimentation we also demonstrate that this framework is practically alluring.


title: Group Sparse Additive Models

abstract: We consider the problem of sparse variable selection in nonparametric additive models, with the prior knowledge of the structure among the covariates to encourage those variables within a group to be selected jointly. Previous works either study the group sparsity in the parametric setting (e.g., group lasso), or address the problem in the non-parametric setting without exploiting the structural information (e.g., sparse additive models). In this paper, we present a new method, called group sparse additive models (GroupSpAM), which can handle group sparsity in additive models. We generalize the l1/l2 norm to Hilbert spaces as the sparsity-inducing penalty in GroupSpAM. Moreover, we derive a novel thresholding condition for identifying the functional sparsity at the group level, and propose an efficient block coordinate descent algorithm for constructing the estimate. We demonstrate by simulation that GroupSpAM substantially outperforms the competing methods in terms of support recovery and prediction accuracy in additive models, and also conduct a comparative experiment on a real breast cancer dataset.


title: Comparison-Based Learning with Rank Nets

abstract: We consider the problem of search through comparisons, where a user is presented with two candidate objects and reveals which is closer to her intended target. We study adaptive strategies for finding the target, that require knowledge of rank relationships but not actual distances between objects. We propose a new strategy based on rank nets, and show that for target distributions with a bounded doubling constant, it finds the target in a number of comparisons close to the entropy of the target distribution and, hence, of the optimum. We extend these results to the case of noisy oracles, and compare this strategy to prior art over multiple datasets.


title: Finding Botnets Using Minimal Graph Clusterings

abstract: We study the problem of identifying botnets and the IP addresses which they comprise, based on the observation of a fraction of the global email spam traffic. Observed mailing campaigns constitute evidence for joint botnet membership, they are represented by cliques in the graph of all messages. No evidence against an association of nodes is ever available. We reduce the problem of identifying botnets to a problem of finding a minimal clustering of the graph of messages. We directly model the distribution of clusterings given the input graph; this avoids potential errors caused by distributional assumptions of a generative model. We report on a case study in which we evaluate the model by its ability to predict the spam campaign that a given IP address is going to participate in.


title: Clustering by Low-Rank Doubly Stochastic Matrix Decomposition

abstract: Clustering analysis by nonnegative low-rank approximations has achieved remarkable progress in the past decade. However, most approximation approaches in this direction are still restricted to matrix factorization. We propose a new low-rank learning method to improve the clustering performance, which is beyond matrix factorization. The approximation is based on a two-step bipartite random walk through virtual cluster nodes, where the approximation is formed by only cluster assigning probabilities. Minimizing the approximation error measured by Kullback-Leibler divergence is equivalent to maximizing the likelihood of a discriminative model, which endows our method with a solid probabilistic interpretation. The optimization is implemented by a relaxed Majorization-Minimization algorithm that is advantageous in finding good local minima. Furthermore, we point out that the regularized algorithm with Dirichlet prior only serves as initialization. Experimental results show that the new method has strong performance in clustering purity for various datasets, especially for large-scale manifold data.


title: Semi-Supervised Learning of Class Balance under Class-Prior Change by Distribution Matching

abstract: In real-world classification problems, the class balance in the training dataset does not necessarily reflect that of the test dataset, which can cause significant estimation bias. If the class ratio of the test dataset is known, instance re-weighting or resampling allows systematical bias correction. However, learning the class ratio of the test dataset is challenging when no labeled data is available from the test domain. In this paper, we propose to estimate the class ratio in the test dataset by matching probability distributions of training and test input data. We demonstrate the utility of the proposed approach through experiments.


title: Linear Regression with Limited Observation

abstract: We consider the most common variants of linear regression, including Ridge, Lasso and Support-vector regression, in a setting where the learner is allowed to observe only a fixed number of attributes of each example at training time. We present simple and efficient algorithms for these problems: for Lasso and Ridge regression they need the same total number of attributes (up to constants) as do full-information algorithms, for reaching a certain accuracy. For Support-vector regression, we require exponentially less attributes compared to the state of the art. By that, we resolve an open problem recently posed by Cesa-Bianchi et al. (2010). Experiments show the theoretical bounds to be justified by superior performance compared to the state of the art.


title: Factorized Asymptotic Bayesian Hidden Markov Models

abstract: This paper addresses the issue of model selection for hidden Markov models (HMMs). We generalize factorized asymptotic Bayesian inference (FAB), which has been recently developed for model selection on independent hidden variables (i.e., mixture models), for time-dependent hidden variables. As with FAB in mixture models, FAB for HMMs is derived as an iterative lower bound maximization algorithm of a factorized information criterion (FIC). It inherits, from FAB for mixture models, several desirable properties for learning HMMs, such as asymptotic consistency of FIC with marginal log-likelihood, a shrinkage effect for hidden state selection, monotonic increase of the lower FIC bound through the iterative optimization. Further, it does not have a tunable hyper-parameter, and thus its model selection process can be fully automated. Experimental results shows that FAB outperforms states-of-the-art variational Bayesian HMM and non-parametric Bayesian HMM in terms of model selection accuracy and computational efficiency.


title: Fast Prediction of New Feature Utility

abstract: We study the new feature utility prediction problem: statistically testing whether adding a new feature to the data representation can improve predictive accuracy on a supervised learning task. In many applications, identifying new informative features is the primary pathway for improving performance. However, evaluating every potential feature by re-training the predictor with it can be costly. The paper describes an efficient, learner-independent technique for estimating new feature utility without re-training based on the current predictor's outputs. The method is obtained by deriving a connection between loss reduction potential and the new feature's correlation with the loss gradient of the current predictor. This leads to a simple yet powerful hypothesis testing procedure, for which we prove consistency. Our theoretical analysis is accompanied by empirical evaluation on standard benchmarks and a large-scale industrial dataset.


title: LPQP for MAP: Putting LP Solvers to Better Use

abstract: MAP inference for general energy functions remains a challenging problem. While most efforts are channeled towards improving the linear programming (LP) based relaxation, this work is motivated by the quadratic programming (QP) relaxation. We propose a novel MAP relaxation that penalizes the Kullback-Leibler divergence between the LP pairwise auxiliary variables, and QP equivalent terms given by the product of the unaries. We develop two efficient algorithms based on variants of this relaxation. The algorithms minimize the non-convex objective using belief propagation and dual decomposition as building blocks. Experiments on synthetic and real-world data show that the solutions returned by our algorithms substantially improve over the LP relaxation.


title: Copula-based Kernel Dependency Measures

abstract: The paper presents a new copula based method for measuring dependence between random variables. Our approach extends the Maximum Mean Discrepancy to the copula of the joint distribution. We prove that this approach has several advantageous properties. Similarly to Shannon mutual information, the proposed dependence measure is invariant to any strictly increasing transformation of the marginal variables. This is important in many applications, for example in feature selection. The estimator is consistent, robust to outliers, and uses rank statistics only. We derive upper bounds on the convergence rate and propose independence tests too. We illustrate the theoretical contributions through a series of experiments in feature selection and low-dimensional embedding of distributions.


title: Marginalized Denoising Autoencoders for Domain Adaptation

abstract: Stacked denoising autoencoders (SDAs) have been successfully used to learn new representations for domain adaptation. Recently, they have attained record accuracy on standard benchmark tasks of sentiment analysis across different text domains. SDAs learn robust data representations by reconstruction, recovering original features from data that are artificially corrupted with noise. In this paper, we propose marginalized SDA (mSDA) that addresses two crucial limitations of SDAs: high computational cost and lack of scalability to high-dimensional features. In contrast to SDAs, our approach of mSDA marginalizes noise and thus does not require stochastic gradient descent or other optimization algorithms to learn parameters ? in fact, they are computed in closed-form. Consequently, mSDA, which can be implemented in only 20 lines of MATLAB^{TM}, significantly speeds up SDAs by two orders of magnitude. Furthermore, the representations learnt by mSDA are as effective as the traditional SDAs, attaining almost identical accuracies in benchmark tasks.


title: Collaborative Topic Regression with Social Matrix Factorization for Recommendation Systems

abstract: Social network websites, such as Facebook, YouTube, Lastfm etc, have become a popular platform for users to connect with each other and share content or opinions. They provide rich information for us to study the influence of user's social circle in their decision process. In this paper, we are interested in examining the effectiveness of social network information to predict the user's ratings of items. We propose a novel hierarchical Bayesian model which jointly incorporates topic modeling and probabilistic matrix factorization of social networks. A major advantage of our model is to automatically infer useful latent topics and social information as well as their importance to collaborative filtering from the training data. Empirical experiments on two large-scale datasets show that our algorithm provides a more effective recommendation system than the state-of-the art approaches. Our results reveal interesting insight that the social circles have more influence on people's decisions about the usefulness of information (e.g., bookmarking preference on Delicious) than personal taste (e.g., music preference on Lastfm). We also examine and discuss solutions on potential information leak in many recommendation systems that utilize social information.


title: Sparse-GEV: Sparse Latent Space Model for Multivariate Extreme Value Time Serie Modeling

abstract: In many applications of time series models, such as climate analysis and social media analysis, we are often interested in extreme events, such as heatwave, wind gust, and burst of topics. These time series data usually exhibit a heavy-tailed distribution rather than a Gaussian distribution. This poses great challenges to existing approaches due to the significantly different assumptions on the data distributions and the lack of sufficient past data on extreme events. In this paper, we propose the Sparse-GEV model, a latent state model based on the theory of extreme value modeling to automatically learn sparse temporal dependence and make predictions. Our model is theoretically significant because it is among the first models to learn sparse temporal dependencies among multivariate extreme value time series. We demonstrate the superior performance of our algorithm to the state-of-art methods, including Granger causality, copula approach, and transfer entropy, on one synthetic dataset, one climate dataset and two Twitter datasets.


title: Discriminative Probabilistic Prototype Learning

abstract: In this paper we propose a simple yet powerful method for learning representations in supervised learning scenarios where each original input datapoint is described by a set of vectors and their associated outputs may be given by soft labels indicating, for example, class probabilities. We represent an input datapoint as a mixture of probabilities over the corresponding set of feature vectors where each probability indicates how likely each vector is to belong to an unknown prototype pattern. We propose a probabilistic model that parameterizes these prototype patterns in terms of hidden variables and therefore it can be trained with conventional approaches based on likelihood maximization. More importantly, both the model parameters and the prototype patterns can be learned from data in a discriminative way. We show that our model can be seen as a probabilistic generalization of learning vector quantization (LVQ). We apply our method to the problems of shape classification, hyperspectral imaging classification and people's work class categorization, showing the superior performance of our method compared to the standard prototype-based classification approach and other competitive benchmark methods.


title: Cyclic Codes from APN and Planar Functions

abstract: Cyclic codes are a subclass of linear codes and have applications in consumer electronics, data storage systems, and communication systems as they have efficient encoding and decoding algorithms. In this paper, almost perfect nonlinear functions and planar functions over finite fields are employed to construct a number of classes of cyclic codes. Lower bounds on the minimum weight of some classes of the cyclic codes are developed. The minimum weights of some other classes of the codes constructed in this paper are determined. The dimensions of the codes are flexible. Many of the codes presented in this paper are optimal or almost optimal in the sense that they meet some bound on linear codes. Ten open problems regarding cyclic codes from highly nonlinear functions are also presented.


title: Keck/NIRC2 Imaging of the Warped, Asymmetric Debris Disk around HD 32297

abstract: We present Keck/NIRC2 $K_{s}$ band high-contrast coronagraphic imaging of the luminous debris disk around the nearby, young A star HD 32297 resolved at a projected separation of $r$ = 0.3-2.5\arcsec{} ($\approx$ 35-280 AU). The disk is highly warped to the north and exhibits a complex, "wavy" surface brightness profile interior to $r$ $\approx$ 110 AU, where the peaks/plateaus in the profiles are shifted between the NE and SW disk lobes. The SW side of the disk is 50--100% brighter at $r$ = 35-80 AU, and the location of its peak brightness roughly coincides with the disk's mm emission peak. Spectral energy distribution modeling suggests that HD 32297 has at least two dust populations that may originate from two separate belts likely at different locations, possibly at distances coinciding with the surface brightness peaks. A disk model for a single dust belt including a phase function with two components and a 5-10 AU pericenter offset explains the disk's warped structure and reproduces some of the surface brightness profile's shape (e.g. the overall "wavy" profile, the SB peak/plateau shifts) but more poorly reproduces the disk's brightness asymmetry. Although there may be alternate explanations, agreement between the SW disk brightness peak and disk's peak mm emission is consistent with an overdensity of very small, sub-blowout-sized dust and large, 0.1-1 mm-sized grains at $\approx$ 45 AU tracing the same parent population of planetesimals. New near-IR and submm observations may be able to clarify whether even more complex grain scattering properties or dynamical sculpting by an unseen planet are required to explain HD 32297's disk structure.


title: Mott versus Slater-type metal-insulator transition in Mn-substituted Sr3Ru2O7

abstract: We present a temperature-dependent x-ray absorption (XAS) and resonant elastic x-ray scattering (REXS) study of the metal-insulator transition (MIT) in Sr3(Ru1-xMnx)2O7. The XAS results reveal that the MIT drives the onset of local antiferromagnetic correlations around the Mn impurities, a precursor of the long-range antiferromagnetism detected by REXS at T_order<T_MIT. This establishes that the MIT is of the Mott-type (electronic correlations) as opposed to Slater-type (magnetic order). While this behavior is induced by Mn impurities, the (1/4,1/4,0) order exists for a wide range of Mn concentrations, and points to an inherent instability of the parent compound.


title: Lifetime of Gapped Excitations in a Collinear Quantum Antiferromagnet

abstract: We demonstrate that local modulations of magnetic couplings have a profound effect on the temperature dependence of the relaxation rate of optical magnons in a wide class of antiferromagnets in which gapped excitations coexist with acoustic spin waves. In a two-dimensional collinear antiferromagnet with an easy-plane anisotropy, the disorder-induced relaxation rate of the gapped mode, Gamma_imp=Gamma_0+A(TlnT)^2, greatly exceeds the magnon-magnon damping, Gamma_m-m=BT^5, negligible at low temperatures. We measure the lifetime of gapped magnons in a prototype XY antiferromagnet BaNi2(PO4)2 using a high-resolution neutron-resonance spin-echo technique and find experimental data in close accord with the theoretical prediction. Similarly strong effects of disorder in the three-dimensional case and in noncollinear antiferromagnets are discussed.


title: Equal Aperture Angles Curve for some Convex Sets in the Plane

abstract: For given convex set $K$ in the plane (not necessarily bounded), we can construct the curve $C$ for which the visibility (aperture) angle of this set has the same, prescribed value. We give the implicit formula for $C$, discuss some issues concerning practical computations of $C$ and bring several simple examples, when the equal visibility angle curves can be effectively computed explicitly. We conclude with some remarks about possible directions for further research in this area. Extensive use of Open Source software (Sage, Pylab, IPython,...) is a key feature of this article.


title: The evolutionary connection between QSOs and SMGs: molecular gas in far-infrared luminous QSOs at z ~ 2.5

abstract: We present IRAM Plateau de Bure Interferometer observations of the 12CO(3-2) emission from two far-infrared luminous QSOs at z ~ 2.5 selected from the Herschel-ATLAS survey. These far-infrared bright QSOs were selected to have supermassive black holes (SMBHs) with masses similar to those thought to reside in sub-millimetre galaxies (SMGs) at z ~ 2.5; making them ideal candidates as systems in transition from an ultraluminous infrared galaxy phase to a sub-mm faint, unobscured, QSO. We detect 12CO(3-2) emission from both QSOs and we compare their baryonic, dynamical and SMBH masses to those of SMGs at the same epoch. We find that these far-infrared bright QSOs have similar dynamical but lower gas masses than SMGs. In particular we find that far-infrared bright QSOs have ~50+-23% less warm/dense gas than SMGs, which combined with previous results showing the QSOs lack the extended, cool reservoir of gas seen in SMGs, suggests that they are at a different evolutionary stage. This is consistent with the hypothesis that far-infrared bright QSOs represent a short (~1Myr) but ubiquitous phase in the transformation of dust obscured, gas-rich, starburst-dominated SMGs into unobscured, gas-poor, QSOs.


title: Molecular and atomic line surveys of galaxies I: the dense, star-forming phase as a beacon

abstract: We predict the space density of molecular gas reservoirs in the Universe, and place a lower limit on the number counts of carbon monoxide (CO), hydrogen cyanide (HCN) molecular and [CII] atomic emission lines in blind redshift surveys in the submillimeter-centimeter spectral regime. Our model uses: (a) recently available HCN Spectral Line Energy Distributions (SLEDs) of local Luminous Infrared Galaxies (LIRGs, L_IR>10^11 L_sun), (b) a value for epsilon=SFR/M_dense(H_2) provided by new developments in the study of star formation feedback on the interstellar medium and (c) a model for the evolution of the infrared luminosity density. Minimal 'emergent' CO SLEDs from the dense gas reservoirs expected in all star-forming systems in the Universe are then computed from the HCN SLEDs since warm, HCN-bright gas will necessarily be CO-bright, with the dense star-forming gas phase setting an obvious minimum to the total molecular gas mass of any star-forming galaxy. We include [CII] as the most important of the far-infrared cooling lines. Optimal blind surveys with the Atacama Large Millimeter Array (ALMA) could potentially detect very distant (z~10-12) [CII] emitters in the >ULIRG galaxy class at a rate of ~0.1-1 per hour (although this prediction is strongly dependent on the star formation and enrichment history at this early epoch), whereas the (high-frequency) Square Kilometer Array (SKA) will be capable of blindly detecting z>3 low-J CO emitters at a rate of ~40-70 per hour. The [CII] line holds special promise for the detection of metal-poor systems with extensive reservoirs of CO-dark molecular gas where detection rates with ALMA can reach up to 2-7 per hour in Bands 4-6.


title: Disrupting Primordial Planet Signatures: The Close Encounter of Two Single-Planet Exosystems in the Galactic Disc

abstract: During their main sequence lifetimes, the majority of all Galactic Disc field stars must endure at least one stellar intruder passing within a few hundred AU. Mounting observations of planet-star separations near or beyond this distance suggest that these close encounters may fundamentally shape currently-observed orbital architectures and hence obscure primordial orbital features. We consider the commonly-occurring fast close encounters of two single-planet systems in the Galactic Disc, and investigate the resulting change in the planetary eccentricity and semimajor axis. We derive explicit 4-body analytical limits for these variations and present numerical cross-sections which can be applied to localized regions of the Galaxy. We find that each wide-orbit planet has a few percent chance of escape and an eccentricity that will typically change by at least 0.1 due to these encounters. The orbital properties established at formation of millions of tight-orbit Milky Way exoplanets are likely to be disrupted.


title: Rapid dynamical chaos in an exoplanetary system

abstract: We report on the long-term dynamical evolution of the two-planet Kepler-36 system, which we studied through numerical integrations of initial conditions that are consistent with observations of the system. The orbits are chaotic with a Lyapunov time of only ~10 years. The chaos is a consequence of a particular set of orbital resonances, with the inner planet orbiting 34 times for every 29 orbits of the outer planet. The rapidity of the chaos is due to the interaction of the 29:34 resonance with the nearby first order 6:7 resonance, in contrast to the usual case in which secular terms in the Hamiltonian play a dominant role. Only one contiguous region of phase space, accounting for ~4.5% of the sample of initial conditions studied, corresponds to planetary orbits that do not show large scale orbital instabilities on the timescale of our integrations (~200 million years). The long-lived subset of the allowed initial conditions are those that satisfy the Hill stability criterion by the largest margin. Any successful theory for the formation of this system will need to account for why its current state is so close to unstable regions of phase space.


title: Self-completeness and spontaneous dimensional reduction

abstract: A viable quantum theory of gravity is one of the biggest challenges facing physicists. We discuss the confluence of two highly expected features which might be instrumental in the quest of a finite and renormalizable quantum gravity -- spontaneous dimensional reduction and self-completeness. The former suggests the spacetime background at the Planck scale may be effectively two-dimensional, while the latter implies a condition of maximal compression of matter by the formation of an event horizon for Planckian scattering. We generalize such a result to an arbitrary number of dimensions, and show that gravity in higher than four dimensions remains self-complete, but in lower dimensions it is not. In such a way we established an "exclusive disjunction" or "exclusive or" (XOR) between the occurrence of self-completeness and dimensional reduction, with the goal of actually reducing the unknowns for the scenario of the physics at the Planck scale. Potential phenomenological implications of this result are considered by studying the case of a two-dimensional dilaton gravity model resulting from dimensional reduction of Einstein gravity.


title: Evidence for asymmetric distribution of circumstellar material around Type Ia Supernovae

abstract: We study the properties of low-velocity material in the line of sight towards nearby Type Ia Supernovae (SNe Ia) that have measured late phase nebular velocity shifts (v_neb), thought to be an environment-independent observable. We have found that the distribution of equivalent widths of narrow blended Na I D1 & D2 and Ca II H & K absorption lines differs significantly between those SNe Ia with negative and positive v_neb, with generally stronger absorption for SNe Ia with v_neb > 0. A similar result had been found previously for the distribution of colors of SNe Ia, which was interpreted as a dependence of the temperature of the ejecta with viewing angle. Our work suggests that: 1) a significant part of these differences in color should be attributed to extinction, 2) this extinction is caused by an asymmetric distribution of circumstellar material (CSM) and 3) the CSM absorption is generally stronger on the side of the ejecta opposite to where the ignition occurs. Since it is difficult to explain 3) via any known physical processes that occur before explosion, we argue that the asymmetry of the CSM is originated after explosion by a stronger ionizing flux on the side of the ejecta where ignition occurs, probably due to a stronger shock breakout and/or more exposed radioactive material on one side of the ejecta. This result has important implications for both progenitor and explosion models.


title: Magnetization of cloud cores and envelopes and other observational consequences of reconnection diffusion

abstract: Recent observational results for magnetic fields in molecular clouds reviewed by Crutcher (2012) seem to be inconsistent with the predictions of the ambipolar diffusion theory of star formation. These include the measured decrease in mass to flux ratio between envelopes and cores, the failure to detect any self-gravitating magnetically subcritical clouds, the determination of the flat PDF of the total magnetic field strengths implying that there are many clouds with very weak magnetic fields, and the observed scaling $B \propto \rho^{2/3}$ that implies gravitational contraction with weak magnetic fields. We consider the problem of magnetic field evolution in turbulent molecular clouds and discuss the process of magnetic field diffusion mediated by magnetic reconnection. For this process that we termed "reconnection diffusion" we provide a simple physical model and explain that this process is inevitable in view of the present day understanding of MHD turbulence. We address the issue of the expected magnetization of cores and envelopes in the process of star formation and show that reconnection diffusion provides an efficient removal of magnetic flux that depends only on the properties of MHD turbulence in the core and the envelope. As a result, the magnetic flux trapped during the collapse in the envelope is being released faster than the flux trapped in the core, resulting in much weaker fields in envelopes than in cores, as observed. We provide simple semi-analytical model calculations which support this conclusion and qualitatively agree with the observational results. We argue that magnetic reconnection provides a solution to the magnetic flux problem of star formation that agrees better with observations than the long-standing ambipolar diffusion paradigm.


title: Molecular and atomic line surveys of galaxies II: unbiased estimates of their star formation mode

abstract: We make use of our 'minimal' cold interstellar medium (ISM) emission line model that predicts the molecular and atomic line emission per unit dense, star-forming gas mass (Geach & Papadopoulos 2012; Paper I) to examine the utility of key line ratios in surveys of the so-called star formation 'mode' as traced by xi_SF = M_dense(H_2)/M_total(H_2). We argue that xi_SF and its proxies provide very sensitive, extinction-free discriminators of rapid starburst/merger-driven versus secular quiescent/disk-like stellar mass assembly, with the most promising diagnostic to be applied in the near-future being CO(4-3)/[CI](1-0). These lines are accessible across nearly the full range 0<z<2 (thus covering the bulk of galaxy evolution) with the Atacama Large Millimeter Array. In addition to their diagnostic power, another advantage of this combination is the similar observed frequencies (Delta nu_0 ~ 30 GHz) of the lines, resulting in nearly spatially-matched beams for a fixed aperture, thus mitigating the effects of resolution/morphology bias in the interpretation of galaxy-averaged line ratios. Finally we discuss the capability of deep blind redshift surveys with the high frequency component of the Square Kilometer Arrray (SKA) in discovering H_2-rich galaxies with very low xi_SF values. These could be the progenitors of starburst galaxies seen prior to the onset of star formation; such galaxies could be a class of extreme outliers from local (gas surface density)-(star formation rate) scaling laws, which would exclude them from current star formatation or stellar mass selected samples. Our conservative model suggests that SKA could detect such systems residing at z~3 at a rate of 20-200 per hour.


title: Quantum Higgs branches of isolated N=2 superconformal field theories

abstract: We study the Higgs branches of the superconformal points of four-dimensional N=2 super Yang-Mills (SYM) which appear due to the occurrence of mutually local monopoles having appropriate charges. We show, for example, that the maximal superconformal point of SU(2n) SYM has a Higgs branch of the form C^2/Z_n. These Higgs branches are intrinsic to the superconformal field theory (SCFT) at the superconformal point, but do not appear in the SYM theory in which it is embedded. This is because the embedding is a UV extension of the SCFT in which some global symmetry acting on the Higgs branch is gauged irrelevantly. Higgs branches deduced from earlier direct studies of these isolated SCFTs using BPS wall-crossing or 3-d mirror symmetry agree with the ones we find here using just the Seiberg-Witten data for the SYM theories.


title: A Flavor Sector for the Composite Higgs

abstract: We discuss flavor violation in large N Composite Higgs models. We focus on scenarios in which the masses of the standard model fermions are controlled by hierarchical mixing parameters, as in models of Partial Compositeness. We argue that a separation of scales between flavor and Higgs dynamics can be employed to parametrically suppress dipole and penguin operators, and thus effectively remove the experimental constraints arising from the lepton sector and the neutron EDM. The dominant source of flavor violation beyond the standard model is therefore controlled by 4-fermion operators, whose Wilson coefficients can be made compatible with data provided the Higgs dynamics approaches a "walking" regime in the IR. Models consistent with all flavor and electroweak data can be obtained with a new physics scale within the reach of the LHC. Explicit scenarios may be realized in a 5D framework, the new key ingredient being the introduction of flavor branes where the wave functions of the bulk fermions end.


title: The Cosmic Infrared Background Experiment (CIBER): The Wide-Field Imagers

abstract: We have developed and characterized an imaging instrument to measure the spatial properties of the diffuse near-infrared extragalactic background light in a search for fluctuations from z > 6 galaxies during the epoch of reionization. The instrument is part of the Cosmic Infrared Background Experiment (CIBER), designed to observe the extragalactic background light above the Earth's atmosphere during a suborbital sounding rocket flight. The imaging instrument incorporates a 2x2 degree field of view, to measure fluctuations over the predicted peak of the spatial power spectrum at 10 arcminutes, and 7"x7" pixels, to remove lower redshift galaxies to a depth sufficient to reduce the low-redshift galaxy clustering foreground below instrumental sensitivity. The imaging instrument employs two cameras with \Delta \lambda / \lambda ~0.5 bandpasses centered at 1.1 and 1.6 microns to spectrally discriminate reionization extragalactic background fluctuations from local foreground fluctuations. CIBER operates at wavelengths where the electromagnetic spectrum of the reionization extragalactic background is thought to peak, and complements fluctuations measurements by AKARI and Spitzer at longer wavelengths. We have characterized the instrument in the laboratory, including measurements of the sensitivity, flat-field response, stray light performance, and noise properties. Several modifications were made to the instrument following a first flight in 2009 February. The instrument performed to specifications in subsequent flights in 2010 July and 2012 March, and the scientific data are now being analyzed.


title: Hierarchical Structure of Magnetohydrodynamic Turbulence In Position-Position-Velocity Space

abstract: Magnetohydrodynamic turbulence is able to create hierarchical structures in the interstellar medium that are correlated on a wide range of scales via the energy cascade. We use hierarchical tree diagrams known as dendrograms to characterize structures in synthetic Position-Position-Velocity (PPV) emission cubes of optically thin isothermal magnetohydrodynamic turbulence. We show that the structures and degree of hierarchy observed in PPV space are related to the physics of the gas, i.e. self-gravity and the global sonic and Alfvenic Mach number. Simulations with higher Alfvenic Mach number, self-gravity and supersonic flows display enhanced hierarchical structure. We observed a strong sonic and Alfvenic dependency when we apply the the statistical moments (i.e. mean, variance, skewness, kurtosis) to the dendrogram distribution. Larger magnetic field and sonic Mach number correspond to larger values of the moments. Application of the dendrogram to 3D density cubes, also known as Position-Position-Position cubes (PPP), reveals that the dominant emission contours in PPP and PPV are related for supersonic gas but not for subsonic. We also explore the effects of smoothing, thermal broadening and velocity resolution on the dendrograms in order to make our study more applicable to observational data. These results all point to hierarchical tree diagrams as being a promising additional tool for studying ISM turbulence and star forming regions in the direction of obtaining information on the degree of self-gravity, the Mach numbers and the complicated relationship between PPV and PPP.


title: Integrable boundaries in AdS/CFT: revisiting the Z=0 giant graviton and D7-brane

abstract: We consider the worldsheet boundary scattering and the corresponding boundary algebras for the Z=0 giant graviton and the Z=0 D7-brane in the AdS/CFT correspondence. We consider two approaches to the boundary scattering, the usual one governed by the (generalized) twisted Yangians and the q-deformed model of these boundaries governed by the quantum affine coideal subalgebras. We show that the q-deformed approach leads to boundary algebras that are of a more compact form than the corresponding twisted Yangians, and thus are favourable to use for explicit calculations. We obtain the q-deformed reflection matrices for both boundaries which in the q->1 limit specialize to the ones obtained using twisted Yangians.