2014_tti.tex

\newif\ifcrossling\crosslingtrue
\newif\ifitmtree\itmtreetrue
\newif\iflong\longfalse
\newif\ifevaluation\evaluationfalse
\newif\ifconjugacy\conjugacyfalse
\newif\ifnonpar\nonparfalse
\newif\ifling\lingfalse
\newif\ifhighlevel\highleveltrue
\newif\iftmreview\tmreviewfalse
\newif\ifevocation\evocationfalse
\newif\ifsupershortmlslda\supershortmlsldatrue

\documentclass[compress]{beamer}

%\usepackage{beamerthemesplit}
\usepackage{xmpmulti}

\definecolor{green}{rgb}{0,.3,0}

\usepackage{graphicx,float,wrapfig, bbm}
\usepackage{amsfonts, bbold, comment}
\usepackage{mdwlist}
\usepackage{listings}
\usepackage{environ}
\usepackage{subfigure}
\usepackage{rotating}
\usepackage{algorithmic}
\usepackage{algorithm}
\usepackage{overpic}

\usepackage{multirow}

\usetheme{Rochester}
%\useoutertheme{infolines}
%\usetheme{Boadilla}
%\usetheme{Singapore}
\usecolortheme{umd}
\title{Big Data Analysis with Topic Models: Human Interaction, Streaming Computation, \\and Social Science Applications}
\author{Jordan Boyd-Graber}
\date{\today}

