# Question on word probability for hierarchical softmax used in natural language processing

I am reading the following paper: https://papers.nips.cc/paper/5021-distributed-representations-of-words-and-phrases-and-their-compositionality.pdf

On page 4 of the paper they describe the hierarchical softmax which is intended to reduce the computational complexity (I believe only during training time) of training a neural network to learn word vectors. The hierarchical softmax output layer is a balanced binary tree.

Here is the description given in the paper for computing $p(w\vert w_I)$ (where $w_I$ is the input word or set of words, and $w$ is the missing word we are trying to predict):

More precisely, each word $w$ can be reached by an appropriate path from the root of the tree. Let $n(w,j)$ be the $j$-th node on the path from the root to $w$, and let $L(w)$ be the length of this path, so $n(w,1)=root$ and $n(w,L(w))=w$. In addition, for any inner node $n$, let $ch(n)$ be an arbitrary fixed child of $n$ and let $\lbrack x \rbrack$ (can't figure out how to generate brackets used in paper) be $1$ if $x$ is true and $-1$ otherwise. Then the hierarchical softmax defines $p(w_O \vert w_I)$ as follows:

$$p(w\vert w_I) =\prod_{j=1}^{L(w)-1}\sigma(\lbrack n(w,j+1)=ch(n(w,j))\rbrack \cdot v_{n(w,j)}'^T v_{w_I})$$

where $\sigma(x) = 1/(1+\exp(-x))$.

Now, I understand that we are using the sigmoid function to essentially "squish" the dot products of our two vector arguments in values between $0$ and $1$ (i.e. probabilities). But, I don't understand the user of the indicator function in this equation. Going down the tree I feel like we should be multiplying probabilities at each branch, and somehow I know the indicator function must be "steering" us down the tree, but I cannot tell how. Intuitively, I feel like it would be more appropriate to have an indicator function that outputted $\sigma(x)$ or $(1-\sigma(x))$ based on left or right turns.

I have figured out my confusion.

The indicator function is $\lbrack x \rbrack$ is set to output a $-1$ or a $1$ based on the argument being false or true, respectively.

When the authors say "let $ch(n)$ be an arbitrary fixed child of node $n$", they mean arbitrary in the sense of left child or right child. But in order for our function to work, we must decide on this arbitrary decision. So, let us assume $ch(n)$ ouputs the left child of unit $n$.

Then as we go down our tree, if $\lbrack n(w,j+1) = ch(n(w,j))\rbrack = 1$ it means the next node on our path is to the left of the parent node $n(w,j)$ and if $\lbrack n(w,j+1) = ch(n(w,j))\rbrack = -1$ it means that the next node is to the right of $n(w,j)$.

As a result, since we defined $ch(n)$ to indicate the left child, all left probabilities are calculated as $\sigma(v_{n(w,j)}'^T\cdot v_{w_I})$ since $\lbrack n(w,j+1) = ch(n(w,j))\rbrack = 1$. Now we know that the probability on the right must then be $1 -\sigma(v_{n(w,j)}'^T\cdot v_{w_I})$. This is where I was confused since the function outputs $\sigma(-v_{n(w,j)}'^T\cdot v_{w_I})$. But let $a=v_{n(w,j)}'^T\cdot v_{w_I}$ and we can verify that $\sigma(-a)=1-\sigma(a)$.

We have $\sigma(a) = \frac{1}{1+e^{-a}}$, now observe that

\begin{align*} 1 - \sigma(a) &= \frac{1+e^{-a}}{1+e^{-a}}-\frac{1}{1+e^{-a}}\\ &=\frac{e^{-a}}{1+e^{-a}}\\ &=\frac{1}{e^a}\times \frac{1}{1+e^{-a}}\\ &=\frac{1}{1+e^a}\\ &=\frac{1}{1+e^{-(-a)}}\\ &=\sigma(-a). \end{align*}

Hence the function $$p(w\vert w_I) =\prod_{j=1}^{L(w)-1}\sigma(\lbrack n(w,j+1)=ch(n(w,j))\rbrack \cdot v_{n(w,j)}'^T v_{w_I})$$

simply multiplies probabilities along the branches corresponding to the path from the root node to the proper leaf node $w$.