%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\sessionHeader{Thu3A: Large-Scale, Distributed and Parallel Mining and Learning II
}{Sofus A.~Macskassy}{Chem, LT1}
\timeTitlePeople{16:10--16:35}{CC-MR -- Finding Connected Components in Huge Graphs with MapReduce}{Thomas Seidl, Brigitte Boden and Sergej Fries}

\abst{The detection of connected components in graphs is a well-known problem arising in a large number of applications including data mining, analysis of social networks, image analysis and a lot of other related problems. 
In spite of the existing very efficient serial algorithms, this problem remains a subject of research due to increasing data amounts produced by modern information systems which cannot be handled by single workstations. 
Only highly parallelized approaches on multi-core-servers or computer clusters are able to deal with these large-scale data sets. In this work we present a solution for this problem for distributed memory architectures, and provide an implementation for the well-known MapReduce framework developed by Google. 
Our algorithm CC-MR significantly outperforms the existing approaches for the MapReduce framework in terms of the number of necessary iterations, communication costs and execution runtime, as we show in our experimental evaluation on synthetic and real-world data. 
Furthermore, we present a technique for accelerating our implementation for datasets with very heterogeneous component sizes as they often appear in real data sets.
}


\timeTitlePeople{16:35--17:00}{Fast Near Neighbor Search in High-Dimensional Binary Data
}{Anshumali Shrivastava and Ping Li}

\abst{Numerous applications in search, databases, machine learning,  and computer vision, can benefit from  efficient algorithms for near neighbor search. This paper proposes a simple framework for {\em fast near neighbor search in high-dimensional binary data}, which are common in practice (e.g., text). We develop a very simple and effective strategy for sub-linear time near neighbor search, by creating hash tables directly using the bits generated by $b$-bit minwise hashing. The advantages of our method are demonstrated through thorough comparisons with two  strong baselines: {\em spectral hashing} and {\em sign (1-bit) random projections}.
}


\timeTitlePeople{17:00--17:25}{Fully Sparse Topic Models
}{Khoat Than and Tu Bao Ho}

\abst{In this paper, we propose Fully Sparse Topic Model (FSTM) for modeling large collections of documents. Three key properties of the model are: (1) the inference algorithm converges in linear time, (2) learning of topics is simply a multiplication of two sparse matrices, (3) it provides a principled way to directly trade off sparsity of solutions against inference quality and running time. These properties enable us to speedily learn sparse topics and to infer sparse latent representations of documents, and help significantly save memory for storage. We show that inference in FSTM is actually MAP inference with an implicit prior. Extensive experiments show that FSTM can perform substantially better than various existing topic models by different performance measures. Finally, our parallel implementation can handily learn thousands of topics from large corpora with millions of terms.
}


\timeTitlePeople{17:25--17:50}{Massively Parallel Feature Selection: An Approach Based on Variance Preservation
}{Zheng Zhao, James Cox, David Duling and Warren Sarle}

\abst{Advances in computer technologies have enabled corporations to accumulate data at an unprecedented speed. Large-scale business data might contain billions of observations and thousands of features, which easily brings their scale to the level of terabytes. Most traditional feature selection algorithms are designed for a centralized computing architecture. Their usability significantly deteriorates when data size exceeds hundreds of gigabytes. High-performance distributed computing frameworks and protocols, such as the Message Passing Interface (MPI) and MapReduce, have been proposed to facilitate software development on grid infrastructures, enabling analysts to process large-scale problems efficiently. This paper presents a novel large-scale feature selection algorithm that is based on variance analysis. The algorithm selects features by evaluating their abilities to explain data variance. It supports both supervised and unsupervised feature selection and can be readily implemented in most distributed computing environments. The algorithm was developed as a SAS High-Performance Analytics procedure, which can read data in distributed form and perform parallel feature selection in both symmetric multiprocessing mode and massively parallel processing mode. Experimental results demonstrated the superior performance of the proposed method for large scale feature selection.}


