\documentclass[11pt]{beamer}
%\documentclass[handout,dvipsnames,table]{beamer}
\mode<presentation>
{
\usetheme{Rochester}
\usecolortheme{crane}
%\usetheme{Trondheim}
\usefonttheme[onlymath]{serif}
%\usetheme{Marburg}
%  \setbeamercovered{transparent}
\setbeamertemplate{navigation symbols}{}
}

\usepackage{graphics}
\usepackage{algorithmicx}
\usepackage{fancybox}
\usepackage{multirow}
\usepackage{rotating}
\usepackage{amssymb}
\usepackage{algpseudocode}
\usepackage{float}
\usepackage{fancyhdr}
\usepackage[retainorgcmds]{IEEEtrantools}
 \DeclareMathOperator*{\argmax}{arg\,max}
 \DeclareMathOperator*{\argmin}{arg\,min}


%\usepackage{concmath}
\usepackage{graphicx}
%\usepackage{subfig}
%\usepackage{epsfig}
\usepackage{url}
%\usepackage{extarrows}
%\usepackage{pstricks}
%\usepackage{pspicture}
\def\bx{{\mathbf x}}
\newcommand{\dmu}{\hat{\mu}}
\newcommand{\dsigma}{\hat{\sigma}}
\def\rhobar{{\bar \rho}}
\def\bX{{\mathbf X}}
\def\bone{{\mathbf 1}}
\def\bw{{\mathbf w}}
\def\ba{{\mathbf a}}
\def\bb{{\mathbf b}}
\def\bz{{\mathbf z}}
\def\bm{{\mathbf m}}
\def\bC{{\mathbf C}}
\def\bD{{\mathbf D}}
\def\bA{{\mathbf A}}
\def\bL{{\mathbf L}}
\def\bS{{\mathbf S}}
\def\bK{{\mathbf K}}
\def\bG{{\mathbf G}}
\def\bH{{\mathbf H}}
\def\bM{{\mathbf M}}
\def\bA{{\mathbf A}}
\def\bI{{\mathbf I}}
\def\bT{{\mathbf T}}
\def\bc{{\mathbf c}}
\def\bgamma{{\mathbf \gamma}}
\def\blambda{{\mathbf \lambda}}
\def\bg{{\mathbf g}}
\def\bh{{\mathbf h}}
\def\bv{{\mathbf v}}
\def\be{{\mathbf e}}
\def\H{{\mathcal H}}
\def\bs{{\mathbf s}}
\def\bd{{\mathbf d}}
\def\by{{\mathbf y}}
\def\bQ{{\mathbf Q}}
\def\bY{{\mathbf Y}}
\def\br{{\mathbf r}}
\def\bu{{\mathbf u}}
\def\bmu{{\mathbf \mu}}
\def\balpha{{\mathbf \alpha}}
\def\btheta{{\mathbf \theta}}
\def\bSigma{{\mathbf \Sigma}}
\def\RR{{\mathbb R}}
\def\Ex{{\mathbb E}}
\def\R{{\mathcal R}}
\def\E{{\mathcal E}}
\def\X{{\mathcal X}}
\def\D{{\mathcal D}}
\def\V{{\mathcal V}}
\def\W{{\mathcal W}}
\def\sign{\textup{sign}}

\title{Efficient Feature/Rule Ensemble Learning using Hierarchical Kernels}

%\subtitle{Ph.D. Colloquium}

\author[Ganesh]{Ganesh Ramakrishnan\\\vspace{0.2in}\small Collaboration: J. Saketha Nath, Pratik J.,\\ Naveen Nair and Amrita Saha.}

\institute[IIT-B]{Indian Institute of Technology --- Bombay}
 
\date[06-Jul-11]{\vskip 0.5in\small}

%\AtBeginSection[]
%{
%  \begin{frame}<beamer>
%    \frametitle{Outline}
%    \tableofcontents[currentsection]
%  \end{frame}
%}

% If you wish to uncover everything in a step-wise fashion, uncomment
% the following command: 

%\beamerdefaultoverlayspecification{<+->}

\begin{document}

\begin{frame}
  \titlepage
\end{frame}

%\begin{frame}
%  \frametitle{Outline}
%  \tableofcontents
  % You might wish to add the option [pausesections]
%\end{frame}

%FRAME
%\begin{frame}
%\frametitle{}
%\end{frame}

%FRAME 1
\begin{frame}
\frametitle{Rule Ensembles --- Overview}
\begin{itemize}
\item Ensembles with base learners as \textit{simple} rules~\tiny(Cohen\&Singer, 99)
\pause
\end{itemize}
\begin{center}\alt<2>{\includegraphics[scale=0.3]{Fig1a.pdf}}{\alt<3>{\includegraphics[scale=0.3]{Fig1b.pdf}}{\includegraphics[scale=0.3]{Fig1c.pdf}}}\end{center}
\pause
\pause
\end{frame}

%FRAME 2
\begin{frame}
\frametitle{Rule Ensembles --- Key Features}
\begin{itemize}
\item Highly \alert{interpretable} hypothesis
\begin{itemize}
\item Small set of rules i.e., \alert{low $q$}
\item \textit{Simple} rules e.g., \alert{short conjunctive propositions}
\end{itemize}
\pause
\item Better \alert{generalization} than conventional rule learners
\end{itemize}
\end{frame}

%FRAME 3
\begin{frame}
\frametitle{Rule Ensemble Learning --- Formal Definition}
\begin{block}{Input:}
\begin{itemize}
\item \small Training Set: $\scriptstyle\mathcal{D}=\left\{(\bx^1,y^1),\ldots,(\bx^m,y^m)\right\}$, $\scriptstyle\bx^i\in\mathbb{R}^n$ and $\scriptstyle y^i\in\{-1,1\}$
\item Basic propositions regarding input features (say, $p$ in number)
\begin{description}
\item[Nominal] e.g., $x_i=a$ and $x_i\ne a$
\item[Numeric] e.g., $x_j\ge b$ and $x_j\le b$
\end{description}
\end{itemize}
\end{block}
\pause
\begin{alertblock}{Goal:}
\begin{itemize}
\item Construct conjunctive rules from basic propositions
\begin{itemize}
\item \alert{Few} in number
\item \alert{Short} conjunctions
\end{itemize}
\item Compute corresponding \alert{weights} ($\bw,b$)
\end{itemize}
\end{alertblock}
\end{frame}

%FRAME 4
\begin{frame}
\frametitle{Rule Ensemble Learning --- Challenging task}
Extremely \alert{large}, atleast $O(2^n)$, rule space!
\begin{center}\includegraphics[scale=0.3]{Fig2.pdf}\end{center}
\end{frame}

%FRAME 5
\begin{frame}
\frametitle{Rule Ensembles --- Existing Methods}
\begin{description}
\item[SLIPPER\tiny(Cohen\&Singer, 99)\normalsize:] AdaBoost + RIPPER --- \alt<1>{greedy}{\alert{greedy}}
\item[RuleFit\tiny(Friedman\&Popescu, 08)\normalsize:] ISLE + decision tree --- \alt<1>{greedy}{\alert{greedy}}
\item[ELCS\tiny(Gao et.al., 07)\normalsize:] Genetic Alg. + post-pruning --- \alt<1>{sub-optimal}{\alert{sub-optimal}}
\item[ENDER\tiny(Dembczynski et.al., 10)\normalsize:] Minimization of empirical risk --- \alt<1>{greedy}{\alert{greedy}}
\end{description}
\pause
\end{frame}

