

\documentclass[11pt]{article}


\usepackage{graphicx}
\usepackage{amssymb}
\usepackage{epstopdf}
\usepackage{amsmath}
\usepackage{tikz}
\usepackage{pgf,tikz}
\usetikzlibrary{matrix}
\usepackage{comment}

\renewcommand{\baselinestretch}{1.}
\usepackage[margin=1in]{geometry}


\newcommand{\E}{\mathbb{E}}
\def\Var{{\rm Var}}
\def\T{{\top}}

\newcommand{\f}{\bf{f}}
\newcommand{\w}{\bf{w}}
\newcommand{\R}{\bf{R}}

\begin{document}

\section{Notation and formulation}

The training dataset consists of pairs of words and their relations. In the training stage, we learn the mapping between the pairs of words and their relations, so that in the testing stage, for a new pair of words, we can predict their relation.  In mathematical notation, suppose there are $M$ types of relations. For a pair of words $(a_1, a_2)$, let $R_i = 1$ if $(a_1, a_2)$ satisfies the $i$-th relation, and $R_i = 0$ otherwise, where $i = 1, ..., M$. We want to learn a mapping $h$ from $(a_1, a_2)$ to $R_i$. In a probabilistic formulation, the mapping predicts the probability that $R_i = 1$, i.e., $h(a_1, a_2) = \Pr(R_i= 1|a_1, a_2)$. 

The raw representation of a word $a$ is a so-called one-hot vector. Suppose there are $N$ words in the dictionary, then each $a$ is represented by a binary vector of $N$ components, so that the $j$-th component is 1 and all the other components are 0 if $a$ is the $j$-th word in the dictionary. 

Given a finite number of training examples $D = \{(a_1, a_2, R_i)\}$, in order to learn $h()$, we need to express $h()$ in a parametric form: $\Pr(R_i = 1|a_1, a_2) = h(a_1, a_2; \theta)$, where $\theta$ denotes the vector of parameters. In logistic regression or more generally neural network, $\theta$ collects the weight parameters (as well as bias terms). The goal of learning is to estimate $\theta$ from the training data $D$, so that the learned $\theta$ can be used to predict $R_i$ for a new pair of $(a_1, a_2)$ in the testing stage. 

\section{Bayesian learning} 

The parameters $\theta$ can be learned by maximum likelihood or more generally by minimizing a loss function. If $\theta$ is high dimensional, a penalty term such as the $\ell_2$ or $\ell_1$ norm of $\theta$ is usually added to the loss function to avoid overfitting. In our work, we adopt a Bayesian approach, where we assume a prior distribution $p(\theta)$, and the learning of $\theta$ is based on the posterior distribution $p(\theta|D) = p(\theta) p(D|\theta) /p(D)$, which, as a function of $\theta$, is proportional to  $p(\theta) p(D|\theta)$, because $p(D) = \int p(\theta) p(D|\theta) d\theta$ is a constant relative to $\theta$. After learning $\theta$ from $D$, for a new pair of words $(a_1, a_2)$, the prediction of $R_i$ can be based on 
\begin{align} 
\Pr(R_i = 1|a_1, a_2, D) =\int \Pr(R_i = 1|a_1, a_2, \theta) p(\theta|D) d\theta,  \label{eq:BayesPredict}
\end{align} 
where we integrate out $\theta$. The integration can be approximated by Monte Carlo samples from $p(\theta|D)$. 

Compared to the aforementioned loss function approach, $\log p(D|\theta)$ is the log-likelihood term or the negative loss function, and $\log p(\theta)$ corresponds to the penalty term. However, the Bayesian approach has the following advantages. 