\sessionend

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\sessionHeader{Thu3B: Natural Language Processing
}{Eric Gaussier}{Chem, LT2}
\timeTitlePeople{16:10--16:35}{Collective Information Extraction with Context-Specific Consistencies
}{Peter Kluegl, Martin Toepfer, Florian Lemmerich, Andreas Hotho and Frank Puppe}

\abst{Conditional Random Fields (CRFs) have been widely used for information extraction from free texts as well as from semi-structured documents. Interesting entities in semi-structured domains are often consistently structured within a certain context or document. However, their actual compositions vary and are possibly inconsistent among different contexts. We present two collective information extraction approaches based on CRFs for exploiting these context-specific consistencies. The first approach extends linear-chain CRFs by additional factors specified by a classifier, which learns such consistencies during inference. In a second extended approach, we propose a variant of skip-chain CRFs, which enables the model to transfer long-range evidence about the consistency of the entities. The practical relevance of the presented work for real-world information extraction systems is highlighted in an empirical study. Both approaches achieve a considerable error reduction.}


\timeTitlePeople{16:35--17:00}{Supervised Learning of  Semantic Relatedness
}{Ran El-Yaniv and David Yanay}

\abst{We propose and study a novel supervised approach
to learning statistical semantic relatedness models from subjectively annotated training examples.
The proposed semantic model consists of parameterized
co-occurrence statistics associated with
textual units of a large background knowledge corpus.
We present an efficient algorithm for learning such semantic
models from a training sample of relatedness preferences.
Our method is corpus independent and can essentially rely on any sufficiently large (unstructured)
collection of coherent texts.
Moreover, the approach facilitates the fitting of semantic models for specific users or groups of users.
We present the results of extensive range of experiments from small to large scale,
indicating that the proposed method is effective and competitive with the state-of-the-art.}


\timeTitlePeople{17:00--17:25}{Unsupervised Bayesian Part of Speech Inference with Particle Gibbs
}{Gregory Dubbin and Phil Blunsom}

\abst{As linguistic models incorporate more subtle nuances of language and its structure, standard inference techniques can fall behind.  These models are often tightly coupled such that they defy clever dynamic programming tricks.  Here we demonstrate that Sequential Monte Carlo approaches, i.e.\ particle filters, are well suited to approximating such models. We implement two particle filters, which jointly sample either sentences or word types, and incorporate them into a Particle Gibbs sampler for Bayesian inference of syntactic part-of-speech categories.  We analyze the behavior of the samplers and compare them to an exact block sentence sampler, a local sampler, and an existing heuristic word type sampler.  We also explore the benefits of mixing Particle Gibbs and standard samplers.}


\timeTitlePeople{17:25--17:50}{WikiSent: Weakly Supervised Sentiment Analysis through Extractive Summarization with Wikipedia}{Subhabrata Mukherjee and Pushpak Bhattacharyya}

\abst{This paper describes a weakly supervised system for sentiment analysis in the movie review domain. The objective is to classify a movie review into a polarity class, positive or negative, based on those sentences bearing opinion on the movie alone, leaving out other irrelevant text. Wikipedia incorporates the world knowledge of movie-specific features in the system which is used to obtain an extractive summary of the review, consisting of the reviewer’s opinions about the specific aspects of the movie. This filters out the concepts which are irrelevant or objective with respect to the given movie. The proposed system, WikiSent, does not require any labeled data for training. It achieves a better or comparable accuracy to the existing semi-supervised and unsupervised systems in the domain, on the same dataset. We also perform a general movie review trend analysis using WikiSent. }


\sessionend

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\sessionHeader{Thu3C: Reinforcement Learning and Planning II
}{Myra Spiliopoulou}{Chem, LT3}
\timeTitlePeople{16:10--16:35}{Bootstrapping Monte Carlo Tree Search with an Imperfect Heuristic
}{Truong-Huy Dinh Nguyen, Wee-Sun Lee and Tze-Yun Leong}