\newcommand{\explain}[2]{\underbrace{#2}_{\mbox{\footnotesize{#1}}}}
\newcommand{\dir}[1]{\mbox{Dir}(#1)}
\newcommand{\mult}[1]{\mbox{Mult}( #1)}
\newcommand{\Beta}[1]{\mbox{Beta}( #1)}
\newcommand{\G}[1]{\Gamma \left( \textstyle #1 \right)}
\newcommand{\LG}[1]{\log \Gamma \left( \textstyle #1 \right)}
\newcommand{\WN}[0]{\textsc{WordNet}}
\newcommand{\itmspace}[0]{\hspace{2cm}}
\newcommand{\abr}[1]{\textsc{#1}}
\newcommand{\lda}[0]{\abr{lda}}
\newcommand{\slda}[0]{\abr{slda}}

\newcommand{\digam}[1]{\Psi \left( \textstyle #1 \right) }
\newcommand{\ddigam}[1]{\Psi' \left( \textstyle #1 \right) }
\newcommand{\e}[2]{\mathbb{E}_{#1}\left[ #2 \right] }
\newcommand{\ind}[1]{\mathbb{I}\left[ #1 \right] }
\newcommand{\ex}[1]{\mbox{exp}\left\{ #1\right\} }
\newcommand{\D}[2]{\frac{\partial #1}{\partial #2}}
\newcommand{\elbo}{\mathcal{L}}


\newcommand{\citename}[1]{\emph{#1} }
\newcommand{\bm}[1]{\mbox{\boldmath$#1$}}
\newcommand{\Dir}{\mathrm{Dir}}
\newcommand{\Mult}{\mathrm{Mult}}
\newcommand{\g}[1]{\Gamma \left( #1 \right)}
\newcommand{\paragraph}[1]{ \vskip 1cm {\bf \large #1}}

\NewEnviron{smalign}{
\vspace{-.6cm}
\begin{small}
\begin{align}
  \BODY
\end{align}
\end{small}
\vspace{-.6cm}
}


\providecommand{\graphscale}{0.6}

\newcommand{\danquote}[1]{

\begin{flushright}
\begin{overpic}[width=5.5cm,tics=10]{general_figures/speech_bubble}
	\put(10,30) { \parbox{4cm}{#1 }}
\end{overpic}
\includegraphics[width=1.5cm]{general_figures/milkman_dan}
\end{flushright}
}


% \AtBeginSection[] % "Beamer, do the following at the start of every section"
% { \begin{frame}

% \frametitle{Outline} % make a frame titled "Outline"
% \tableofcontents[currentsection] % show TOC and highlight current section
% \end{frame} }

\lstset{language=Python}

\DeclareMathSymbol{\R}{\mathbin}{AMSb}{"52}

%\setbeamertemplate{footline}{\hspace*{.5cm}\scriptsize{\insertauthor

\begin{document}

% this prints title, author etc. info from above

\frame{\titlepage
\vspace{-2cm}
\includegraphics[width=0.3\linewidth]{general_figures/umd_logo} \\
\tiny

}



\begin{frame}
\frametitle{The Challenge of Big Data}

\begin{columns}

\column{.5\linewidth}

Every second \dots
\begin{itemize}
  \item 600 new blog posts appear
  \item 34,000 tweets are tweeted
  \item 30 GB of data uploaded to Facebook
\end{itemize}
\pause

\begin{block}{Unstructured}
  No XML, no semantic web, no annotation.  Often just raw text.
\end{block}

\column{.5\linewidth}

\only<3->{
Common task: what's going on in this dataset.
\begin{itemize}
   \item Intelligence analysts
   \item Brand monitoring
   \item Journalists
   \item Humanists
\end{itemize}
}
\only<4>{
\centering
Common solution: topic models
}

\end{columns}

\end{frame}

\begin{frame}

\begin{center}
\frametitle{Topic Models as a Black Box}
From an \textbf<1>{input corpus} and number of topics \textbf<1>{$K$} $\rightarrow$ \textbf<2>{words to topics} \\
\only<1>{\includegraphics[width=0.6\linewidth]{reading_tea_leaves/figures/heldout_0} }
\only<2>{\includegraphics[width=0.9\linewidth]{reading_tea_leaves/figures/nyt_topics_wide}}
\only<3>{\includegraphics[width=0.9\linewidth]{topic_models/nyt_documents}}
\end{center}

\end{frame}


\begin{frame}
\frametitle{Topic Models in Academia}

\begin{columns}

\column{.6\linewidth}

\begin{itemize}
  \item Useful
    \begin{itemize}
      \item Computer Vision \cite{feifei-05}
      \item Social Networks \cite{airoldi-08}
      \item Music \cite{hu-09}
      \item Cognitive Science \cite{griffiths-06}
    \end{itemize}

\begin{block}{Latent Dirichlet Allocation}
Blei, Ng, and Jordan.  Journal of Machine Learning Research, 2003.
\end{block}


  \item Popular: most cited on Mendeley
  \item Easy: reasonable undergrad programming assignment
\end{itemize}


\column{.39\linewidth}
\begin{center}
\includegraphics[width=0.8\linewidth]{topic_models/feifei} \\
\includegraphics[width=0.8\linewidth]{topic_models/socialnetworks} \\
\includegraphics[width=0.8\linewidth]{topic_models/hu}
\end{center}
\end{columns}
\end{frame}

\begin{frame}
\frametitle{Topic Models in the Real World}

\vspace{-1cm}

\begin{columns}
  \column{.5\linewidth}
\begin{center}
\includegraphics[width=0.8\linewidth]{topic_models/tobacco_litigation} \\
\includegraphics[width=0.8\linewidth]{topic_models/nih_topics} \\
\includegraphics[width=0.7\linewidth]{topic_models/sentiment}
\end{center}

  \column{.5\linewidth}

  \begin{itemize}
    \item E-discovery
    \item Understanding funding decisions
    \item Social media monitoring and sentiment analysis
  \end{itemize}

\end{columns}

\end{frame}

%\input{topic_models/topic_models}

\begin{frame}
  \frametitle{Outline of This Talk}

  \begin{columns}
    \column{.2\linewidth}
       \includegraphics[width=\linewidth]{cognitive/crowdsourcing_on}
    \column{.6\linewidth}
       \begin{block}{Evaluating Topic Models}
         Crowdsourced evaluation of topic models
        \end{block}

  \end{columns}


  \begin{columns}
    \column{.2\linewidth}
       \includegraphics[width=\linewidth]{cognitive/user_on}
    \column{.6\linewidth}
       \begin{block}{Interaction}
         Representing meaning and new applications
        \end{block}

  \end{columns}


  \begin{columns}
    \column{.2\linewidth}
       \includegraphics[width=\linewidth]{cognitive/algorithms_on}
    \column{.6\linewidth}
       \begin{block}{Algorithms}
         Efficient algorithms for streaming datasets
        \end{block}
  \end{columns}

  \begin{columns}
    \column{.2\linewidth}
       \includegraphics[width=\linewidth]{cognitive/framing_on}
    \column{.6\linewidth}
       \begin{block}{Computational Social Science}
         Detecting spin via hierarchical models
        \end{block}

  \end{columns}

\end{frame}

\section{Evaluating Topic Models}

\begin{frame}
  \vspace{-2cm}
  \begin{columns}
    \column{.45\linewidth}
    \begin{center}
      \includegraphics[width=\linewidth]{cognitive/crowdsourcing_on}
      \end{center}
    \column{.45\linewidth}
    \begin{center}
      \includegraphics[width=\linewidth]{cognitive/user_off}
      \end{center}

  \end{columns}

  \begin{columns}
    \column{.45\linewidth}
    \begin{center}
      \includegraphics[width=\linewidth]{cognitive/algorithms_off}
      \end{center}
    \column{.45\linewidth}
    \begin{center}
      \includegraphics[width=\linewidth]{cognitive/framing_off}
      \end{center}
  \end{columns}

\only<2->{
\vspace{-3cm}
\begin{block}{Reading Tea Leaves}
        How we used to evaluate topic models was wrong; but there is a better
        way using crowdsourcing
\end{block}
}

\end{frame}

\begin{frame}{Evaluating Topic Models}

\begin{columns}

\column{.6\linewidth}
\begin{block}{ Reading Tea Leaves: How Humans Interpret Topic Models}
Jonathan Chang, Jordan Boyd-Graber, Chong Wang, Sean Gerrish, and David
M. Blei. Reading Tea Leaves: How Humans Interpret Topic Models. Neural
Information Processing Systems, 2009.
\end{block}

{\bf Jonathan and I shared a NIPS 2009 Best Student Paper HM}

\column{.3\linewidth}
\includegraphics[width=.8\linewidth]{general_figures/jonathan}

\end{columns}

\end{frame}



\frame{
\frametitle{Evaluation}
\begin{center}
%\only<1>{\includegraphics[width=0.9\linewidth]{reading_tea_leaves/figures/heldout_1} }
\only<1>{\includegraphics[width=\linewidth]{reading_tea_leaves/figures/heldout_2} }
%\only<3>{\includegraphics[width=\linewidth]{reading_tea_leaves/figures/heldout_3} }
\only<2>{\includegraphics[width=\linewidth]{reading_tea_leaves/figures/heldout_4}  \\
	\large Measures predictive power (likelihood / perplexity)}
\end{center}
}


\frame{
        \frametitle{Interruption}

  \begin{columns}
  \column{.6\linewidth}
  \begin{block}{Do you have any real results?}
  \centering
     \includegraphics[width=0.5\linewidth]{reading_tea_leaves/jelinek} \\
     Fred Jelinek, inventor of perplexity~\cite{jelinek-76}
  \end{block}

  \column{.4\linewidth}

  \begin{itemize}
    \item Computational linguists and machine learning researchers like {\bf numbers}
    \item Likelihood and perplexity are convenient numbers
    \pause
    \item What do we {\bf actually} care about in topic models?
  \end{itemize}

  \end{columns}
}

\frame{
\frametitle{Qualitative Evaluation of the Latent Space}

\begin{center}
\only<1>{\includegraphics[width=0.9\linewidth]{reading_tea_leaves/topics_from_papers/1} \\ \cite{hofmann-99} }
\only<2>{\includegraphics[width=0.7\linewidth]{reading_tea_leaves/topics_from_papers/2} \\ \cite{blei-03} }
\only<3>{\includegraphics[width=0.7\linewidth]{reading_tea_leaves/topics_from_papers/3} \\ \cite{mimno-09} }
\only<4>{\includegraphics[width=0.7\linewidth]{reading_tea_leaves/topics_from_papers/4} \\ \cite{maskeri-08} }

\only<5->{
\begin{block}{Interpretability}
        When a user looks at a topic, does it make sense?
\end{block}
\pause
  \begin{itemize}
   \item Interpretability is a human judgment
    \item We will ask people directly
    \item Experiment Goals
      \begin{itemize}
        \item Quick
        \item Fun
        \item Consistent
      \end{itemize}
      \pause
      \item We turn to Amazon Mechanical Turk
        \iflong
       \item Two tasks: Word Intrusion and Topic Intrusion
         \else
         \item Primary task: Word Intrusion
         \fi

  \end{itemize}
}
\end{center}
}

\frame{
\frametitle{Data from the Cloud}
\begin{columns}[c]


\column{0.45\linewidth}

\begin{block}{Then}
\includegraphics[width=0.95\linewidth]{evocation/figures/mechanical_turk_old}
\end{block}


\column{0.45\linewidth}

\begin{block}{Now}
\includegraphics[width=0.95\linewidth]{evocation/figures/mechanical_turk_new}
\end{block}

\end{columns}
}

\frame{
  \frametitle{Word Intrusion}

  \begin{enumerate}
    \item Take the highest probability words from a topic

      \begin{block}{Original Topic}
        dog, cat, horse, pig, cow
      \end{block}
\pause
    \item Take a high-probability word from another topic and add it
      \begin{block}{Topic with Intruder}
        dog, cat, \alert<2->{apple}, horse, pig, cow
      \end{block}
\pause
     \item We ask users to find the word that doesn't belong
  \end{enumerate}
\begin{block}{Hypothesis}
If the topics are interpretable, users will consistently choose true intruder
\end{block}
}

\frame{
  \frametitle{Word Intrusion}

\begin{center}
\only<1>{\includegraphics[width=\linewidth]{reading_tea_leaves/tasks/word1}  }
\only<2>{\includegraphics[width=\linewidth]{reading_tea_leaves/tasks/word2}  }
\pause
  \begin{itemize}
    \item Order of words was shuffled
    \item Which intruder was selected varied
    \item Model precision: percentage of users who clicked on intruder
  \end{itemize}

\end{center}
}


\frame{
\frametitle{Word Intrusion: Which Topics are Interpretable?}
  \begin{block}{New York Times, 50 Topics}
    \begin{center}
      \includegraphics[width=0.8\linewidth]{reading_tea_leaves/figures/topic_precision}
    \end{center}
  \end{block}
  \begin{center}
    Model Precision: percentage of correct intruders found
  \end{center}
}

\frame{

\frametitle{Interpretability and Likelihood}

\begin{center}
\only<1>{Model Precision on New York Times}
\end{center}

\begin{columns}
\column{.84\linewidth}
\begin{flushright}
  \only<1>{\includegraphics[scale=\graphscale]{reading_tea_leaves/tasks/mp}}
  \only<1>{\includegraphics[scale=\graphscale]{reading_tea_leaves/tasks/mp_y}\includegraphics[scale=\graphscale]{reading_tea_leaves/tasks/nyt_mp}\\}
  \only<1>{\includegraphics[scale=\graphscale]{reading_tea_leaves/tasks/nyt_x}}

\end{flushright}
\column{.15\linewidth}
  \includegraphics[scale=\graphscale]{reading_tea_leaves/tasks/legend}
\end{columns}
\vspace{-0.75cm}
\begin{center}
  \includegraphics[scale=\graphscale]{reading_tea_leaves/tasks/held-out} \\
\only<1> {within a model, higher likelihood $\not =$ higher interpretability}
\end{center}
}


\begin{frame}{Since then \dots}

  \begin{itemize}
    \item A way to get at an evaluation that matches {\bf what we care about}
    \item A necessary step to improving topic models for navigating large datasets~\cite{talley-11}
    \item Others have discovered automatic methods that uncover the same properties~\cite{newman-10,mimno-11}
    \item And extended the technique to structured topics and phrases~\cite{lindsey-12,weninger-12}
  \end{itemize}

\end{frame}

\section{Interactive Topic Modeling}

\begin{frame}
  \vspace{-2cm}
  \begin{columns}
    \column{.45\linewidth}
    \begin{center}
      \includegraphics[width=\linewidth]{cognitive/crowdsourcing_off}
      \end{center}
    \column{.45\linewidth}
    \begin{center}
      \includegraphics[width=\linewidth]{cognitive/user_on}
      \end{center}

  \end{columns}

  \begin{columns}
    \column{.45\linewidth}
    \begin{center}
      \includegraphics[width=\linewidth]{cognitive/algorithms_off}
      \end{center}
    \column{.45\linewidth}
    \begin{center}
      \includegraphics[width=\linewidth]{cognitive/framing_off}
      \end{center}
  \end{columns}

\only<2->{
\vspace{-3cm}
\begin{block}{Interactive Topic Modeling}
        When a topic model goes bad, a novice user can fix it.
\end{block}
}

\end{frame}


\frame{

\begin{columns}

\column{.5\linewidth}

\includegraphics[width=.8\linewidth]{general_figures/yuening}

\column{.5\linewidth}

\begin{block}{Interactive Topic Modeling}
Yuening Hu, Jordan Boyd-Graber, and Brianna Satinoff.  Association for Computational Linguistics, 2011.
\end{block}

\end{columns}

}


\frame{

\frametitle{The Problem: User Perspective}

\begin{columns}

\column{.4\linewidth}
\begin{center}
\begin{tabular}{ccc}
& \only<2->{\itmspace}\color<2->{red}{bladder} & \\
& \only<3->{\hspace{-2cm}} \color<3->{blue}{spinal\_cord}  & \\
& \only<3->{\hspace{-2cm}} \color<3->{blue}{sci} & \\
& \only<3->{\hspace{-2cm}}\color<3->{blue}{spinal\_cord\_injury} & \\
& \only<3->{\hspace{-2cm}}\color<3->{blue}{spinal} & \\
& \only<2->{\itmspace}\color<2->{red}{urinary} & \\
& \only<2->{\itmspace}\color<2->{red}{urothelial} & \\
& \only<3->{\hspace{-2cm}}\color<3->{blue}{cervical} & \\
& injury & \\
& recovery & \\
& \only<2->{\itmspace}\color<2->{red}{urinary\_tract} & \\
& locomotor & \\
& \only<3->{\hspace{-2cm}}\color<3->{blue}{lumbar} & \\
\end{tabular}
\end{center}

\column{.6\linewidth}

\danquote{These words don't belong together!}

\end{columns}

}

\begin{frame}
        \frametitle{This is serious business!}


        \begin{itemize}
          \item Decision makers see problems
          \item No easy way to correct the problem
          \item Result: entire approach is abandoned
\pause
          \item Two ingredients in the fix:
            \begin{itemize}
              \item New models
              \item How to learn from mistakes
            \end{itemize}
        \end{itemize}

\end{frame}



\frame{
	\frametitle{Fix Ingredient \#1: The model}

\begin{columns}

\column{.4\linewidth}

\begin{itemize}
	\item The topics in a topic model are \only<2->{\alert<2>{uncorrelated}} distributions over words
	\only<3->{
	\item The advice you get can be encoded as correlations
		\begin{itemize}
			\alert<4>{\item Positive correlations}
			\alert<5>{\item Negative correlations}
		\end{itemize}
	}

\end{itemize}

\column{.6\linewidth}

	\only<1-2>{	\includegraphics[width=\linewidth]{interactive_topic_models/constraints_1}     }
	\only<3-4>{	\includegraphics[width=\linewidth]{interactive_topic_models/constraints_2}     }
	\only<5->{	\includegraphics[width=\linewidth]{interactive_topic_models/constraints_3}     }
\end{columns}

}

\begin{frame}
  \frametitle{Adding meaning to topic models}

        \begin{itemize}
	 \item Add an additional step to model topics as a distribution over concepts

         \item We've used this formalism to build probabilistic word-sense
           disambiguation algorithms~\cite{boyd-graber-07} and multilingual models~\cite{boyd-graber-10}

         \item Others have used it to encode database constraints (e.g. cannot link and must link)~\cite{andrzejewski-09} or first order logic~\cite{andrzejewski-11}
        \end{itemize}

\end{frame}

\begin{frame}
  \frametitle{Adding meaning to topic models}
        \begin{block}{Traditional Topic Models}
                $ p(w) = \prod_d \prod_n^{N_d} \left( p(w_{d,n} | \phi_{z_{d,n}})
                  \explain{\alert<3>{topic}}{p(z_{d,n} | \theta_d)} \right) p(\theta_d | \alpha)                 \explain{\alert<2>{topic to words}}{ \prod_k^K
p(\phi_k | \eta) }$
        \end{block}

        \begin{block}{Our Model}
          \vspace{-0.8cm}
          \begin{align*}
               p(w) = \prod_d \prod_n^{N_d} & \left( p(w_{d,n} | \pi_{l_{d,n}})
                 \explain{\alert<6>{meaning and topic}} {p(l_{d,n} | \phi_{d,n} )
                   p(z_{d,n} | \theta_d)}  \right) p(\theta_d | \alpha) \\
               &  \explain{\alert<4>{topic to concept}}{\prod_k^K
                p(\phi_k | \eta)} \explain{\alert<5>{concept to word}}{\prod_c^C \left(
                  p(\pi_{k,c} | \tau) \right) }
           \end{align*}
        \end{block}


\end{frame}

\begin{frame}

        % TODO(jbg): add image
        \frametitle{Fix Ingredient \#2: Online Learning}

        \begin{itemize}
                \item Feedback shows data where you made mistakes
                \item ``Forget'' those data~\cite{yao-09}
                \item Then rerun inference, pretending you're seeing them for the first time
                \item Allows you to escape from local optima
        \end{itemize}

\end{frame}


\frame{
	\frametitle{How to incorporate feedback?}

	\begin{columns}

	\column{.5\linewidth}

		\begin{columns}

			\column{.6\linewidth}

			\includegraphics[width=\linewidth]{topic_models/nyt_topics}


			\column{.4\linewidth}
			\begin{center}
				\only<2->{\includegraphics[width=.6\linewidth]{general_figures/arrow_right_down} \\}
				\only<2->{\includegraphics[width=.6\linewidth]{general_figures/milkman_dan} \\}
				\invisible<-2>{\includegraphics[width=.6\linewidth,angle=270]{general_figures/arrow_right_down}}
			\end{center}

		\end{columns}

	\column{.5\linewidth}

	\begin{enumerate}
		\item Fit initial topic model
			\pause
		\item Get feedback from user
			\pause
		\item Incrementally relearn model
			\begin{itemize}
                                \item Forget your mistakes
				\item Replace the model with a correlated one
				\item Continue inference
			\end{itemize}
	\end{enumerate}
\pause
Keep computation \alert<4>{fast and consistent} \cite{Hu-12a}
	\end{columns}

}

\input{interactive_topic_models/nyt_soviet_russia}

\input{interactive_topic_models/nih_topics}



\begin{frame}

        \frametitle{Experiments}

\begin{columns}

\column{.5\linewidth}

  \begin{itemize}
   \item Simulating users through classifying social media
     \begin{itemize}
       \item Investigating different learning strategies
       \item How much to forget
     \end{itemize}
   \end{itemize}

\column{.5\linewidth}

\begin{center}
\includegraphics[width=\linewidth]{interactive_topic_models/ablation_30_topics}
\end{center}

\end{columns}

\begin{itemize}
    \item User study: mechanical Turk
      \begin{itemize}
        \item We can't do everything users want: proper names, mac vs. pc
        \item Users are senstive to polysemy (``msg'': food or e-mail)
      \end{itemize}
    \item User study: exploring congressional debates
      \begin{itemize}
        \item Collaboration with social scientists
        \item Interactivity makes people use topic models more
       \end{itemize}
  \end{itemize}


\end{frame}

\section{Online LDA With Infinite Vocabulary}

\begin{frame}
  \vspace{-2cm}
  \begin{columns}
    \column{.45\linewidth}
    \begin{center}
      \includegraphics[width=\linewidth]{cognitive/crowdsourcing_off}
      \end{center}
    \column{.45\linewidth}
    \begin{center}
      \includegraphics[width=\linewidth]{cognitive/user_off}
      \end{center}

  \end{columns}

  \begin{columns}
    \column{.45\linewidth}
    \begin{center}
      \includegraphics[width=\linewidth]{cognitive/algorithms_on}
      \end{center}
    \column{.45\linewidth}
    \begin{center}
      \includegraphics[width=\linewidth]{cognitive/framing_off}
      \end{center}
  \end{columns}

\only<2->{
\vspace{-3cm}
\begin{block}{Infinite Vocabulary Topic Models}
        A model that can handle big, streaming data without assuming a fixed vocabulary
\end{block}
}


\end{frame}



\frame{

\begin{columns}

\column{.5\linewidth}

\begin{block}{Online Topic Models with Infinite Vocabulary}
Ke Zhai and Jordan Boyd-Graber.  International Conference on Machine Learning, 2013.
\end{block}

\column{.5\linewidth}

\includegraphics[width=.8\linewidth]{general_figures/ke}

\end{columns}

}

\begin{frame}{The Problem}

  \begin{center}
    \includegraphics[width=.7\linewidth]{infvoc/batch} \\
    Batch algorithms can't scale
  \end{center}

\end{frame}

\begin{frame}{One Solution: Parallelization}
  \begin{center}
    \includegraphics[width=.7\linewidth]{infvoc/parallel} \\
    Throw more computers at the problem \\
    For topic models, \textsc{Mr Lda}~\cite{zhai-12}
  \end{center}
\end{frame}

\begin{frame}{Another Solution: Streaming Algorithms}
  \begin{center}
    \only<1>{ \includegraphics[width=.8\linewidth]{infvoc/streaming-0}}
    \only<2>{ \includegraphics[width=.8\linewidth]{infvoc/streaming-1}}
    \only<3>{ \includegraphics[width=.8\linewidth]{infvoc/streaming-2}}
    \only<4>{ \includegraphics[width=.8\linewidth]{infvoc/streaming-3}}
    \only<5>{ \includegraphics[width=.8\linewidth]{infvoc/streaming-4}}
    \only<6>{ \includegraphics[width=.8\linewidth]{infvoc/streaming-5}}
    \only<7>{ \includegraphics[width=.8\linewidth]{infvoc/streaming-6}}
    \only<8>{ \includegraphics[width=.8\linewidth]{infvoc/streaming-7}}
    \\
    Handle the data as they come
  \end{center}
\end{frame}


% Making inference more efficient

% Streaming algorithms

% Why this is a problem for LDA


\begin{frame}{Online Topic Models}

\begin{block}{Past approaches for online topics models}
\begin{itemize}
%\item Gibbs sampling~\cite{yao-09}
\item Sequential Monte Carlo~\cite{canini-09}
%\item With the idea of an evolution matrix~\citep{alsumait-08}
\item Variational inference~\cite{hoffman-10}
\item Hybrid MCMC inference~\cite{mimno-12}
\end{itemize}
\end{block}

\begin{block}{Same assumption: constant vocabulary}
\begin{itemize}
\item The vocabulary is known \textit{a priori}
\item Topic distribution is {\bf fixed} Dirichlet \\
\begin{center}
$\boldsymbol{\beta}_k \sim \dir{\lambda}$.
\end{center}
\end{itemize}
\end{block}

\end{frame}

\begin{frame}{Online Algorithms and Fixed Vocabularies}

\begin{block}{}
\begin{itemize}
\item proper nouns, e.g., ``sch\"{a}uble''
\item words being invented, e.g., ``crowdsourcing''
\item words cross languages, e.g., ``Gangnam''
\item words cross topics, e.g., ``vuvuzelas'' (\textit{music}
  $\rightarrow$ \textit{sports}), etc
\end{itemize}
\end{block}
\pause
\begin{columns}

\column{.5\linewidth}

\centering
\includegraphics[width=.5\linewidth]{infvoc/psy}


\column{.5\linewidth}

\begin{itemize}
  \item Hard-to-detect errors: \{``style'', ``korea'',
    ``download'', ``youtube''\}
\pause
      \item Our approach: an infinite vocabulary
\end{itemize}


\end{columns}

\end{frame}

% Nonparametric models

\begin{frame}{The Infinite Dirichlet Process}
  \only<1>{ \includegraphics[width=.95\linewidth]{infvoc/dp_monkey-1} }
  \only<2>{ \includegraphics[width=.95\linewidth]{infvoc/dp_monkey-2} }
  \only<3>{ \includegraphics[width=.95\linewidth]{infvoc/dp_monkey-3} }
  \only<4>{ \includegraphics[width=.95\linewidth]{infvoc/dp_monkey-5} }
  \only<5>{ \includegraphics[width=.95\linewidth]{infvoc/dp_monkey-6} }
  \only<6>{ \includegraphics[width=.95\linewidth]{infvoc/dp_monkey-7} }
  \only<7>{ \includegraphics[width=.95\linewidth]{infvoc/dp_monkey-8} }
  \only<8>{ \includegraphics[width=.95\linewidth]{infvoc/dp_monkey-9} }
  \only<9>{ \includegraphics[width=.95\linewidth]{infvoc/dp_monkey-10} }
  \only<10->{ \includegraphics[width=.95\linewidth]{infvoc/dp_monkey-11} \\}
  \only<11->{Example of Bayesian nonparametrics \cite{ferguson-73,sethuraman-94}}
\end{frame}

% Our model

\begin{frame}{Infinite Vocabulary Topic Model}

  \begin{columns}
     \column{.44\linewidth}
     \begin{itemize}
       \item Each topic $\theta_k \sim \mbox{DP}(\alpha, G_0)$
       \item Infinite collection of atoms and weights
     \begin{itemize}
       \item For each word, ``stick breaks'' \alert<2>{$b_{k, w} \sim \mbox{Beta}(1,\alpha)$}
       \item Each atom gets weight \alert<3>{$\beta_{k, w} = \prod_{j=1}^{w} (1 - b_j)$}
       \item Atom identity drawn from base distribution $\rho_k \sim G_0$
     \end{itemize}
     \end{itemize}
     \column{.55\linewidth}
       \includegraphics[width=1.0\linewidth]{infvoc/dp_monkey-topics}
  \end{columns}

\end{frame}

% Comics

\begin{frame}{Inference}

We can't optimize the joint likelihood
\begin{align}
& \textstyle p( \boldsymbol{W}, \boldsymbol{\rho}, \boldsymbol{\beta},
\boldsymbol{\theta}, \boldsymbol{z} ) = \prod_{k=1}^K
\left[ \prod_{t=1}^{\infty} p( \rho_{kt} | G_0 ) \cdot p( \beta_{kt}
| \alpha^{\beta} ) \right] \notag \\
& \textstyle \left[ \prod_{d=1}^{D} p( \boldsymbol{\theta}_d | \alpha^{\theta} )
\prod_{n=1}^{N_d} p( z_{dn} | \boldsymbol{\theta}_d ) p( \omega_{dn} |
z_{dn}, \boldsymbol{\beta}_{z_{dn}} ) \right] . \notag
\end{align}
\pause
so we optimize a lower bound of the objective based on a variational distribution $q$,
\begin{align}
\textstyle \log p(\boldsymbol{W}) \geq {\e{q(\boldsymbol{Z})}{\log p(\boldsymbol{W},\boldsymbol{Z})} - \e{q(\boldsymbol{Z})}{q}} = \elbo,
\label{eq:elbo-vague}
\end{align}
which we optimize $\elbo(\boldsymbol{Z})$ using gradient steps.
\end{frame}



\begin{frame}{Incorporating New Words}
%\begin{center}
%\begin{figure}
  \only<1>{\includegraphics[width=\linewidth]{infvoc/new_words_highlight_1}}
  \only<2>{\includegraphics[width=\linewidth]{infvoc/new_words_highlight_2}}
  \only<3>{\includegraphics[width=\linewidth]{infvoc/new_words_highlight_3}}
  \only<4>{\includegraphics[width=\linewidth]{infvoc/new_words_highlight_4}}
  \only<5>{\includegraphics[width=\linewidth]{infvoc/new_words_highlight_5}}
  \only<6>{\includegraphics[width=\linewidth]{infvoc/new_words_highlight_6}}
  \only<7>{\includegraphics[width=\linewidth]{infvoc/new_words_highlight_7}}
  \only<8>{\includegraphics[width=\linewidth]{infvoc/new_words_highlight_8}}
%\end{figure}
%\end{center}
\begin{center}
\vspace{-5mm}
An example topic from \textit{20 newsgroups} under our model.
Numbers preceeding words are ranks in topic.
\end{center}

\end{frame}


\begin{frame}{Do the topics make sense?}

\centering
       \only<1>{\includegraphics[width=1.0\linewidth]{infvoc/coherence_0}}
       \only<2>{\includegraphics[width=1.0\linewidth]{infvoc/coherence_1}}
       \only<3>{\includegraphics[width=1.0\linewidth]{infvoc/coherence_2}}
       \only<4>{\includegraphics[width=1.0\linewidth]{infvoc/coherence_3}}

\begin{columns}
\column{.5\linewidth}
\begin{itemize}
  \item Finite topic models
  \item ``Dynamic'' topic models
\end{itemize}

\column{.5\linewidth}
\begin{itemize}
  \item Hashed vocabulary
  \item Other inference techniques
\end{itemize}
\end{columns}


\end{frame}


% Interpretability results

%\input{mlslda/mlslda}


\section{SHLDA: Detecting Framing}

\providecommand{\shlda}{\textsc{ShLDA}}

\begin{frame}
  \vspace{-2cm}
  \begin{columns}
    \column{.45\linewidth}
    \begin{center}
      \includegraphics[width=\linewidth]{cognitive/crowdsourcing_off}
      \end{center}
    \column{.45\linewidth}
    \begin{center}
      \includegraphics[width=\linewidth]{cognitive/user_off}
      \end{center}

  \end{columns}

  \begin{columns}
    \column{.45\linewidth}
    \begin{center}
      \includegraphics[width=\linewidth]{cognitive/algorithms_off}
      \end{center}
    \column{.45\linewidth}
    \begin{center}
      \includegraphics[width=\linewidth]{cognitive/framing_on}
      \end{center}
  \end{columns}

\only<2->{
\vspace{-3cm}
\begin{block}{Detecting Framing}
        Using topic models to detect spin
\end{block}
}


\end{frame}


\frame{

\begin{columns}

\column{.5\linewidth}

\includegraphics[width=.8\linewidth]{general_figures/an}

\column{.5\linewidth}

\begin{block}{Lexical and Hierarchical Topic Regression}
Viet-An Nguyen, Jordan Boyd-Graber, and Philip Resnik. NIPS 2013.
\end{block}

\end{columns}

}



% The problem of framing
\begin{frame}{Message Matters}

\begin{itemize}
  \item People make radically different decisions based on how information is
  presented~\cite{tversky-92}
  \item Politicians and marketers do this too
\begin{columns}
\column{.45\linewidth}
\begin{block}{Gain frame}
    Flossing your teeth daily removes particles of food in the mouth, avoiding bacteria, which promotes great breath.
\end{block}
\column{.49\linewidth}
\begin{block}{Loss frame}
    If you do not floss your teeth daily, particles of food remain in the mouth, collecting bacteria, which causes bad breath.
\end{block}

\end{columns}
\pause
  \item Can we discover this automatically?
\end{itemize}




\end{frame}

% Our model

\begin{frame}{The data}
  \begin{columns}
    \column{.5\linewidth}
    \begin{itemize}
      \item Every document has an associated {\bf response variable}
        \begin{itemize}
      \item Politicians: \alert<1>{Ideology of speaker}
      \item Products: \alert<2>{Stars on a review}
       \end{itemize}
      \item We need the response to find association of frame and topic
    \end{itemize}

    \column{.5\linewidth}
    \only<1>{
    \begin{center}
    \includegraphics[width=0.8\linewidth]{shlda/ideology_scale}
    \end{center}
       \begin{block}{}
       This Christmas I want you to do the most loving thing and I want you to buy each of your children an SKS rifle and 500 rounds of ammunition.
       \end{block}
    }
    \only<2>{
      \includegraphics[width=0.6\linewidth]{shlda/response}
      }

  \end{columns}
\end{frame}

\begin{frame}{Our Model}

\providecommand{\shldascale}{0.3}

\centering
  \only<1>{ \includegraphics[scale=\shldascale]{shlda/intuition_topics_0}}
  \only<2>{ \includegraphics[scale=\shldascale]{shlda/intuition_topics_1}}
  \only<3>{ \includegraphics[scale=\shldascale]{shlda/intuition_regression_0}}
  \only<4>{ \includegraphics[scale=\shldascale]{shlda/intuition_regression_1}}
  \only<5>{ \includegraphics[scale=\shldascale]{shlda/intuition_regression_2}}
  \only<6>{ \includegraphics[scale=\shldascale]{shlda/intuition_regression_3}}
  \only<7>{ \includegraphics[scale=\shldascale]{shlda/intuition_regression_4}}
  \only<8>{ \includegraphics[scale=\shldascale]{shlda/intuition_regression_5}}
  \only<9>{ \includegraphics[scale=\shldascale]{shlda/intuition_regression_6}}
  \only<10>{ \includegraphics[scale=\shldascale]{shlda/intuition_full_0}}
  \only<11->{ \includegraphics[scale=\shldascale]{shlda/intuition_full_1}}

  \only<11->{We call this model \alert<14>{supervised} \alert<13>{hierarchical} \alert<12>{latent Dirichlet
    allocation} (SHLDA).}

\end{frame}

% Examples


\begin{frame}{Adding in Lexical Regression}

\centering
    \only<1>{ \includegraphics[width=.6\linewidth]{shlda/equation_0}}
    \only<2>{ \includegraphics[width=.65\linewidth]{shlda/equation_1}}
    \only<3>{ \includegraphics[width=.675\linewidth]{shlda/equation_2}}
    \only<4>{ \includegraphics[width=.675\linewidth]{shlda/equation_3}}
    \only<5>{ \includegraphics[width=.7\linewidth]{shlda/equation_4}}

 \begin{itemize}
    \item Some words have {\bf context-specific} contributions (topics)
    \item Some words have {\bf constant} contributions (words)
    \item Long noted for sentiment analysis
      \begin{itemize}
        \item ``Wonderful'': always good
          \item ``Unpredictable'': good for books, bad for steering
        \end{itemize}
    \end{itemize}


\end{frame}



\begin{frame}{Qualitative Results}
   \begin{center}
   \only<1>{ \includegraphics[width=0.8\linewidth]{shlda/ideology_topics}}
   \only<2>{ \includegraphics[width=1.0\linewidth]{shlda/amazon_topics}}
   \only<3>{ \includegraphics[width=0.7\linewidth]{shlda/amazon_topics_zoom}}
   \end{center}
\end{frame}

\begin{frame}{Quantitative Results}

\centering

\begin{tabular}{|c||c|c|c|c|}
  \hline
Models & Floor Debates & Amazon & Movie \\
  \hline
  $\textsc{svr-}\lda{}_{10}$     & $1.247$       & $1.241$ & $0.970$ \\
  $\textsc{svr-}\lda{}_{30}$     & $1.183$       & $1.091$ & $0.938$ \\
  $\textsc{svr-}\lda{}_{50}$     & $1.135$       & $1.130$ & $0.906$ \\
  {\textsc{svr-voc}}             & $1.467$       & $0.972$ & $0.681$\\
  {\textsc{svr-lda-voc}}         & $1.101$       & $0.965$ & $0.678$\\ \hline \hline
  $\textsc{mlr-}\lda{}_{10}$     & $1.151$       & $1.034$ & $0.957$ \\
  $\textsc{mlr-}\lda{}_{30}$     & $1.125$       & $1.065$ &$0.936$ \\
  $\textsc{mlr-}\lda{}_{50}$     & $1.081$       & $1.114$ & $0.914$ \\
  {\textsc{mlr-voc}}             & $1.124$       & $0.869$ & $0.721$\\
  {\textsc{mlr-lda-voc}}         & $1.120$       & $\bm {0.860}$ & $0.702$\\\hline \hline
  $\slda{}_{10}$                 & $1.145$       & $1.113$ & $0.953$\\
  $\slda{}_{30}$                 & $1.188$       & $1.146$ & $0.852$\\
  $\slda{}_{50}$                 & $1.184$       & $1.939$ & $0.772$\\ \hline \hline
  {\shlda{}}                     & $\bm {1.076}$ & $0.871$ & $\bm {0.673}$\\ \hline
\end{tabular}

Mean squared error averaged over 5 folds.
\end{frame}

\begin{frame}
   \frametitle{What's next \dots}

   \begin{columns}
     \column{.5\linewidth}
       \begin{block}{Stem-cell (R)}
         \begin{itemize}
           \footnotesize
           \item When the teachings of a faith are described as ``a culture of death'' \dots its [adherents] are being slandered.
           \item I accept, as an inseparable component of my faith, the omnipotence, omnipresence, and omniscience of God.
         \end{itemize}
       \end{block}
     \column{.5\linewidth}
       \begin{block}{Stem-cell (D)}
         \begin{itemize}
           \tiny
           \item They [conservatives] would surely---and appropriately---have
           ridiculed were it not supporting their current point of view.  In
           fact, there is little credible evidence to suggest adult stem cells
           have the same therapeutic potential as embryonic stem cells.

           \item Opponents assert that embryonic stem cells are unnecessary
           because adult stem cells, as well as umbilical cord blood stem cells,
           will perform at least as well as embryonic stem cells.

         \end{itemize}
       \end{block}
   \end{columns}

   \begin{itemize}
     \item Detecting sentences that are ``framed''
     \item Working with political scientists to validate results
     \item Creating a ``spin detector''
     \item Offering the opposing spin
   \end{itemize}

\end{frame}


%\input{topicshift-an/topicshift-an}

\begin{frame}
  \vspace{-2cm}
  \begin{columns}
    \column{.45\linewidth}
    \begin{center}
      \includegraphics[width=\linewidth]{cognitive/crowdsourcing_off}
      \end{center}
    \column{.45\linewidth}
    \begin{center}
      \includegraphics[width=\linewidth]{cognitive/user_off}
      \end{center}

  \end{columns}

  \begin{columns}
    \column{.45\linewidth}
    \begin{center}
      \includegraphics[width=\linewidth]{cognitive/algorithms_off}
      \end{center}
    \column{.45\linewidth}
    \begin{center}
      \includegraphics[width=\linewidth]{cognitive/framing_off}
      \end{center}
  \end{columns}

  \vspace{-5cm}

        \begin{block}{Topic models: understanding big data}

           \begin{itemize}
              \item Rethinking {\bf evaluation}
                \item Facilitating {\bf users interaction}
                  \item Solving {\bf computational challenges}
                    \item Enabling {\bf interdisciplinary collaborations}
            \end{itemize}

        \end{block}

\end{frame}

\frame{
  \frametitle{Ongoing and Future Work}

  \begin{itemize}
        \item Embedding interactivity in applications
      \item User evaluations
    \item Further improve inference: Using rich priors in spectral learning~\cite{Hu-12a}
    \item Using morphology in infinite vocabulary topic model
    \item Apply online learning to adaptor grammars (a generalization of topic models)
      \item Using deep learning to detect ideology
    \end{itemize}
}

\frame{
  \frametitle{But wait, there's more!}

\begin{columns}

  \column{.5\linewidth}
    \begin{block}{Latent Variable Image Models}
    \centering
        \includegraphics[width=0.7\linewidth]{general_figures/tibp} \\
       \cite{hu-12b}
    \end{block}

    \begin{block}{Machine Translation}
    \vspace{-.3cm}
      \begin{center}
        \begin{large}
          $p_{\mbox{topic}}(e | f)$ \\
         \end{large}
      \cite{eidelman-12}
       \end{center}
    \vspace{-.3cm}
    \end{block}

   \begin{block}{Computational Biology}
     \centering
     \includegraphics[width=0.4\linewidth]{general_figures/protein} \\
     \cite{nguyen-13b}
   \end{block}

  \column{.5\linewidth}

    \begin{block}{Assistive Devices}
     \centering
        \includegraphics[width=0.5\linewidth]{evocation/figures/jordan_at_adler} \\
       \cite{boyd-graber-06b,ma-09,nikolova-09}
    \end{block}

    \begin{block}{Question Answering}
      \centering
        \includegraphics[width=0.5\linewidth]{qb/quizbowl} \\
      \cite{boyd-graber-12}
    \end{block}

\end{columns}

}


\frame{

	\frametitle{Thanks}

        \begin{block}{Collaborators}
          Yuening Hu (UMD), Ke Zhai (UMD), Viet-An Nguyen (UMD), Dave Blei
          (Princeton), Jonathan Chang (Facebook), Philip Resnik (UMD), Christiane Fellbaum (Princeton), Jerry
          Zhu (Wisconsin), Sean Gerrish (Sift), Chong Wang (CMU), Dan Osherson
          (Princeton), Sinead Williamson (CMU)
        \end{block}

        \begin{block}{Funders}
        \end{block}
        \begin{center}
          \includegraphics[width=0.2\linewidth]{general_figures/nsf}
          \hspace{0.5cm}
          \includegraphics[width=0.2\linewidth]{general_figures/arl}
          \hspace{0.5cm}
          \includegraphics[width=0.2\linewidth]{general_figures/iarpa}
          \hspace{0.5cm}
          \includegraphics[width=0.2\linewidth]{general_figures/lockheed-martin}
       \end{center}

}


\begin{frame}{References}
\bibliographystyle{style/acl}
\tiny
\bibliography{bib/journal-full,bib/jbg}
\end{frame}



\begin{frame}{Latent Dirichlet Allocation: A Generative Model}

\begin{itemize}
\item Focus in this talk: statistical methods
  \begin{itemize}
    \item Model: story of how your data came to be
    \item Latent variables: missing pieces of your story
    \item Statistical inference: filling in those missing pieces
  \end{itemize}
\item We use latent Dirichlet allocation (LDA)~\cite{blei-03}, a fully Bayesian
  version of pLSI~\cite{hofmann-99}, probabilistic version of
  LSA~\cite{landauer-97}
\end{itemize}

\end{frame}

\frame
{
  \frametitle{Latent Dirichlet Allocation: A Generative Model}

\begin{center}
\only<1>{ \includegraphics[scale=0.4]{topic_models/lda1.pdf} }
\only<2>{ \includegraphics[scale=0.4]{topic_models/lda2.pdf} }
\only<3>{ \includegraphics[scale=0.4]{topic_models/lda3.pdf} }
\only<4->{ \includegraphics[scale=0.4]{topic_models/lda4.pdf} }
\end{center}

\begin{itemize}
\item<1-> For each topic $k \in \{1, \dots, K\}$, draw a multinomial distribution $\beta_k$ from a Dirichlet distribution with parameter $\lambda$
\item<2-> For each document $d \in \{1, \dots, M\}$, draw a multinomial distribution $\theta_d$ from a Dirichlet distribution with parameter $\alpha$
\item<3-> For each word position $n \in \{1, \dots, N\}$, select a hidden topic $z_n$ from the multinomial distribution parameterized by $\theta$.
\item<4-> Choose the observed word $w_n$ from the distribution $\beta_{z_n}$.
\end{itemize}

\only<5->{We use statistical inference to uncover the most likely unobserved variables given observed data.}
}

\begin{frame}

	\includegraphics[width=1.0\linewidth]{mrlda/lda_graphmod_nyt}

\end{frame}


\begin{frame}{SHLDA Model}
                    \centering
    \includegraphics[width=.5\linewidth]{shlda/shLDA}
\end{frame}


\begin{frame}
\frametitle{Infvoc Classification Accuracy}

\begin{table}[tb]
\centering
%\begin{footnotesize}
\begin{tabular}{ c | c | c | c | c}
%\hline
%\multicolumn{4}{c|}{model settings} & accuracy $\%$ \\
\hline
\multirow{10}{*}{ \begin{sideways}{\visible<1->{$S=155$}}\end{sideways}} &
\multirow{9}{*}{\begin{sideways}{\visible<1->{$\tau_0=64$
      $\kappa=0.6$}}\end{sideways}} & \visible<3->{\textit{infvoc}} &
\visible<3->{$\alpha^\beta=3k$ $T=40k$ $U=10$} & \visible<3->{$52.683$} \\
\cline{3-5}
& & \visible<1->{\textit{fixvoc}} & \visible<1->{vb-dict} & \visible<1->{$45.514$} \\
& & \visible<4->{\textit{fixvoc}} & \visible<4->{vb-null} & \visible<4->{$49.390$} \\
& & \visible<4->{\textit{fixvoc}} & \visible<4->{hybrid-dict} & \visible<4->{$46.720$} \\
& & \visible<4->{\textit{fixvoc}} & \visible<4->{hybrid-null} & \visible<4->{$50.474$} \\
\cline{3-5}
& & \visible<2->{\textit{fixvoc-hash}} & \visible<2->{vb-dict} & \visible<2->{$52.525$} \\
& & \visible<4->{\textit{fixvoc-hash}} & \visible<4->{vb-full $T=30k$} & \visible<4->{$51.653$} \\
& & \visible<4->{\textit{fixvoc-hash}} & \visible<4->{hybrid-dict} & \visible<4->{$50.948$} \\
& & \visible<4->{\textit{fixvoc-hash}} & \visible<4->{hybrid-full $T=30k$} & \visible<4->{$50.948$} \\
\cline{2-5}
& \multicolumn{3}{c|}{\visible<5->{\textit{dtm-dict} $tcv=0.001$}} & \visible<5->{$62.845$} \\
\hline
\end{tabular}
%\end{footnotesize}
\caption{Classification accuracy based on $50$ topic features
  extracted from \textit{20 newsgroups} data.}
% \label{tbl:20-news-class}
\end{table}

\only<2->{
\begin{center}
Topics learned with \textit{hashing} are no longer interpretable, they
can only be used as features.
\end{center}}

\end{frame}

\input{topic_models/gibbs_sampling.tex}

\input{interactive_topic_models/itm_appendix}


\end{document}