%FRAME 6
\begin{frame}
\frametitle{Proposed Methodology --- Overview}
%\begin{itemize}
\textit{Optimal} search for rules over \alert{all} conjunctions
\begin{itemize}
\item \alert{Regularized} loss minimization
\item \alert{Convex} formulation
\item Discovers \alert{compact} ruleset (small set with short rules)
\end{itemize}
%\end{itemize}
\pause
\begin{block}{Technical Contribution:}
%\begin{itemize}
Efficient mirror-descent based active set method
\begin{itemize}
\item Complexity: \alert{polynomial} in active set size ($\ll 2^p$)
\end{itemize}
%\end{itemize}
\end{block}
\pause
\begin{alertblock}{Key Structure Exploited:}
Sub-lattices with \alert{long rules are discouraged}.
\end{alertblock}
\end{frame}

%FRAME 7
\begin{frame}
\frametitle{A Primitive Formulation}
\begin{itemize}
\item Decision function\footnote{$\V$ is index set for conjunctive lattice}: $\textup{sign}\left(\sum_{v\in\V}w_vR_v(\bx)-b\right)$
\item $l_1$ regularize to force many $w_v$ to zero
\end{itemize}
\pause
\begin{block}{$l_1$ regularized formulation:}
\begin{equation*}
\min_{\bw,b} \frac{1}{2}\left(\sum_{v\in\V}|w_v|\right)^2 + C\sum_{i=1}^mL\left(y^i,\sum_{v\in\V}w_vR_v(\bx^i)-b\right)
\end{equation*}
\end{block}
\end{frame}

%FRAME 8
\begin{frame}
\frametitle{A Primitive Formulation}
\begin{center}\alt<1>{\includegraphics[scale=0.23]{Fig3a.pdf}}{\alt<2>{\includegraphics[scale=0.23]{Fig3b.pdf}}{\includegraphics[scale=0.23]{Fig3c.pdf}}}\end{center}
\pause
\pause
\pause
\begin{alertblock}{Short-comings:}
\begin{itemize}
\item \alert{long rules} may be selected
\item Computationally \alert{difficult} problem
\end{itemize}
\end{alertblock}
\end{frame}

%FRAME 9
\begin{frame}
\frametitle{An Improved Formulation}
\begin{alertblock}{Key Idea:}
Block $l_1$ regularizer discourages long rules: $\left(\sum_{v\in\V}\|\bw_{D(v)}\|_2\right)^2$
\end{alertblock}
\only<1>{\begin{center}\includegraphics[scale=0.29]{blank.pdf}\end{center}}
\pause
\only<2>{\begin{center}\includegraphics[scale=0.29]{Fig4a.pdf}\end{center}}
\only<3>{\begin{center}\includegraphics[scale=0.29]{Fig4b.pdf}\end{center}}
\only<4>{\begin{center}\includegraphics[scale=0.29]{Fig4c.pdf}\end{center}}
\only<5>{\begin{center}\includegraphics[scale=0.29]{Fig4d.pdf}\end{center}}
\only<6>{\begin{center}\includegraphics[scale=0.29]{Fig4e.pdf}\end{center}}
\only<7>{\begin{center}\includegraphics[scale=0.29]{Fig4f.pdf}\end{center}}
\only<8>{\begin{center}\includegraphics[scale=0.29]{Fig4g.pdf}\end{center}}
\only<9>{\begin{center}\includegraphics[scale=0.29]{Fig4h.pdf}\end{center}}
\pause
\pause
\pause
\pause
\pause
\pause
\pause
\end{frame}

%FRAME 10
\begin{frame}
\frametitle{Hierarchical Kernel Learning (HKL)\tiny(Bach, 08)}
\begin{itemize}
\item Kernels arranged on DAG (lattice) are given
\item Optimal combination of kernels (Multiple Kernel Learning)
\end{itemize}
\only<1>{\begin{center}\includegraphics[scale=0.3]{blank.pdf}\end{center}}
\pause
\only<2>{\begin{center}\includegraphics[scale=0.3]{Fig5a.pdf}\end{center}}
\only<3>{\begin{center}\includegraphics[scale=0.3]{Fig5b.pdf}\end{center}}
\only<4>{\begin{center}\includegraphics[scale=0.3]{Fig5c.pdf}\end{center}}
\only<5>{\begin{center}\includegraphics[scale=0.3]{Fig5d.pdf}\end{center}}
\only<6>{\begin{center}\includegraphics[scale=0.3]{Fig5e.pdf}\end{center}}
\only<7>{\begin{center}\includegraphics[scale=0.3]{Fig5f.pdf}\end{center}}
\pause
\pause
\pause
\pause
\pause
\end{frame}

%FRAME 11
\begin{frame}
\frametitle{HKL --- Key Result}
\begin{block}{Active Set Algorithm:}
\begin{itemize}
\item Complexity: \alert{Polynomial} in number of selected kernels
\item Condition: kernels are summable in \textit{linear} time over a sub-lattice
\end{itemize}
\end{block}
\pause
\begin{alertblock}{Our case:}
\begin{itemize}
\item Kernels indeed easily summable 
\begin{itemize}
\item $R_v$ is nothing but product of few base proposition evaluations
\item Sum of exponential no. terms = Product of linear no. terms
\item E.g., $1+R_1+R_2+R_1R_2=(1+R_1)(1+R_2)$
\item Our problem can be solved in reasonable time
\end{itemize}
\end{itemize}
\end{alertblock}
\end{frame}

%FRAME 12
\begin{frame}
\frametitle{Performance Comparison}
\begin{center}
\tiny{
\begin{tabular}{lcccc}
\hline
{\textbf{Dataset}} & {\textbf{RuleFit}} & {\textbf{SLI}} &{\textbf{ENDER}} & {\textbf{HKL}} \\
\hline
\\
\texttt{TIC-TAC-TOE} & $0.652\pm0.068$ & $0.747\pm0.026$ & $0.633\pm0.011$ & $\mathbf{0.889}\pm0.029$\\
\uncover<2->{& (\uncover<3->{\textbf{40},} 2.51) & (\uncover<3->{59,} 2.35) & (\uncover<3->{111,} 2.46) & (\uncover<3->{\alt<1-3>{129}{\alert{129}},} \textbf{1.85})}\\\\
\texttt{BALANCE} & $0.835\pm0.034$ & $0.856\pm0.027$ & $0.827\pm0.013$ & $\mathbf{0.893}\pm0.027$ \\
\uncover<2->{&(\uncover<3->{\textbf{17},} 2.18)&(\uncover<3->{25,} 1.88)&(\uncover<3->{64,} 1.99)&(\uncover<3->{65,} \textbf{1.65})}\\\\
\texttt{HABERMAN} & $0.512\pm0.072$ & $0.565\pm0.066$ & $0.424\pm0.000$ & $\mathbf{0.594}\pm0.056$ \\
\uncover<2->{&(\uncover<3->{\textbf{6},} 1.68)&(\uncover<3->{8,} \textbf{1.14})&(\uncover<3->{18,} 1.87)&(\uncover<3->{\alt<1-3>{32}{\alert{32}},} 1.27)}\\\\
\texttt{CAR} & $0.913\pm0.033$ & $0.895\pm0.024$ & $0.755\pm0.028$ & $\textbf{0.943}\pm0.024$ \\
\uncover<2->{&(\uncover<3->{\textbf{34},} 3.12)&(\uncover<3->{141,} 2.27)&(\uncover<3->{80,} 1.85)&(\uncover<3->{87,} \textbf{1.78})}\\\\
\texttt{BLOOD TRANS.} & $0.549\pm0.092$ & $0.559\pm0.100$ & $0.489\pm0.054$ & $\mathbf{0.594}\pm0.009$ \\
\uncover<2->{&(\uncover<3->{18,} 1.99)&(\uncover<3->{\textbf{6},} \textbf{1.07})&(\uncover<3->{58,} 1.5)&(\uncover<3->{\alt<1-3>{242}{\alert{242}},} 1.64)}\\\\
\texttt{CMC} & $0.632\pm0.013$ & $0.601\pm0.041$ & $0.644\pm0.026$ & $\mathbf{0.656}\pm0.014$ \\
\uncover<2->{&(\uncover<3->{39,} 2.41)&(\uncover<3->{\textbf{13},} 2.13)&(\uncover<3->{74,} 2.65)&(\uncover<3->{\alt<1-3>{127}{\alert{217}},} \textbf{1.96})}\\\\
\hline
\end{tabular}
}
\end{center}
\pause
\pause
\pause
\end{frame}