(1) We can incorporate prior knowledge  into $p(\theta)$. In fact, $p(\theta)$ may well be the posterior distribution learned from the past data $D_0$, i.e., $p(\theta|D_0)$, and $p(\theta|D)$ is actually the updated posterior distribution 
\begin{align}
p(\theta|D, D_0) &= \frac{p(D|\theta) p(\theta|D_0)}{p(D|D_0)} \nonumber \\
 &= \frac{p(D|\theta) p(\theta|D_0)}{\int p(D|\theta) p(\theta|D_0)d\theta} \nonumber \\
 &\propto p(D|\theta) p(\theta|D_0),
\end{align}
 where we assume $p(D|\theta, D_0) = p(D|\theta)$,  or equivalently $p(D, D_0|\theta) = p(D|\theta) p(D_0|\theta)$. Prior knowledge is used in BART. 
 

(2) The prediction in equation (\ref{eq:BayesPredict}) averages out the posterior uncertainty $p(\theta|D)$. Such model averaging is used in BART. It avoids overfitting and often leads to better predicting performance compared to methods based on a point estimate $\hat{\theta}$. 

There are two commonly used methods for Bayesian learning. One is to design Markov chain Monte Carlo (MCMC) method to draw samples from $p(\theta|D)$. The other is to design a simpler approximated distribution $q_\phi(\theta)$ parameterized by $\phi$, and estimate $\phi$ by minimizing the Kullback-Leibler divergence $D_{\rm KL}(q_\phi(\theta)||p(\theta|D)) = \E_{q_\phi}[\log (q_\phi(\theta)/p(\theta|D))]$. This method is called variational Bayes, and is used by BART. 

\section{The model} 

We can parametrize $h(a_1, a_2; \theta)$ by a multi-layer network of the following form: 
\begin{align} 
      & f_1 = h(V a_1);  f_2 = h(V a_2) \\
      & f_1' = (f_1, \phi(f_1));  f_2' = (f_2, \phi(f_2))\\
      & f = s(f_1', f_2')\\
      & \Pr(R_i = 1|f, w) = {1}/{[1 + \exp(- f^\T w)]}. 
 \end{align} 
We shall explain the above equations. 

(1) Feature extraction.  For a word $a$, we can embed it into a $d$-dimensional Euclidean space, e.g., $d = 300$, to obtain a feature vector $f$, by $f = h(V a)$.  $V$ is a $d \times M$ matrix, where, recall,  $M$ is the number of words in the dictionary, and $h$ is an element-wise non-linear transformation, such as sigmoid or tanh. Recall $a$ is a one-hot vector. Let $V = (V_1, ..., V_j, ..., V_M)$, where $V_j$ is the $j$-th column vector of $V$. If $a$ is the $j$-th word, i.e., the $j$-element of $a$ is 1 and the other elements are 0. Then $V a = V_j$, and $f = h(V_j)$. 

The matrix $V$ can be considered part of the parameters $\theta$, however, it is learned from a big corpus of text $D_0$. In our work, we use the popular word2vec representation. It is learned by fitting a two-layer network on the training data $D_0 = \{(a, \tilde{a})\}$, where $a$ is a word in the text, and $\tilde{a}$ is a word that is within a certain window centered at $a$ in the text. The two layer network  consists of an encoder: $f = h(V a)$,  which encodes the input word $a$ into a vector $f$, and a decoder $g = U^\T f$, which decodes $f$ into an $M$ dimensional vector $g$, where $U$ is another $d \times M$ matrix, so that the probability distribution of the output word $\tilde{a}$ is given by the soft-max probability $p(\tilde{a}_j = 1) = \exp(g_j)/\sum_{j'=1}^{M} \exp(g_{j'})$. $(V, U)$ is learned from $D_0$, so that the encoding or embedding of $(a_1, a_2)$, i.e., $(f_1, f_2)$ is assumed given. 