\abst{We consider the problem of using a heuristic policy to improve the value approximation by the Upper Confidence Bound applied in Trees (UCT) algorithm in non-adversarial settings such as planning with large-state space Markov Decision Processes. Current improvements to UCT focus on either changing the action selection formula at the internal nodes or the rollout policy at the leaf nodes of the search tree. In this work, we propose to add an auxiliary arm to each of the internal nodes, and always use the heuristic policy to roll out simulations at the auxiliary arms. The method aims to get fast convergence to optimal values at states where the heuristic policy is optimal, while retaining similar approximation as the original UCT at other states. We show that bootstrapping with the proposed method in the new algorithm, UCT-Aux, performs better compared to the original UCT algorithm and its variants in two benchmark experiment settings. We also examine conditions under which UCT-Aux works well.}


\timeTitlePeople{16:35--17:00}{Fast Reinforcement Learning with Large Action Sets Using Error-Correcting Output Codes for MDP Factorization}{Gabriel Dulac-Arnold, Ludovic Denoyer, Philippe Preux and Patrick Gallinari}

\abst{The use of Reinforcement Learning in real-world scenarios is strongly limited by issues of scale.  
Most RL learning algorithms are unable to deal with problems composed of hundreds or sometimes even dozens of possible actions, and therefore cannot be applied to many real-world problems. We consider the RL problem in the supervised classification framework where the optimal policy is obtained through a multiclass classifier, the set of classes being the set of actions of the problem.
We introduce error-correcting output codes (ECOCs) in this setting and propose two new methods for reducing complexity when using rollouts-based approaches. The first method consists in using an ECOC-based classifier as the multiclass classifier, reducing the learning complexity from $\mathcal{O}(A^2)$ to $\mathcal{O}(A \log(A))$. 
We then propose a novel method that profits from the ECOC's coding dictionary to split the initial MDP into $\mathcal{O}(\log(A))$ separate two-action MDPs. This second method reduces learning complexity even further, from $\mathcal{O}(A^2)$ to $\mathcal{O}(\log(A))$, thus rendering problems with large action sets tractable.
We finish by experimentally demonstrating the advantages of our approach on a set of benchmark problems, both in speed and performance. 
}


\timeTitlePeople{17:00--17:25}{Learning Policies For Battery Usage Optimization in Electric Vehicles
}{Stefano Ermon, Yexiang Xue, Carla Gomes and Bart Selman}

\abst{The high cost, limited capacity, and long recharge time of batteries pose a number of obstacles for the widespread adoption of electric vehicles. Multi-battery systems that combine a standard battery with supercapacitors are currently one of the most promising ways to increase battery lifespan and reduce operating costs. However, their performance crucially depends on how they are designed and operated. 

In this paper, we formalize the problem of optimizing real-time energy management of multi-battery systems as a stochastic planning problem, and we propose a novel solution based on a combination of optimization, machine learning and data-mining techniques. 
We evaluate the performance of our intelligent energy management system on various large datasets of commuter trips crowdsourced in the United States. We show that our policy significantly outperforms the leading algorithms that were previously proposed as part of an open algorithmic challenge.}


\timeTitlePeople{17:25--17:50}{Structured Apprenticeship Learning
}{Abdeslam Boularias, Oliver Kr\"{o}mer and Jan Peters}

\abst{We propose a graph-based algorithm for apprenticeship learning when the reward features are noisy.
Previous apprenticeship learning techniques learn a reward function by using only local state features.
This can be a limitation in practice, as often some features are misspecified or subject to measurement noise.
Our graphical framework, inspired from the work on Markov Random Fields, allows to alleviate this problem by propagating information between states, and rewarding
policies that choose similar actions in adjacent states. We demonstrate the advantage of the proposed approach
on grid-world navigation problems, and on the problem of teaching a robot to grasp novel objects in simulation.}