%FRAME 13
\begin{frame}
\frametitle{HKL --- Introspection}
\begin{center}\includegraphics[scale=0.25]{Fig4f.pdf}\end{center}
\pause
\begin{itemize}
\item Node selected \alert{only} if all its ancesters are!
\pause
\item $l_1$ promotes sparsity.
\item $l_2$ promotes non-sparsity. \uncover<3->{\alert{Employ sparsity inducing norm!}}
\end{itemize}
\pause
\end{frame}

%FRAME 14
\begin{frame}
\frametitle{Proposed Formulation}
\begin{alertblock}{Generalized HKL}
\begin{equation*}
\min_{\bw,b} \frac{1}{2}\left(\sum_{v\in\V}d_v\|\bw_{D(v)}\|_\rho\right)^2 + C\sum_{i=1}^mL\left(y^i,\sum_{v\in\V}w_vR_v(\bx^i)-b\right)
\end{equation*}
where $1<\rho\le2$.
\end{alertblock}
\end{frame}

%FRAME 15
\begin{frame}
\frametitle{Active Set Method}
\only<1>{\ \ \ \ \ \ \uncover<2>{p}}
\only<1>{\begin{center}\includegraphics[scale=0.34]{Fig6a.pdf}\end{center}}
\only<2>{Initialize active set with root node ($\W=\{0\}$).\uncover<1>{p}}
\only<2>{\begin{center}\includegraphics[scale=0.34]{Fig6b.pdf}\end{center}}
\only<3>{Solve small problem}
\only<3>{\begin{center}\includegraphics[scale=0.34]{Fig6b.pdf}\end{center}}
\only<4>{Solve small problem}
\only<4>{\begin{center}\includegraphics[scale=0.34]{Fig6c.pdf}\end{center}}
\only<5>{Identify potential active set entries (i.e., $sources(\W^c)$)}
\only<5>{\begin{center}\includegraphics[scale=0.34]{Fig6d.pdf}\end{center}}
\only<6>{Among them, optimality condition violators}
\only<6>{\begin{center}\includegraphics[scale=0.34]{Fig6e.pdf}\end{center}}
\only<7>{Among them, optimality condition violators}
\only<7>{\begin{center}\includegraphics[scale=0.34]{Fig6f.pdf}\end{center}}
\only<8-10>{\alt<10>{Solve small problem}{Append them to active set ($\W=\{0,1,3,4\}$). \uncover<9>{\tiny(repeat until suff. cond. satisfied)}}}
\only<8-10>{\begin{center}\includegraphics[scale=0.34]{Fig6g.pdf}\end{center}}
\only<11>{Identify potential active set entries (i.e., $sources(\W^c)$)}
\only<11>{\begin{center}\includegraphics[scale=0.34]{Fig6h.pdf}\end{center}}
\only<12>{Among them, optimality condition violators}
\only<12>{\begin{center}\includegraphics[scale=0.34]{Fig6i.pdf}\end{center}}
\only<13>{Append them to active set ($\W=\{0,1,3,4,6,7,10\}$)}
\only<13>{\begin{center}\includegraphics[scale=0.34]{Fig6j.pdf}\end{center}}
\only<14-15>{Final active set: $\W=\{0,1,3,4,6,7,10\}$ \uncover<15>{\tiny(Complexity: Polynomial in active set size)}}
\only<14-15>{\begin{center}\includegraphics[scale=0.34]{Fig6k.pdf}\end{center}}
\only<16>{Solution with HKL}
\only<16>{\begin{center}\includegraphics[scale=0.34]{Fig6l.pdf}\end{center}}
\only<17>{\alert{Key difference from HKL: Node selected without its ancestor!}}
\only<17>{\begin{center}\includegraphics[scale=0.34]{Fig6m.pdf}\end{center}}
\pause
\pause
\pause
\pause
\pause
\pause
\pause
\pause
\pause
\pause
\pause
\pause
\pause
\end{frame}

%FRAME 16
\begin{frame}
\frametitle{Key Technical Result}
\begin{theorem}\label{thm:dual}
A highly specialized partial dual of generalized HKL is:
\begin{eqnarray*}
\min_{\eta\in\R^{|\V|}}&g(\eta)\\
\textup{s.t.}& \eta\ge0,\ \sum_{v\in\V}\eta_v=1
\end{eqnarray*}
\uncover<2->{where $g(\eta)$ is the optimal objective value of the following convex problem:
\begin{equation*}\label{eqn:g}\scriptstyle
\max_{\alpha\in\R^m} \ \ \sum_{i=1}^m\alpha_i - \frac{1}{2}\left(\sum_{v\in \V}\zeta_v(\eta)\left(\alpha^\top\bK_v\alpha\right)^\rhobar\right)^{\frac{1}{\rhobar}}\ \textup{s.t.}\ 0\le\alpha_i\le C,\ \sum_{i=1}^m\alpha_iy^i = 0.
\end{equation*}
where $\zeta_v(\eta)=\left(\sum_{u\in A(v)}d_u^\rho\eta_u^{1-\rho}\right)^{\frac{1}{1-\rho}}$, $\rhobar=\frac{\rho}{2(\rho-1)}$ and $\bK_v$ is matrix with entries: $y^iy^jk_v(\bx^i,\bx^j)$.}
\end{theorem}
\pause
\end{frame}

%FRAME 17
\begin{frame}
\frametitle{Solving small problem}
\begin{itemize}
\item Dual is min. of convex, Lipschitz conts., sub-differential objective over a simplex.
\item Mirror-descent  --- \alert{highly scalable} alg. for such problems.
\item Sub-gradient --- solve $l_p$-MKL~\tiny(Vishwanathan et.al., 10).
\end{itemize}
\end{frame}

%FRAME 18
\begin{frame}
\frametitle{Key Technical Result}
\begin{theorem}\label{thm:necsuff}
Suppose the active set $\W$ is such that $\W=A(\W)$. Let the reduced solution with this $\W$ be $(\bw_\W,b_\W)$ and the corresponding dual variables be $(\eta_\W,\alpha_\W)$. Then the reduced solution is a solution to the full problem with a duality gap less than $\epsilon$ if:
\begin{equation*}\label{eqn:suff}
\scriptstyle\max_{t\in sources(\W^c)} \left(\sum_{v\in D(t)}\left(\frac{\alpha_\W^\top\bK_v\alpha_\W}{\left(\sum_{u\in A(v)\cap D(t)}d_u\right)^2}\right)^\rhobar\right)^\frac{1}{\rhobar} \le \left(\Omega(\bw_\W)\right)^2 + 2(\epsilon-\epsilon_{\W})
\end{equation*}
where $\epsilon_{\W}$ is a duality gap term associated with the computation of the reduced solution.
\end{theorem}
\end{frame}