(2) Feature alignment. For a word $a$, its embedding $f$ is a $d$ dimensional vector, and each dimension of $f$ encodes a different aspect of the semantic meaning of $a$. For a pair of words $(a_1, a_2)$, let their embeddings be $f_1 = (f_{11}, ..., f_{1k}, ...., f_{1d})$ and $f_2 = (f_{21}, ..., f_{2k}, ...., f_{2d})$. For different pairs $(f_1, f_2)$, the relation $R_i$ may be determined by different dimensions.  To re-align these dimensions, we re-order the dimensions of $(f_1, f_2)$ as follows.  Let $\Delta = (\Delta_1 = |f_{11}-f_{21}|, ..., \Delta_k = |f_{1k}-f_{2k}|, ..., \Delta_d = |f_{1d}-f_{2d}|)$ be the element-wise differences. We can order the components of $\Delta$ so that $\Delta_{\phi(1)} \geq \Delta_{\phi(2)} \geq ... \geq \Delta_{\phi(d)}$, where $(\phi(k), k = 1, ..., d)$ is a permutation of $(1, ..., d)$. Overloading the notation $\phi$ slightly, we define $\phi(f_1) = (f_{1 \phi(1)}, ..., f_{1 \phi(k)}, ..., f_{1 \phi(d)})$ and $\phi(f_2) = (f_{2 \phi(1)}, ..., f_{2 \phi(k)}, ...., f_{2 \phi(d)})$. We then append $\phi(f_1)$ to $f_1$ to get the augmented vector $f_1' = (f_1, \phi(f_1))$. Similarly we get $f_2' = (f_2, \phi(f_2))$. 

If we have much bigger training data $D$, we can learn the alignment re-ordering $\phi$ by some form of attention model, i.e., for each pair $(f_1, f_2)$, we pay attention to specific dimensions in order to determine the relation. 

(3) Feature selection. The dimensionality of $(f_1', f_2')$ can still be too high for our training data. It is preferable to reduce the dimensionality of $(f_1', f_2')$ in order to avoid overfitting. The dimensionality of $f_1' = (f_1, \phi(f_1))$ is $2d$, so is the dimensionality of $f_2'$. So there are a total of $4d$ components in $(f_1', f_2')$. Among these $4d$ components, we only select a small number of components for predicting $R_i$. Such a variable selection step is accomplished by fitting a $\ell_1$ regularized logistic regression on $\{(f_1', f_2', R_i)\}$, which minimizes $\sum_{D} \log (1 + \exp(R_i (f_1', f_2')^\T \beta)) + \lambda \|\beta\|_{\ell_1}$, where $\sum_{D}$ denotes the summation over the training examples, $(f_1', f_2')$ is the concatenated column vector, $\beta$ is the coefficient vector of the same dimension as $(f_1', f_2')$. $\|\beta\|_{\ell_1}$ is the $\ell_1$ norm of $\beta$, i.e., the sum of absolute values of the components of $\beta$. $\lambda$ is the tuning constant. The $\ell_1$ norm is known to induce sparsity of the learned $\beta$, so that only a small number of components of $\beta$ are non-zero. We then select the components of $(f_1', f_2')$ whose corresponding components of $\beta$ is non-zero, and form the vector $f = s(f_1', f_2')$, where $s()$ stands for feature selection. 

(4) Bayesian learning. After obtaining $f$, we then fit a Bayesian logistic regression on $\{(f, R_i)\}$ using BART. The log posterior distribution is $\log p(w|D) = - \sum_D \log(1 + \exp(-f^T w)) + \log p(w)$, where $p(w)$ is the prior distribution of the weight parameter $w$. We approximate $p(w|D)$ by a variational posterior $q_\phi(w)$ using the variational Bayes approach. 

The whole model can be considered a multi-layer network, where (1)-(4) above are the four layers of feature extraction, feature aligning, feature selection, and relation prediction. If we have big training data, we may train the whole model end-to-end. However, with smaller training data, we may separate the learning of the four layers. While layer (1) has to be learned from long term experience and big data, layers (2)-(4) can be learned from short term experience and small data. 




\end{document}
