%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\sessionHeader{Tue1A: Bayesian Learning and Graphical Models}{Jaakko Hollm\'{e}n}{Chem, LT1}
\timeTitlePeople{10:30--10:55}{An Experimental Comparison of Hybrid Algorithms for Bayesian Network Structure Learning}
{Maxime Gasse, Alex Aussem and Haytham Elghazel} 

\abst{We present a novel hybrid algorithm for Bayesian network
  structure learning, called Hybrid HPC (H2PC). It first reconstructs
  the skeleton of a Bayesian network and then performs a
  Bayesian-scoring greedy hill-climbing search to orient the edges. It
  is based on a subroutine called HPC, that combines ideas from
  incremental and divide-and-conquer constraint-based methods to learn
  the parents and children of a target variable.  We conduct an
  experimental comparison of H2PC against Max-Min Hill-Climbing
  (MMHC), which is currently the most powerful state-of-the-art
  algorithm for Bayesian network structure learning, on several
  benchmarks with various data sizes. Our extensive experiments show
  that H2PC outperforms MMHC both in terms of goodness of fit to new
  data and in terms of the quality of the network structure itself,
  which is closer to the true dependence structure of the data,
  without increasing the computational burden involved. The source
  code (in \textit{R}) of H2PC as well as all data sets used for the
  empirical tests are publicly available.}

\timeTitlePeople{10:55--11:20}{Bayesian Network Classifiers with Reduced
  Precision Parameters}{Sebastian Tschiatschek, Peter Reinprecht,
  Manfred M\"ucke and Franz Pernkopf} 

\abst{Bayesian network classifiers (BNCs) are probabilistic
  classifiers showing good performance in many applications. They
  consist of a directed acyclic graph and a set of conditional
  probabilities associated with the nodes of the graph. These
  conditional probabilities are also referred to as parameters of the
  BNCs.  According to common believe, these classifiers are
  insensitive to deviations of the conditional probabilities under
  certain conditions. The first condition is that these probabilities
  are not too extreme, i.e.\ not too close to $0$ or $1$. The second
  is that the posterior over the classes is significantly
  different. In this paper, we investigate the effect of precision
  reduction of the parameters on the classification performance of
  BNCs. The probabilities are either determined generatively or
  discriminatively.  Discriminative probabilities are typically more
  extreme.  However, our results indicate that BNCs with
  discriminatively optimized parameters are almost as robust to
  precision reduction as BNCs with generatively optimized parameters.
  Furthermore, even large precision reduction does not decrease
  classification performance significantly. Our results allow the
  implementation of BNCs with less computational complexity. This
  supports application in embedded systems using floating-point
  numbers with small bit-width.  Reduced bit-widths further enable to
  represent BNCs in the integer domain while maintaining the
  classification performance.}

\timeTitlePeople{11:20--11:45}{Combining Subjective Probabilities and Data in
  Training Markov Logic Networks}{Tivadar P\'{a}pai, Shalini Ghosh and
  Henry Kautz}

\abst{Markov logic is a rich language that allows one to specify a
  knowledge base as a set of weighted first-order logic formulas, and
  to define a probability distribution over truth assignments to
  ground atoms using this knowledge base.  Usually, the weight of a
  formula cannot be related to the probability of the formula without
  taking into account the weights of the other formulas.  In general,
  this is not an issue, since the weights are learned from training
  data. However, in many domains ({\em e.g.} healthcare,
  dependable systems, {\em etc.}), only little or no training data
  may be available, but one has access to a domain expert whose
  knowledge is available in the form of subjective probabilities.
  Within the framework of Bayesian statistics, we present a formalism
  for using a domain expert's knowledge for weight learning. Our
  approach defines priors that are different from and more general
  than previously used Gaussian priors over weights.  We show how one
  can learn weights in an MLN by combining subjective probabilities
  and training data, without requiring that the domain expert provides
  consistent knowledge. Additionally, we also provide a formalism for
  capturing conditional subjective probabilities, which are often
  easier to obtain and more reliable than non-conditional
  probabilities. We demonstrate the effectiveness of our approach by
  extensive experiments in a domain that models failure dependencies
  in a cyber-physical system. Moreover, we demonstrate the advantages
  of using our proposed prior over that of using non-zero mean
  Gaussian priors in a commonly cited social network MLN testbed.}

%\continueSessionOnNewPage{Tue1A: Bayesian Learning and Graphical Models}{Jaakko Hollm\'{e}n}{LT1}
\timeTitlePeople{11:45--12:10}{Score-Based Bayesian Skill Learning}{Shengbo
  Guo, Scott Sanner, Thore Graepel and Wray Buntine}

\abst{We extend the Bayesian skill rating system of TrueSkill to
  accommodate score-based match outcomes. TrueSkill has proven to be a
  very effective algorithm for matchmaking --- the process of pairing
  competitors based on similar skill-level --- in competitive online
  gaming.  However, for the case of two teams/players, TrueSkill only
  learns from win, lose, or draw outcomes and cannot use additional
  match outcome information such as scores.  To address this
  deficiency, we propose novel Bayesian graphical models as extensions
  of TrueSkill that (1) model player's offence and defence skills
  separately and (2) model how these offence and defence skills
  interact to generate score-based match outcomes.  We derive
  efficient (approximate) Bayesian inference methods for inferring
  latent skills in these new models and evaluate them on three real
  data sets including Halo 2 XBox Live matches. Empirical evaluations
  demonstrate that the new score-based models (a) provide more
  accurate win/loss probability estimates than TrueSkill when training
  data is limited, (b) provide competitive and often better win/loss
  classification performance than TrueSkill, and (c) provide
  reasonable score outcome predictions with an appropriate choice of
  likelihood --- prediction for which TrueSkill was not designed, but
  which can be useful in many applications.}

\sessionend


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\sessionHeader{Tue1B: Association Rules and Frequent Patterns}{Matthijs van Leeuwen}{Chem, LT2}
\timeTitlePeople{10:30--10:55}{Discovering Descriptive Tile Trees by Mining
  Optimal Geometric Subtiles}{Nikolaj Tatti and Jilles Vreeken}

\abst{When analysing binary data, the ease at which one can interpret results is very important. Many existing methods, however, discover either models that are difficult to read, or return so many results interpretation becomes impossible. 
Here, we study a fully automated approach for mining easily
interpretable models for binary data. We model data hierarchically
with noisy tiles---rectangles with significantly different density
than their parent tile. To identify good trees, we employ the Minimum
Description Length principle.

We propose \Mondrian, a greedy any-time algorithm for mining good tile
trees from binary data. Iteratively, it finds the
locally \emph{optimal} addition to the current tree, allowing overlap
with tiles of the same parent. A major result of this paper is that we
find the optimal tile in only
$\Theta(\numrows\numcols\min(\numrows,\numcols))$ time. \Mondrian can
either be employed as a top-$k$ miner, or by MDL we can identify the
tree that describes the data best.

Experiments show we find succinct models that accurately summarise the
data, and, by their hierarchical property are easily interpretable.}

\timeTitlePeople{10:55--11:20}{Efficient Discovery of Association Rules and
  Frequent Itemsets through Sampling with Tight
  Performance Guarantees}{Matteo Riondato and Eli Upfal} 

\abst{The tasks of extracting (top-$K$) Frequent Itemsets (FI's) and
  Association Rules (AR's) are fundamental primitives in data mining
  and database applications. Exact algorithms for these problems exist
  and are widely used, but their running time is hindered by the need
  of scanning the entire dataset, possibly multiple times.  High
  quality approximations of FI's and AR's are sufficient for most
  practical uses, and a number of recent works explored the
  application of sampling for fast discovery of approximate solutions
  to the problems. However, these works do not provide satisfactory
  performance guarantees on the quality of the approximation, due to
  the difficulty of bounding the probability of under- or
  over-sampling any one of an unknown number of frequent itemsets. In
  this work we circumvent this issue by applying the statistical
  concept of \emph{Vapnik-Chervonenkis (VC) dimension} to develop a
  novel technique for providing tight bounds on the sample size that
  guarantees approximation within user-specified parameters.  Our
  technique applies both to absolute and to relative approximations of
  (top-$K$) FI's and AR's. The resulting sample size is linearly
  dependent on the VC-dimension of a range space associated with the
  dataset to be mined. The main theoretical contribution of this work
  is a characterization of the VC-dimension of this range space and a
  proof that it is upper bounded by an easy-to-compute characteristic
  quantity of the dataset which we call \emph{d-index}, namely the
  maximum integer $d$ such that the dataset contains at least $d$
  transactions of length at least $d$. We show that this bound is
  strict for a large class of datasets. The resulting sample size for
  an absolute (resp.~relative) $(\varepsilon, \delta)$-approximation
  of the collection of FI's is
  $O(\frac{1}{\varepsilon^2}(d+\log\frac{1}{\delta}))$ (resp.
  $O(\frac{2+\varepsilon}{\varepsilon^2(2-\varepsilon)\theta}(d\log\frac{2+\varepsilon}{(2-\varepsilon)\theta}+\log\frac{1}{\delta}))$)
  transactions, which is a significant improvement over previous known
  results. We present an extensive experimental evaluation of our
  technique on real and artificial datasets, demonstrating the
  practicality of our methods, and showing that they achieve even
  higher quality approximations than what is guaranteed by the
  analysis.}

\timeTitlePeople{11:20--11:45}{General Algorithms for Mining Closed Flexible Patterns under Various Equivalence Relations}
{Tomohiro I, Yuki Enokuma, Hideo Bannai and Masayuki Takeda}


\abst{We address the closed pattern discovery problem
in sequential databases for the class of {\em flexible} patterns.
We propose two techniques of coarsening existing equivalence relations
on the set of patterns to obtain new equivalence relations.
Our new algorithm {\GCF} is a generalization of
\textsf{MaxFlex} proposed by Arimura and Uno (2007)
that was designed for a particular equivalence relation.  {\GCF} can
cope with existing, as well as new equivalence relations, and we
investigate the computational complexities of the algorithm for
respective equivalence relations.  Then, we present an improved
algorithm {\GCFP} based on new pruning techniques, which improve the
delay time per output for some of the equivalence relations.  By
computational experiments on synthetic data, we show that most of the
redundancies in the mined patterns are removed using the proposed
equivalence relations.}



\timeTitlePeople{11:45--12:10}{Smoothing Categorical Data}{Arno Siebes and
  Ren\'{e} Kersten}

\abst{Global models of a dataset reflect not only the large scale structure
of the data distribution, they also reflect small(er) scale structure.
Hence, if one wants to see the large scale structure, one should
somehow subtract this smaller scale structure from the model.

While for some kinds of model -- such as boosted classifiers -- it is
easy to see the ``important" components, for many kind of models this
is far harder, if at all possible.  In such cases one might try an
implicit approach: simplify the data distribution without changing the
large scale structure. That is, one might first smooth the local
structure out of the dataset. Then induce a new model from this
smoothed dataset. This new model should now reflect the large scale
structure of the original dataset.  In this paper we propose such a
smoothing for categorical data and for one particular type of models,
viz., code tables.

By experiments we show that our approach preserves the large scale
structure of a dataset well. That is, the smoothed dataset is simpler
while the original and smoothed datasets share the same large scale
structure.}

\sessionend



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\sessionHeader{Tue1C: Reinforcement Learning and Planning I}{Balaraman Ravindran}{Chem, LT3}
\timeTitlePeople{10:30--10:55}
{Adaptive Planning for Markov Decision Processes with Uncertain Transition Models via\break Incremental Feature Dependency Discovery}
{N.\ Kemal Ure, Alborz Geramifard, Girish Chowdhary and Jonathan P.\ How}

\abst{
Solving large scale sequential decision making problems without prior
knowledge of the state transition model is a key problem in the planning
literature. One approach to tackle this problem is to learn the state
transition model online using limited observed measurements. We present an adaptive function approximator (incremental
Feature Dependency Discovery (iFDD))
that grows the set of
features online to approximately represent the transition
model. The approach leverages existing
feature-dependencies to build a sparse representation of the state
transition model. 
Theoretical analysis and numerical simulations in domains with state space sizes varying from thousands to millions are used to illustrate the benefit of using iFDD for incrementally building transition models in a planning framework.
\vspace{-2mm}
}

\timeTitlePeople{10:55--11:20}
{APRIL: Active Preference Learning-Based Reinforcement Learning}{Riad Akrour, Marc Schoenauer and Mich\`ele Sebag}

\abst{This paper focuses on reinforcement learning (RL) with limited prior
knowledge. In the domain of swarm robotics for instance, the expert
can hardly design a reward function or demonstrate the target
behavior, forbidding the use of both standard RL and inverse
reinforcement learning. Although with a limited expertise, the human
expert is still often able to emit preferences and rank the agent
demonstrations. Earlier work has presented an iterative
preference-based RL framework: expert preferences are exploited to
learn an approximate policy return, thus enabling the agent to achieve
direct policy search. Iteratively, the agent selects a new candidate
policy and demonstrates it; the expert ranks the new demonstration
comparatively to the previous best one; the expert's ranking feedback
enables the agent to refine the approximate policy return, and the
process is iterated. 

In this paper, preference-based reinforcement learning is combined
with active ranking in order to decrease the number of ranking queries
to the expert needed to yield a satisfactory policy.  Experiments on
the mountain car and the cancer treatment testbeds witness that a
couple of dozen rankings enable to learn a competent policy.}

\timeTitlePeople{11:20--11:45}{Autonomous Data-Driven Decision-Making in Smart Electricity Markets}
{Markus Peters, Wolfgang Ketter, Maytal Saar-Tsechansky and John Collins}

\abst{For the vision of a Smart Grid to materialize, substantial advances in intelligent
decentralized control mechanisms are required. We propose a novel
class of autonomous broker agents for retail electricity trading that
can operate in a wide range of Smart Electricity Markets, and that are
capable of deriving long-term, profit-maximizing policies. Our brokers
use Reinforcement Learning with function approximation, they can
accommodate arbitrary economic signals from their environments, and
they learn efficiently over the large state spaces resulting from
these signals. Our design is the first that can accommodate an offline
training phase so as to automatically optimize the broker for
particular market conditions. We demonstrate the performance of our
design in a series of experiments using real-world energy market data,
and find that it outperforms previous approaches by a significant
margin.}

\timeTitlePeople{11:45--12:10}
{Bayesian Nonparametric Inverse Reinforcement Learning}
{Bernard Michini and Jonathan P.\ How}

\abst{Inverse reinforcement learning (IRL) is the task of learning the reward
function of a Markov Decision Process (MDP) given the transition
function and a set of observed demonstrations in the form of
state-action pairs. Current IRL algorithms attempt to find a single
reward function which explains the entire observation set. In
practice, this leads to a computationally-costly search over a large
(typically infinite) space of complex reward functions. This paper
proposes the notion that if the observations can be partitioned into
smaller groups, a class of much simpler reward functions can be used
to explain each group. The proposed method uses a Bayesian
nonparametric mixture model to automatically partition the data and
find a set of simple reward functions corresponding to each
partition. The simple rewards are interpreted intuitively as subgoals,
which can be used to predict actions or analyze which states are
important to the demonstrator. Experimental results are given for
simple examples showing comparable performance to other IRL algorithms
in nominal situations. Moreover, the proposed method handles cyclic
tasks (where the agent begins and ends in the same state) that would
break existing algorithms without modification. Finally, the new
algorithm has a fundamentally different structure than previous
methods, making it more computationally efficient in a real-world
learning scenario where the state space is large but the demonstration
set is small.}

\sessionend