%FRAME 19
\begin{frame}
\frametitle{Complexity: Polynomial in size of $\W$?}
\begin{alertblock}{\uncover<6->{Final} Sufficiency Condition:}
\begin{equation*}
\scriptstyle\max_{t\in sources(\W^c)} \left(\sum_{v\in D(t)}\left(\frac{\alpha_\W^\top\bK_v\alpha_\W}{\left(\sum_{u\in A(v)\cap D(t)}d_u\right)^2}\right)^{\alt<6->{\ }{\rhobar}}\right)^{\alt<6>{\ }{\frac{1}{\rhobar}}} \le \left(\Omega(\bw_\W)\right)^2 + 2(\epsilon-\epsilon_{\W})
\end{equation*}
\end{alertblock}
\pause
\begin{itemize}
\item $\rho\rightarrow1$ ($\rhobar\rightarrow\infty$), suff. cond. \alert{tight}
\pause
\item $\rho=2$ ($\rhobar=1$), suff. cond. loose; computationally \alert{feasible}
\pause
\item How much ground lost by replacing $l_\infty$ with $l_1$ ?
\pause
\begin{itemize}
\item \alert{Not much}: As kernels near bottom are extremely sparse!
\end{itemize}
\end{itemize}
\pause
\end{frame}

%FRAME 20
\begin{frame}
\frametitle{Performance Comparison}
\begin{center}
\tiny{
\begin{tabular}{lccccc}
\hline
{\textbf{Dataset}} & {\textbf{RuleFit}} & {\textbf{SLI}} &{\textbf{ENDER}} & {\textbf{HKL}} &{\textbf{HKL$_{\rho=1.1}$}}\\
\hline
\\
\texttt{TIC-TAC-TOE} & $0.652\pm0.068$ & $0.747\pm0.026$ & $0.633\pm0.011$ & ${0.889}\pm0.029$ & $\mathbf{0.935}\pm0.043$\\
& ({\textbf{40},} 2.51) & ({59,} 2.35) & ({111,} 2.46) & ({129}, {1.85}) & (79, \textbf{1.77})\\\\
\texttt{BLOOD TRANS.} & $0.549\pm0.092$ & $0.559\pm0.100$ & $0.489\pm0.054$ & $\mathbf{0.594}\pm0.009$ & $0.593\pm0.011$ \\
&({18,} 1.99)&({\textbf{6},} \textbf{1.07})&({58,} 1.5)&({242}, 1.64)&(7,1.40)\\\\
\texttt{BALANCE} & $0.835\pm0.034$ & $0.856\pm0.027$ & $0.827\pm0.013$ & $0.893\pm0.027$ & $\mathbf{0.899}\pm0.023$\\
&({\textbf{17},} 2.18)&({25,} 1.88)&({64,} 1.99)&({65,} {1.65})&(28,\textbf{1.23})\\\\
\texttt{HABERMAN} & $0.512\pm0.072$ & $0.565\pm0.066$ & $0.424\pm0.000$ & $\mathbf{0.594}\pm0.056$ & $\mathbf{0.594}\pm0.056$\\
&({\textbf{6},} 1.68)&({8,} \textbf{1.14})&({18,} 1.87)&({32}, 1.27)&(12,1.20)\\\\
\texttt{CAR} & $0.913\pm0.033$ & $0.895\pm0.024$ & $0.755\pm0.028$ & $\textbf{0.943}\pm0.024$ & $0.935\pm0.036$ \\
&({\textbf{34},} 3.12)&({141,} 2.27)&({80,} 1.85)&({87,} {1.78})&(50,\textbf{1.68})\\\\
\texttt{CMC} & $0.632\pm0.013$ & $0.601\pm0.041$ & $0.644\pm0.026$ & $0.656\pm0.014$ & $\mathbf{0.659}\pm0.008$\\
&({39,} 2.41)&({\textbf{13},} 2.13)&({74,} 2.65)&({127}, {1.96})&(43,\textbf{1.70})\\\\
\hline
\end{tabular}
}
\end{center}
\end{frame}

