%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\sessionHeader{Tue2A: Graphs, Trees, Sequences and Strings I}{Jos\'{e} L. Balc\'{a}zar}{Chem, LT1}
\timeTitlePeople{14:00--14:25}{A Family of Feed-forward Models for Protein Sequence Classification}
{Sam Blasiak, Huzefa Rangwala and Kathryn Laskey} 

\abst{Advances in sequencing have greatly outpaced experimental methods
for determining a protein's structure and function. As a result, biologists
increasingly rely on computational techniques to infer these properties
of proteins from sequence information alone. We present a sequence
classification framework that differs from the common SVM/kernel-based
approach. We introduce a type of artificial neural network which we
term the Subsequence Network (SN) that incorporates structural models
over sequences in its lowest layer. These structural models, which
we call Sequence Scoring Models (SSM), are similar to Hidden Markov
Models and act as a mechanism to extract relevant features from sequences.
In contrast to SVM/kernel methods, which only allow learning of linear
discrimination weights, our feed-forward structure allows linear weights
to be learned in conjunction with sequence-level features using standard
optimization techniques.}


\timeTitlePeople{14:25--14:50}{Nearly Exact Mining of Frequent Trees in Large Networks}
{Ashraf M. Kibriya and Jan Ramon} 

\abst{Mining frequent patterns in a single network (graph) poses a
  number of challenges. Already only to match one path pattern to a
  network (upto subgraph isomorphism) is NP-complete. Matching
  algorithms that exist, become intractable even for reasonably small
  patterns, on networks which are large or have a high average degree.
  Based on recent advances in parameterized complexity theory, we
  propose a novel miner for rooted trees in networks. The miner, for a
  fixed parameter $k$ (maximal pattern size), can mine all rooted
  trees with \emph{delay} linear in the size of the network and only
  mildly exponential in the fixed parameter $k$ ($2^k$). This allows
  us to mine tractably, rooted trees, in large networks such as the
  WWW or social networks. We establish the practical applicability of
  our miner, by presenting an experimental evaluation on both
  synthetic and real-world data.}


\timeTitlePeople{14:50--15:15}{Reachability Analysis and Modeling of
  Dynamic Event Networks} {Kathy Macropol and Ambuj Singh}

\abst{A wealth of graph data, from email and telephone graphs to
  Twitter networks, falls into the category of dynamic ``event''
  networks. Edges in these networks represent brief events, and their
  analysis leads to multiple interesting and important topics, such as
  the prediction of road traffic or modeling of communication flow. In
  this paper, we analyze a novel new dynamic event graph property, the
  ``Dynamic Reachability Set'' (DRS), which characterizes reachability
  within graphs across time. We discover that DRS histograms of
  multiple real world dynamic event networks follow novel distribution
  patterns. From these patterns, we introduce a new generative dynamic
  graph model, DRS-Gen. DRS-Gen captures the dynamic graph properties
  of connectivity and reachability, as well as generates time values
  for its edges. To the best of our knowledge, DRS-Gen is the first
  such model which produces exact time values on edges, allowing us to
  understand simultaneity across multiple information flows.}


\timeTitlePeople{15:15--15:40}{An Efficiently Computable Support Measure for Frequent Subgraph Pattern Mining}
{Yuyi Wang and Jan Ramon} 

\abst{Graph support measures are functions measuring how frequently a
  given subgraph pattern occurs in a given database graph.  An
  important class of support measures relies on overlap graphs.  A
  major advantage of the overlap graph based approaches is that they
  combine anti-monotonicity with counting occurrences of a pattern
  which are independent according to certain criteria.  However,
  existing overlap graph based support measures are expensive to
  compute.

In this paper, we propose a new support measure which is based on a
new notion of independence.  We show that our measure is the solution
to a linear program which is usually sparse, and using interior point
methods can be computed efficiently.  We show experimentally that for
large networks, in contrast to earlier overlap graph based proposals,
pattern mining based on our support measure is feasible.  }


\sessionend


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\sessionHeader{Tue2B: Rankings and Recommendations}{Carlos Soares}{Chem, LT2}
\timeTitlePeople{14:00--14:25}{A Live Comparison of Methods for
  Personalized Article Recommendation at Forbes.com} {Evan
  Kirshenbaum, George Forman and Michael Dugan}

\abst{We present the results of a multi-phase study to optimize
  strategies for generating personalized article recommendations at
  the Forbes.com web site.  In the first phase we compared the
  performance of a variety of recommendation methods on historical
  data.  In the second phase we deployed a live system at Forbes.com
  for five months on a sample of 82,000 users, each randomly assigned
  to one of 20 methods.  We analyze the live results both in terms of
  click-through rate (CTR) and user session lengths.  The method with
  the best CTR was a hybrid of collaborative-filtering and a
  content-based method that leverages Wikipedia-based concept
  features, post-processed by a novel Bayesian remapping technique
  that we introduce.  It both statistically significantly beat decayed
  popularity and increased CTR by 37\%.}


\timeTitlePeople{14:25--14:50}{Active Evaluation of Ranking Functions Based on Graded Relevance} 
{Christoph Sawade, Steffen Bickel, Timo
  von Oertzen, Tobias Scheffer and Niels Landwehr}

\abst{Evaluating the quality of ranking functions is a core task in
  web search and other information retrieval domains. Because query
  distributions and item relevance change over time, ranking models
  often cannot be evaluated accurately on held-out training
  data. Instead, considerable effort is spent on manually labeling the
  relevance of query results for test queries in order to track
  ranking performance. We address the problem of estimating ranking
  performance as accurately as possible on a fixed labeling
  budget. Estimates are based on a set of most informative test
  queries selected by an active sampling distribution. Query labeling
  costs depend on the number of result items as well as item-specific
  attributes such as document length. We derive cost-optimal sampling
  distributions for the commonly used performance measures Discounted
  Cumulative Gain (DCG) and Expected Reciprocal Rank
  (ERR). Experiments on web search engine data illustrate significant
  reductions in labeling costs.}


\timeTitlePeople{14:50--15:15}{Fast ALS-Based Tensor Factorization for Context-Aware Recommendation from Implicit\break Feedback} 
{Bal\'azs Hidasi and Domonkos Tikk}

\abst{Albeit the implicit feedback based recommendation problem---when
  only the user history is available but there are no ratings---is the
  most typical setting in real-world applications, it is much less
  researched than the explicit feedback case. State-of-the-art
  algorithms that are efficient on the explicit case cannot be
  straightforwardly transformed to the implicit case if scalability
  should be maintained. There are few implicit feedback benchmark
  datasets, therefore new ideas are usually experimented on explicit
  benchmarks. In this paper, we propose a generic context-aware
  implicit feedback recommender algorithm, coined iTALS. iTALS applies
  a fast, ALS-based tensor factorization learning method that scales
  linearly with the number of non-zero elements in the tensor. The
  method also allows us to incorporate various contextual information
  into the model while maintaining its computational efficiency. We
  present two context-aware implementation variants of iTALS. The
  first incorporates seasonality and enables to distinguish user
  behavior in different time intervals. The other views the user
  history as sequential information and has the ability to recognize
  usage pattern typical to certain group of items, e.g. to
  automatically tell apart product types that are typically purchased
  repetitively or once.  Experiments performed on five implicit
  datasets (LastFM 1K, Grocery, VoD, and ``implicitized'' Netflix and
  MovieLens 10M) show that by integrating context-aware information
  with our factorization framework into the state-of-the-art implicit
  recommender algorithm the recommendation quality improves
  significantly. }


\timeTitlePeople{15:15--15:40}{Probability Estimation for Multi-class Classification Based on Label Ranking}
{Weiwei Cheng and Eyke H\"ullermeier} 

\abst{We consider the problem of probability estimation in the setting
  of multi-class classification. While this problem has already been
  addressed in the literature, we tackle it from a novel
  perspective. Exploiting the close connection between probability
  estimation and ranking, our idea is to solve the former on the basis
  of the latter, taking advantage of recently developed methods for
  label ranking. More specifically, we argue that the Plackett-Luce
  ranking model is a very natural choice in this context, especially
  as it can be seen as a multinomial extension of the Bradley-Terry
  model. The latter provides the basis of pairwise coupling
  techniques, which arguably constitute the state-of-the-art in
  multi-class probability estimation. We explore the relationship
  between the pairwise and the ranking-based approach to probability
  estimation, both formally and empirically. Using synthetic and
  real-world data, we show that our method does not only enjoy nice
  theoretical properties, but is also competitive in terms of accuracy
  and efficiency.}


\sessionend


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\sessionHeader{Tue2C: Ensemble Methods}{Herna Viktor}{Chem, LT3}
\timeTitlePeople{14:00--14:25}{Boosting Nearest
Neighbors for the Efficient Estimation of Posteriors} 
{Roberto D'Ambrosio, Richard Nock, Wafa Bel Haj Ali, Frank Nielsen and
  Michel Barlaud}

\abst{It is an admitted fact that mainstream boosting algorithms like
  AdaBoost do not perform well to estimate class conditional
  probabilities.  In this paper, we analyze, in the light of this
  problem, a recent algorithm, \unn, which leverages nearest neighbors
  while minimizing a convex loss.  Our contribution is
  threefold. First, we show that there exists a subclass of surrogate
  losses, elsewhere called balanced, whose minimization brings simple
  and statistically efficient estimators for Bayes posteriors. Second,
  we show \textit{explicit} convergence rates towards these estimators
  for \unn, for any such surrogate loss, under a Weak Learning
  Assumption which parallels that of classical boosting results. Third
  and last, we provide experiments and comparisons on synthetic and
  real datasets, including the challenging SUN computer vision
  database. Results clearly display that boosting nearest neighbors
  may provide highly accurate estimators, sometimes more than a
  hundred times more accurate than those of other contenders like
  support vector machines.}


\timeTitlePeople{14:25--14:50}{Diversity Regularized Ensemble Pruning}
{Nan Li, Yang Yu and Zhi-Hua Zhou} 

\abst{ Diversity among individual classifiers is recognized to play a
  key role in ensemble, however, few theoretical properties are known
  for classification.
%
In this paper, by focusing on the popular ensemble pruning setting
(i.e., combining classifier by \emph{voting} and measuring diversity
in \emph{pairwise} manner), we present a theoretical study on the
effect of diversity on the generalization performance of voting in the
PAC-learning framework. It is disclosed that the diversity is
closely-related to the hypothesis space complexity, and encouraging
diversity can be regarded to apply regularization on ensemble methods.
%
Guided by this analysis, we apply explicit diversity regularization to
ensemble pruning, and propose the {\it Diversity Regularized Ensemble
  Pruning} ({DREP}) method.
%,
Experimental results show the effectiveness of DREP.}


\timeTitlePeople{14:50--15:15}{Ensembles on Random Patches}
{Gilles Louppe and Pierre Geurts} 

\abst{In this paper, we consider supervised learning under the
  assumption that the available memory is small compared to the
  dataset size. This general framework is relevant in the context of
  big data, distributed databases and embedded systems. We investigate
  a very simple, yet effective, ensemble framework that builds each
  individual model of the ensemble from a random patch of data
  obtained by drawing random subsets of \textit{both} instances and
  features from the whole dataset. We carry out an extensive and
  systematic evaluation of this method on 29 datasets, using decision
  tree-based estimators. With respect to popular ensemble methods,
  these experiments show that the proposed method provides on par
  performance in terms of accuracy while simultaneously lowering the
  memory needs, and attains significantly better performance when
  memory is severely constrained.}


\timeTitlePeople{15:15--15:40}{Multi-Task Boosting by Exploiting Task Relationships}
{Yu Zhang and Dit-Yan Yeung} 

\abst{Multi-task learning aims at improving the performance of one
  learning task with the help of other related tasks.  It is
  particularly useful when each task has very limited labeled data.  A
  central issue in multi-task learning is to learn and exploit the
  relationships between tasks.  In this paper, we generalize boosting
  to the multi-task learning setting and propose a method called
  multi-task boosting~(MTBoost).  Different tasks in \mbox{MTBoost}
  share the same base learners but with different weights which are
  related to the estimated task relationships in each iteration.  In
  \mbox{MTBoost}, unlike ordinary boosting methods, the base learners,
  weights and task covariances are learned together in an integrated
  fashion using an alternating optimization procedure.  We conduct
  theoretical analysis on the convergence of \mbox{MTBoost} and also
  empirical analysis comparing it with several related methods.}


\sessionend

