TOP

Accepted Papers

  • Session: 1 | Room: 103-104 | Time: 11:00 – 11:20, Tuesday 16 Sept Link Prediction in Multi-modal Social Networks (Panagiotis Symeonidis, Christos Perentis)

    Authors

    Panagiotis Symeonidis, Aristotle University of Thessaloniki, Thessaloniki, Greece
    Christos Perentis, Fondazione Bruno Kessler (FBK)

    Abstract

    Online social networks like Facebook recommend new friends to users based on an explicit social network that users build by adding each other as friends. The majority of earlier work in link prediction infers new interactions between users by mainly focusing on a single network type. However, users also form several implicit social networks through their daily interactions like commenting on people’s posts or rating similarly the same products. Prior work primarily exploited both explicit and implicit social networks to tackle the group/item recommendation problem that recommends to users groups to join or items to buy. In this paper, we show that auxiliary information from the user-item network fruitfully combines with the friendship network to enhance friend recommendations. We transform the well-known Katz algorithm to utilize a multi-modal network and provide friend recommendations. We experimentally show that the proposed method is more accurate in recommending friends when compared with two single source path-based algorithms using both synthetic and real data sets.

  • Session: 1 | Room: 103-104 | Time: 11:20 – 11:40, Tuesday 16 Sept Density-Based Subspace Clustering in Heterogeneous Networks (Brigitte Boden, Martin Ester, Thomas Seidl)

    Authors

    Brigitte Boden, RWTH Aachen University
    Martin Ester, Simon Fraser University
    Thomas Seidl, RWTH Aachen University, Germany

    Abstract

    Many real-world data sets, like data from social media or bibliographic data, can be represented as heterogeneous networks with several vertex types. Often additional attributes are available for the vertices, such as keywords for a paper. Clustering vertices in such networks, and analyzing the complex interactions between clusters of different types, can provide useful insights into the structure of the data. To exploit the full information content of the data, clustering approaches should consider the connections in the network as well as the vertex attributes.We propose the density-based clustering model TCSC for the detection of clusters in heterogeneous networks that are densely connected in the network as well as in the attribute space. Unlike previous approaches for clustering heterogeneous networks, TCSC enables the detection of clusters that show similarity only in a subset of the attributes, which is more effective in the presence of a large number of attributes.

  • Session: 1 | Room: 103-104 | Time: 11:40 – 12:00, Tuesday 16 Sept Interestingness-driven Diffusion Process Summarization in Dynamic Networks (Qiang Qu, Siyuan Liu, Christian Jensen, Feida Zhu, Christos Faloutsos)

    Authors

    Qiang Qu, Aarhus University
    Siyuan Liu
    Christian Jensen
    Feida Zhu
    Christos Faloutsos, Carnegie Mellon University

    Abstract

    The widespread use of social networks enables the rapid diffusion of information, e.g., news, among users in very large communities. It is a substantial challenge to be able to observe and understand such diffusion processes, which may be modeled as networks that are both very large and highly dynamic. A key tool in this regard is data summarization. However, to the best of our knowledge, few existing studies aim to summarize graphs/networks for dynamics. Dynamic network offers new challenges over static settings, including time sensitivity and the needs for online interestingness evaluation and summary traceability, that render existing techniques inapplicable.We study the topic of dynamic network summarization: how to summarize dynamic networks with millions of nodes by only capturing the few most interesting nodes or edges over time, and we address the problem of computing summaries that represent information diffusion processes from start to end. Based on the concepts of diffusion radius and scope, we define interestingness measures in dynamic networks, and we propose OSNet, an online summarization framework for dynamic diffusion process networks.We report on extensive experiments with both synthetic and different large-scale real-life datasets. The study offers insight into the effectiveness, efficiency, and design properties of OSNet.

  • Session: 1 | Room: 103-104 | Time: 12:00 – 12:20, Tuesday 16 Sept FLIP: Active Learning for Relational Network Classification (Tanwistha Saha, Huzefa Rangwala, Carlotta Domeniconi)

    Authors

    Tanwistha Saha, George Mason University
    Huzefa Rangwala, George Mason University
    Carlotta Domeniconi

    Abstract

    Active learning in relational networks has gained popularity in recent years, especially for scenarios when the costs of obtaining training samples are very high. We investigate the problem of active learning for both single- and multi-labeled relational network classification in the absence of node features during training. The problem becomes harder when the number of labeled nodes available for training a model is limited due to budget constraints. The inability to use a traditional learning setup for classification of relational data, has motivated researchers to propose Collective Classification algorithms that jointly classifies all the test nodes in a network by exploiting the underlying correlation between the labels of a node and its neighbors. In this paper, we propose active learning algorithms based on different query strategies using a collective classification model where each node in a network can belong to either one class (single-labeled network) or multiple classes (multi-labeled network). We have evaluated our method on both single-labeled and multi-labeled networks, and our results are promising in both the cases for several real world datasets.

  • Session: 1 | Room: 103-104 | Time: 12:20 – 12:40, Tuesday 16 Sept Faster way to agony: discovering hierarchies in directed graphs (Nikolaj Tatti)

    Author

    Nikolaj Tatti, Aalto University

    Abstract

    Many real-world phenomena exhibit strong hierarchical structure. Consequently, in many real-world directed social networks vertices do not play equal role. Instead, vertices form a hierarchy such that the edges appear mainly from upper levels to lower levels. Discovering hierarchies from such graphs is a challenging problem that has gained attention. Formally, given a directed graph, we want to partition vertices into levels such that ideally there are only edges from upper levels to lower levels. From computational point of view, the ideal case is when the underlying directed graph is acyclic. In such case, we can partition the vertices into a hierarchy such that there are only edges from upper levels to lower edges. In practice, graphs are rarely acyclic, hence we need to penalize the edges that violate the hierarchy. One practical approach is agony, where each violating edge is penalized based on the severity of the violation. The fastest algorithm for computing agony requires O(nm^2) time. In the paper we present an algorithm for computing agony that has better theoretical bound, namely O(m^2). We also show that in practice the obtained bound is pessimistic and that we can use our algorithm to compute agony for large datasets. Moreover, our algorithm can be used as any-time algorithm.

  • Session: 2 | Room: 102 | Time: 11:00 – 11:20, Tuesday 16 Sept Flexible Shift-Invariant Locality and Globality Preserving Projections (Feiping Nie, Xiao Cai, Heng Huang)

    Authors

    Feiping Nie, UT Arlington
    Xiao Cai
    Heng Huang

    Abstract

    In data mining and machine learning, the embedding methods have commonly been used as a principled way to understand the high-dimensional data. To solve the out-of-sample problem, local preserving projection (LPP) was proposed and applied to many applications. However, LPP suffers two crucial deficiencies: 1) the LPP has no shift-invariant property which is an important property of embedding methods; 2) the rigid linear embedding is used as constraint, which often inhibits the optimal manifold structures finding. To overcome these two important problems, we propose a novel flexible shift-invariant locality and globality preserving projection method, which utilizes a newly defined graph Laplacian and the relaxed embedding constraint. The proposed objective is very challenging to solve, hence we derive a new optimization algorithm with rigorously proved global convergence. More importantly, we prove our optimization algorithm is a Newton method with fast quadratic convergence rate. Extensive experiments have been performed on six benchmark data sets. In all empirical results, our method shows promising results.

  • Session: 2 | Room: 102 | Time: 11:20 – 11:40, Tuesday 16 Sept Anomaly Detection with Score Functions based on the Reconstruction Error of the Kernel PCA (Laetitia Chapel, Chloé Friguet)

    Authors

    Laetitia Chapel, IRISA
    Chloé Friguet

    Abstract

    We propose a novel non-parametric statistical test that allows the detection of anomalies given a set of (possibly high dimensional) sample points drawn from a nominal probability distribution. Our test statistic is the distance of a query point mapped in a feature space to its projection on the eigen-structure of the kernel matrix computed on the sample points. Indeed, the eigenfunction expansion of a Gram matrix is dependent on the input data density f_0. The resulting statistical test is shown to be uniformly most powerful for a given false alarm level alpha when the alternative density is uniform over the support of the null distribution. The algorithm can be computed in O(n^3 + n^2) and testing a query point only involves matrix vector products. Our method is tested on both artificial and benchmarked real data sets and demonstrates good performances w.r.t. competing methods.

  • Session: 2 | Room: 102 | Time: 11:40 – 12:00, Tuesday 16 Sept Learning Binary Codes with Bagging PCA (Cong Leng, Jian Cheng, Ting Yuan, Hanqing Lu)

    Authors

    Cong Leng, Chinese Academy of Science
    Jian Cheng, Chinese Academy of Science
    Ting Yuan
    Hanqing Lu

    Abstract

    For the eigendecomposition based hashing approaches, the information caught in different dimensions is unbalanced and most of them is typically contained in the top eigenvectors. This often leads to an unexpected phenomenon that longer code does not necessarily yield better performance. This paper attempts to leverage the bootstrap sampling idea and integrate it with PCA, resulting in a new projection method called Bagging PCA, in order to learn effective binary codes. Specifically, a small fraction of the training data is randomly sampled to learn the PCA directions each time and only the top eigenvectors are kept to generate one piece of short code. This process is repeated several times and the obtained short codes are concatenated into one piece of long code. By considering each piece of short code as a “”super-bit””, the whole process is closely connected with the core idea of LSH. Both theoretical and experimental analyses demonstrate the effectiveness of the proposed method.

  • Session: 2 | Room: 102 | Time: 12:00 – 12:20, Tuesday 16 Sept A Unified Framework for Probabilistic Component Analysis (Mihalis Nicolaou, Stefanos Zafeiriou, Maja Pantic)

    Authors

    Mihalis Nicolaou, Imperial College London
    Stefanos Zafeiriou, Imperial College London
    Maja Pantic, Imperial College London

    Abstract

    We present a unifying framework which reduces the construction of probabilistic component analysis techniques to a mere selection of the latent neighbourhood, thus providing an elegant and principled framework for creating novel component analysis models as well as constructing probabilistic equivalents of deterministic component analysis methods. Under our framework, we unify many very popular and well-studied component analysis algorithms, such as Principal Component Analysis (PCA), Linear Discriminant Analysis (LDA), Locality Preserving Projections (LPP) and Slow Feature Analysis (SFA), some of which have no probabilistic equivalents in literature thus far. We firstly define the Markov Random Fields (MRFs) which encapsulate the latent connectivity of the aforementioned component analysis techniques; subsequently, we show that the projection directions produced by all PCA, LDA, LPP and SFA are also produced by the Maximum Likelihood (ML) solution of a single joint probability density function, composed by selecting one of the defined MRF priors while utilising a simple observation model. Furthermore, we propose novel Expectation Maximization (EM) algorithms, exploiting the proposed joint PDF, while we generalize the proposed methodologies to arbitrary connectivities via parametrizable MRF products. Theoretical analysis and experiments on both simulated and real world data show the usefulness of the proposed framework, by deriving methods which well outperform state-of-the-art equivalents.

  • Session: 2 | Room: 102 | Time: 12:20 – 12:40, Tuesday 16 Sept Interactive Knowledge-Based Kernel PCA (Dino Oglic, Daniel Paurat, Thomas Gaertner)

    Authors

    Dino Oglic, University of Bonn
    Daniel Paurat, University of Bonn
    Thomas Gaertner, Fraunhofer IAIS

    Abstract

    Data understanding is an iterative process in which domain experts combine their knowledge with the data at hand to explore and confirm hypotheses. One important set of tools for exploring hypotheses about data are visualizations. Often, however, traditional, unsupervised dimensionality reduction algorithms are used for visualization. These tools allow for interaction, i.e., exploring different visualizations, only by means of manipulating some technical parameters of the algorithm. Therefore, instead of being able to intuitively interact with the visualization, domain experts have to learn and argue about these technical parameters. In this paper we propose a knowledge-based kernel PCA approach that allows for intuitive interaction with data visualizations. Each embedding direction is given by a non-convex quadratic optimization problem over an ellipsoid and has a globally optimal solution in the kernel feature space. A solution can be found in polynomial time using the algorithm presented in this paper. To facilitate direct feedback, i.e., updating the whole embedding with a sufficiently high frame-rate during interaction, we reduce the computational complexity further by incremental up- and down-dating. Our empirical evaluation demonstrates the flexibility and utility of this approach.

  • Session: 3 | Room: 105 | Time: 11:00 – 11:20, Tuesday 16 Sept Optimal Thresholding of Classifiers to Maximize F1 Measure (Zachary Lipton, Charles Elkan, Balakrishnan Narayanaswamy)

    Authors

    Zachary Lipton, UCSD
    Charles Elkan, UC San Diego
    Balakrishnan Narayanaswamy

    Abstract

    This paper provides new insight into maximizing F1 measures in the context of binary classification and also in the context of multilabel classification. The harmonic mean of precision and recall, the F1 measure is widely used to evaluate the success of a binary classifier when one class is rare. Micro average, macro average, and per instance average F1 measures are used in multilabel classification. For any classifier that produces a real-valued output, we derive the relationship between the best achievable F1 value and the decision-making threshold that achieves this optimum. As a special case, if the classifier outputs are well-calibrated conditional probabilities, then the optimal threshold is half the optimal F1 value. As another special case, if the classifier is completely uninformative, then the optimal behavior is to classify all examples as positive. When the actual prevalence of positive examples is low, this behavior can be undesirable. As a case study, we discuss the results, which can be surprising, of maximizing F1 when predicting 26,853 labels for Medline documents.

  • Session: 3 | Room: 105 | Time: 11:20 – 11:40, Tuesday 16 Sept Rate-constrained ranking and the rate-weighted AUC (Louise Millard, Peter Flach, Julian Higgins)

    Authors

    Louise Millard, University of Bristol
    Peter Flach, University of Bristol
    Julian Higgins, University of Bristol

    Abstract

    Ranking tasks, where instances are ranked by a predicted score, are common in machine learning. Often only a proportion of the instances in the ranking can be processed, and this quantity, the predicted positive rate (PPR), may not be known precisely. In this situation, the evaluation of a model’s performance needs to account for these imprecise constraints on the PPR, but existing metrics such as the area under the ROC curve (AUC) and early retrieval metrics such as normalised discounted cumulative gain (NDCG) cannot do this. In this paper we introduce a novel metric, the rate-weighted AUC (rAUC), to evaluate ranking models when constraints across the PPR exist, and provide an efficient algorithm to estimate the rAUC using an empirical ROC curve. Our experiments show that rAUC, AUC and NDCG often select different models. We demonstrate the usefulness of rAUC on a practical application: ranking articles for rapid reviews in epidemiology.

  • Session: 3 | Room: 105 | Time: 11:40 – 12:00, Tuesday 16 Sept Rate-oriented point-wise confidence bounds for ROC curves (Louise Millard, Meelis Kull, Peter Flach)

    Authors

    Louise Millard, University of Bristol
    Meelis Kull, University of Bristol
    Peter Flach, University of Bristol

    Abstract

    Common approaches to generating confidence bounds around ROC curves have several shortcomings. We resolve these weaknesses with a new `rate-oriented’ approach. We generate confidence bounds composed of a series of confidence intervals for a consensus curve, each at a particular predicted positive rate (PPR), with the aim that each confidence interval contains new samples of this consensus curve with probability 95%. We propose two approaches; a parametric and a bootstrapping approach, which we base on a derivation from first principles. Our method is particularly appropriate with models used for a common type of task that we call rate-constrained, where a certain proportion of examples needs to be classified as positive by the model, such that the operating point will be set at a particular PPR value.

  • Session: 3 | Room: 105 | Time: 12:20 – 12:40, Tuesday 16 Sept On the null distribution of the precision and recall curve (Miguel Lopes, Gianluca Bontempi)

    Authors

    Miguel Lopes, ULB
    Gianluca Bontempi, Universite Libre de Bruxelles

    Abstract

    Precision recall curves (pr-curves) and the associated area under (AUPRC) are commonly used to assess the accuracy of information retrieval (IR) algorithms. An informative baseline is random selection. The associated probability distribution makes it possible to assess pr-curve significancy (as a p-value relative to the null of random). To our knowledge, no analytical expression of the null distribution of empirical pr-curves is available, and the only measure of significancy used in the literature relies on non-parametric Monte Carlo simulations. In this paper, we derive analytically the expected null pr-curve and AUPRC, for different interpolation strategies. The AUPRC variance is also derived, and we use it to propose a continuous approximation to the null AUPRC distribution, based on the beta distribution. Properties of the empirical pr-curve and common interpolation strategies are also discussed.

  • Session: S-ILP | Room: 101 | Time: 11:00 – 11:20, Tuesday 16 Sept Evidence-based Clustering for Scalable Inference in Markov Logic (Deepak Venugopal, Vibhav Gogate)

    Authors

    Deepak Venugopal, The University of Texas Dallas
    Vibhav Gogate, UT-Dallas

    Abstract

    Markov Logic is a powerful representation that unifies first-order logic and probabilistic graphical models. However, scaling-up inference in Markov Logic Networks (MLNs) is extremely challenging. Standard graphical model inference algorithms operate on the propositional Markov network obtained by grounding the MLN and do not scale well as the number of objects in the real-world domain increases. On the other hand, algorithms which perform inference directly at the first-order level, namely lifted inference algorithms, although more scalable than propositional algorithms, require the MLN to have specific symmetric structure. Worse still, evidence breaks symmetries, and the performance of lifted inference is the same as propositional inference (or sometimes worse, due to overhead). In this paper, we propose a general method for solving this “”evidence”” problem. The main idea in our method is to approximate the given MLN having, say, objects by an MLN having k objects such that k is much lesser than n and the results obtained by running potentially much faster inference on the smaller MLN are as close as possible to the ones obtained by running inference on the larger MLN. We achieve this by finding clusters of “”similar”” groundings using standard clustering algorithms (e.g., K-means), and replacing all groundings in the cluster by their cluster center. To this end, we develop a novel distance (or similarity) function for measuring the similarity between two groundings, based on the evidence presented to the MLN. We evaluated our approach on many different benchmark MLNs utilizing various clustering and inference algorithms. Our experiments clearly show the generality and scalability of our approach.

  • Session: S-ILP | Room: 101 | Time: 11:20 – 11:40, Tuesday 16 Sept Effective Blending of Two and Three-way Interactions for Modeling Multi-relational Data (Alberto Garcia-Duran, Antoine Bordes, Nicolas Usunier)

    Authors

    Alberto Garcia-Duran, CNRS
    Antoine Bordes, CNRS
    Nicolas Usunier, UTC, Compiegne

    Abstract

    Much work has been recently proposed to model relational data, especially in the multi-relational case, where different kinds of relationships are used to connect the various data entities. Previous attempts either consist of powerful systems with high capacity to model complex connectivity patterns, which unfortunately usually end up overfitting on rare relationships, or in approaches that trade capacity for simplicity in order to fairly model all relationships, frequent or not. In this paper, we propose a happy medium obtained by complementing a high-capacity model with a simpler one, both pre-trained separately and jointly fine- tuned. We show that our approach outperforms existing models on different types of relationships, and achieves state-of-the-art results on two benchmarks of the literature.

  • Session: S-ILP | Room: 101 | Time: 11:40 – 12:00, Tuesday 16 Sept Towards Automatic Feature Construction for Supervised Classification (Marc Boullé)

    Author

    Marc Boullé, Orange Labs

    Abstract

    We suggest an approach to automate variable construction for supervised learning, especially in the multi-relational setting. Domain knowledge is specified by describing the structure of data by the means of variables, tables and links across tables, and choosing construction rules. The space of variables that can be constructed is virtually infinite, which raises both combinatorial and over-fitting problems. We introduce a prior distribution over all the constructed variables, as well as an effective algorithm to draw samples of constructed variables from this distribution. Experiments show that the approach is robust and efficient.

  • Session: S-ILP | Room: 101 | Time: 12:00 – 12:20, Tuesday 16 Sept Fast Learning of Relational Dependency Networks (Oliver Schulte, Zhensong Qian, Arthur E. Kirkpatrick, Xiaoqian Yin, Yan Sun)

    Authors

    Oliver Schulte
    Zhensong Qian
    Arthur E. Kirkpatrick
    Xiaoqian Yin
    Yan Sun

    Abstract

    A Relational Dependency Network (RDN) is a directed graphical model widely used for multi-relational data. These networks allow cyclic dependencies, necessary to represent relational autocorrelations. We describe an approach for learning both the RDN’s structure and its parameters, given an input relational database: First learn a Bayesian network (BN), then transform the Bayesian network to an RDN. Thus fast Bayes net learning can provide fast RDN learning. The BN-to-RDN transform comprises a simple, local adjustment of the Bayes net structure and a closed-form transform of the Bayes net parameters. This method can learn an RDN for a dataset with a million tuples in minutes. We empirically compare our approach to state-of-the art RDN learning methods that use functional gradient boosting, on ve benchmark datasets. Learning RDNs via BNs scales much better to large datasets than learning RDNs with boosting, and provides competitive accuracy in predictions.

  • Session: S-ILP | Room: 101 | Time: 12:20 – 12:40, Tuesday 16 Sept Complex aggregates over subsets of elements (Celine Vens, Sofie Van Gassen, Tom Dhaene, Yvan Saeys)

    Authors

    Celine Vens
    Sofie Van Gassen
    Tom Dhaene
    Yvan Saeys

    Abstract

    Complex aggregates have been proposed as a way to bridge the gap between approaches that handle sets by imposing conditions on specific elements, and approaches that handle them by imposing conditions on aggregated values. A complex aggregate aggregates over a subset of the elements in a set, where this subset is defined by conditions on the attribute values. In this paper, we present a new type of complex aggregate, where this subset is defined to be a cluster of the set. This is useful if subsets that are relevant for the task at hand are difficult to describe in terms of attribute conditions. This work is motivated from the analysis of flow cytometry data, where the sets are cells, and the subsets are cell populations. We describe two approaches to aggregate over clusters, and validate one of them empirically, motivating future research in this direction.

  • Session: 4 | Room: 102 | Time: 14:00 – 14:20, Tuesday 16 Sept Attributed Graph Kernels Using the Jensen-Tsallis q-Differences (Lu Bai, Luca Rossi, Horst Bunke, Edwin Hancock)

    Authors

    Lu Bai, University of York
    Luca Rossi
    Horst Bunke
    Edwin Hancock

    Abstract

    We propose a family of attributed graph kernels based on mutual information measures, i.e., the Jensen-Tsallis (JT) q-differences (for q\in[1,2]) between probability distributions over the graphs. To this end, we first assign a probability to each vertex of the graph through a continuous-time quantum walk (CTQW). We then adopt the tree-index approach to strengthen the original vertex labels, and we show how the CTQW can induce a probability distribution over these strengthened labels. We show that our JT kernel (for q=1) overcomes the shortcoming of discarding non-isomorphic substructures arising in the R-convolution kernels. Moreover, we prove that the JT kernels generalize the Jensen-Shannon graph kernel (for q=1) and the classical subtree kernel (for q=2), respectively. Experimental evaluations demonstrate the effectiveness and efficiency of the JT kernels.

  • Session: 4 | Room: 102 | Time: 14:20 – 14:40, Tuesday 16 Sept Relative Comparison Kernel Learning with Auxiliary Kernels (Eric Heim, Hamed Valizadegan, Milos Hauskrecht)

    Authors

    Eric Heim, University of Pittsburgh
    Hamed Valizadegan, NASA Ames Research Center
    Milos Hauskrecht, University of Pittsburgh

    Abstract

    In this work we consider the problem of learning a positive semidefinite kernel matrix from relative comparisons of the form: “object A is more similar to object B than it is to C”, where comparisons are given by humans. Existing solutions to this problem assume many comparisons are provided to learn a meaningful kernel. However, this can be considered unrealistic for many real-world tasks since a large amount of human input is often costly or difficult to obtain. Because of this, only a limited number of these comparisons may be provided. We propose a new kernel learning approach that supplements the few relative comparisons with “auxiliary” kernels built from more easily extractable features in order to learn a kernel that more completely models the notion of similarity gained from human feedback. Our proposed formulation is a convex optimization problem that adds only minor overhead to methods that use no auxiliary information. Empirical results show that in the presence of few training relative comparisons, our method can learn kernels that generalize to more out-of-sample comparisons than methods that do not utilize auxiliary information, as well as similar metric learning methods.

  • Session: 4 | Room: 102 | Time: 14:40 – 15:00, Tuesday 16 Sept Approximate Consistency: Towards Foundations of Approximate Kernel Selection (Lizhong Ding, Shizhong Liao)

    Authors

    Lizhong Ding, Tianjin University
    Shizhong Liao

    Abstract

    Kernel selection is critical to kernel methods. Approximate kernel selection is an emerging approach to alleviating the computational burdens of kernel selection by introducing kernel matrix approximation. Theoretical problems faced by approximate kernel selection are how kernel matrix approximation impacts kernel selection and whether this impact can be ignored for large enough examples. In this paper, we introduce the notion of approximate consistency for kernel matrix approximation algorithm to tackle the theoretical problems and establish the preliminary foundations of approximate kernel selection. By analyzing the approximate consistency of kernel matrix approximation algorithms, we can answer the question that, under what conditions, and how, the approximate kernel selection criterion converges to the accurate one. Taking two kernel selection criteria as examples, we analyze the approximate consistency of Nystr¨om approximation and multilevel circulant matrix approximation. Finally, we empirically verify our theoretical findings.

  • Session: 4 | Room: 102 | Time: 15:00 – 15:20, Tuesday 16 Sept Kernel Principal Geodesic Analysis (Suyash Awate, Yen-Yun Yu, Ross Whitaker)

    Authors

    Suyash Awate, Indian Institute of Technology (IIT) Bombay
    Yen-Yun Yu, University of utah
    Ross Whitaker, University of Utah

    Abstract

    Kernel principal component analysis (kPCA) has been proposed as a dimensionality-reduction technique that achieves nonlinear, low-dimensional representations of data via the mapping to kernel feature space. Conventionally, kPCA relies on Euclidean statistics in kernel feature space. However, Euclidean analysis can make kPCA inefficient or incorrect for many popular kernels that map input points to a hypersphere in kernel feature space. To address this problem, this paper proposes a novel adaptation of kPCA, namely kernel principal geodesic analysis (kPGA), for hyperspherical statistical analysis in kernel feature space. This paper proposes tools for statistical analyses on the Riemannian manifold of the Hilbert sphere in the reproducing kernel Hilbert space, including algorithms for computing the sample weighted Karcher mean and eigen analysis of the sample weighted Karcher covariance. It then applies these tools to propose novel methods for (i)~dimensionality reduction and (ii)~clustering using mixture-model fitting. The results, on simulated and real-world data, show that kPGA-based methods perform favorably relative to their kPCA-based analogs.

  • Session: 4 | Room: 102 | Time: 15:20 – 15:40, Tuesday 16 Sept FASOLE: Fast Algorithm for Structured Output LEarning (Vojtech Franc)

    Author

    Vojtech Franc, Czech Technical University

    Abstract

    This paper proposes a novel Fast Algorithm for Structured Ouput LEarning (FASOLE). FASOLE implements the Sequential Dual Ascent (SDA) algorithm for solving the dual problem of the Structured Output Support Vector Machines (SO-SVM). Unlike existing instances of SDA algorithm applied for SO-SVM, the proposed FASOLE uses a different working set selection strategy which provides nearly maximal improvement of the objective function in each update. FASOLE processes examples in on-line fashion and it provides certificate of optimality. FASOLE is proven to find the $\veps$-optimal solution in $\SO(\frac{1}{\veps^2})$ time in the worst case. In the empirical comparison FASOLE consistently outperforms the existing state-of-the-art solvers, like the Cutting Plane Algorithm or the Block-Coordinate Frank-Wolfe algorithm, achieving up to an order of magnitude speedups while obtaining the same precise solution.

  • Session: 5 | Room: 105 | Time: 14:00 – 14:20, Tuesday 16 Sept Robust Distributed Training of Linear Classifiers Based on Divergence Minimization Principle (Junpei Komiyama, Hidekazu Oiwa, Hiroshi Nakagawa)

    Authors

    Junpei Komiyama, The University of Tokyo
    Hidekazu Oiwa, The University of Tokyo
    Hiroshi Nakagawa, The University of Tokyo

    Abstract

    We study a distributed training of a linear classifier in which the data is separated into many shards and each worker only has access to its own shard. The goal of this distributed training is to utilize the data of all shards to obtain a well-performing linear classifier. The iterative parameter mixture (IPM) framework (Mann et al., 2009) is a state-of-the-art distributed learning framework that has a strong theoretical guarantee when the data is clean. However, contamination on shards, which sometimes arises in real world environments, largely deteriorates the performances of the distributed training. To remedy the negative effect of the contamination, we propose a divergence minimization principle for the weight determination in IPM. From this principle, we can naturally derive the Beta-IPM scheme, which leverages the power of robust estimation based on the beta divergence. A mistake/loss bound analysis indicates the advantage of our Beta-IPM in contaminated environments. Experiments with various datasets revealed that, even when 80% of the shards are contaminated, Beta-IPM can suppress the influence of the contamination.

  • Session: 5 | Room: 105 | Time: 14:40 – 15:00, Tuesday 16 Sept Integer Bayesian Network Classifiers (Sebastian Tschiatschek, Karin Paul, Franz Pernkopf)

    Authors

    Sebastian Tschiatschek, Graz University of Technology
    Karin Paul
    Franz Pernkopf

    Abstract

    This paper introduces integer Bayesian network classifiers (BNCs), i.e. BNCs with discrete valued nodes where parameters are stored as integer numbers. These networks allow for efficient implementation in hardware while maintaining a (partial) probabilistic interpretation under scaling. An algorithm for the computation of margin maximizing integer parameters is presented and its efficiency is demonstrated. The resulting parameters have superior classification performance compared to parameters obtained by simple rounding of double-precision parameters, particularly for very low number of bits.

  • Session: 5 | Room: 105 | Time: 15:00 – 15:20, Tuesday 16 Sept Randomized Operating Point Selection in Adversarial Classification (Viliam Lisý, Robert Kessl, Tomas Pevny)

    Authors

    Viliam Lisý, CTU in Prague
    Robert Kessl, CTU in Prague
    Tomas Pevny, CTU in Prague

    Abstract

    Security systems for email spam filtering, network intrusion detection, steganalysis, and watermarking, frequently use classifiers to separate malicious behavior from legitimate. Typically, they use a fixed operating point minimizing the expected cost / error. This allows a rational attacker to deliver invisible attacks just below the detection threshold. We model this situation as a non-zero sum normal form game capturing attacker’s expected payoffs for detected and undetected attacks, and detector’s costs for false positives and false negatives computed based on the Receiver Operating Characteristic (ROC) curve of the classifier. The analysis of Nash and Stackelberg equilibria reveals that using a randomized strategy over multiple operating points forces the rational attacker to design less efficient attacks and substantially lowers the expected cost of the detector. We present the equilibrium strategies for sample ROC curves from network intrusion detection system and evaluate the corresponding benefits.

  • Session: 5 | Room: 105 | Time: 15:20 – 15:40, Tuesday 16 Sept Separating Rule Refinement and Rule Selection Heuristics in Inductive Rule Learning (Julius Stecher, Frederik Janssen, Johannes Fuernkranz)

    Authors

    Julius Stecher, TU Darmstadt
    Frederik Janssen, TU Darmstadt
    Johannes Fuernkranz, TU Darmstadt

    Abstract

    Conventional rule learning algorithms use a single heuristic for evaluating both, rule refinements and rule selection. However, whereas rule selection proceeds in a bottom-up specific-to-general direction, rule refinement typically operates top-down. Hence, we propose in this paper that criteria for evaluating rule refinements should reflect this by operating in an inverted coverage space. We motivate this choice by examples, and show that a suitably adapted rule learning algorithm outperforms its original counter-part on a large set of benchmark problems.

  • Session: 6 | Room: 106 | Time: 14:00 – 14:20, Tuesday 16 Sept Deterministic Feature Selection for Regularized Least Squares Classification (Saurabh Paul, Petros Drineas)

    Authors

    Saurabh Paul, CS Dept, RPI
    Petros Drineas, CS Dept, Rensselaer Polytechnic Inst

    Abstract

    We introduce a deterministic sampling based feature selection technique for regularized least squares classification. The method is unsupervised and gives worst-case guarantees of the generalization power of the classification function after feature selection with respect to the classification function obtained using all features. We perform experiments on synthetic and real-world datasets, namely a subset of TechTC-300 datasets, to support our theory. Experimental results indicate that the proposed method performs better than the existing feature selection methods.

  • Session: 6 | Room: 106 | Time: 14:20 – 14:40, Tuesday 16 Sept Automatic design of neuromarkers for OCD characterization (Oscar Garcia-Hinde, Emilio Parrado-Hernandez, Vanessa Gomez-Verdejo, Manel Martinez-Ramon, Carles Soriano-Mas)

    Authors

    Oscar Garcia-Hinde, Universidad Carlos III Madrid
    Emilio Parrado-Hernandez, Universidad Carlos III Madrid
    Vanessa Gomez-Verdejo, Universidad Carlos III Madrid
    Manel Martinez-Ramon, Universidad Carlos III Madrid
    Carles Soriano-Mas, IDIBELL

    Abstract

    This paper proposes a new paradigm to discover biomarkers capable of characterizing obsessive-compulsive disorder (OCD). These biomarkers, named neuromarkers, will be obtained through the analysis of sets of magnetic resonance images (MRI) of OCD patients and control subjects. The design of the neuromarkers stems from a method for the automatic discovery of clusters of voxels relevant to OCD recently published by the authors. With these clusters as starting point, we will define the neuromarkers as a set of measurements describing features of these individual regions. The principal goal of the project is to come up with a set of about 50 neuromarkers for OCD characterization that are easy to interpret and handle by the psychiatric community.

  • Session: 6 | Room: 106 | Time: 14:40 – 15:00, Tuesday 16 Sept Unsupervised Feature Selection via Unified Trace Ratio Formulation and K-means Clustering (TRACK) (De Wang, Feiping Nie, Heng Huang)

    Authors

    De Wang, Univ. of Texas at Arlington
    Feiping Nie, UT Arlington
    Heng Huang

    Abstract

    Feature selection plays a crucial role in scientific research and practical applications. In the real world applications, labeling data is time and labor consuming. Thus, unsupervised feature selection methods are desired for many practical applications. Linear discriminant analysis (LDA) with trace ratio criterion is a supervised dimensionality reduction method that has shown good performance to improve classifications. In this paper, we first propose a unified objective to seamlessly accommodate trace ratio formulation and K-means clustering procedure, such that the trace ratio criterion is extended to unsupervised model. After that, we propose a novel unsupervised feature selection method by integrating unsupervised trace ratio formulation and structured sparsity-inducing norms regularization. The proposed method can harness the discriminant power of trace ratio criterion, thus it tends to select discriminative features. Meanwhile, we also provide two important theorems to guarantee the unsupervised feature selection process. Empirical results on four benchmark data sets show that the proposed method outperforms other sate-of-the-art unsupervised feature selection algorithms in all three clustering evaluation metrics.

  • Session: 6 | Room: 106 | Time: 15:00 – 15:20, Tuesday 16 Sept Covariate-Correlated Lasso for Feature Selection (Bo Jiang, Chris Ding, Bin Luo)

    Authors

    Bo Jiang, Anhui University
    Chris Ding, University of Texas, Arlington
    Bin Luo

    Abstract

    Lasso-type variable selection has been increasingly adopted in many applications. In this paper, we propose a covariate-correlated Lasso that selects the covariates correlated more strongly with the response variable. We propose an efficient algorithm to solve this Lasso-type optimization and prove its convergence. Experiments on DNA gene expression data sets show that the selected covariates correlate more strongly with the response variable, and the residual values are decreased, indicating better covariate selection. The selected covariates lead to better classification performance.

  • Session: 7 | Room: 103-104 | Time: 14:00 – 14:20, Tuesday 16 Sept Clustering via Mode Seeking by Direct Estimation of the Gradient of a Log-Density (Hiroaki Sasaki, Aapo Hyvarinen, Masashi Sugiyama)

    Authors

    Hiroaki Sasaki, Tokyo Institute of Technology
    Aapo Hyvarinen
    Masashi Sugiyama

    Abstract

    Mean shift clustering finds the modes of the data probability density by identifying the zero points of the density gradient. Since it does not require to fix the number of clusters in advance, the mean shift has been a popular clustering algorithm in various application fields. A typical implementation of the mean shift is to first estimate the density by kernel density estimation and then compute its gradient. However, since a good density estimation does not necessarily imply an accurate estimation of the density gradient, such an indirect two-step approach is not reliable. In this paper, we propose a method to directly estimate the gradient of the log-density without going through density estimation. The proposed method gives the global solution analytically and thus is computationally efficient. We then develop a mean-shift-like fixed-point algorithm to find the modes of the density for clustering. As in the mean shift, one does not need to set the number of clusters in advance. We experimentally show that the proposed clustering method significantly outperforms the mean shift especially for high-dimensional data.

  • Session: 7 | Room: 103-104 | Time: 14:20 – 14:40, Tuesday 16 Sept Fast Gaussian Pairwise Constrained Spectral Clustering (David Chatel, Marc Tommasi, Pascal Denis)

    Authors

    David Chatel, Inria
    Marc Tommasi, Université Lille 3, Inria
    Pascal Denis, Inria

    Abstract

    We consider the problem of spectral clustering with partial supervision in the form of must-link and cannot-link constraints. Such pairwise constraints are common in problems like coreference resolution in natural language processing. The approach developed in this paper is to learn a new representation space for the data together with a distance in this new space. The representation space is obtained through a constraint-driven linear transformation of a spectral embedding of the data. Constraints are expressed with a Gaussian function that locally reweights the similarities in the projected space. A global, non-convex optimization objective is then derived and the model is learned via gradient descent techniques. Our algorithm is evaluated on standard datasets and compared with state of the art algorithms, like [Kamvar 2003,Li 2009,Wang and Davidson 2010]. Results on these datasets, as well on the CoNLL-2012 coreference resolution shared task dataset, show that our algorithm significantly outperforms related approaches and is also much more scalable.

  • Session: 7 | Room: 103-104 | Time: 14:40 – 15:00, Tuesday 16 Sept Ratio-based Multiple Kernel Clustering (Grigorios Tzortzis, Aristidis Likas)

    Authors

    Grigorios Tzortzis, University of Ioannina
    Aristidis Likas, University of Ioannina

    Abstract

    Maximum margin clustering (MMC) approaches extend the large margin principle of SVM to unsupervised learning with considerable success. In this work, we utilize the ratio between the margin and the intra-cluster variance, to explicitly consider both the separation and the compactness of the clusters in the objective. Moreover, we employ multiple kernel learning (MKL) to jointly learn the kernel and a partitioning of the instances, thus overcoming the kernel selection problem of MMC. Importantly, the margin alone cannot reliably reflect the quality of the learned kernel, as it can be enlarged by a simple scaling of the kernel. In contrast, our ratio-based objective is scale invariant and also invariant to the type of norm constraints on the kernel parameters. Optimization of the objective is performed using an iterative gradient-based algorithm. Comparative clustering experiments on various datasets demonstrate the effectiveness of the proposed formulation.

  • Session: 7 | Room: 103-104 | Time: 15:00 – 15:20, Tuesday 16 Sept Boosted Mean Shift Clustering (Yazhou Ren, Uday Kamath, Carlotta Domeniconi, Guoji Zhang)

    Authors

    Yazhou Ren, SCUT
    Uday Kamath
    Carlotta Domeniconi
    Guoji Zhang

    Abstract

    Mean shift is a nonparametric clustering technique that does not require the number of clusters in input and can find clusters of arbitrary shapes. While appealing, the performance of the mean shift algorithm is sensitive to the selection of the bandwidth, and can fail to capture the correct clustering structure when multiple modes exist in one cluster. DBSCAN is an efficient density based clustering algorithm, but it is also sensitive to its parameters and typically merges overlapping clusters. In this paper we propose Boosted Mean Shift Clustering (BMSC) to address these issues. BMSC partitions the data across a grid and applies mean shift locally on the cells of the grid, each providing a number of intermediate modes (iModes). A mode-boosting technique is proposed to select points in denser regions iteratively, and DBSCAN is utilized to partition the obtained iModes iteratively. Our proposed BMSC can overcome the limitations of mean shift and DBSCAN, while preserving their desirable properties. Complexity analysis shows its potential to deal with large-scale data and extensive experimental results on both synthetic and real benchmark data demonstrate its effectiveness and robustness to parameter settings.

  • Session: 7 | Room: 103-104 | Time: 15:20 – 15:40, Tuesday 16 Sept FILTA: Better View Discovery from Collections of Clusterings via Filtering (Yang Lei, Nguyen Xuan Vinh, Jeffrey Chan, James Bailey)

    Authors

    Yang Lei, University of Melbourne
    Nguyen Xuan Vinh, University of Melbourne
    Jeffrey Chan, University of Melbourne
    James Bailey, University of Melbourne

    Abstract

    Multiple clustering analysis is a growing area whose aim is to discover multiple high quality and non-redundant clusterings (views) of a dataset. A popular method for this task is meta clustering, which involves generation of a large number of base clusterings, that serve as input for further user navigation and refinement. However, the effectiveness of meta clustering for view discovery is highly dependent on the distribution of the base clusterings and open challenges exist with regard to its stability and noise tolerance. In this paper we propose a simple and effective filtering algorithm (FILTA) that can be flexibly used in conjunction with any meta clustering method.Given a (raw) set of base clusterings, FILTA employs information theoretic criteria to remove those having poor quality or high redundancy, yielding a filtered output set of clusterings. This filtered set is then highly suitable for further exploration, particularly the use of visualization for determining the dominant views that exist in the dataset. We evaluate FILTA on both synthetic and real world datasets, and see how its use can enhance view discovery for complex scenarios.

  • Session: 8 | Room: 103-104 | Time: 16:10 – 16:30, Tuesday 16 Sept Pushing-Down Tensor Decompositions over Unions to Promote Reuse of Materialized Decompositions (Mijung Kim, K. Selcuk Candan)

    Authors

    Mijung Kim, Arizona State University
    K. Selcuk Candan, Arizona State University

    Abstract

    From data collection to decision making, the life cycle of data often involves many steps of integration, manipulation, and analysis. To be able to provide end-to-end support for the full data life cycle, today’s data management and decision making systems increasingly combine operations for data manipulation, integration as well as data analysis. Tensor-relational model (TRM) is a framework proposed to support both relational algebraic operations (for data manipulation and integration) and tensor algebraic operations (for data analysis). In this paper, we consider joint processing of relational algebraic and tensor analysis operations. In particular, we focus on data processing workflows that involve data integration from multiple sources (through unions) and tensor decomposition tasks. While, in traditional relational algebra, the costliest operation is known to be the join, in a framework that provides both relational and tensor operations, tensor decomposition tends to be the computationally costliest operation. Therefore, it is most critical to reduce the cost of the tensor decomposition task by manipulating the data processing workflow in a way that reduces the cost of the tensor decomposition step. Therefore, in this paper, we consider data processing workflows involving tensor decomposition and union operations and we propose a novel scheme for pushing down the tensor decompositions over the union operations to reduce the overall data processing times and to promote reuse of materialized tensor decomposition results. Experimental results confirm the efficiency and effectiveness of the proposed scheme.

  • Session: 8 | Room: 103-104 | Time: 16:30 – 16:50, Tuesday 16 Sept Hierarchical Latent Tree Analysis for Topic Detection (Tengfei LIU, Nevin Zhang, Peixian Chen)

    Authors

    Tengfei LIU, HKUST
    Nevin Zhang
    Peixian Chen

    Abstract

    In the LDA approach to topic detection, a topic is determined by identifying the words that are used with high frequency when writing about the topic. However, high frequency words in one topic may be also used with high frequency in other topics. Thus they may not be the best words to characterize the topic. In this paper, we propose a new method for topic detection, where a topic is determined by identifying words that appear with high frequency in the topic and low frequency in other topics. We model patterns of word co-occurrence and co-occurrences of those patterns using a hierarchy of discrete latent variables. The states of the latent variables represent clusters of documents and they are interpreted as topics. The words that best distinguish a cluster from other clusters are selected to characterize the topic. Empirical results show that the new method yields topics with clearer thematic characterizations than the alternative approaches.

  • Session: 8 | Room: 103-104 | Time: 16:50 – 17:10, Tuesday 16 Sept Causal Clustering for 2-Factor Measurement Models (Peter Spirtes, Erich Kummerfeld, Joseph Ramsey, Renjie Yang, Richard Scheines)

    Authors

    Peter Spirtes, Carnegie Mellon University
    Erich Kummerfeld, Carnegie Mellon Univeristy
    Joseph Ramsey, Carnegie Mellon University
    Renjie Yang, Carnegie Mellon University
    Richard Scheines

    Abstract

    Many social scientists are interested in inferring causal relations between “latent” variables that they cannot directly measure. One strategy commonly used to make such inferences is to use the values of variables that can be measured directly (often answers to questions in surveys or test “items”) that are thought to be measures or “indicators” of the latent variables of interest, together with a hypothesized causal graph relating the latent variables to their indicators. To use the data on the indicators to draw inferences about the causal relations between the latent variables (known as the structural model), it is necessary to hypothesize causal relations between the indicators and the latents that they are intended to indirectly measure, (known as the measurement model). The problem addressed in this paper is how to reliably infer the measurement model given measurements of the indicators, without knowing anything about the structural model, which is ultimately the question of interest. In this paper, we develop the FindTwoFactorClusters (FTFC) algorithm, a search algorithm that, in addition to being faster than existing algorithms based on vanishing tetrad constraints, also works for a more complex class of measurement models, and does not assume that the structural model is linear.

  • Session: 8 | Room: 103-104 | Time: 17:10 – 17:30, Tuesday 16 Sept On learning matrices with orthogonal columns or disjoint supports (Kevin Vervier, Pierre Mahé, Alexandre d’Aspremont, Jean-Baptiste Veyrieras, Jean-Philippe Vert)

    Authors

    Kevin Vervier
    Pierre Mahé
    Alexandre d’Aspremont
    Jean-Baptiste Veyrieras
    Jean-Philippe Vert, Mines ParisTech

    Abstract

    We investigate new matrix penalties to jointly learn linear models with orthogonality constraints, generalizing the work of Xiao et al. (2011) who proposed a strictly convex matrix norm for orthogonal transfer. We show that this norm converges to a particular atomic norm when its convexity parameter decreases, leading to new algorithmic solutions to minimize it. We also investigate concave formulations of this norm, corresponding to more aggressive strategies to induce orthogonality, and show how these penalties can also be used to learn sparse models with disjoint supports.

  • Session: 8 | Room: 103-104 | Time: 17:30 – 17:50, Tuesday 16 Sept Scalable Moment-based Inference for Latent Dirichlet Allocation (Chi Wang, Xueqing Liu, Yanglei Song, Jiawei Han)

    Authors

    Chi Wang, UIUC
    Xueqing Liu
    Yanglei Song
    Jiawei Han

    Abstract

    Topic models such as Latent Dirichlet Allocation have been useful text analysis methods of wide interest. Recently, moment-based inference with provable performance has been proposed for topic models. Compared with inference algorithms that approximate the maximum likelihood objective, moment-based inference has theoretical guarantee in recovering model parameters. One such inference method is tensor orthogonal decomposition, which requires only mild assumptions for exact recovery of topics. However, it suffers from scalability issue due to creation of dense, high-dimensional tensors. In this work, we propose a speedup technique by leveraging the special structure of the tensors. It is efficient in both time and space, and only requires passing the corpus twice. It improves over the state-of-the-art inference algorithm by one to three orders of magnitude, while preserving equal inference ability.

  • Session: 9 | Room: 102 | Time: 16:10 – 16:30, Tuesday 16 Sept Distinct Chains for Different Instances: an Effective Strategy for Multi-Label Classifier Chains (Pablo Silva, Eduardo Gonçalves, Alex Freitas, Alexandre Plastino)

    Authors

    Pablo Silva, Fluminense Federal University
    Eduardo Gonçalves, Fluminense Federal University
    Alex Freitas, Kent University
    Alexandre Plastino, Fluminense Federal University

    Abstract

    Multi-label classification (MLC) is a predictive problem in which an object may be associated with multiple labels. One of the most prominent MLC methods is the classifier chains (CC). This method induces q binary classifiers, where q represents the number of labels. Each one is responsible for predicting a specific label. These q classifiers are linked in a chain, such that at classification time each classifier considers the labels predicted by the previous ones as additional information. Although the performance of CC is largely influenced by the chain ordering, the original method uses a random ordering. To cope with this problem, in this paper we propose a novel method which is capable of finding a specific and more effective chain for each new instance to be classified. Experiments have shown that the proposed method obtained, overall, higher predictive accuracies than the well-established binary relevance, CC and CC ensemble methods.

  • Session: 9 | Room: 102 | Time: 16:30 – 16:50, Tuesday 16 Sept Bi-Directional Representation Learning for Multi-label Classification (Xin Li, Yuhong Guo)

    Authors

    Xin Li, Temple University
    Yuhong Guo, Temple University

    Abstract

    Multi-label classification is a central problem in many application domains. In this paper, we present a novel supervised bi-directional model that learns a low-dimensional mid-level representation for multi-label classification. Unlike traditional multi-label learning methods which identify intermediate representations from either the input space or the output space but not both, the mid-level representation in our model has two complementary parts that capture intrinsic information of the input data and the output labels respectively under the auto encoder principle while augmenting each other for the target output label prediction. The resulting optimization problem can be solved efficiently using an iterative procedure with alternating steps, while closed-form solutions exist for one major step. Our experiments conducted on a variety of multi-label data sets demonstrate the efficacy of the proposed bi-directional representation learning model for multi-label classification.

  • Session: 9 | Room: 102 | Time: 16:50 – 17:10, Tuesday 16 Sept Gaussian Process Multi-task Learning Using Joint Feature Selection (Srijith P. K., Shirish Shevade)

    Authors

    Srijith P. K., Indian Institute of Science
    Shirish Shevade, Indian Institute of Science

    Abstract

    Multi-task learning involves solving multiple related learning problems by sharing some common structure for improved generalization performance. A promising idea to multi-task learning is joint feature selection where a sparsity pattern is shared across task specific feature representations. In this paper, we propose a novel Gaussian Process (GP) approach to multi-task learning based on joint feature selection. The novelty of the proposed approach is that it captures the task similarity by sharing a sparsity pattern over the kernel hyper-parameters associated with each task. This is achieved by considering a hierarchical model which imposes a multi-Laplacian prior over the kernel hyper-parameters. This leads to a flexible GP model which can handle a wide range of multi-task learning problems and can identify features relevant across all the tasks. The hyper-parameter estimation results in an optimization problem which is solved using a block co-ordinate descent algorithm. Experimental results on synthetic and real world multi-task learning data sets demonstrate that the flexibility of the proposed model is useful in getting better generalization performance.

  • Session: 9 | Room: 102 | Time: 17:10 – 17:30, Tuesday 16 Sept Conic Multi-Task Classification (Cong Li, Michael Georgiopoulos, Georgios Anagnostopoulos)

    Authors

    Cong Li, University of Central Florida
    Michael Georgiopoulos, University of Central Florida
    Georgios Anagnostopoulos, Florida Institute of Technology

    Abstract

    Traditionally, Multi-task Learning (MTL) models optimize the average of task-related objective functions, which is an intuitive approach and which we will be referring to as Average MTL. However, a more general framework, referred to as Conic MTL, can be formulated by considering conic combinations of the objective functions instead; in this framework, Average MTL arises as a special case, when all combination coefficients equal 1. Although the advantage of Conic MTL over Average MTL has been shown experimentally in previous works, no theoretical justification has been provided to date. In this paper, we derive a generalization bound for the Conic MTL method, and demonstrate that the tightest bound is not necessarily achieved, when all combination coefficients equal 1; hence, Average MTL may not always be the optimal choice, and it is important to consider Conic MTL. As a byproduct of the generalization bound, it also theoretically explains the good experimental results of previous relevant works. Finally, we propose a new Conic MTL model, whose conic combination coefficients minimize the generalization bound, instead of choosing them heuristically as has been done in previous methods. The rationale and advantage of our model is demonstrated and verified via a series of experiments by comparing with several other methods.

  • Session: 9 | Room: 102 | Time: 17:30 – 17:50, Tuesday 16 Sept Random forests with random projections of the output space for high dimensional multi-label classification (Arnaud Joly, Pierre Geurts, Louis Wehenkel)

    Authors

    Arnaud Joly, University of Liège
    Pierre Geurts, University of Liege
    Louis Wehenkel, University of Liege

    Abstract

    We adapt the idea of random projections applied to the output space, so as to enhance tree-based ensemble methods in the context of multi-label classification. We show how learning time complexity can be reduced without affecting computational complexity and accuracy of predictions. We also show that random output space projections may be used in order to reach different bias-variance tradeoffs, over a broad panel of benchmark problems, and that this may lead to improved accuracy while reducing significantly the computational burden of the learning stage.

  • Session: 10 | Room: 105 | Time: 16:50 – 17:10, Tuesday 16 Sept Revisit Behavior in Social Media: The Phoenix-R Model and Discoveries (Flavio Figueiredo, Jussara Almeida, Christos Faloutsos, Bruno Ribeiro, Yasuko Matsubara)

    Authors

    Flavio Figueiredo, UFMG
    Jussara Almeida, Universidade Federal de Minas Gerais
    Christos Faloutsos, Carnegie Mellon University
    Bruno Ribeiro, Carnegie Mellon University
    Yasuko Matsubara, Kumamoto University

    Abstract

    How many listens will an artist receive on a online radio? How about plays on a YouTube video? How many of these visits are new or returning users? Modeling and mining popularity dynamics of social activity has important implications for researchers, content creators and providers. We here investigate the effect of revisits (successive visits from a single user) on content popularity. Using four datasets of social activity, with up to tens of millions media objects (e.g., YouTube videos, Twitter hashtags or LastFM artists), we show the effect of revisits in the popularity evolution of such objects. Secondly, we propose the Phoenix-R model which captures the popularity dynamics of individual objects. Phoenix-R has the desired properties of being: (1) parsimonious, being based on the minimum description length principle, and achieving lower root mean squared error than state-of-the-art baselines; (2) applicable, the model is effective for predicting future popularity values of objects.

  • Session: 10 | Room: 105 | Time: 17:10 – 17:30, Tuesday 16 Sept Conditional Log-linear Models for Mobile Application Usage Prediction (Jingu Kim, Taneli Mielikäinen)

    Authors

    Jingu Kim, Nokia
    Taneli Mielikäinen, Nokia

    Abstract

    Over the last decade, mobile device usage has evolved rapidly from basic calling and texting to primarily using applications. On average, smartphone users have tens of applications installed in their devices. As the number of installed applications grows, finding a right application at a particular moment is becoming more challenging. To alleviate the problem, we study the task of predicting applications that a user is most likely going to use at a given situation. We formulate the prediction task with a conditional log-linear model and present an online learning scheme suitable for resource-constrained mobile devices. Using real-world mobile application usage data, we evaluate the performance and the behavior of the proposed solution against other prediction methods. Based on our experimental evaluation, the proposed approach offers competitive prediction performance with moderate resource needs.

  • Session: 10 | Room: 105 | Time: 17:30 – 17:50, Tuesday 16 Sept Students, Teachers, Exams and MOOCs: Predicting and Optimizing Attainment In Web-Based Education Using A Probabilistic Graphical Model (Yoram Bachrach, Bar Shalem, John Guiver, Chris Bishop)

    Authors

    Yoram Bachrach, Microsoft Research
    Bar Shalem, Bar-Ilan University
    John Guiver, Microsoft Research
    Chris Bishop, Microsoft Research

    Abstract

    We propose a probabilistic graphical model for predicting student attainment in web-based education. We empirically evaluate our model on a crowdsourced dataset with students and teachers; Teachers prepared lessons on various topics. Students read lessons by various teachers and then solved a multiple choice exam. Our model gets input data regarding past interactions between students and teachers and past student attainment. It then estimates abilities of students, competence of teachers and difficulty of questions, and predicts future student outcomes. We show that our model’s predictions are more accurate than heuristic approaches. We also show how demographic profiles and personality traits correlate with student performance in this task. Finally, given a limited pool of teachers, we propose an approach for using information from our model to maximize the number of students passing an exam of a given difficulty, by optimally assigning teachers to students. We evaluate the potential impact of our optimization approach using a simulation based on our dataset, showing an improvement in the overall performance.

  • Session: 11 | Room: 106 | Time: 16:10 – 16:30, Tuesday 16 Sept Fast estimation of the pattern frequency spectrum (Matthijs van Leeuwen, Antti Ukkonen)

    Authors

    Matthijs van Leeuwen, KU Leuven
    Antti Ukkonen, HIIT

    Abstract

    Both exact and approximate counting of the number of frequent patterns for a given frequency threshold are hard problems. Still, having even coarse prior estimates of the number of patterns is useful, as these can be used to appropriately set the threshold and avoid waiting endlessly for an unmanageable number of patterns. Moreover, we argue that the number of patterns for different thresholds is an interesting summary statistic of the data: the pattern frequency spectrum. To enable fast estimation of the number of frequent patterns, we adapt the classical algorithm by Knuth for estimating the size of a search tree. Although the method is known to be theoretically suboptimal, we demonstrate that in practice it not only produces very accurate estimates, but is also very efficient. Moreover, we introduce a small variation that can be used to estimate the number of patterns under constraints for which the Apriori property does not hold. The empirical evaluation shows that this approach obtains good estimates for closed itemsets. Finally, we show how the method, together with isotonic regression, can be used to quickly and accurately estimate the frequency pattern spectrum: the curve that shows the number of patterns for every possible value of the frequency threshold. Comparing such a spectrum to one that was constructed using a random data model immediately reveals whether the dataset contains any structure of interest.

  • Session: 11 | Room: 106 | Time: 16:30 – 16:50, Tuesday 16 Sept A Fast Method of Statistical Assessment for Combinatorial Hypotheses Based on Frequent Itemset Enumeration (Shin-ichi Minato, Takeaki Uno, Koji Tsuda, Aika Terada, Jun Sese)

    Authors

    Shin-ichi Minato, Hokkaido University
    Takeaki Uno, National Institute of Informatics, Japan
    Koji Tsuda, The University of Tokyo
    Aika Terada, Ochanomizu University
    Jun Sese, Ochanomizu University

    Abstract

    In many scientific communities using experiment databases, one of the crucial problem is how to assess the statistical significance (P-value) of a discovered hypothesis. Especially, combinatorial hypothesis assessment is a hard problem because it requires a multiple-testing procedure with a very large factor of the P-value correction. Recently, Terada et al. proposed a novel method of the P-value correction, called “Limitless Arity Multiple-testing Procedure” (LAMP), which is based on frequent itemset enumeration to exclude meaninglessly infrequent itemsets which never be significant. The LAMP makes much more accurate P-value correction than previous method, and it empowers the scientific discovery. However, the original LAMP implementation is sometimes too time-consuming for practical databases. We propose a new LAMP algorithm that essentially executes itemset mining algorithm once, while the previous one executes many times. Our experimental results show that the proposed method is much (10 to 100 times) faster than the original LAMP. This algorithm enables us to discover significant P-value patterns in quite short time even for very large-scale databases.

  • Session: 11 | Room: 106 | Time: 16:50 – 17:10, Tuesday 16 Sept Ranked Tiling (Thanh Le Van, Matthijs van Leeuwen, Siegfried Nijssen, Ana Carolina Fierro, Kathleen Marchal, Luc De Raedt)

    Authors

    Thanh Le Van, KULeuven
    Matthijs van Leeuwen, KU Leuven
    Siegfried Nijssen, KU Leuven
    Ana Carolina Fierro, KULeuven
    Kathleen Marchal, KULeuven
    Luc De Raedt, KU Leuven

    Abstract

    Tiling is a well-known pattern mining technique. Traditionally, it discovers large areas of ones in binary databases or matrices, where an area is defined by a set of rows and a set of columns. In this paper, we introduce the novel problem of ranked tiling, which is concerned with finding interesting areas in ranked data. In this data, each transaction defines a complete ranking of the columns. Ranked data occurs naturally in applications like sports or other competitions. It is also a useful abstraction when dealing with numeric data in which the rows are incomparable. We introduce a scoring function for ranked tiling, as well as an algorithm using constraint programming and optimization principles. We empirically evaluate the approach on both synthetic and real-life datasets, and demonstrate the applicability of the framework in several case studies. One case study involves a heterogeneous dataset concerning the discovery of biomarkers for different subtypes of breast cancer patients. An analysis of the tiles by a domain expert shows that our approach can lead to the discovery of novel insights.

  • Session: 11 | Room: 106 | Time: 17:10 – 17:30, Tuesday 16 Sept A Lossless Data Reduction For Mining Constrained Patterns in n-ary Relations (Gabriel Poesia, Loic Cerf)

    Authors

    Gabriel Poesia, Universidade Federal de Minas Gerais
    Loic Cerf, UFMG Belo Horizonte, Brazil

    Abstract

    Given a binary relation, listing the itemsets takes exponential time. The problem grows worse when searching for analog patterns defined in n-ary relations. However, real-life relations are sparse and, with a greater number n of dimensions, they tend to be even sparser. Moreover, not all itemsets are searched. Only those satisfying some user-defined constraints, such as minimal size constraints. This article proposes to exploit together the sparsity of the relation and the presence of constraints satisfying a common property, the monotonicity per dimension. It details a pre-processing step to identify and erase n-tuples whose removal does not change the collection of patterns to be discovered. That reduction of the relation is achieved in a time and a space that is linear in the number of n-tuples. Experiments on two real-life datasets show that, whatever the algorithm used afterward to actually list the patterns, the pre-process allows to lower the overall running time by a factor typically ranging from 10 to 100.

  • Session: 12 | Room: 105 | Time: 10:10 – 10:30, Wednesday 17 Sept Convergence of Min-Sum-Min Message-Passing for Quadratic Optimization (Guoqiang Zhang, Richard Heusdens)

    Authors

    Guoqiang Zhang, Delft University of Technology
    Richard Heusdens, Delft University of Technology

    Abstract

    We propose a new message-passing algorithm for the quadratic optimization problem. As opposed to the min-sum algorithm, the new algorithm involves two minimizations and one summation at each iteration. The new min-sum-min algorithm exploits feedback from last iteration in generating new messages, resembling the Jacobi-relaxation algorithm. We show that if the feedback signal is large enough, the min-sum-min algorithm is guaranteed to converge to the optimal solution. Experimental results show that the min-sum-min algorithm outperforms two reference methods w.r.t. the convergence speed.

  • Session: 12 | Room: 105 | Time: 10:30 – 10:50, Wednesday 17 Sept Error-bounded Approximations for Infinite-horizon Discounted Decentralized POMDPs (Jilles Dibangoye, Olivier Buffet, Francois Charpillet)

    Authors

    Jilles Dibangoye, Inria
    Olivier Buffet, Inria
    Francois Charpillet, Inria

    Abstract

    We address decentralized stochastic control problems represented as decentralized partially observable Markov decision processes (Dec-POMDPs). This formalism provides a general model for decision-making under uncertainty in cooperative, decentralized settings, but the worst-case complexity makes it difficult to solve optimally (NEXP-complete). Recent advances suggest recasting Dec-POMDPs into continuous-state and deterministic MDPs. In this form, however, states and actions are embedded into high-dimensional spaces, making accurate estimate of states and greedy selection of actions intractable for all but trivial-sized problems. The primary contribution of this paper is the first framework for error-monitoring during approximate estimation of states and selection of actions. Such a framework permits us to convert state-of-the-art exact methods into error-bounded algorithms, which results in a scalability increase as demonstrated by experiments over problems of unprecedented sizes.

  • Session: 12 | Room: 105 | Time: 10:50 – 11:10, Wednesday 17 Sept Fast LSTD using stochastic approximation: Finite time analysis and application to traffic control (Prashanth L.A, Nathaniel Korda, Remi Munos)

    Authors

    Prashanth L.A., Inria
    Nathaniel Korda, Oxford university
    Remi Munos, Inria

    Abstract

    We propose a stochastic approximation based method with randomization of samples for policy evaluation using the least squares temporal difference (LSTD) algorithm. Our method results in an O(d) improvement in complexity in comparison to vanilla LSTD, where d is the dimension of the data. We provide convergence rate results for our proposed method, both in high probability and in expectation. Moreover, we also establish that using our scheme in place of LSTD does not impact the rate of convergence of the approximate value function to the true value function. This result coupled with the low complexity of our method makes it attractive for implementation in big data settings, where d is large. Further, we also analyse a similar low-complexity alternative for least squares regression and provide finite-time bounds there. We demonstrate the practicality of our method for LSTD empirically by combining it with the LSPI algorithm in a traffic signal control application.

  • Session: 13 | Room: 106 | Time: 10:10 – 10:30, Wednesday 17 Sept Kernel Alignment Inspired Linear Discriminant Analysis (Shuai Zheng, Chris Ding)

    Authors

    Shuai Zheng, UT Arlington
    Chris Ding, University of Texas, Arlington

    Abstract

    Kernel alignment measures the degree of similarity between two kernels. In this paper, inspired from kernel alignment, we propose a new Linear Discriminant Analysis (LDA) formulation, kernel alignment LDA (kaLDA). We first define two kernels, data kernel and class indicator kernel. The problem is to find a subspace to maximize the alignment between subspace-transformed data kernel and class indicator kernel. Surprisingly, the kernel alignment induced kaLDA objective function is very similar to classical LDA and can be expressed using between-class and total scatter matrices. This can be extended to multi-label data. We use a Stiefel-manifold gradient descent algorithm to solve this problem. We perform experiments on 8 single-label and 6 multi-label data sets. Results show that kaLDA has very good performance on many single-label and multi-label problems.

  • Session: 13 | Room: 106 | Time: 10:30 – 10:50, Wednesday 17 Sept Deconstructing Kernel Machines (Mohsen Ali, Muhammad Rushdi, Jeffrey Ho)

    Author

    Mohsen Ali, UF
    Muhammad Rushdi
    Jeffrey Ho, UF

    Abstract

    This paper studies the following problem: Given an SVM (kernel)-based binary classifier $\bC$ as a black-box oracle, how much can we learn of its internal working by querying it? Specifically, we assume the feature space $\RR^d$ is known and the kernel machine has $m$ support vectors such that $d > m$ (or $d >> m$), and in addition, the classifier $\bC$ is laconic in the sense that for a feature vector, it only provides a predicted label ($\pm 1$) without divulging other information such as margin or confidence level. We formulate the the problem of understanding the inner working of $\bC$ as characterizing the decision boundary of the classifier, and we introduce the simple notion of bracketing to sample points on the decision boundary within a prescribed accuracy. For the five most common types of kernel function, linear, quadratic and cubic polynomial kernels, hyperbolic tangent kernel and Gaussian kernel, we show that with O(dm) number of queries, the type of kernel function and the (kernel) subspace spanned by the support vectors can be determined. In particular, for polynomial kernels, additional O(m^3) queries are sufficient to reconstruct the entire decision boundary, providing a set of quasi-support vectors that can be used to efficiently evaluate the deconstructed classifier. We speculate briefly on the future application potential of deconstructing kernel machines and we present experimental results validating the proposed method. A simple user-friendly MATLAB implementation has been submitted as supplemental material for review.

  • Session: 13 | Room: 106 | Time: 10:50 – 11:10, Wednesday 17 Sept Preventing Over-Fitting of Cross-Validation with Kernel Stability (Yong Liu, Shali Jiang, Shizhong Liao)

    Authors

    Yong Liu, Tianjin University
    Shali Jiang, Tianjin University
    Shizhong Liao

    Abstract

    Kernel selection is critical to kernel methods. Cross-validation (CV) is a widely accepted kernel selection method. However, the CV based estimates generally exhibit a relatively high variance and are therefore prone to over-fitting. In order to prevent the high variance, we first propose a novel version of stability, called kernel stability. This stability quantifies the perturbation of the kernel matrix with respect to the changes in the training set. Then we establish the connection between the kernel stability and variance of CV. By restricting the derived upper bound of the variance, we present a kernel selection criterion, which can prevent the high variance of CV and hence guarantee good generalization performance. Furthermore, we derive a closed form for the estimate of the kernel stability, making the criterion based on the kernel stability computationally efficient. Theoretical analysis and experimental results demonstrate that our criterion is sound and effective.

  • Session: 14 | Room: 103-104 | Time: 10:30 – 10:50, Wednesday 17 Sept Beyond Blocks: Hyperbolic Community Detection (Miguel Araujo, Stephan Günnemann, Gonzalo Mateos, Christos Faloutsos)

    Authors

    Miguel Araujo, CMU
    Stephan Günnemann, CMU
    Gonzalo Mateos, CMU
    Christos Faloutsos, Carnegie Mellon University

    Abstract

    What do real communities in social networks look like? Community detection plays a key role in understanding the structure of real-life graphs with impact on recommendation systems, load balancing and routing. Previous community detection methods look for uniform blocks in adjacency matrices. However, after studying 4 real networks with ground-truth communities, we provide empirical evidence that communities are best represented as having an hyperbolic structure. We detail HyCoM – the Hyperbolic Community Model – as a better representation of communities and the relationships between their members, and show improvements in compression compared to standard methods. We also introduce HyCoM-FIT, a fast, parameter free algorithm to detect communities with hyperbolic structure. We show that our method is effective in finding communities with a similar structure to self-declared ones. We report findings in real social networks, including a community in a blogging platform with over 34 million edges in which more than 1000 users established over 300000 relations.

  • Session: 14 | Room: 103-104 | Time: 10:50 – 11:10, Wednesday 17 Sept Discovering dynamic communities in interaction networks (Polina Rozenshtein, Nikolaj Tatti, Aristides Gionis)

    Authors

    Polina Rozenshtein, Aalto University
    Nikolaj Tatti, Aalto University
    Aristides Gionis, Aalto University

    Abstract

    Very often online social networks are defined by aggregating information regarding the interaction between the nodes of the network. For example, a call graph is defined by considering an edge for each pair of individuals who have called each other at least once; or at least k times. Similarly, an implicit social network in a social-media site is defined by considering an edge for each pair of users who have interacted in some way, e.g., have made a conversation, commented to each other’s content, etc. Despite the fact that this type of definitions have been used to obtain a lot of insights regarding the structure of social networks, it is obvious that they suffer from a severe limitation: they neglect the precise time that the interaction between network nodes occurs. In this paper we propose to study interaction networks, where one considers not only the underlying topology of the social network, but also the exact time instances that nodes interact. In an interaction network an edge is associated with a time stamp, and multiple edges may occur for the same pair of nodes. Consequently, interaction networks offer a rich fine-grained representation that can be used to reveal dynamic phenomena in the network. In the context of interaction networks, we study the problem of discovering communities, which are dense, and whose edges occur in short time intervals. Such communities represent groups of individuals who interact with each other in some specific time instances, for example, a group of employees working on the same project and whose interaction intensifies before certain milestones of the project. We prove that the problem we define is NP-hard, and we provide effective algorithms by adapting techniques used to find dense subgraphs. We perform extensive evaluation of the proposed methods on synthetic and real datasets, which demonstrates the validity of our concepts and the good performance of our algorithms.

  • Session: 15 | Room: 102 | Time: 11:40 – 12:00, Wednesday 17 Sept Bayesian Multi-View Tensor Factorization (Suleiman Khan, Samuel Kaski)

    Authors

    Suleiman Khan, Aalto University
    Samuel Kaski, Aalto University

    Abstract

    We introduce a Bayesian extension of the tensor factorization problem to multiple coupled tensors. For a single tensor it reduces to standard PARAFAC-type Bayesian factorization, and for two tensors it is the first Bayesian Tensor Canonical Correlation Analysis method. It can also be seen to solve a tensorial extension of the recent Group Factor Analysis problem. The method decomposes the set of tensors to factors shared by subsets of the tensors, and factors private to individual tensors, and does not assume orthogonality. For a single tensor, the method empirically outperforms existing methods, and we demonstrate its performance on multiple tensor factorization tasks in toxicogenomics and functional neuroimaging.

  • Session: 15 | Room: 102 | Time: 12:40 – 13:00, Wednesday 17 Sept Scalable Nonnegative Matrix Factorization with Block-wise Updates (Jiangtao Yin, Lixin Gao, Zhongfei Zhang)

    Authors

    Jiangtao Yin, UMASS Amherst
    Lixin Gao, university of massachusetts, amherst
    Zhongfei Zhang, Binghamton University, NY, USA

    Abstract

    Nonnegative Matrix Factorization (NMF) has been applied with great success to many applications. As NMF is applied to massive datasets such as web-scale dyadic data, it is desirable to leverage a cluster of machines to speed up the factorization. However, it is challenging to efficiently implement NMF in a distributed environment. In this paper, we show that by leveraging a new form of update functions, we can perform local aggregation and fully explore parallelism. Moreover, under the new form of update functions, we can perform frequent updates, which aim to use the most recently updated data whenever possible. As a result, frequent updates are more efficient than their traditional concurrent counterparts. Through a series of experiments on a local cluster as well as the Amazon EC2 cloud, we demonstrate that our implementation with frequent updates is up to two orders of magnitude faster than the existing implementation with the traditional form of update functions.

  • Session: 16 | Room: 103-104 | Time: 11:40 – 12:00, Wednesday 17 Sept Sub-sampling for multi-armed bandits (Akram Baransi, Odalric-Ambrym Maillard, Shie Mannor)

    Authors

    Akram Baransi, Technion
    Odalric-Ambrym Maillard, Technion
    Shie Mannor, Technion

    Abstract

    The stochastic multi-armed bandit problem is a popular model of the exploration/exploitation trade-off in sequential decision problems. We introduce a novel algorithm that is based on sub-sampling. Despite its simplicity, we show that the algorithm demonstrates excellent empirical performances against state-of-the-art algorithms, including Thompson sampling and KL-UCB. The algorithm is very flexible, it does need to know a set of reward distributions in advance nor the range of the rewards. It is not restricted to Bernoulli distributions and is also invariant under rescaling of the rewards. We provide a detailed experimental study comparing the algorithm to the state of the art, the main intuition that explains the striking results, and conclude with a finite-time regret analysis for this algorithm in the simplified two-arm bandit setting.

  • Session: 16 | Room: 103-104 | Time: 12:00 – 12:20, Wednesday 17 Sept Concurrent bandits and cognitive radio networks (Orly Avner, Shie Mannor)

    Authors

    Orly Avner, Technion
    Shie Mannor, Technion

    Abstract

    We consider the problem of multiple users targeting the arms of a single multi-armed stochastic bandit. The motivation for this problem comes from cognitive radio networks, where selfish users need to coexist without any side communication between them, implicit cooperation or common control. Even the number of users may be unknown and can vary as users join or leave the network. We propose an algorithm that combines an ε-greedy learning rule with a collision avoidance mechanism. We analyze its regret with respect to the system-wide optimum and show that sub-linear regret can be obtained in this setting. Experiments show dramatic improvement comparing to other algorithms for this setting.

  • Session: 16 | Room: 103-104 | Time: 12:20 – 12:40, Wednesday 17 Sept Experimental design in dynamical system identification: a bandit-based active learning approach (Artemis Llamosi, Adel Mezine, Florence D’Alché-Buc, Veronique Letort, Michele Sebag)

    Authors

    Artemis Llamosi, IBISC, University of Evry
    Adel Mezine, IBISC, University of Evry, France
    Florence D’Alché-Buc, University of Evry
    Veronique Letort, MAS, Ecole Centrale Paris, France
    Michele Sebag, CNRS

    Abstract

    This paper is interested in dynamical system identification, with the reverse modeling of a gene regulatory network as motivating application. An active learning approach is used to iteratively select the most informative experiments needed to improve the parameters and hidden variables estimates in a dynamical model given a budget of experiments. The design of experiments under these budgeted resources is formalized in terms of sequential optimization. A local optimization criterion (reward) is designed to assess each experiment in the sequence, and the global optimization of the sequence is tackled in a game-inspired setting, within the Upper Confidence Tree framework combining Monte-Carlo tree-search and multi-armed bandits. The approach, called EDEN for Experimental Design for parameter Estimation in a Network, shows very good performances on several realistic simulated problems of gene regulatory network reverse-modeling, inspired from the international challenge DREAM7.

  • Session: 16 | Room: 103-104 | Time: 12:40 – 13:00, Wednesday 17 Sept Infinitely Many-Armed Bandits with Unknown Value Distribution (Yahel David, Nahum Shimkin)

    Yahel David, Technion
    Nahum Shimkin, Technion

    Abstract

    We consider a version of the classical stochastic Multi-Armed bandit problem in which the number of arms is large compared to the time horizon, with the goal of minimizing the cumulative regret. Here, the mean-reward (or value) of newly chosen arms is assumed to be i.i.d. We further make the simplifying assumption that the value of an arm is revealed once this arm is chosen. We present a general lower bound on the regret, and learning algorithms that achieve this bound up to a logarithmic factor. Contrary to previous work, we do not assume that the functional form of the tail of the value distribution is known. Furthermore, we also consider a variant of our model where sampled arms are non-retainable, namely are lost if not used continuously, with similar near-optimality results.

  • Session: 17 | Room: 105 | Time: 12:40 – 13:00, Wednesday 17 Sept Nowcasting with numerous candidate predictors (Brendan Duncan, Charles Elkan)

    Authors

    Brendan Duncan, UC San Diego
    Charles Elkan, UC San Diego

    Abstract

    The goal of nowcasting, or “predicting the present,” is to estimate up-to-date values for a time series whose actual observations are available only with a delay. Methods for this task leverage observations of correlated time series to estimate values of the target series. This paper introduces a nowcasting technique called FDR (false discovery reduction) that combines tractable variable selection with a time series model trained using a Kalman filter. The FDR method guarantees that all variables selected have statistically significant predictive power. We apply the method to sales figures provided by the United States census bureau, and to a consumer sentiment index. As side data, the experiments use time series from Google Trends of the volumes of search queries. In total, there are 39,059 potential correlated time series. We compare results from the FDR method to those from several baseline methods. The new method outperforms the baselines and achieves comparable performance to a state-of-the-art nowcasting technique on the consumer sentiment time series, while allowing variable selection from over 250 times as many side data series.

  • Session: 18 | Room: 106 | Time: 11:40 – 12:00, Wednesday 17 Sept Joint Prediction of Topics in a URL Hierarchy (Michael Großhans, Christoph Sawade, Tobias Scheffer, Niels Landwehr)

    Authors

    Michael Großhans, University of Potsdam
    Christoph Sawade, SoundCloud Ltd.
    Tobias Scheffer, University of Potsdam
    Niels Landwehr, University of Potsdam

    Abstract

    We study the problem of jointly predicting topics for all web pages within URL hierarchies. We employ a graphical model in which latent variables represent the predominant topic within a subtree of the URL hierarchy. The model is built around a generative process that infers how web site administrators hierarchically structure web site according to topic, and how web page content is generated depending on the page topic. The resulting predictive model is linear in a joint feature map of content, topic labels, and the latent variables. Inference reduces to message passing in a tree-structured graph; parameter estimation is carried out using concave-convex optimization. We present a case study on web page classification for a targeted advertising application.

  • Session: 18 | Room: 106 | Time: 12:00 – 12:20, Wednesday 17 Sept Clustering Image Search Results by Entity Disambiguation (Kaiqi Zhao, Zhiyuan Cai, Qingyu Sui, Enxun Wei, Kenny Zhu)

    Authors

    Kaiqi Zhao, Shanghai Jiao Tong University
    Zhiyuan Cai
    Qingyu Sui
    Enxun Wei
    Kenny Zhu, Shanghai Jiao-Tong University, P.R China

    Abstract

    Existing key-word based image search engines return images whose title or immediate surrounding text contains the search term as a keyword. When the search term is ambiguous and means different things, the results often come in a mixed bag of different entities. This paper proposes a novel framework that understands the context and thus infers the most likely entity in the given image by disambiguating the terms in the context into the corresponding concepts from external knowledge in a process called conceptualization. The images can subsequently be clustered by the most likely associated entities. This approach outperforms the best competing image clustering techniques by 29.2% in NMI score. In addition, the framework automatically annotates each cluster of images by its key entities which allows users to quickly identify the images they want.

  • Session: 18 | Room: 106 | Time: 12:20 – 12:40, Wednesday 17 Sept How Many Topics? Stability Analysis for Topic Models (Derek Greene, Derek O’Callaghan, Pádraig Cunningham)

    Authors

    Derek Greene, University College Dublin
    Derek O’Callaghan, University College Dublin
    Pádraig Cunningham, UCD

    Abstract

    Topic modeling refers to the task of discovering the underlying thematic structure in a text corpus, where the output is commonly presented as a report of the top terms appearing in each topic. Despite the diversity of topic modeling algorithms that have been proposed, a common challenge in successfully applying these techniques is the selection of an appropriate number of topics for a given corpus. Choosing too few topics will produce results that are overly broad, while choosing too many will result in the “over-clustering” of a corpus into many small, highly-similar topics. In this paper, we propose a term-centric stability analysis strategy to address this issue, the idea being that a model with an appropriate number of topics will be more robust to perturbations in the data. Using a topic modeling approach based on matrix factorization, evaluations performed on a range of corpora show that this strategy can successfully guide the model selection process.

  • Session: 18 | Room: 106 | Time: 12:40 – 13:00, Wednesday 17 Sept Open-domain Question Answering with Weakly Supervised Embedding Models (Antoine Bordes, Jason Weston, Nicolas Usunier)

    Authors

    Antoine Bordes, CNRS
    Jason Weston, Google
    Nicolas Usunier, UTC, Compiegne

    Abstract

    Building computers able to answer questions on any subject is a long standing goal of artificial intelligence. Promising progress has recently been achieved by methods that learn to map questions to logical forms or database queries. Such approaches can be effective but at the cost of either large amounts of human-labeled data or by defining lexicons and grammars tailored by practitioners. In this paper, we instead take the radical approach of learning to map questions to vectorial feature representations. By mapping answers into the same space one can query any knowledge base independent of its schema, without requiring any grammar or lexicon. Our method is trained with a new optimization procedure combining stochastic gradient descent followed by a fine-tuning step using the weak supervision provided by blending automatically and collaboratively generated resources. We empirically demonstrate that our model can capture meaningful signals from its noisy supervision leading to major improvements over PARALEX, the only existing method able to be trained on similar weakly labeled data.

  • Session: 19 | Room: 105-106 | Time: 16:40 – 17:00, Wednesday 17 Sept On the Equivalence Between Deep NADE and Generative Stochastic Networks (Li Yao, Sherjil Ozair, Kyunghyun Cho, Yoshua Bengio)

    Authors

    Li Yao
    Sherjil Ozair
    Kyunghyun Cho, University of Montreal
    Yoshua Bengio

    Abstract

    Neural Autoregressive Distribution Estimators (NADEs) have recently been shown as successful alternatives for modeling high dimen- sional multimodal distributions. One issue associated with NADEs is that they rely on a particular order of factorization for P(x). This issue has been recently addressed by a variant of NADE called Orderless NADEs and its deeper version, Deep Orderless NADE. Orderless NADEs are trained based on a criterion that stochastically maximizes P (x) with all possible orders of factorizations. Unfortunately, ancestral sampling from deep NADE is very expensive, corresponding to running through a neural net separately predicting each of the visible variables given some others. This work makes a connection between this criterion and the training criterion for Generative Stochastic Networks (GSNs). It shows that training NADEs in this way also trains a GSN, which defines a Markov chain associated with the NADE model. Based on this connection, we show an alternative way to sample from a trained Orderless NADE that allows to trade-off computing time and quality of the samples: a 3 to 10-fold speedup (taking into account the waste due to correla- tions between consecutive samples of the chain) can be obtained without noticeably reducing the quality of the samples. This is achieved using a novel sampling procedure for GSNs called annealed GSN sampling, sim- ilar to tempering methods that combines fast mixing (obtained thanks to steps at high noise levels) with accurate samples (obtained thanks to steps at low noise levels).

  • Session: 19 | Room: 105-106 | Time: 17:00 – 17:20, Wednesday 17 Sept Knowledge-Powered Deep Learning for Word Embedding (Jiang Bian, Bin Gao, Tie-Yan Liu)

    Authors

    Jiang Bian, Microsoft Research
    Bin Gao, Microsoft Research
    Tie-Yan Liu, Microsoft Research

    Abstract

    Recent years have witnessed the increasing efforts that apply deep learning techniques to solve text mining and natural language processing tasks. The basis of these tasks is to obtain high-quality distributed representations of words, i.e., word embeddings, from large amounts of text data. However, text itself usually contains limited information, which makes necessity to leverage extra knowledge to understand it. Fortunately, since text is generated by human, it already contains well-defined morphological and syntactic knowledge; moreover, the large amount of human-generated texts on the Web enable the extraction of plenty of semantic knowledge. Thus, novel deep learning algorithms and systems are needed in order to leverage the above knowledge to compute more effective word embedding. In this paper, we conduct an empirical study on the capacity of leveraging morphologic, syntactic, and semantic knowledge to achieve high-quality word embeddings. Our study explores these types of knowledge to define new basis for word representation, provide additional input information, and serve as auxiliary supervision in deep learning, respectively. Experiments on a popular analogical reasoning task, a word similarity task, and a word completion task have all demonstrated that knowledge-powered deep learning can enhance the effectiveness of word embedding.

  • Session: 19 | Room: 105-106 | Time: 17:20 – 17:40, Wednesday 17 Sept Learned-Norm Pooling for Deep Feedforward and Recurrent Neural Networks (Caglar Gulcehre, Kyunghyun Cho, Razvan Pascanu, Yoshua Bengio)

    Authors

    Caglar Gulcehre, University of Montreal
    Kyunghyun Cho, University of Montreal
    Razvan Pascanu
    Yoshua Bengio

    Abstract

    In this paper we propose and investigate a novel nonlinear unit, called Lp unit, for deep neural networks. The proposed Lp unit receives signals from several projections of a subset of units in the layer below and computes a normalized Lp norm. We notice two interesting interpretations of the Lp unit. First, the proposed unit can be understood as a generalization of a number of conventional pooling operators such as average, root-mean-square and max pooling widely used in, for instance, convolutional neural networks (CNN), HMAX models and neocognitrons. Furthermore, the Lp unit is, to a certain degree, similar to the recently proposed maxout unit which achieved the state-of-the-art object recognition results on a number of benchmark datasets. Secondly, we provide a geometrical interpretation of the activation function based on which we argue that the Lp unit is more efficient at representing complex, nonlinear separating boundaries. Each Lp unit defines a superelliptic boundary, with its exact shape defined by the order p. We claim that this makes it possible to model arbitrarily shaped, curved boundaries more efficiently by combining a few Lp units of different orders. This insight justifies the need for learning different orders for each unit in the model. We empirically evaluate the proposed Lp units on a number of datasets and show that multilayer perceptrons (MLP) consisting of the Lp units achieve the state-of-the-art results on a number of benchmark datasets. Furthermore, we evaluate the proposed Lp unit on the recently proposed deep recurrent neural networks (RNN).

  • Session: 20 | Room: 102 | Time: 16:20 – 16:40, Wednesday 17 Sept Policy Search for Path Integral Control (Vicenç Gomez, Jan Peters, Hilbert Kappen, Gerhard Neumann)

    Authors

    Vicenç Gomez, Universitat Pompeu Fabra
    Jan Peters, Technische Universitaet Darmstadt
    Hilbert Kappen, Radboud University Nijmegen
    Gerhard Neumann, TU Darmstadt

    Abstract

    Path integral (PI) control defines a general class of control problems for which the optimal control computation is equivalent to an inference problem that can be solved by evaluation of a path integral over state trajectories. However, this potential is mostly unused in real-world problems because of two main limitations: first, current approaches can typically only be applied to learn open-loop controllers and second, current sampling procedures are inefficient and not scalable to high dimensional systems. We introduce the efficient Path Integral Relative-Entropy Policy Search (PI-REPS) algorithm for learning feedback policies with PI control. Our algorithm is inspired by information theoretic policy updates that are often used in policy search. We use these updates to approximate the state trajectory distribution that is known to be optimal from the PI control theory. Our approach allows for a principled treatment of different sampling distributions and can be used to estimate many types of parametric or non-parametric feedback controllers. We show that PI-REPS significantly outperforms current methods and is able to solve tasks that are out of reach for current methods.

  • Session: 20 | Room: 102 | Time: 16:40 – 17:00, Wednesday 17 Sept An Online Policy Gradient Algorithm for Markov Decision Processes with Continuous States and Actions (Yao Ma, Tingting Zhao, Kohei Hatano, Masashi Sugiyama)

    Authors

    Yao Ma, Tokyo Institute of Technology
    Tingting Zhao
    Kohei Hatano
    Masashi Sugiyama

    Abstract

    We consider the learning problem under an online Markov decision process (MDP), which is aimed at learning the time-dependent decision-making policy of an agent that minimizes the regret — the difference from the best fixed policy. The difficulty of online MDP learning is that the reward function changes over time. In this paper, we show that a simple online policy gradient algorithm could achieves regret bound in order of squre root T for T steps with concavity assumption. To the best of our knowledge, this is the first work to give an online MDP algorithm that can handle continuous state ,action and parameter spaces. We demonstrate the performance of the online policy gradient method through experiments.

  • Session: 20 | Room: 102 | Time: 17:00 – 17:20, Wednesday 17 Sept Boosted Bellman Residual Minimization Handling Expert Demonstrations (Bilal Piot, Matthieu Geist, Olivier Pietquin)

    Authors

    Bilal Piot, Supelec
    Matthieu Geist
    Olivier Pietquin

    Abstract

    This paper addresses the problem of batch Reinforcement Learning with Expert Demonstrations (RLED). In RLED, the goal is to find an optimal policy of a Markov Decision Process (MDP), using a data set of fixed sampled transitions of the MDP as well as a data set of fixed expert demonstrations. This is slightly different from the batch Reinforcement Learning (RL) framework where only fixed sampled transitions of the MDP are available. Thus, the aim of this article is to propose algorithms that leverage those expert data. The idea proposed here differs from the Approximate Dynamic Programming methods in the sense that we minimize the Optimal Bellman Residual (OBR), where the minimization is guided by constraints defined by the expert demonstrations. This choice is motivated by the the fact that controlling the OBR implies controlling the distance between the estimated and optimal quality functions. However, this method presents some difficulties as the criterion to minimize is non-convex, non-differentiable and biased. Those difficulties are overcome via the embedding of distributions in a Reproducing Kernel Hilbert Space (RKHS) and a boosting technique which allows obtaining non-parametric algorithms. Finally, our algorithms are compared to the only state of the art algorithm, Approximate Policy Iteration with Demonstrations (APID) algorithm, in different experimental settings.

  • Session: 20 | Room: 102 | Time: 17:20 – 17:40, Wednesday 17 Sept Local Policy Search in a Convex Space and Conservative Policy Iteration as Boosted Policy Search (Bruno Scherrer, Matthieu Geist)

    Authors

    Bruno Scherrer, INRIA
    Matthieu Geist

    Abstract

    Local Policy Search is a popular reinforcement learning approach for handling large state spaces. Formally, it searches locally in a parameterized policy space in order to maximize the associated value function averaged over some predefined distribution. The best one can hope in general from such an approach is to get a local optimum of this criterion. The first contribution of this article is the following surprising result: if the policy space is convex, any (approximate) local optimum enjoys a global performance guarantee. Unfortunately, the convexity assumption is strong: it is not satisfied by commonly used parameterizations and designing a parameterization that induces this property seems hard. A natural solution to alleviate this issue consists in deriving an algorithm that solves the local policy search problem using a boosting approach (constrained to the convex hull of the policy space). The resulting algorithm turns out to be a slight generalization of conservative policy iteration; thus, our second contribution is to highlight an original connection between local policy search and approximate dynamic programming.

  • Session: 21 | Room: 103-104 | Time: 16:20 – 16:40, Wednesday 17 Sept A Bayesian Generative Model for Item and User Recommendation in Social Rating Networks with Trust Relationships (Gianni Costa, Giuseppe Manco, Riccardo Ortale)

    Authors

    Gianni Costa, ICAR – CNR
    Giuseppe Manco, ICAR, National Research Council, Italy
    Riccardo Ortale, ICAR – CNR

    Abstract

    A Bayesian generative model is presented for recommending interesting items and trustworthy users to the targeted users in social rating networks with asymmetric and directed trust relationships. The proposed model is the first unified approach to the combination of the two recommendation tasks. Within the devised model, each user is associated with two latent-factor vectors, i.e., her susceptibility and expertise. Items are also associated with corresponding latent-factor vector representations. The probabilistic factorization of the rating data and trust relationships is exploited to infer user susceptibility and expertise. Statistical social-network modeling is instead used to constrain the trust relationships from a user to another to be governed by their respective susceptibility and expertise. The inherently ambiguous meaning of unobserved trust relationships between users is suitably disambiguated. An intensive comparative experimentation on real-world social rating networks with trust relationships demonstrates the superior predictive performance of the presented model in terms of RMSE and AUC.

  • Session: 21 | Room: 103-104 | Time: 17:20 – 17:40, Wednesday 17 Sept A two-step learning approach for solving full and almost full cold start problems in dyadic prediction (Tapio Pahikkala, Michiel Stock, Antti Airola, Tero Aittokallio, Bernard De Baets, Willem Waegeman)

    Authors

    Tapio Pahikkala, University of Turku
    Michiel Stock
    Antti Airola
    Tero Aittokallio
    Bernard De Baets
    Willem Waegeman, Universiteit Gent

    Abstract

    Dyadic prediction methods operate on pairs of objects (dyads), aiming to infer labels for out-of-sample dyads. We consider the full and almost full cold start problem in dyadic prediction, a setting that occurs when both objects in an out-of-sample dyad have not been observed during training, or if one of them has been observed, but very few times. A popular approach for addressing this problem is to train a model that makes predictions based on a pairwise feature representation of the dyads, or, in case of kernel methods, based on a tensor product pairwise kernel. As an alternative to such a kernel approach, we introduce a novel two-step learning algorithm that borrows ideas from the fields of pairwise learning and spectral filtering. We show theoretically that the two-step method is very closely related to the tensor product kernel approach, and experimentally that it yields a slightly better predictive performance. Moreover, unlike existing tensor product kernel methods, the two-step method allows closed-form solutions for training and parameter selection via cross-validation estimates both in the full and almost full cold start settings, making the approach much more efficient and straightforward to implement.

  • Session: 22 | Room: 101 | Time: 16:40 – 17:00, Wednesday 17 Sept Classifying A Stream of Infinite Concepts: A Bayesian Non-Parametric Approach (Abbas Hosseini, Hamid R. Rabiee, Hassan Hafez, Ali Soltani-Farani)

    Authors

    Abbas Hosseini, Sharif University of Tech.
    Hamid R. Rabiee, Sharif University of Tech
    Hassan Hafez, Sharif University of Technology
    Ali Soltani-Farani, Sharif University of Tech

    Abstract

    Classifying streams of data, for instance financial transactions or emails, is an essential element in applications such as online advertising and spam or fraud detection. The data stream is often large or even unbounded, and in many instances non-stationary. Therefore, an adaptive approach that can manage concept drift in an online fashion, is often required. This paper presents a probabilistic, non-parametric, and generative model for stream classification that can handle concept drift efficiently, and adjust its complexity over time. Unlike recent methods, the proposed model handles concept drift by adapting data-concept association without the unnecessary i.i.d. assumption among the data, in a batch. This allows the model to efficiently classify data by using fewer and simpler base classifiers. Moreover, an online algorithm for making inference on the proposed non-conjugate, time-dependent, and non-parametric model is proposed. Extensive experimental results on several stream datasets demonstrate the effectiveness of the proposed model.

  • Session: 22 | Room: 101 | Time: 17:00 – 17:20, Wednesday 17 Sept Speeding Up Recovery From Concept Drifts (Silas Santos, Paulo Gonçalves, Geyson Silva, Roberto Barros)

    Authors

    Silas Santos, UFPE
    Paulo Gonçalves
    Geyson Silva
    Roberto Barros

    Abstract

    The extraction of knowledge from data streams is an activity that has progressively been receiving an increased demand. However, in this type of environment, changes in data distribution, or concept drift, can occur constantly and is a challenge. This paper proposes the Adaptable Diversity-based Online Boosting (ADOB), a modified version of the online boosting, as proposed by Oza and Russell, which is aimed at speeding up the experts recovery after concept drifts. We performed experiments to compare the accuracy as well as the execution time and memory use of ADOB against a number of other methods using several artificial and real world datasets, chosen from the most used ones in the area. Results suggest that, in many different situations, the proposed approach maintains a high accuracy, outperforming the other tested methods in regularity, with no significant change in the execution time and memory use. In particular, ADOB was specially efficient in situations where frequent and abrupt concept drifts occur.

  • Session: 22 | Room: 101 | Time: 17:20 – 17:40, Wednesday 17 Sept Mining Top-K Largest Tiles in a Data Stream (Hoang Thanh Lam, Wenjie Pei, Adriana Prado, Baptiste Jeudy, Elisa Fromont)

    Authors

    Hoang Thanh Lam, IBM Research Dublin
    Wenjie Pei, TU Delft, the Netherlands
    Adriana Prado, Laboratoire Hubert Curien, UMR CNRS 5516, Université de St-Etienne
    Baptiste Jeudy
    Elisa Fromont, Universite Saint-Etienne

    Abstract

    Large tiles in a database are itemsets with the largest area which is defined as the itemset frequency in the database multiplied by its size. Mining these large tiles is an important pattern mining problem since tiles with a large area describe a large part of the database. In this paper, we introduce the problem of mining top-k largest tiles in a data stream under the sliding window model. We propose a candidate-based approach which summarizes the data stream and produces the top-k largest tiles efficiently for moderate window size. We also propose an approximation algorithm with theoretical bounds on the error rate to cope with large size windows. In the experiments with two real-life datasets, the approximation algorithm is up to hundred times faster than the candidate-based solution and the baseline algorithms based on the state-of-the-art solutions. We also investigate an application of large tile mining in computer vision and in emerging search topics monitoring.

  • Session: 23 | Room: 102 | Time: 10:30 – 10:50, Thursday 18 Sept Reliability maps: A tool to enhance probability estimates and improve classification accuracy (Meelis Kull, Peter Flach)

    Authors

    Meelis Kull, University of Bristol
    Peter Flach, University of Bristol

    Abstract

    We propose a general method to assess the reliability of two-class probabilities in an instance-wise manner. This is relevant, for instance, for obtaining calibrated multi-class probabilities from two-class probability scores. The LS-ECOC method approaches this by performing least-squares fitting over a suitable error-correcting output code matrix, where the optimisation resolves potential conflicts in the input probabilities. While this gives all input probabilities equal weight, we would like to spend less effort fitting unreliable probability estimates. We introduce the concept of a reliability map to accompany the more conventional notion of calibration map; and LS-ECOC-R which modifies LS-ECOC to take reliability into account. We demonstrate on synthetic data that this gets us closer to the Bayes-optimal classifier, even if the base classifiers are linear and hence have high bias. Results on UCI data sets demonstrate that multi-class accuracy also improves.

  • Session: 24 | Room: 105 | Time: 10:30 – 10:50, Thursday 18 Sept Code you are Happy to Paste: an Algorithmic Dictionary of Exponential Families (Olivier Schwander)

    Author

    Olivier Schwander, Supélec

    Abstract

    We describe a library and a companion website designed to ease the usage of exponential families in various programming languages. Implementation of mathematical formulas in computer programs is often error-prone, difficult to debug and difficult to read afterwards. Moreover, this implementation is heavily dependent of the programming language used and often needs an important knowledge of the idioms of the language. In our system, formulas are described in a high-level language and mechanically exported to the chosen target language and a LaTeX export allows to quickly review correctness of formulas. Although our system is not limited by design to exponential families, we focus on this kind of formulas since they are of great interest for machine learning and statistical modeling applications. Besides, exponential families are a good usecase of our dictionary: among other usages, they may be used with generic algorithms for mixture models such as Bregman Soft Clustering, in which case lots of formulas from the canonical decomposition of the family need to be implemented. We thus illustrate our library by generating code which can be plugged into generic Expectation-Maximization schemes written in multiple languages.

  • Session: 25 | Room: 106 | Time: 10:10 – 10:30, Thursday 18 Sept GMRF Estimation under Topological and Spectral constraints (Victorin Martin, Cyril Furtlehner, Yufei Han, Jean-Marc Lasgouttes)

    Authors

    Victorin MARTIN, Mines ParisTech
    Cyril Furtlehner, INRIA
    Yufei Han
    Jean-Marc Lasgouttes, INRIA

    Abstract

    We investigate the problem of Gaussian Markov random field selection under a non-analytic constraint: the estimated models must be compatible with a fast inference algorithm, namely the Gaussian belief propagation algorithm. To address this question, we introduce the *-IPS framework, based on iterative proportional scaling, which incrementally selects candidate links in a greedy manner. Besides its intrinsic sparsity-inducing ability, this algorithm is flexible enough to incorporate various spectral constraints, like e.g. walk summability, and topological constraints, like short loops avoidance. Experimental tests on various datasets, including traffic data from San Francisco Bay Area, indicate that this approach can deliver, with reasonable computational cost, a broad range of efficient inference models, which are not accessible through penalization with traditional sparsity-inducing norms.

  • Session: 25 | Room: 106 | Time: 10:30 – 10:50, Thursday 18 Sept Discriminative Subnetworks with Regularized Spectral Learning for Global-state Network Data (Xuan-Hong Dang, Ambuj K. Singh, Petko Bogdanov, Hongyuan You, Bayyuan Hsu)

    Authors

    Xuan-Hong Dang, UCSB
    Ambuj K. Singh, UCSB
    Petko Bogdanov, UCSB
    Hongyuan You, UCSB
    Bayyuan Hsu, UCSB

    Abstract

    Data mining practitioners are facing challenges from data with network structure. In this paper, we address a specific class of global-state networks which comprises of a set of network instances sharing a similar structure yet having different values at local nodes. Each instance is associated with a global state which indicates the occurrence of an event. The objective is to uncover a small set of discriminative subnetworks that can optimally classify global network values. Unlike most existing studies which explore an exponential subnetwork space, we address this difficult problem by adopting a space transformation approach. Specifically, we present an algorithm that optimizes a constrained dual-objective function to learn a low-dimensional subspace that is capable of discriminating networks labelled by different global states, while reconciling with common network topology sharing across instances. Our algorithm takes an appealing approach from spectral graph learning and we show that the globally optimum solution can be achieved via matrix eigen-decomposition.

  • Session: 25 | Room: 106 | Time: 10:50 – 11:10, Thursday 18 Sept Hypernode Graphs for Spectral Learning on Binary Relations over Sets (Thomas Ricatte, Rémi Gilleron, Marc Tommasi)

    Authors

    Thomas Ricatte, INRIA
    Rémi Gilleron
    Marc Tommasi, Université Lille 3, Inria

    Abstract

    We introduce hypernode graphs as weighted binary relations between sets of nodes: a hypernode is a set of nodes, a hyperedge is a pair of hypernodes, and each node in a hypernode of a hyperedge is given a non negative weight that represents the node contribution to the relation. Hypernode graphs model binary relations between sets of individuals while allowing to reason at the level of individuals. We present a spectral theory for hypernode graphs that allows us to introduce an unnormalized Laplacian and a smoothness semi-norm. In this framework, we are able to extend spectral graph learning algorithms to the case of hypernode graphs. We show that hypernode graphs are a proper extension of graphs from the expressive power point of view and from the spectral analysis point of view. Therefore hypernode graphs allow to model higher order relations whereas it is not true for hypergraphs as shown in Higher Order Learning with Graphs. In order to prove the potential of the model, we represent multiple players games with hypernode graphs and introduce a novel method to infer skill ratings from game outcomes. We show that spectral learning algorithms over hypernode graphs obtain competitive results with skill ratings specialized algorithms such as Elo duelling and TrueSkill.

  • Session: 26 | Room: 103-104 | Time: 11:40 – 12:00, Thursday 18 Sept Restricted Boltzmann Machines with Overlapping Partitions (Hasari Tosun, John Sheppard)

    Authors

    Hasari Tosun, Montana State University
    John Sheppard, Montana State University

    Abstract

    Restricted Boltzmann Machines (RBM) are energy-based models that are successfully used as generative learning models as well as crucial components of Deep Belief Networks (DBN). The most successful training method to date for RBMs is the Contrastive Divergence method. However, Contrastive Divergence is inefficient when the number of features is very high and the mixing rate of the Gibbs chain is slow. We propose a new training method that partitions a single RBM into multiple overlapping small RBMs. The final RBM is learned by layers of partitions. We show that this method is not only fast, it is also more accurate in terms of its generative power.

  • Session: 26 | Room: 103-104 | Time: 12:00 – 12:20, Thursday 18 Sept Recurrent Greedy Parsing with Neural Networks (Joël Legrand, Ronan Collobert)

    Authors

    Joël Legrand, Idiap Research Institute
    Ronan Collobert, Idiap Research Institute

    Abstract

    In this paper, we propose a bottom-up greedy and purely discriminative syntactic parsing approach that relies only on a few simple features. The core of the architecture is a simple neural network architecture, trained with an objective function similar to a Conditional Random Field. This parser leverages continuous word vector representations to model the conditional distributions of context-aware syntactic rules. The learned distribution rules are naturally smoothed, thanks to the continuous nature of the input features and the model. Generalization accuracy compares very well with the existing generative or discriminative (non-reranking) parsers (despite the greedy nature of our approach), and prediction speed is very fast.

  • Session: 26 | Room: 103-104 | Time: 12:20 – 12:40, Thursday 18 Sept Large-scale Multi-label Text Classification — Revisiting Neural Networks (Jinseok Nam, Jungi Kim, Eneldo Loza Mencia, Iryna Gurevych, Johannes Fuernkranz)

    Authors

    Jinseok Nam, TU Darmstadt
    Jungi Kim
    Eneldo Loza Mencia, TU Darmstadt
    Iryna Gurevych
    Johannes Fuernkranz, TU Darmstadt

    Abstract

    Recent works have proposed the use of neural networks for multi-label classification because they are able to capture and model label dependencies in the output layer. In this work, we investigate limitations of BP-MLL, a neural network (NN) architecture that aims at minimizing pairwise ranking error. Instead, we propose to use a comparably simple NN approach with recently proposed learning techniques for large-scale multi-label text classification tasks. In particular, we show that BP-MLL’s ranking loss minimization can be efficiently and effectively replaced with the commonly used cross entropy error function, and demonstrate that several advances in neural network training that have been recently developed in the realm of deep learning can be effectively employed in this setting. Our experimental results show that simple NN models equipped with recent advanced techniques such as rectified linear units, dropout, and adagrad perform as well as or even outperform state-of-the-art approaches on six large-scale textual datasets with diverse characteristics.

  • Session: 26 | Room: 103-104 | Time: 12:40 – 13:00, Thursday 18 Sept Neural Gaussian Conditional Random Fields (Vladan Radosavljevic, Slobodan Vucetic, Zoran Obradovic)

    Authors

    Vladan Radosavljevic, Temple University
    Slobodan Vucetic, Temple University
    Zoran Obradovic, Temple University

    Abstract

    We propose a Conditional Random Field (CRF) model for structured regression. By constraining the feature functions as quadratic functions of outputs, the model can be conveniently represented in a Gaussian canonical form. We improved the representational power of the resulting Gaussian CRF (GCRF) model by (1) introducing an adaptive feature function that can learn nonlinear relationships between inputs and outputs and (2) allowing the weights of feature functions to be dependent on inputs. Since both the adaptive feature functions and weights can be constructed using feedforward neural networks, we call the resulting model Neural GCRF. The appeal of Neural GCRF is in conceptual simplicity and computational efficiency of learning and inference through use of sparse matrix computations. Experimental evaluation on the remote sensing problem of aerosol estimation from satellite measurements and on the problem of document retrieval showed that Neural GCRF is more accurate than the benchmark predictors.

  • Session: 27 | Room: 102 | Time: 11:40 – 12:00, Thursday 18 Sept Statistical Hypothesis Testing in Positive Unlabelled Data (Konstantinos Sechidis, Borja Calvo, Gavin Brown)

    Authors

    Konstantinos Sechidis, University of Manchester
    Borja Calvo, University of the Basque Country
    Gavin Brown, University Of Manchester

    Abstract

    We propose a set of novel methodologies which enable valid statistical hypothesis testing when we have only positive and unlabelled (PU) examples. This type of problem, a special case of semi-supervised data, is common in text mining, bioinformatics, and computer vision. Focusing on a generalised likelihood ratio test, we have 3 key contributions: (1) a proof that assuming all unlabelled examples are negative cases is sufficient for independence testing, but not for power analysis activities; (2) a new methodology that compensates this and enables power analysis, allowing sample size determination for observing an effect with a desired power; and finally, (3) a new capability, supervision determination, which can determine a-priori the number of labelled examples the user must collect before being able to observe a desired statistical effect. Beyond general hypothesis testing, we suggest the tools will additionally be useful for information theoretic feature selection, and Bayesian Network structure learning.

  • Session: 27 | Room: 102 | Time: 12:00 – 12:20, Thursday 18 Sept Hetero-Labeled LDA: A partially supervised topic model with heterogeneous labels (Dongyeop Kang, Youngja Park, Suresh Chari)

    Authors

    Dongyeop Kang, KAIST
    Youngja Park, IBM T.J. Watson Research Center
    Suresh Chari, IBM T.J. Watson Research Center

    Abstract

    We propose, Hetero-Labeled LDA (hLLDA), a novel semi-supervised topic model, which can learn from multiple types of labels such as document labels and feature labels, and also accommodate labels for only a subset of classes (i.e., partial labels). This addresses two major limitations in existing semi-supervised learning methods: they can incorporate only one type of domain knowledge (e.g. document labels or feature labels), and they assume that provided labels cover all the classes in the problem space. This limits their applicability in real-life situations where domain knowledge for labeling comes in different forms from different groups of domain experts and some classes may not have labels. hLLDA resolves both the label heterogeneity and label partialness problems in a unified generative process. hLLDA can leverage different forms of supervision and discover semantically coherent topics by exploiting domain knowledge mutually reinforced by different types of labels. Experiments with three document collections–Reuters, 20Newsgroup and Delicious– validate that our model generates a better set of topics and efficiently discover additional latent topics not covered by the labels resulting in better classification and clustering accuracy than existing supervised or semi-supervised topic models. The empirical results demonstrate that learning from multiple forms of domain knowledge in a unified process creates an enhanced combined effect that is greater than a sum of multiple models learned separately with one type of supervision.

  • Session: 27 | Room: 102 | Time: 12:20 – 12:40, Thursday 18 Sept Semi-Supervised Learning Using an Unsupervised Atlas (Chris Russell, Lourdes Agapito , Nikos Pitelis)

    Authors

    Chris Russell, University College London
    Lourdes Agapito , UCL
    Nikos Pitelis, UCL

    Abstract

    In many machine learning problems, high-dimensional datasets often lie on or near manifolds of locally low-rank. This knowledge can be exploited to avoid the “”curse of dimensionality”” when learning a classifier. Explicit manifold learning formulations such as LLE are rarely used for this purpose, and instead classifiers may make use of methods such as local co-ordinate coding or auto-encoders to implicitly characterise the manifold. We propose novel manifold-based kernels for semi-supervised and supervised learning. We show how smooth classifiers can be learnt from existing descriptions of manifolds that characterise the manifold as a set of piecewise affine charts, or an atlas. We experimentally validate the importance of this smoothness vs. the more natural piecewise smooth classifiers, and we show a significant improvement over competing methods on standard datasets. In the semi-supervised learning setting our experiments show how using unlabelled data to learn the detailed shape of the underlying manifold substantially improves the accuracy of a classifier trained on limited labelled data.

  • Session: 27 | Room: 102 | Time: 12:40 – 13:00, Thursday 18 Sept Consistency of losses for learning from weak labels (Jesus Cid Sueiro, Raul Santos-Rodriguez, Dario Garcia-Garcia)

    Authors

    Jesus Cid Sueiro, Universidad Carlos III de Madr
    Raul Santos-Rodriguez, Universitat de València
    Dario Garcia-Garcia

    Abstract

    In this paper we analyze the consistency of loss functions for learning from weakly labelled data, and its relation to properness. We show that the consistency of a given loss depends on the mixing matrix, which is the transition matrix relating the weak labels and the true class. A linear transformation can be used to convert a conventional classification-calibrated (CC) loss into a weak CC loss. By comparing the maximal dimension of the set of mixing matrices that are admissible for a given CC loss with that for proper losses, we show that classification calibration is a much less restrictive condition than properness. Moreover, we show that while the transformation of conventional proper losses into a weak proper losses does not preserve convexity in general, conventional convex CC losses can be easily transformed into weak and convex CC losses. Our analysis provides a general procedure to construct convex CC losses, and to identify the set of mixing matrices admissible for a given transformation. Several examples are provided to illustrate our approach.

  • Session: 28 | Room: 105 | Time: 11:40 – 12:00, Thursday 18 Sept Transductive Minimax Probability Machine (Gao Huang, Shiji Song, Zhixiang Xu, Kilian Weinberger)

    Authors

    Gao Huang, Tsinghua University
    Shiji Song
    Zhixiang Xu
    Kilian Weinberger

    Abstract

    The Minimax Probability Machine (MPM) is an elegant machine learning algorithm for inductive learning. It learns a classifier that minimizes an upper bound on its own generalization error. In this paper, we extend its celebrated inductive formulation to an equally elegant transductive learning algorithm. In the transductive setting, the label assignment of a test set is already optimized during training. This optimization problem is an intractable mixed-integer programming. Thus, we provide an efficient label-switching approach to solve it approximately. The resulting method scales naturally to large data sets and is very efficient to run. In comparison with nine competitive algorithms on eleven data sets, we show that the proposed Transductive MPM (TMPM) almost outperforms all the other algorithms in both accuracy and speed.

  • Session: 28 | Room: 105 | Time: 12:20 – 12:40, Thursday 18 Sept Combination of one-class support vector machines for classification with reject option (Blaise Hanczar, Michele Sebag)

    Authors

    Blaise Hanczar, University Paris Descartes
    Michele Sebag, CNRS

    Abstract

    This paper focuses on binary classification with reject option, enabling the classifier to detect and abstain hazardous decisions. While reject classification produces in more reliable decisions, there is a tradeoff between accuracy and rejection rate. Two type of rejection are considered: ambiguity and outlier rejection. The state of the art mostly handles ambiguity rejection and ignored outlier rejection. The proposed approach, referred as CONSUM, handles both ambiguity and outliers detection. Our method is based on a quadratic constrained optimization formulation, combining one-class support vector machines. An adaptation of the sequential minimal optimization algorithm is proposed to solve the minimization problem. The experimental study on both artificial and real world datasets exams the sensitivity of the CONSUM with respect to the hyper-parameters and demonstrates the superiority of our approach.

  • Session: 28 | Room: 105 | Time: 12:40 – 13:00, Thursday 18 Sept Cautious Ordinal Classification by Binary Decomposition (Sebastien Destercke, Gen Yang)

    Authors

    Sebastien Destercke, CNRS
    Gen Yang, UTC

    Abstract

    We study the problem of performing cautious inferences for an ordinal classification (a.k.a. ordinal regression) task, that is when the possible classes are totally ordered. By cautious inference, we mean that we may produce partial predictions when available information is insufficient to provide reliable precise ones. We do so by estimating probabilistic bounds instead of precise ones. These bounds induce a (convex) set of possible probabilistic models, from which we perform inferences. As the estimates or predictions for such models are usually computationally harder to obtain than for precise ones, we study the extension of two binary decomposition strategies that remain easy to obtain and computationally efficient to manipulate when shifting from precise to bounded estimates. We demonstrate the possible usefulness on such a cautious attitude on tests performed on benchmark data sets.

  • Session: 29 | Room: 106 | Time: 11:40 – 12:00, Thursday 18 Sept Multi-Target Regression via Random Linear Target Combinations (Grigorios Tsoumakas, Eleftherios Spyromitros-Xioufis, Aikaterini Vrekou, Ioannis Vlahavas)

    Authors

    Grigorios Tsoumakas, Aristotle University of Thessaloniki, Greece
    Eleftherios Spyromitros-Xioufis, Aristotle University of Thessaloniki
    Aikaterini Vrekou, Aristotle University of Thessaloniki
    Ioannis Vlahavas, Aristotle University of Thessaloniki

    Abstract

    Multi-target regression is concerned with the simultaneous prediction of multiple continuous target variables based on the same set of input variables. It arises in several interesting industrial and environmental application domains, such as ecological modelling and energy forecasting. This paper presents an ensemble method for multi-target regression that constructs new target variables via random linear combinations of existing targets. We discuss the connection of our approach with multi-label classification algorithms, in particular RAkEL, which originally inspired this work, and a family of recent multi-label classification algorithms that involve output coding. Experimental results on 12 multi-target datasets show that it performs significantly better than a strong baseline that learns a single model for each target using gradient boosting and compares favourably to the state-of-the-art multiobjective random forest approach. The experiments further show that our approach improves more when stronger unconditional dependencies exist among the targets.

  • Session: 29 | Room: 106 | Time: 12:00 – 12:20, Thursday 18 Sept Transfer Learning with Multiple Sources via Consensus Regularized Autoencoders (Fuzhen Zhuang, Xiaohu Cheng, Sinno Jialin Pan, Qing He, zhongzhi Shi)

    Authors

    Fuzhen Zhuang, Chinese Academy of Sciences
    Xiaohu Cheng, ICT, CAS
    Sinno Jialin Pan, Institute for Infocomm Research, Singapore
    Qing He
    zhongzhi Shi, ICT, CAS

    Abstract

    Knowledge transfer from multiple source domains to a target domain is crucial in transfer learning. Most existing methods are focused on learning weights for different domains based on the similarities between each source domain and the target domain or learning more precise classifiers from the source domain data jointly by maximizing their consensus of predictions on the target domain data. However, these methods only consider measuring similarities or building classifiers on the original data space, and fail to discover a more powerful feature representation of the data when transferring knowledge from multiple source domains to the target domain. In this paper, we propose a new framework for transfer learning with multiple source domains. Specifically, in the proposed framework, we adopt autoencoders to construct a feature mapping from an original instance to a hidden representation, and train multiple classifiers from the source domain data jointly by performing an entropy-based consensus regularizer on the predictions on the target domain. Based on the framework, a particular solution is proposed to learn the hidden representation and classifiers simultaneously. Experimental results on image and text real-world datasets demonstrate the effectiveness of our proposed method compared with state-of-the-art methods.

  • Session: 29 | Room: 106 | Time: 12:20 – 12:40, Thursday 18 Sept Importance Weighted Inductive Transfer Learning for Regression (Thomas Vanck, Jochen Garcke)

    Authors

    Thomas Vanck, TU Berlin
    Jochen Garcke, Universität Bonn

    Abstract

    We consider inductive transfer learning for dataset shift, a situation in which the distributions of two sampled, but closely related, datasets differ. When the target data to be predicted is scarce, one would like to improve its prediction by employing data from the other, secondary, dataset. Transfer learning tries to address this task by suitably compensating such a dataset shift. In this work we assume that the distributions of the covariates and the dependent variables can differ arbitrarily between the datasets. We propose two methods for regression based on importance weighting. Here to each instance of the secondary data a weight is assigned such that the data contributes positively to the prediction of the target data. Experiments show that our method yields good results on benchmark and real world datasets.

  • Session: 29 | Room: 106 | Time: 12:40 – 13:00, Thursday 18 Sept Domain adaptation with regularized optimal transport (Nicolas Courty, Devis Tuia, Rémi Flamary)

    Authors

    Nicolas Courty, Univeristy of Bretagne Sud
    Devis Tuia, EPFL
    Rémi Flamary, University of Nice

    Abstract

    We present a new and original method to solve the domain adaptation problem using optimal transport. By searching for the best transportation plan between the probability distribution functions of a source and a target domain, a non-linear and invertible transformation of the learning set samples can be estimated. Any standard machine learning method can then be applied on the transformed set, which makes our method very generic. We propose an new optimal transport algorithm that incorporates the information contained in the labels available in the learning set in the optimization: this is achieved by combining an efficient matrix scaling technique together with a majoration of a non-convex regularization term. By using the proposed optimal transport with label regularization, we obtain significant increases of the performances compared with the original transport solution. The proposed algorithm is computationally efficient and effective, as illustrated by its evaluation on a toy example and a challenging real life vision dataset, against which it achieves competitive results with respect to state-of-the-art methods.

  • Session: 30 | Room: 102 | Time: 16:20 – 16:40, Thursday 18 Sept Active Learning for Support Vector Machines with Maximal Model Change (Wenbin Cai, Ya Zhang, Siyuan Zhou, Wenquan Wang, Chris Ding, Xiao Gu)

    Authors

    Wenbin Cai, Shanghai Jiao Tong University
    Ya Zhang
    Siyuan Zhou
    Wenquan Wang
    Chris Ding
    Xiao Gu

    Abstract

    Margin-based strategies and model change based strategies represent two important types of strategies for active learning. While margin-based strategies have been dominant for Support Vector Machines (SVMs), most methods are based on heuristics and lack a solid theoretical support. In this paper, we propose an active learning strategy for SVMs based on Maximum Model Change (MMC). The model change is defined as the difference between the current model parameters and the updated parameters obtained with the enlarged training set. Inspired by Stochastic Gradient Descent (SGD) update rule, we measure the change as the gradient of the loss at a candidate point. We analyze the convergence property of the proposed method, and show that the upper bound of label requests made by MMC is smaller than passive learning. Moreover, we connect the proposed MMC algorithm with the widely used simple margin method in order to provide a theoretical justification for margin-based strategies. Extensive experimental results on various benchmark data sets from UCI machine learning repository have demonstrated the effectiveness and efficiency of the proposed method.

  • Session: 30 | Room: 102 | Time: 16:40 – 17:00, Thursday 18 Sept Support Vector Machines for Differential Prediction (Finn Kuusisto, Vitor Santos Costa, Houssam Nassif, Elizabeth Burnside, David Page, Jude Shavlik)

    Authors

    Finn Kuusisto, UW – Madison
    Vitor Santos Costa, University of Porto
    Houssam Nassif
    Elizabeth Burnside, University of Wisconsin
    David Page, University of Wisconsin-Madison
    Jude Shavlik

    Abstract

    Machine learning is continually being applied to a growing set of fields, including the social sciences, business, and medicine. Some fields present problems that are not easily addressed using standard machine learning approaches and, in particular, there is growing interest in differential prediction. In this type of task we are interested in producing a classifier that specifically characterizes a subgroup of interest by maximizing the difference in predictive performance for some outcome between subgroups in a population. We discuss adapting maximum margin classifiers for differential prediction. We first introduce multiple approaches that do not affect the key properties of maximum margin classifiers, but which also do not directly attempt to optimize a standard measure of differential prediction. We next propose a model that directly optimizes a standard measure in this field, the uplift measure. We evaluate our models on real data from two medical applications and show excellent results.

  • Session: 30 | Room: 102 | Time: 17:00 – 17:20, Thursday 18 Sept Accelerating Model Selection with Safe Screening for L1-Regularized L2-SVM (Zheng Zhao, Jun Liu, James Cox)

    Authors

    Zheng Zhao, SAS Institute
    Jun Liu, SAS Institute Inc.
    James Cox, SAS Institute Inc.

    Abstract

    The L1-regularized support vector machine (SVM) is a powerful predictive learning model that can generate sparse solutions. Compared to a dense solution, a sparse solution is usually more interoperable and more effective for removing noise and preserving signals. The L1-regularized SVM has been successfully applied in numerous applications to solve problems from text mining, bioinformatics, and image processing. The regularization parameter has a significant impact on the performance of an L1-regularized SVM model. Therefore, model selection needs to be performed to choose a good regularization parameter. In model selection, one needs to learn a solution path using a set of predefined parameter values. Therefore, many L1-regularized SVM models need to be fitted, which is usually very time consuming. This paper proposes a novel safe screening technique to accelerate model selection for the L1-regularized L2-SVM, which can lead to much better efficiency in many scenarios. The technique can successfully identify most inactive features in an optimal solution of the L1-regularized L2-SVM model and remove them before training. To achieve safe screening, the technique solves a minimization problem for each feature on a convex set that is formed by the intersection of a tight n-dimensional hyperball and the upper half-space. An efficient algorithm is designed to solve the problem based on zero-finding. Every feature that is removed by the proposed technique is guaranteed to have zero weight in the optimal solution. Therefore, an L1-regularized L2-SVM solver achieves exactly the same result by using only the selected features as when it uses the full feature set. Empirical study on high-dimensional benchmark data sets produced promising results and demonstrated the effectiveness of the proposed technique.

  • Session: 31 | Room: 105 | Time: 16:20 – 16:40, Thursday 18 Sept Anti-discrimination Analysis Using Privacy Attack Strategies (Salvatore Ruggieri, Sara Hajian, Faisal Kamiran, Xiangliang Zhang)

    Authors

    Salvatore Ruggieri, University of Pisa, Italy
    Sara Hajian, Universitat Rovira i Virgili
    Faisal Kamiran, King Abdullah University of Science and Technology
    Xiangliang Zhang, King Abdullah University of Science and Technology

    Abstract

    Social discrimination discovery from data is an important task to identify illegal and unethical discriminatory patterns towards protected-by-law groups, e.g., ethnic minorities. We deploy privacy attack strategies as tools for discrimination discovery under hard assumptions which have rarely tackled in the literature: indirect discrimination discovery, privacy-aware discrimination discovery, and discrimination data recovery. The intuition comes from the intriguing parallel between the role of the anti-discrimination authority in the three scenarios above and the role of an attacker in private data publishing. We design strategies and algorithms inspired/based on Frèchet bounds attacks, attribute inference attacks, and minimality attacks to the purpose of unveiling hidden discriminatory practices. Experimental results show that they can be effective tools in the hands of anti-discrimination authorities.

  • Session: 31 | Room: 105 | Time: 16:40 – 17:00, Thursday 18 Sept Neutralized Empirical Risk Minimization with Generalization Neutrality Bound (Kazuto Fukuchi, Jun Sakuma)

    Authors

    Kazuto Fukuchi, University of Tsukuba
    Jun Sakuma, University of Tsukuba

    Abstract

    Currently, machine learning plays an important role in the lives and individual activities of numerous people. Accordingly, it has become necessary to design machine learning algorithms to ensure that discrimination, biased views, or unfair treatment do not result from decision making or predictions made via machine learning. In this work, we introduce a novel empirical risk minimization (ERM) framework for supervised learning, neutralized ERM (NERM) that ensures that any classifiers obtained can be guaranteed to be neutral with respect to a viewpoint hypothesis. More specifically, given a viewpoint hypothesis, NERM works to find a target hypothesis that minimizes the empirical risk while simultaneously identifying a target hypothesis that is neutral to the viewpoint hypothesis. Within the NERM framework, we derive a theoretical bound on empirical and generalization neutrality risks. Furthermore, as a realization of NERM with linear classification, we derive a max-margin algorithm, neutral support vector machine (SVM). Experimental results show that our neutral SVM shows improved classification performance in real datasets without sacrificing the neutrality guarantee.

  • Session: 32 | Room: 106 | Time: 16:20 – 16:40, Thursday 18 Sept Linear State-Space Model with Time-Varying Dynamics (Jaakko Luttinen, Tapani Raiko, Alexander Ilin)

    Jaakko Luttinen, Aalto University
    Tapani Raiko, Aalto University
    Alexander Ilin, Aalto University

    Abstract

    This paper introduces a linear state-space model with time-varying dynamics. The time dependency is obtained by forming the state dynamics matrix as a time-varying linear combination of a set of matrices. The time dependency of the weights in the linear combination is modelled by another linear Gaussian dynamical model allowing the model to learn how the dynamics of the process changes. Previous approaches have used switching models which have a small set of possible state dynamics matrices and the model selects one of those matrices at each time, thus jumping between them. Our model forms the dynamics as a linear combination and the changes can be smooth and more continuous. The model is motivated by physical processes which are described by linear partial differential equations whose parameters vary in time. An example of such a process could be a temperature field whose evolution is driven by a varying wind direction. The posterior inference is performed using variational Bayesian approximation. The experiments on stochastic advection-diffusion processes and real-world weather processes show that the model with time-varying dynamics can outperform previously introduced approaches.

  • Session: 32 | Room: 106 | Time: 16:40 – 17:00, Thursday 18 Sept Nonparametric Markovian Learning of Triggering Kernels for Mutually Exciting and Mutually Inhibiting Multivariate Hawkes Processes (Remi Lemonnier, Nicolas Vayatis)

    Authors

    Remi Lemonnier, ENS Cachan – CMLA
    Nicolas Vayatis, CMLA – ENS Cachan

    Abstract

    In this paper, we address the problem of fitting multivariate Hawkes processes to potentially large-scale data in a setting where series of events are not only mutually-exciting but can also exhibit inhibitive patterns. We focus on nonparametric learning and propose a novel algorithm called MEMIP (Markovian Estimation of Mutually Interacting Processes) that makes use of polynomial approximation theory and selfconcordant analysis in order to learn both triggering kernels and base intensities of events. Moreover, considering that N historical observations are available, the algorithm performs log-likelihood maximization in O(N) operations, while the complexity of non-Markovian methods is in O(N2). Numerical experiments on simulated data, as well as real-world data, show that our method enjoys improved prediction performance when compared to state-of-the art methods like MMEL and exponential kernels.

  • Session: 32 | Room: 106 | Time: 17:00 – 17:20, Thursday 18 Sept Bayesian Models for Structured Sparse Estimation via Set Cover Prior (Xianghang Liu, Xinhua Zhang, Tiberio Caetano)

    Authors

    Xianghang Liu, NICTA and UNSW
    Xinhua Zhang, NICTA and ANU
    Tiberio Caetano, NICTA

    Abstract

    A number of priors have been recently developed for Bayesian estimation of sparse models. In many applications the variables are simultaneously relevant or irrelevant in groups, and appropriately modeling this correlation is important for improved sample efficiency. Although group sparse priors are also available, most of them are either limited to disjoint groups, or do not infer sparsity at group level, or fail to induce appropriate patterns of support in the posterior. In this paper we tackle this problem by proposing a new framework of prior for overlapped group sparsity. It follows a hierarchical generation from group to variable, allowing group-driven shrinkage and relevance inference. It is also connected with set cover complexity in its maximum a posterior. Analysis on shrinkage profile and conditional dependency unravels favorable statistical behavior compared with existing priors. Experimental results also demonstrate its superior performance in sparse recovery and compressive sensing.

  • Session: 32 | Room: 106 | Time: 17:20 – 17:40, Thursday 18 Sept Cutset Networks: A Simple, Tractable, and Scalable Approach for Improving the Accuracy of Chow-Liu Trees (Tahrima Rahman, Prasanna Kothalkar, Vibhav Gogate)

    Authors

    Tahrima Rahman, University of Texas at Dallas
    Prasanna Kothalkar, The University of Texas at Dallas
    Vibhav Gogate, UT-Dallas

    Abstract

    In this paper, we present cutset networks, a new tractable probabilistic model for representing multi-dimensional discrete distributions. Cutset networks are rooted OR search trees, in which each OR node represents conditioning of a variable in the model, with tree Bayesian networks (Chow-Liu trees) at the leaves. From an inference point of view, cutset networks model the mechanics of Pearl’s cutset conditioning algorithm, a popular exact inference method for probabilistic graphical models. We present efficient algorithms, which leverage and adopt vast amount of research on decision tree induction for learning cutset networks from data. We also present an expectation-maximization (EM) algorithm for learning mixtures of cutset networks. Our experiments on a wide variety of benchmark datasets clearly demonstrate that compared to approaches for learning other tractable models such as thin-junction trees, latent tree models, arithmetic circuits and sum-product networks, our approach is significantly more scalable, and provides similar or better accuracy.

  • Session: 33 | Room: 103-104 | Time: 16:20 – 16:40, Thursday 18 Sept Fast Nearest Neighbor Search on Large Time-Evolving Graphs (Leman Akoglu, Rohit Khandekar, Vibhore Kumar, Srinivasan Parthasarathy, Deepak Rajan, Kun-Lung Wu, Christos Faloutsos)

    Authors

    Leman Akoglu, Stonybrook
    Rohit Khandekar, Knight Capital Group
    Vibhore Kumar, IBM T. J. Watson Research
    Srinivasan Parthasarathy, IBM T. J. Watson Research
    Deepak Rajan, Lawrence Livermore National Labs
    Kun-Lung Wu, IBM T. J. Watson Research
    Christos Faloutsos, Carnegie Mellon University

    Abstract

    Finding the k nearest neighbors (k-NNs) of a given vertex in a graph has many applications such as link prediction, keyword search, and image tagging. An established measure of vertex-proximity in graphs is the Personalized Page Rank (PPR) score based on random walk with restarts. Since PPR scores have long-range correlations, computing them accurately and efficiently is challenging when the graph is too large to fit in main memory, especially when it also changes over time. In this work, we propose an efficient algorithm to answer PPR-based k-NN queries in large time-evolving graphs. Our key approach is to use a divide-and-conquer framework and efficiently compute answers in a distributed fashion. We represent a given graph as a collection of dense vertex- clusters with their inter connections. Each vertex-cluster maintains certain information related to internal random walks and updates this information as the graph changes. At query time, we combine this information from a small set of relevant clusters and compute PPR scores efficiently. We validate the effectiveness of our method on large real-world graphs from diverse domains. To the best of our knowledge, this is one of the few works that simultaneously addresses answering k-NN queries in possibly disk-resident and time-evolving graphs.

  • Session: 33 | Room: 103-104 | Time: 16:40 – 17:00, Thursday 18 Sept Scalable Information Flow Mining in Networks (Karthik Subbian, Chidananda Sridhar, Charu Aggarwal, Jaideep Srivastava)

    Authors

    Karthik Subbian, University of Minnesota
    Chidananda Sridhar, University of Minnesota
    Charu Aggarwal, IBM Research
    Jaideep Srivastava, University of Minnesota

    Abstract

    The problem of understanding user activities and their patterns of communication is extremely important in social and collaboration networks. This can be achieved by tracking the dominant content flow trends and their interactions between users in the network. Our approach tracks all possible paths of information flow using its network structure, content propagated and the time of propagation. We also show that the complexity class of this problem is \#P-complete. Because most social networks have many activities and interactions, it is inevitable the proposed method will be computationally intensive. Therefore, we propose an efficient method for mining information flow patterns, especially in large networks, using distributed vertex-centric computational models. We use the Gather-Apply-Scatter (GAS) paradigm to implement our approach. We experimentally show that our approach achieves over three orders of magnitude advantage over the state-of-the-art, with an increasing advantage with a greater number of cores. We also study the effectiveness of the discovered content flow patterns by using it in the context of an influence analysis application.

  • Session: 33 | Room: 103-104 | Time: 17:20 – 17:40, Thursday 18 Sept Communication-Efficient Distributed Online Prediction by Decentralized Variance Monitoring (Michael Kamp, Mario Boley, Daniel Keren, Assaf Schuster, Izchak Sharfman)

    Authors

    Michael Kamp, Fraunhofer IAIS
    Mario Boley, University of Bonn and Fraunhofer IAIS, Germany
    Daniel Keren, Haifa University
    Assaf Schuster, Technion, Israel Institute of Technology
    Izchak Sharfman, Technion, Israel Institute of Technology

    Abstract

    We present the first protocol for distributed online prediction that aims to minimize online prediction loss and network communication at the same time. This protocol can be applied wherever a prediction-based service must be provided timely for each data point of a multitude of high frequency data streams, each of which is observed at a local node of some distributed system. Exemplary applications include social content recommendation and algorithmic trading. The challenge is to balance the joint predictive performance of the nodes by exchanging information between them, while not letting communication overhead deteriorate the responsiveness of the service. Technically, the proposed protocol is based on controlling the variance of the local models in a decentralized way. This approach retains the asymptotic optimal regret of previous algorithms. At the same time, it allows to substantially reduce network communication, and, in contrast to previous approaches, it remains applicable when the data is non-stationary and shows rapid concept drift. We demonstrate empirically that the protocol is able to hold up a high predictive performance using only a fraction of the communication required by benchmark methods.

X