\begin{frame}
\frametitle{Summary}
\begin{itemize}
\item Applied HKL to rule ensemble learning
\begin{itemize}
\item Improved generalization
\item \alert{Bridged gap} between kernel and rule learning communities
\end{itemize}
\pause
\item Generalized HKL
\begin{itemize}
\item Generalizes well while learning compact ruleset
\item Sometimes \alert{25\%} improvement in generalization
\item Applicable elsewhere
\end{itemize}
\pause
\item Efficient mirror-descent based active set method
\begin{itemize}
\item Complexity: polynomial in active set size ($\ll O(2^n)$
\item Searched rule space size \alert{$\sim2^{50}$ in $\sim10$ min.}
\end{itemize}
\end{itemize}
\end{frame}

\section{REL-HKL on structured output spaces}

\begin{frame}{}
 \scriptsize
\begin{block}{}
\large
 \begin{center}\textbf{Rule Ensemble Learning using Hierarchical Kernels framework for Structured Output Spaces.}\end{center}
\end{block}	
\end{frame}

\begin{frame}{REL-HKL on structured output spaces}
 \scriptsize
 \begin{itemize}
  \item Output is a structure (Implicitly, we have expanded scope to multi-class problem)
  \item SVM maximizes the margin of true output with all possible outputs in output space.
  \item HMM is a structured output problem (which we explore in this work).
 \end{itemize}
\end{frame}


\begin{frame}{Example: Activity Recognition Lattice}
  \begin{figure}[H]
    \centering
    \includegraphics[width=85mm]{activity_lattice.png}
    \caption{Activity Recognition Lattice}
   \end{figure}
\end{frame}


\subsection{SVM for structured output spaces}
\begin{frame}{ SVM for structured output spaces}
\scriptsize 
\textbf{Notations}
 \begin{itemize}
  \item $\mathcal{X}$: input sequence space,\qquad $\mathcal{Y}$: output sequence space.
  \item $X_i \in \mathcal{X}$: an instance of input sequence.
  \item $Y_i \in \mathcal{Y}$: an instance of output sequence\footnote{\scriptsize Subscript $i$ is used to denote $i^{th}$ example sequence and should not be confused with the $i^{th}$ element of a vector.}.
  \item $\mathbf{x}_i^p$: joint state of feature values at $p^{th}$ position of the $i^{th}$ example.
  \item $y_i^p$: output at $p^{th}$ position of the $i^{th}$ example.
\item $\boldsymbol{\psi}$: feature vector.
\item $\mathbf{f}$: feature weights vector.
 \end{itemize}
\end{frame}

\begin{frame}{SVM for structured output spaces \footnote{\scriptsize [Tsochantaridis et. al.,2004,2006]}}
\scriptsize
 \begin{itemize}
  \item Generalize multiclass support vector machine learning.
  \item Features constructed from input and output variables.
  \item In case of HMM, features constructed from emission and transition distribution.
 \end{itemize}
Define discriminant function $F:\mathcal{X} \times \mathcal{Y} \rightarrow \mathbb{R}$, such that,  $F(X,Y;\mathbf{f}) = \langle \mathbf{f},\boldsymbol{\psi}(X,Y) \rangle$\qquad\footnote{\scriptsize $F(X,Y;\mathbf{f})$ represents a score which is a scalar value based on the features $\boldsymbol{\psi}$ involving input sequence $X$ and output sequence $Y$ values and parameterised by a parameter vector $\mathbf{f}$.}\\ and prediction is given by
\begin{block}{}
\centering
$\hat{Y}=\mathcal{F}(X;\mathbf{f})=\argmax\limits_{Y\in\mathcal{Y}} F(X,Y;\mathbf{f})$
\end{block}
\textbf{Loss function for HMM}
\begin{itemize}
 \item  Predicted sequences that deviate more from the actual should be penalized more.
  \item Loss function, $\Delta:\mathcal{Y}\times \mathcal{Y} \rightarrow \mathbb{R}$. $\Delta(Y,\hat{Y})$ is the loss value when the true output is $Y$ and the prediction is $\hat{Y}$.
\end{itemize}
\end{frame}


\begin{frame}{ SVM for structured output spaces}
\scriptsize
\begin{block}{SVM formulation for structured output spaces (HMM)}
\noindent $SVM_0$:
\begin{IEEEeqnarray*}{lCl}
 \min_{\mathbf{f},\boldsymbol{\xi}}\; \frac{1}{2}\parallel \mathbf{f}\parallel ^2 \; + \; \frac{C}{m}\sum\limits_{i=1}^m\xi_i,\quad \quad s.t. \;\;\forall i:\; \xi_i \geq 0 \\
\forall i,\;\forall\; Y \in \mathcal{Y}\setminus Y_i :\; \langle \mathbf{f}, \boldsymbol{\psi}_i^{\delta}(Y) \rangle \geq 1 - \frac{\xi_i}{\Delta(Y_i,Y)}.
\label{svm0}
\end{IEEEeqnarray*}
\end{block}
\begin{itemize}
 \item $C$ is the regularization parameter.
  \item $\xi$ s are the slack variables introduced to allow errors in the training set in a soft margin SVM.
  \item $\langle \mathbf{f}, \boldsymbol{\psi}_i^{\delta}(Y) \rangle = \langle \mathbf{f}, \boldsymbol{\psi}(X_i,Y_i) \rangle - \langle \mathbf{f}, \boldsymbol{\psi}(X_i,Y) \rangle$.
\end{itemize}
When the sequence length is large, the number of constraints in $SVM_0$ can be extremely large. A cutting plane method can be used to find a polynomially sized subset of constraints that ensures a solution very near to the optimum [Tsochantarids et. al.].
\end{frame}


\begin{frame}{ SVM for structured output spaces: Remarks}
\scriptsize
 \begin{block}{To learn optimum structure and parameters of HMM (structSVM)}
\begin{enumerate}
 \item  Modify StructSVM to include features that can be ordered in the form of a lattice.
  \item Include the $\rho$-norm regularizer (as `in RELHKL) for emission features and 2-norm for transition features.
  \item Derive a dual for the new formulation that can be computed efficiently.
  \item Derive a sufficiency condition to stop the active set algorithm.
\end{enumerate}
\end{block}
\end{frame}

\subsection{REL-HKL on structured output spaces for learning optimum HMM model}
\begin{frame}{ REL-HKL on structured output spaces for learning optimum HMM model}
\scriptsize 
\textbf{Notations}
 \begin{itemize}
\item $\boldsymbol{\psi}$: feature vector containing emission and transition features.
  \item $\boldsymbol{\psi_E}$: part of $\boldsymbol{\psi}$ corresponding to emission features.
  \item $\boldsymbol{\psi_T}$: part of $\boldsymbol{\psi}$ corresponding to transition features.\footnote{\scriptsize For convenience we assume $\boldsymbol{\psi_E}$ and $\boldsymbol{\psi_T}$ as two vectors of dimension same as $\boldsymbol{\psi}$, but with non zero elements to features only on their context.}
  \item $\mathbf{f}$: feature weights vector.
  \item $\mathbf{f_E}$: feature weights vector corresponding to emission.
  \item $\mathbf{f_T}$: feature weights vector corresponding to transition.
  \item $\mathcal{V}$: indices of the elements of $\boldsymbol{\psi}$.
  \item $\mathcal{V}_\mathbf{E}$: indices corresponding to emission elements.
  \item $\mathcal{V}_\mathbf{T}$: indices corresponding to transition elements.
 \end{itemize}
\end{frame}


\begin{frame}{ REL-HKL on structured output spaces for learning optimum HMM model}
\scriptsize
\begin{itemize}
 \item Regularizer used in RELHKL is for the features obeying lattice structure.
  \item Also that We are not interested in learning sparse transition features.
  \item Therefore, We separate the regularizer into two, viz, emission and transition.
\end{itemize}

SVM formulation after separating the regularizer.
 \begin{block}{  $SVM_1$:}
\begin{IEEEeqnarray*}{lCl}
 \min\limits_{\mathbf{f},\boldsymbol{\xi}}\frac{1}{2}\Omega_E(\mathbf{f_E})^2 \; + \; \frac{1}{2}\Omega_T(\mathbf{f_T})^2 \; +\;  \frac{C}{m}\sum\limits_{i=1}^m\xi_i,\\
\forall i,\forall Y \in \mathcal{Y}\setminus Y_i :\; \langle \mathbf{f}, \boldsymbol{\psi}_i^{\delta}(Y) \rangle \geq 1 - \frac{\xi_i}{\Delta(Y_i,Y)}\\
\forall i:\; \xi_i \geq 0
\label{svm1}
\end{IEEEeqnarray*}
 \end{block}
\begin{itemize}
 \item $\Omega_E(\mathbf{f_E}) = \sum\limits_{v\in \mathcal{V}_\mathbf{E}} d_v \parallel \mathbf{f}_{\mathbf{E}D(v)}\parallel _\rho ,\; \; \rho \in (1,2]$
  \item $\Omega_T(\mathbf{f_T}) = \big(\sum\limits_i f_{Ti}^2\big)^{\frac{1}{2}}$
  \item $\langle \mathbf{f}, \boldsymbol{\psi}_i^{\delta}(Y) \rangle = \langle \mathbf{f}, \boldsymbol{\psi}(X_i,Y_i) \rangle - \langle \mathbf{f}, \boldsymbol{\psi}(X_i,Y) \rangle$
\end{itemize}
\end{frame}

\begin{frame}{ REL-HKL on structured output spaces for learning optimum HMM model}
\scriptsize
\begin{itemize}
 \item At optimality, most of the emission feature weights are expected to be zero [Ganesh et. al.,2011].
  \item Therefore an active set algorithm can be employed to solve efficiently.
  \item In each iteration, a subset of featues ($\mathcal{W}$) is considered to be active.
\end{itemize}
  \begin{figure}[h]
    \centering
    \includegraphics[width=3in]{sparse}
  \end{figure}
\end{frame}

\begin{frame}{ REL-HKL on structured output spaces for learning optimum HMM model}
 \scriptsize
SVM formulation considering only the featues in $\mathcal{W}$ (reduced problem),
\begin{block}{$SVM_2$}
 \begin{IEEEeqnarray*}{lCl}
 \min\limits_{\mathbf{f},\boldsymbol{\xi}}\frac{1}{2}\left(\sum\limits_{v\in \mathcal{W}} d_v \parallel \mathbf{f}_{\mathbf{E}D(v)\bigcap\mathcal{W}}\parallel _\rho \right)^2 \; + \; \frac{1}{2} \parallel \mathbf{f_T}\parallel _2^2 \; +\;  \frac{C}{m}\sum\limits_{i=1}^m\xi_i,\\\\
\forall i,\forall Y \in \mathcal{Y}\setminus Y_i :\\ -\left(\sum\limits_{v\in\mathcal{W}}\langle f_{Ev}, \psi_{Evi}^{\delta}(Y) \rangle +  \sum\limits_{v\in\mathcal{V}_\mathbf{T}}\langle f_{Tv},\psi_{Tvi}^{\delta}(Y) \rangle  +  \frac{\xi_i}{\Delta(Y_i,Y)}  -  1 \right) \leq 0\\
\forall i:\; -\xi_i \leq 0
\end{IEEEeqnarray*}
\end{block}
\end{frame}


\begin{frame}{ REL-HKL on structured output spaces for learning optimum HMM model}
\scriptsize
Applying variational characterization\footnote{\scriptsize Micchelli\&Pontil,2005,Bach,2009,Jawanpuria et.al.,2011} on $\Omega_E(\mathbf{f_E})^2$\\
 \begin{block}{Partial dual (wrt. $\mathbf{f},\boldsymbol{\xi}$) of $SVM_1$}
 $$\min\limits_{\gamma\in\Delta_{|\mathcal{V}_\mathbf{E}|,1}}\;\; \min\limits_{\lambda_{v}\in\Delta_{|D(v)|,\hat{\rho}}\forall v\in \mathcal{V}_\mathbf{E}}\; \max\limits_{\alpha \in S(\mathcal{Y},C)}\;  G(\gamma, \lambda, \alpha)$$
where 
$$G(\gamma, \lambda, \alpha) =\sum\limits_{i,Y\neq Y_i}\alpha_{iY} - \frac{1}{2}\boldsymbol{\alpha}^{\top}\left( \sum\limits_{w \in \mathcal{V}_{\mathbf{E}}} \delta_{w}(\gamma,\lambda)\boldsymbol{\kappa}_{\mathbf{E}w}  \right)\boldsymbol{\alpha} - \frac{1}{2} \boldsymbol{\alpha}^{\top} \boldsymbol{\kappa}_\mathbf{T} \boldsymbol{\alpha} $$, $S(\mathcal{Y},C) = \{\boldsymbol{\alpha}\in \mathbb{R}^m\;|\; \alpha_{i,Y} \geq 0, \; n \sum\limits_{Y \neq Y_i} \frac{\alpha_{iY}}{\Delta(Y,Y_i)}\leq C, \; \forall i,Y \}$, $\Delta_{d,r}  =  \left\{ \eta \in \mathbb{R}^d | \eta \geq 0, \sum\limits_{i=1}^d \eta_i^r = 1 \right\}$, $\delta_w(\gamma,\lambda)^{-1}=\underset{v\in A(w)}{\sum}\frac{d_v^2}{\gamma_v\lambda_{wv}}$ and $\hat{\rho} = \frac{\rho}{2-\rho}$.
\end{block}
\end{frame}


\begin{frame}{ REL-HKL on structured output spaces for learning optimum HMM model}
 \scriptsize
\begin{block}{\scriptsize Sufficiency condition for the reduced solution to have a duality gap less than $\epsilon$}
 \begin{IEEEeqnarray*}{lCl}
\underset{u\in sources(\mathcal{W}^c)}{\max}\;\sum_{i,Y\neq Y_i}\;\sum_{j,Y'\neq Y_j} \boldsymbol{\alpha}_{\mathcal{W}iY}^\top 
\sum_{p=1}^{l_i}\sum_{q=1}^{l_j} 2 \Big( \prod_{k\in u}\frac{\psi_{Ek}(\mathbf{x}_i^p)\psi_{Ek}(\mathbf{x}_j^q)}{b^2}\Big)\\\Big( \prod_{k\not\in u}\big( 1 + \frac{\psi_{Ek}(\mathbf{x}_i^p)\psi_{Ek}(\mathbf{x}_j^q)}{(1+b)^2}\big) \Big)    \boldsymbol{\alpha}_{\mathcal{W}jY'} \leq \Omega_E(\mathbf{f}_{\mathbf{E}\mathcal{W}})^2 + \Omega_T(\mathbf{f}_{\mathbf{T}\mathcal{W}})^2 +2(\epsilon - e_{\mathcal{W}})\\
\end{IEEEeqnarray*}
where $e_{\mathcal{W}}=\Omega_E(\mathbf{f}_{\mathbf{E}\mathcal{W}})^2 + \Omega_T(\mathbf{f}_{\mathbf{T}\mathcal{W}})^2 + \frac{C}{m}\sum\limits_i \xi_i + \frac{1}{2}\boldsymbol{\alpha}_\mathcal{W}^{\top}\boldsymbol{\kappa}_\mathbf{T}\boldsymbol{\alpha}_\mathcal{W}-\sum\limits_{i,Y\neq Y_i}\alpha_{\mathcal{W}iY}$.
\end{block}
\end{frame}

\begin{frame}{ REL-HKL on structured output spaces for learning optimum HMM model}
\scriptsize
\begin{block}{\scriptsize Final dual}
\begin{IEEEeqnarray*}{rCl}
\min_{\eta\in\Delta_{|\mathcal{V}|,1}} g(\eta)
\IEEEyesnumber
\label{finalDualOuter}
\end{IEEEeqnarray*}
where $g(\eta)$ is defined as,
\scriptsize 
\begin{IEEEeqnarray*}{rCl}
 \max_{\alpha\in S(\mathcal{Y},C)} \sum_{i,Y\neq Y_i}\alpha_{iY} - \frac{1}{2}\boldsymbol{\alpha}^\top \boldsymbol{\kappa}_{\mathbf{T}}\boldsymbol{\alpha} - \frac{1}{2}\Big(\sum_{w \in \mathcal{V}} \zeta_w(\eta)(\boldsymbol{\alpha}^\top \boldsymbol{\kappa}_{\mathbf{E}w}\boldsymbol{\alpha})^{\hat{\rho}}\Big)^{\frac{1}{\hat{\rho}}}\\
\IEEEyesnumber
\label{finalDualInner}
\end{IEEEeqnarray*}
and $\zeta_w(\eta)=\big(\sum\limits_{v\in A(w)}d_v^\rho \eta_v^{1-\rho}\big)^{\frac{1}{1-\rho}}$.
\end{block}
\begin{itemize}
 \item Equation (\ref{finalDualOuter}) is solved using mirror descent algorithm.
  \item For a given $\eta$, equation (\ref{finalDualInner}) is solved using a cutting plane algorithm.
\end{itemize}
For mirror descent algorithm, the $i^{th}$ subgradient is computed using,
\begin{IEEEeqnarray*}{rCl}
(\bigtriangledown g(\eta))_i = -\frac{d_i^{\rho}\eta_i^{-\rho}}{2\hat{\rho}}\Big(\underset{w\in \mathcal{V}_\mathbf{E}}{\sum}\zeta_w(\eta)(\bar{\boldsymbol{\alpha}}^\top \boldsymbol{\kappa}_{\mathbf{E}w}\bar{\boldsymbol{\alpha}})^{\hat{\rho}}\Big)^{\frac{1}{\hat{\rho}}-1}
\Big(\underset{w\in D(i)}{\sum}\zeta_w(\eta)^{\rho}(\bar{\boldsymbol{\alpha}}^\top \boldsymbol{\kappa}_{\mathbf{E}w}\bar{\boldsymbol{\alpha}})^{\hat{\rho}}\Big)
\end{IEEEeqnarray*}
\end{frame}

\begin{frame}{ REL-HKL on structured output spaces for learning optimum HMM model}
\scriptsize
\begin{block}{\scriptsize Active set algorithm}
 \textbf{Input:} Training data D, Oracle for computing kernels, Maximum tolerance $\epsilon$\\
1. Initialize $\mathcal{W}=Top\; nodes$ in the lattice as the active set\\
2. Compute $\eta,\alpha$ by solving (\ref{finalDualOuter}) using mirror descent\\
3. \textbf{while} sufficiency condiiton is not satisfied, \textbf{do}\\
4. \qquad Add sufficiency condition violating nodes to active set $\mathcal{W}$\\
5. \qquad Recompute $\eta, \alpha$ by solving (\ref{finalDualOuter})\\
6. \textbf{end while}\\
7. \textbf{Output:} active-set $W, \eta, \alpha$\\
\end{block}
Step 2 and 5 are solved as
\begin{itemize}
 \item For a fixed $\eta$, an optimum $\alpha$ is computed by solving (\ref{finalDualInner}) using cutting plane algorithm.
  \item Update $\eta$ using the gradient computed using the obtained $\alpha$.
  \item Repeat above two steps until convergence.
\end{itemize}
\end{frame}

\begin{frame}{\scriptsize Cutting plane algorithm}
\scriptsize
\textbf{Input:} kernels, C, $\epsilon_{margin}$ (allowed violation of margin)\\
1. $S_i \leftarrow \phi\;\;\;\forall i=1,...,m$\\
2. \textbf{repeat}\\
3. \qquad \textbf{for}$i = 1,...,m$ \textbf{do}\\
4. \qquad \qquad $\forall Y:\;H(Y)$ is computed using (\ref{costFunction}).\\
5. \qquad \qquad compute $\hat{Y}=\argmax\limits_{Y}\;H(Y)$.\\
6. \qquad \qquad compute $\xi_i=\max\{0,\underset{Y\in S_i}{max}\;H(Y)\}$.\\
7. \qquad \qquad \textbf{if} $H(\hat{Y}) > \xi_i + \epsilon_{margin}$, \textbf{then}\\
8. \qquad \qquad \qquad $S_i\leftarrow S_i \bigcup \{\hat{Y}\}$.\\
9. \qquad \qquad \qquad compute $\boldsymbol{\alpha}$ using $S = \bigcup_i \;S_i$ in (\ref{finalDualInner}).\\
10.\qquad \qquad \textbf{end if}\\
11.\qquad \textbf{end for}\\
12.\textbf{until} no $S_i$ has changed during the iteration.\\
\vspace{9.5pt}
where cost for boundary violation,
\begin{IEEEeqnarray*}{rCl}
H(Y)\equiv \Big[1- \langle \mathbf{f}, \boldsymbol{\psi}_i^{\delta}(Y) \rangle \Big]\Delta(Y_i,Y)
\IEEEyesnumber
\label{costFunction}
\end{IEEEeqnarray*}
\end{frame}

\begin{frame}{RELHKL on Structured Output Spaces Results}
\begin{center}
\tiny{
  \begin{tabular}[m]{l|cccccc}
  \hline
  \multirow{2}{*}{\textbf{Dataset}}\footnote{\tiny Activity recognition dataset, Kasteren et. al.} & \multicolumn{2}{c}{\textbf{Std HMM}} & \multicolumn{2}{c}{\textbf{Greedy feature induction}} &\multicolumn{2}{c}{\textbf{RELHKL on StructSVM}}\footnote{\tiny Greedy feature induction and RELHKL on StructSVM consider positive conjunctions}\\
   \cline{2-7}
  & Timeslice & class & Timeslice & class & Timeslice & class\footnote{\tiny{Timeslice accuracy is percentage of time the prediction is correct. Class accuracy is the average percentage of time a class is predicted correctly}}\\
  \hline\\
  \texttt{Raw} &  25.4 & 21.75 & 26.88 & 21.33 & 63.96& 32.01\\\\
  \texttt{Change}  & 23.64 & 25.99  & 44.39 & 31.42 & 56.74&33.85\\\\
  \texttt{Last} & 51.83 & 38.56 & 49.74 & 27.76 & 92.57&53.91\\\\
  \texttt{Change + Last} & 37.86 & 30.12 & 37.29 & 27.67 & 94.47&55.82\\\\
  \hline
  \end{tabular}
}
\end{center}
\end{frame}



\section{Hierarchical Kernel Learning for Propositional Features}
\begin{frame}{}
\begin{block}
\large
 \begin{center}\textbf{Hierarchical Kernel learning For Propositional Features}\end{center}
\end{block}
\end{frame}

\begin{frame}{Applications of Hierarchical Kernel learning For Propositional Features}
Learning rule ensembles\\
 \begin{itemize}
  \item Conjunctive propositional features \checkmark ~\cite{ganeshRELHKL}
  \item Disjunctive propositional features
 \end{itemize}
\end{frame}

\begin{frame}{Disjunctive propositional features}
   \begin{itemize}
    \item Since HKL follows a top-down approach $\rightarrow$ descendant norm is more suitable
    \item Top node in lattice is the most general, i.e. disjunction of all basic features  $\displaystyle\bigvee_{n=1}^N  \phi_n$
    \item descendant of node is a more specialized node; got by removing one of the features of its parent.
    \item Only sufficiency condition changes; everything else remains same.
   \end{itemize}
\end{frame}

\begin{frame}{Disjunctive propositional features}
   \begin{itemize}
   \item feature map $\phi(x)$ as $ (1-\overline{\phi}(x))$  ($\overline{\phi}(x)$ is boolean complement of $\phi(x)$).
   \item a disjunctive feature corresponding to $\displaystyle\bigvee_{n=1}^N  \phi_n(x_i) = (1-\displaystyle\Pi_{n=1}^N \overline{\phi_n}(x_i))$
   \item kernel corresponding to the disjunctive feature is $ (1-\displaystyle\Pi_{n=1}^N \overline{\phi_n}(x_i))(1-\displaystyle\Pi_{n=1}^N \overline{\phi_n}(x_j))$
   \end{itemize}
 \end{frame}

\begin{frame}{Hierarchical Kernel learning For Disjunctive Features}   
 \begin{itemize}
   \item sum of exponential kernels of the entire lattice: \\
    $\underset{v \in V}{\sum} K_v(x_i,x_j)  =  1 + 2^N  +\displaystyle\Pi_{n=1}^N (1+\overline{\phi}_{n}(x_i)\overline{\phi}_{n}(x_j)) -\underset{n}{\Pi} (1+\overline{\phi}_n(x_i)) -\underset{n}{\Pi} (1+\overline{\phi}_n(x_j)) $ %-\displaystyle\Pi_{n=1}^N (\overline{\phi}_n(x_i)\overline{\phi}_n(x_j)) + \displaystyle\sum_{n=1}^N \overline{\phi}_n(x_i) + \displaystyle\sum_{n=1}^N \overline{\phi}_n(x_i)$\\\\
 \end{itemize}
\end{frame}

\begin{frame}{Hierarchical Kernel learning For Disjunctive Features}   
 \begin{itemize}
  \item sufficiency condition:
   $\underset{t\in sources(W^C)}{max}\underset{i,j}{\sum} \alpha_{Wi}Q(t)_{ij}\alpha_{Wj} \leq \Omega_s(f)^2 +\epsilon$\\
   where $Q(t)_{ij}=\frac{1}{(1+b)^{2|t|}}((1+(\frac{1+b}{b})^2)^{|t|} - \underset{k \in t}{\Pi}(1+ \frac{\overline{\phi}_k(x_i)}{(\frac{b}{b+1})^2}) - \underset{k \in t}{\Pi}(1+\frac{\overline{\phi}_k(x_j)}{(\frac{b}{b+1})^2})$\\$ + \underset{k\in t}{\Pi}   (1+\frac{\overline{\phi}_k(x_i)}{\frac{b}{1+b}}  \frac{\overline{\phi}_k(x_j)}{\frac{b}{1+b}}))$
  \end{itemize}
\end{frame}

\begin{frame}{Hierarchical Kernel learning For Learning Taxonomies}
 \begin{itemize}
  \item Inherent hierarchical structure exploited
 \item Vocabulary consisiting of important sense tagged words 
  \item Every sense of every word becomes a basic feature of HKL
  \item Syntagmatic Information (context-co-occurrence): conjunctive lattice
  \item Paradigmatic Information (synonymous words): disjunctive lattice
 \end{itemize}
\end{frame}

\section{Conclusion and Future work}

\begin{frame}{Conclusion}
 \begin{itemize}
  \item Hierarchical Kernel Learning: Large features are discarded.
  \item Rule Ensemble Learning using Hierarchical Kernels: Sparsity feature sets and sparse individual features
  \item Code contributed as a weka classifier
  \item REL-HKL framework in structured output spaces
  \item Hierarchical Kernel Learning for disjunctive features.
 \end{itemize}
\end{frame}

\begin{frame}{Ongoing and Future Work}
 \begin{itemize}
  \item Scaling up feature induction: 
  \begin{itemize}
    \item Other formulations
    \item Restricting search space
  \item Extending the framework to more complex feature spaces (such as FOL)
  \item Grand Goal: Learning sparse features and structure templates optimally for various SRL models
 \end{itemize}
\end{frame}


\begin{frame}{Search Space Restrictions}
  \begin{figure}[H]
    \centering
    \includegraphics[width=58mm]{bottom_clause_and_rlgg_lattice.png}
    \caption{Feature Lattice: Example independent vs. Example induced}
    \end{figure}
\end{frame}


\begin{frame}{Bibliography}
 \begin{thebibliography}{99}
\scriptsize
%   \footnotesize
    \bibitem{commonSense} Shiaokai Wang, William Pentney, Ana-Maria Popescu, Tanzeem Choudhury, Matthai Philipose: Common sense based joint training of human activity recognizers. In: 20th International Joint Conference on Artifical Intelligence (2007)

    \bibitem{crf} John Lafferty, Andrew McCallum, Fernando Pereira: Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data. In: International Conference on Machine Learning (2001)

    \bibitem{kfoil} Niels Landwehr, Andrea Passerini, Luc De Raedt, Paolo Frasconi: KFOIL: Learning Simple Relational Kernels. In: 21st National Conference on Artificial Intelligence (2006)

    \bibitem{tildeCRF} Bernd Gutmann, Kristian Kersting: TildeCRF: Conditional Random Fields for Logical Sequences. In: 15th European Conference on Machine Learning (2006)
  
    \bibitem{featureRelational} N. Di Mauro, T.M.A. Basile, S. Ferilli, F. Esposito: Feature Construction for Relational Sequence Learning. In: Technical Report, arXiv:1006.5188 (2010)
    
    \bibitem{aleph} Ashwin Srinivasan: The Aleph Manual. Technical Report, University of Oxford (2007)

\end{thebibliography}
\end{frame}
\begin{frame}{Bibliography}
 \begin{thebibliography}{99}
  \scriptsize

    \bibitem{relTransorm} Niels Landwehr, Bernd Gutmann, Ingo Thon, Luc De Raedt, Matthai Philipose: Relational Transformation-based Tagging for Activity Recognition. Progress on Multi-Relational Data Mining 89(1):111-129 (2009)

    \bibitem{modelbasedsequence} Henri Binsztok, Thierry Artieres, Patrick Gallinari: A model-based approach to sequence clustering. In: European Conference on Artificial Intelligence (2004)

    \bibitem{featureInductionMccallum} Andrew McCallum: Efficiently Inducing Features of Conditional Random Fields. In: Nineteenth Conference on Uncertainty in Artificial Intelligence (2003)

    \bibitem{wilcoxon} S. Siegel: Nonparametric statistics for the behavioural sciences. New York: McGraw-Hill (1956)

    \bibitem{naveenActivity} Naveen Nair, Ganesh Ramakrishnan and Shonali Krishnaswamy, \emph{Enhancing Activity Recognition in Smart Homes Using Feature Induction}, International Conference on Data Warehousing and Knowledge Discovery, 2011.
  
    \bibitem{ganeshRELHKL} Pratik Jawanpuria, Saketha Nath Jagarlapudi and Ganesh Ramakrishnan, \emph{Efficient Rule Ensemble Learning using Hierarchical Kernels}, International Conference on Machine Learning, 2011.

    \bibitem{TsochantaridisSVMStructured} Ioannis Tsochantaridis, Thomas Hofmann, Thorsten Joachims and Yasemin Altun, \emph{Support Vector Machine Learning for Interdependent and Structured Output Spaces}, International Conference on Machine Learning, 2004.

   
  \end{thebibliography}
\end{frame}
\begin{frame}{Bibliography}
 \begin{thebibliography}{99}
  \scriptsize
 \bibitem{AltHofTso06}Tsochantaridis Ioannis, \emph{Support vector machine learning for interdependent and structured output spaces},2006.

    \bibitem{MichelliPontil2005}Charles Micchelli and  Massimiliano Pontil, \emph{Learning the Kernel Function via Regularization}, Journal of Machine Learning Research,2005.

    \bibitem{healthWilson} Daniel H. wilson, \emph{Assistive Intelligent Environments for Automatic Health Monitoring}, PhD Thesis, Carnegie Mellon University, 2005.

    \bibitem{kasteren08} Tim van Kasteren, Athanasios Noulas, Gwenn Englebienne and Ben krose, \emph{Accurate activity recognition in a home setting}, 10th International conference on Ubiquitous computing, 2008.

    \bibitem{kasterenMonitoring} C.H.S. Gibson, T.L.M. van Kasteren and Ben Krose, \emph{Monitoring Homes with Wireless Sensor Networks}, Proceedings of the International Med-e-Tel Conference, 2008.
  
    \bibitem{hmm} R. Rabiner, \emph{A tutorial on hidden Markov models and selected applications in speech recognition}, Proceedings of the IEEE, 77(2):257--286, 1989.

    \bibitem{srl} Lise Getoor and Ben Taskar, \emph{Statistical Relational Learning}, MIT Press, 2006.
  
    \bibitem{viterbi} Forney GD, \emph{The viterbi algorithm}, Proceedings of IEEE, 61(3):268--278, 1973


\end{thebibliography}
\end{frame}
\begin{frame}{Bibliography}
 \begin{thebibliography}{99}
  \scriptsize
    \bibitem{bachHKL} Bach F., \emph{High-Dimensional Non-Linear Variable Selection through Hierarchical Kernel Learning}, Technical report, INRIA, France, 2009.

    \bibitem{rakotomamonjy} Rakotomamonjy A., Bach F., Canu S., and Grandvalet Y., \emph{SimpleMKL}, JMLR, 9:2491-2521, 2008.

    \bibitem{szafranskiRhonorm} Szafranski M., Grandvalet Y., and Rakotomanmonjy A., \emph{Composite Kernel Learning}, ICML, 2008.

    \bibitem{mkl} Kloft M., Brefeld U., Sonnenburg S., Laskov P., Muller K. R., and Zien A., \emph{Efficient and Accurate p-Norm Multiple Kernel Learning}, NIPS, 2009.

    \bibitem{minmax} Sion M., \emph{On General Minimax Theorem}, Pacific Journal of Mathematics, 1958.
 \end{thebibliography}

\end{frame}

% \begin{frame}{Bibliography for figures}
% \scriptsize
% kitchen: http://depositphotos.com/1461962/stock-illustration-Kitchen-mistresson-the-kitchen.html
% \end{frame}

\begin{frame}
\begin{center}
 
 \Huge \textbf{Thanks}
\end{center}

\end{frame}



\end{document}
