coursera/text-mining-and-analytics/notes/week2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Week 2 Overview\n",
    "\n",
    "During this week's lessons, you will learn more about word association mining with a particular focus on mining the other basic form of word association (i.e., syntagmatic relations), and start learning topic analysis with a focus on techniques for mining one topic from text."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Goals and Objectives\n",
    "\n",
    "After you actively engage in the learning experiences in this module, you should be able to:\n",
    "\n",
    "* Explain how to discover syntagmatic relations from text data\n",
    "* Explain the computation task of mining and analyzing topics in text data, particularly its input and the expected output.\n",
    "* Explain the problems with defining a topic as just one term when mining and analyzing topics in text data.\n",
    "* Explain the limitations of using one term to represent a topic and how they can be addressed by representing a topic as a distribution over words.\n",
    "* Explain basic concepts in statistical language models such as “language model”, “unigram language model”, “likelihood”, Maximum Likelihood estimate.\n",
    "* Explain how to mine one topic from a text document, i.e., estimate a unigram language model"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Key Concepts\n",
    "\n",
    "* Entropy\n",
    "* Conditional entropy\n",
    "* Mutual information\n",
    "* Topic and coverage of topic\n",
    "* Language model\n",
    "* Generative model\n",
    "* Unigram language model\n",
    "* Word distribution\n",
    "* Background language model\n",
    "* Parameters of a probabilistic model\n",
    "* Likelihood\n",
    "* Bayes rule\n",
    "* Maximum likelihood estimation\n",
    "* Prior and posterior distributions\n",
    "* Bayesian estimation & inference\n",
    "* Maximum a posteriori (MAP) estimate\n",
    "* Prior model\n",
    "* Posterior mode"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Guiding Questions\n",
    "\n",
    "Develop your answers to the following guiding questions while watching the video lectures throughout the week."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### What is entropy? For what kind of random variables does the entropy function reach its minimum and maximum, respectively?\n",
    "\n",
    "Let:<br>\n",
    "\n",
    "(\\*) **Probabilies** here means frequencies of outcomes in random experiments.<br>\n",
    "\n",
    "(\\*) An **Ensemble** \\\\(X\\\\) is a triple \\\\((x, Ax, Px)\\\\), where the *outcome* \\\\(x\\\\) is the value of a random variable, which takes on one of a set of possible values, \\\\(Ax=(a_1, a_2, ..., a_i, ..., a_I)\\\\), having probabilities \\\\(Px(p_1, p_2, ..., p_I)\\\\), with \\\\(P(x=a_i)=p_i,p_i \\geq 0\\\\) and \\\\(\\sum_{a_i \\in Ax} P(x=a_i)=1\\\\).<br>\n",
    "\n",
    "(\\*) The Shannon **Information Content** of an outcome \\\\(x\\\\) is defined to be:<br>\n",
    "\n",
    "$$\\eqalign{\n",
    "h(x) &= log_2 \\frac{1}{P(x)} \\ \\text{bits}\\\\\n",
    "     &= -log_2 P(x) \\ \\text{bits}\n",
    "}$$\n",
    "<br>\n",
    "\n",
    "Then:<br>\n",
    "\n",
    "(\\*) The **Entropy of an ensemble** \\\\(X\\\\) is defined to be the average Shannon information content of an outcome:<br>\n",
    "$$H(X) = -\\sum\\limits_{x \\in Ax} P(x) \\ log_2 P(x) \\ \\text{bits}$$<br><br>\n",
    "\\\\(H(X)\\\\) is **minimum** when \\\\(P(x)=0\\\\), so that:<br>\n",
    "$$H(X) = - \\sum\\limits_{x \\in Ax} 0 * log_2 0 \\equiv 0$$\n",
    "\n",
    "since \\\\(lim_{\\theta \\rightarrow 0^-} -\\theta log_2 \\theta = 0\\\\) and \\\\(lim_{\\theta \\rightarrow 0^+} \\theta log_2 1/\\theta = 0\\\\)<br><br>\n",
    "\\\\(H(X)\\\\) is **maximum** when \\\\(P(x)=1/|x|\\\\), so that:<br>\n",
    "$$H(X) = - \\sum\\limits_{x \\in Ax} \\frac{1}{|x|} * log_2 \\frac{1}{|x|} = log_2 \\frac{1}{|x|}$$\n",
    "<br><br>\n",
    "\n",
    "For further explanation, please read [Information Theory Inference Learning Algorithms](https://www.amazon.com/Information-Theory-Inference-Learning-Algorithms/dp/0521642981) at page 32.\n",
    "<br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### What is conditional entropy?<br><br>\n",
    "\n",
    "Let:<br>\n",
    "\n",
    "(\\*) **Joint probability** is probability that event \\\\(X\\\\) and event \\\\(Y\\\\) occurred together at the same time:<br>\n",
    "$$\\eqalign{\n",
    "P(X, Y) &= \\frac{\\sum\\limits_{y \\in A_x} y=Y}{N}\\\\\n",
    "P(X, Y) &= \\frac{f_X(Y)}{N}\n",
    "}$$<br>\n",
    "\n",
    "(\\*) **Conditional probability** beautifuly defined by [Kolmogorov](https://en.wikipedia.org/wiki/Andrey_Kolmogorov) is projection of \\\\(f_X(Y)\\\\) in the space \\\\(Y\\\\):\n",
    "$$\\eqalign{\n",
    "P(X|Y) &= \\frac{f_X(Y)}{Y}\\\\\n",
    "&= \\frac{P(X,Y)/N}{P(Y)/N}\\\\\n",
    "&= \\frac{P(X,Y)}{P(Y)}\n",
    "}$$<br>\n",
    "\n",
    "(\\*) **Bayes rule** tells us about corelation between joint probability and conditional probability:<br>\n",
    "$$P(X|Y)P(Y) = P(X,Y) = P(Y|X)P(X)$$<br>\n",
    "\n",
    "(\\*) **Joint entropy** is entropy of joint ensembles \\\\(X\\\\) and \\\\(Y\\\\):\n",
    "$$\\eqalign{\n",
    "H(X,Y) &= -\\sum\\limits_{x \\in A_x}\\sum\\limits_{y \\in A_y} P(x,y) \\ log_2 \\ P(x,y)\\\\\n",
    "       &= -E \\ log_2 \\ P(X,Y)\n",
    "}$$<br>\n",
    "\n",
    "Then:<br>\n",
    "\n",
    "(\\*) **Conditional entropy** is entropy of conditional ensembles \\\\(X\\\\) and \\\\(Y\\\\) or by expand Kolmogorov definition, how much bits we need to encode uncertainty of each \\\\(P(y, x) \\ \\text{in} \\ 1/P(x|y) \\ bits \\ \\text{where} \\ yx \\in A_yA_x\\\\):<br>\n",
    "$$\\eqalign{\n",
    "H(X|Y) &= \\sum\\limits_{y \\in A_y} P(y) \\ H(X|Y=y)\\\\\n",
    "       &= - \\sum\\limits_{y \\in A_y} P(y) \\sum\\limits_{x \\in A_x} P(x|y) \\ log_2 \\ P(x|y)\\\\\n",
    "       & \\text{apply bayes rule}\\\\\n",
    "       &= - \\sum\\limits_{y \\in A_y}\\sum\\limits_{x \\in A_x} P(y,x) \\ log_2 \\ P(x|y)\\\\\n",
    "       &= - E \\ log_2 \\ P(X|Y)\n",
    "}$$<br>\n",
    "\n",
    "For further explanation, please read [Elements of Information Theory](https://www.amazon.com/Elements-Information-Theory-Telecommunications-Processing/dp/0471241954) at page 16-17.\n",
    "<br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### What is the relation between conditional entropy H(X|Y) and entropy H(X)? Which is larger?<br><br>\n",
    "Let:<br>\n",
    "\n",
    "(a) \\\\(H(X)\\\\) is uncertainty of \\\\(X\\\\) encoded in \\\\(1/P(X) \\ bits\\\\), so that \\\\(H(X) \\leq log_2 1/P(X)\\\\)<br><br>\n",
    "\n",
    "(b) \\\\(H(Y)\\\\) is uncertainty of \\\\(Y\\\\) encoded in \\\\(1/P(Y) \\ bits\\\\), so that \\\\(H(Y) \\leq log_2 1/P(Y)\\\\)<br><br>\n",
    "\n",
    "(c) \\\\(H(X,Y)\\\\) is joint of uncertainties of \\\\(X \\cap Y\\\\) in \\\\(1/P(X,Y) \\ bits\\\\), so that \\\\(H(X,Y) \\leq log_2 1/P(X,Y)\\\\)<br><br>\n",
    "\n",
    "(d) \\\\(H(Y,X)\\\\) is joint of uncertainties of \\\\(Y \\cap X\\\\) in \\\\(1/P(Y,X) \\ bits\\\\), so that \\\\(H(Y,X) \\leq log_2 1/P(Y,X)\\\\)<br><br>\n",
    "\n",
    "We know that:<br>\n",
    "\n",
    "(\\*) \\\\(H(X|Y)\\\\) is conditional of uncertainties of \\\\(X\\\\) given known event of \\\\(Y\\\\) in \\\\(1/P(X|Y) \\ bits\\\\), so that \\\\(H(X|Y) \\leq log_2 1/P(X|Y)\\\\)<br><br>\n",
    "\n",
    "(\\*) Based on bayes rule, if we know \\\\(H(Y,X)\\\\) then we know about \\\\(H(X|Y)\\\\) and \\\\(H(Y)\\\\):\n",
    "$$\\eqalign{\n",
    "H(Y,X) &= -\\sum\\limits_{y \\in A_y} \\sum\\limits_{x \\in A_x} P(y, x) \\ log_2 \\ P(y,x)\\\\\n",
    "       &= -\\sum\\limits_{y \\in A_y} \\sum\\limits_{x \\in A_x} P(y, x) \\ log_2 \\ P(y) \\ P(x|y)\\\\\n",
    "       &= -\\sum\\limits_{y \\in A_y} \\sum\\limits_{x \\in A_x} P(y,x) \\ log_2 \\ P(y) -\\sum\\limits_{y \\in A_y} \\sum\\limits_{x \\in A_x} P(y,x) \\ log_2 \\ P(x|y)\\\\\n",
    "       &= -\\sum\\limits_{y \\in A_y} P(y) \\ log_2 \\ P(y) - \\sum\\limits_{y \\in A_y} \\sum\\limits_{x \\in A_x} P(y,x) \\ log_2 \\ P(x|y)\\\\\n",
    "       &= H(Y) + H(X|Y)\n",
    "}$$<br>\n",
    "\n",
    "(\\*) Rule above also apply for \\\\(H(X,Y)\\\\):\n",
    "$$H(X,Y) = H(X) + H(Y|X)$$<br>\n",
    "Then:<br>\n",
    "\n",
    "(\\*) \\\\(H(X|Y) \\leq H(Y) \\leq H(Y,X)\\\\)<br>\n",
    "\n",
    "(\\*) \\\\(H(Y|X) \\leq H(X) \\leq H(X,Y)\\\\)<br>\n",
    "\n",
    "(\\*) This innequalities will be disscussed further in mutual information.\n",
    "<br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### How can conditional entropy be used for discovering syntagmatic relations?<br><br>\n",
    "\n",
    "Let:<br>\n",
    "\n",
    "(\\*) An **Ensemble W** is a triple \\\\((w, A_w, P_w)\\\\) where *outcome* of word \\\\(w\\\\) is the random word, which takes on one of a set of possible values, \\\\(A_w = (a_1, a_2, a_3, ..., a_I)\\\\), having probabilities \\\\(P_w = (p_1, p_2, p_3, ..., p_I)\\\\), which \\\\(P(w=a_i)=p_i, \\ p_i \\geq 0\\\\) and \\\\(\\sum_{a_i \\in A_w} P(w=a_i) = 1\\\\)<br><br>\n",
    "\n",
    "(\\*) \\\\(WORDS\\\\) is set of words \\\\(\\{w_1, w_2, w_3, ..., w_I\\}\\\\)<br><br>\n",
    "\n",
    "(\\*) \\\\(WORDS^x\\\\) subset of \\\\(WORDS\\\\) which contains unknown words, such that \\\\(\\{w_1, w_2, ..., w_H \\ | \\ w \\in WORDS^x \\}, WORDS^x \\subset WORDS\\\\)<br><br>\n",
    "\n",
    "(\\*) \\\\(WORDS^{-x}\\\\) is reduced set of \\\\(WORDS\\\\) which contains known words, such that \\\\(\\{w_1, w_2, ..., w_J \\ | \\ w_j \\notin WORDS^x \\}\\\\)<br><br>\n",
    "We want to know:<br>\n",
    "\n",
    "(\\*) Information about unkown word \\\\(w_h\\\\) given by set of known words \\\\(\\{w \\ | \\ w_j \\in WORDS^{-x}\\}\\\\), such that \\\\(H(w_h \\ | \\ w_j)\\\\)<br><br>\n",
    "Assume:<br>\n",
    "\n",
    "(\\*) \\\\(A_w\\\\) is boolean values indicate whether each word \\\\(\\{w_i \\ | \\ w_i \\in WORDS\\}\\\\) is present or not, such that \\\\(A_w = \\{0, 1\\}\\\\)<br><br>\n",
    "Then:<br>\n",
    "\n",
    "(\\*) If the word \\\\(w_j\\\\) is known always present, then information about unknown word \\\\(w_h\\\\):<br>\n",
    "$$H(w_h \\ | \\ w_j=1) = -\\sum\\limits_{a_i \\in A_w} P(w_h = a_i \\ | \\ w_j = 1) \\ log_2 \\ P(w_h = a_i \\ | \\ w_j = 1)$$\n",
    "<br>\n",
    "\n",
    "(\\*) If the word \\\\(w_j\\\\) is known always not present, then information about unknown word \\\\(w_h\\\\):<br>\n",
    "$$H(w_h \\ | \\ w_j=0) = -\\sum\\limits_{a_i \\in A_w} P(w_h = a_i \\ | \\ w_j = 0) \\ log_2 \\ P(w_h = a_i \\ | \\ w_j = 0)$$\n",
    "<br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### What is mutual information I(X;Y)? How is it related to entropy H(X) and conditional entropy H(X|Y)?<br><br>\n",
    "\n",
    "Let:<br>\n",
    "\n",
    "(\\*) \\\\(P(x)\\\\) and \\\\(Q(y)\\\\) are two different probability distributions defined on the set of possible values, \\\\(Ax=(a_1, a_2, ..., a_i, ..., a_I)\\\\).<br><br>\n",
    "\n",
    "(\\*) The **Relative Entropy** or **Kullback-Leibler divergence** between \\\\(P(x)\\\\) and \\\\(Q(x)\\\\) is:<br>\n",
    "$$\\eqalign{\n",
    "D_{KL}(P||Q) &= \\sum\\limits_{x} P(x) log_2 \\frac{P(x)}{Q(x)}\\\\\n",
    "             &= E_p log_2 \\frac{P(x)}{Q(x)}\n",
    "}$$\n",
    "\n",
    "which satisfies **Gibbs' inequality**:<br>\n",
    "$$D_{KL}(P||Q) \\geq 0$$\n",
    "\n",
    "with equality if only if \\\\(P = Q\\\\)<br>\n",
    "and if \\\\(P(x) > 0\\\\) and \\\\(Q(x) = 0\\\\), then \\\\(D_{KL}(P||Q) = \\infty\\\\)<br><br>\n",
    "\n",
    "(\\*) **Kullback-Leibler divergence** is asymetric distance, such that:<br>\n",
    "$$D_{KL}(P||Q) \\neq D_{KL}(Q||P)$$<br>\n",
    "\n",
    "(\\*) **Mutual Information** \\\\(I(X; Y)\\\\) is the relative entropy between the joint distribution and the product distribution \\\\(p(x)p(y)\\\\):<br>\n",
    "$$\\eqalign{\n",
    "I(X;Y) &= \\sum\\limits_{x \\in Ax}\\sum\\limits_{y \\in Ay} P(x,y) log_2 \\frac{P(x,y)}{P(x)P(y)}\\\\\n",
    "       &= D_{LK}(P(x,y)||P(x)P(y))\\\\\n",
    "       &= E_{P(x,y)} log_2 \\frac{P(X,Y)}{P(X)P(Y)}\n",
    "}$$\n",
    "<br>\n",
    "\n",
    "Then:<br>\n",
    "\n",
    "(\\*) **Relationship between Entropy and Mutual Information** can be revealed by decomposing mutual information formula:<br>\n",
    "$$\\eqalign{\n",
    "I(X;Y) &= \\sum\\limits_{x,y} P(x,y) log_2 \\frac{P(x,y)}{P(x)P(y)}\\\\\n",
    "       &= \\sum\\limits_{x,y} P(x,y) log_2 \\frac{P(x|y)}{p(x)}\\\\\n",
    "       &= -\\sum\\limits_{x,y} P(x,y) log_2 P(x) + \\sum\\limits_{x,y} P(x,y) log_2 P(x|y)\\\\\n",
    "       &= -\\sum\\limits_{x} P(x) log_2 P(x) - \\big(-\\sum\\limits_{x,y} P(x,y) log P(x|y) \\big)\\\\\n",
    "       &= H(X) - H(X|Y)\n",
    "}$$<br>\n",
    "\n",
    "For further explanation, please read [Elements of Information Theory](https://www.amazon.com/Elements-Information-Theory-Telecommunications-Processing/dp/0471241954) at page 19-30.\n",
    "<br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### What’s the minimum value of I(X;Y)? Is it symmetric?<br><br>\n",
    "\n",
    "(\\*) Mutual information has symetry relationship, such that:<br>\n",
    "$$I(X;Y)=H(X)-H(X|Y)=H(Y)-H(Y|X)=I(Y;X)$$<br>\n",
    "\n",
    "**Proof**: Let expand previous mutual information equation with respect tu \\\\(Y\\\\):<br>\n",
    "$$\\eqalign{\n",
    "I(X;Y) &= \\sum\\limits_{x,y}P(x,y) log_2 \\frac{P(x,y)}{P(x)P(y)}\\\\\n",
    "       &= \\sum\\limits_{x,y}P(x,y) log_2 \\frac{P(x,y)}{P(x)} - \\sum\\limits_{x,y}P(x,y) log_2 P(y)\\\\\n",
    "       &= \\sum\\limits_{x,y}P(x) P(y|x) log_2 P(y|x) - \\sum\\limits_{x,y} log_2 P(y) P(x,y)\\\\\n",
    "       &= \\sum\\limits_{x} P(x) \\big( \\sum\\limits_{y} P(y|x) log_2 P(y|x) \\big) - \\sum\\limits_{y} log_2 P(y)\\\\\n",
    "       &= -H(Y|X) + H(Y)\\\\\n",
    "       &= H(Y) - H(Y|X)\n",
    "}$$<br>\n",
    "\n",
    "(\\*) Since:<br>\n",
    "$$\\eqalign{\n",
    "H(X,Y) &= H(X) + H(Y|X)\\\\\n",
    "H(Y,X) &= H(Y) + H(X|Y)\n",
    "}$$\n",
    "\n",
    "thus,we have:<br>\n",
    "$$I(X;Y) = H(X) + H(Y) - H(X,Y)$$<br>\n",
    "\n",
    "(\\*) Follow the Gibb's inequality on Relative Entropy, Mutual Information satisfies Jensen's inequality:<br>\n",
    "$$I(X;Y) \\geq 0$$<br>\n",
    "\n",
    "with equality if only if \\\\(X\\\\) and \\\\(Y\\\\) are independent.\n",
    "<br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### For what kind of X and Y, does mutual information I(X;Y) reach its minimum? For a given X, for what Y does I(X;Y) reach its maximum?<br><br>\n",
    "\n",
    "(\\*) Since mutual information is non-negative, then the minimum value is \\\\(I(X;Y) = 0\\\\).<br>\n",
    "\n",
    "(\\*) Mutual information reach its minimum if only if \\\\(X\\\\) and \\\\(Y\\\\) are independent, such that \\\\(P(x,y) = p(x)p(y)\\\\):<br>\n",
    "$$\\eqalign{\n",
    "I(X;Y) &= \\sum\\limits_{x,y}P(x,y) log_2 \\frac{P(x,y)}{P(x)P(y)}\\\\\n",
    "       &= \\sum\\limits_{x,y}P(x,y) log_2 1\\\\\n",
    "       &= \\sum\\limits_{x,y}P(x,y) 0\\\\\n",
    "       &= 0\n",
    "}$$\n",
    "<br>\n",
    "\n",
    "(\\*) Let expand the mutual information inequality into a throrem:<br>\n",
    "$$0 \\leq I(X;Y) = H(X) - H(X|Y)$$\n",
    "\n",
    "the theorem above tells us that knowing another random variable \\\\(Y\\\\) can only reduce the uncertainty in \\\\(X\\\\). Note that this is true only on the average. Specially, \\\\(H(X|Y=y)\\\\) may be greate than or less than or equal to \\\\(H(x)\\\\), but on the average \\\\(H(X|Y) = \\sum_y P(y) H(X|Y=y) \\leq H(X)\\\\).\n",
    "<br><br>\n",
    "\n",
    "(\\*) Mutual information also reach its maximum if only if it contains itself, such that \\\\(I(X;X) = H(X)\\\\)\n",
    "<br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Why is mutual information sometimes more useful for discovering syntagmatic relations than conditional entropy?<br><br>\n",
    "\n",
    "1. Conditional entropy only compute each pair of word probability and not comparable, such as:\n",
    "$$H(w_h \\ | \\ w_j) \\neq H(w_i \\ | \\ w_j)$$\n",
    "    <br>\n",
    "\n",
    "2. Mutual information is more general than conditional entropy: Given two probabiliy distribution \\\\(P(X)\\\\) and \\\\(Q(X)\\\\), know one of them wen can also know all of them, such that:\n",
    "$$I(X;Y)=H(X)-H(X|Y)=H(Y)-H(Y|X)=I(Y;X)$$\n",
    "<br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### What is a topic?<br><br>\n",
    "\n",
    "Topic is main idea of a document.\n",
    "\n",
    "<br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### How can we define the task of topic mining and analysis computationally? What’s the input? What’s the output?<br><br>\n",
    "\n",
    "Input:<br>\n",
    "\n",
    "(\\*) \\\\(N\\\\) indicate number of collections.<br>\n",
    "\n",
    "(\\*) \\\\(C=\\{d_1, ..., d_N\\}\\\\) is a collection of document<br>\n",
    "\n",
    "(\\*) \\\\(k\\\\) indicate desired number of topics.<br><br>\n",
    "\n",
    "Output:<br>\n",
    "\n",
    "(\\*) \\\\(k\\\\) number topics \\\\(\\{\\theta_1, ..., \\theta_k\\}\\\\)<br>\n",
    "\n",
    "(\\*) Coverage of topics in each document: \\\\(d_i = \\{\\Pi_{i1}, ..., \\Pi_{ik}\\}\\\\)<br>\n",
    "\n",
    "(\\*) \\\\(\\Pi_{ij}\\\\) is probability of \\\\(d_i\\\\) covering topic \\\\(\\theta_j\\\\), such as:\n",
    "$$\\sum\\limits_{j=1}^k \\Pi_{ij} = 1$$\n",
    "<br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### How can we heuristically solve the problem of topic mining and analysis by treating a term as a topic? What are the main problems of such an approach?<br><br>\n",
    "\n",
    "There are step by step approach to do topic mining and analysis by treating a term as a topic:<br>\n",
    "\n",
    "- Parse text in colection \\\\(C\\\\) to obtain candidate term, e.g: term = word or term = phrase.<br>\n",
    "- Design a term scoring scoring function, e.g: TF-IDF, domain specific heuristics (favor title words, hashtag, etc).<br>\n",
    "- Pick \\\\(k\\\\) terms with the highest scores, but try to minimize redudancy, e.g: Using WordNet to find synonyms, latent semantic indexing to find corelation between words.\n",
    "<br><br>\n",
    "\n",
    "Problem with \"term as topic\":<br>\n",
    "- Does not have broad vocabulary coverage, e.g: related words.<br>\n",
    "- Can not detect word ambiguity, e.g: \"basketball star\" vs \"star in the sky\".\n",
    "<br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### What are the benefits of representing a topic by a word distribution?<br><br>\n",
    "- Used multiple words to describe complicated topic.\n",
    "- Used word weighting to model subtle semantic variations of a topic.\n",
    "<br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### What is a statistical language model? What is a unigram language model? How can we compute the probability of a sequence of words given a unigram language model?<br><br>\n",
    "- The statistical language model is model use probability distribution over word sequences. Alse called as generative model.\n",
    "- Unigram language model is a model which treat each word independently. Thus, a probability of text \"today is wed\" is:<br>\n",
    "$$P(\"\\text{today is wed}\") = P(\"\\text{today}\")P(\"\\text{is}\")P(\"\\text{wed}\")$$\n",
    "<br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### What is Maximum Likelihood estimate of a unigram language model given a text article?<br><br>\n",
    "\n",
    "- Maximum likehood is find the best probability \\\\(P\\\\) to describe a topic \\\\(\\theta\\\\), such that:\n",
    "$$\\hat{\\theta} = arg \\ max_{\\theta} P(X|\\theta)$$\n",
    "<br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### What is the basic idea of Bayesian estimation? What is a prior distribution? What is a posterior distribution? How are they related with each other? What is Bayes rule?<br><br>\n",
    "\n",
    "- The basic idea of Bayesia Estimation is find the best estimation based on initial probability. Or in another word, compute posterior believe based on priori knowledge about evidence, such that:\n",
    "\n",
    "$$\\eqalign{\n",
    "\\hat{\\theta} &= arg \\ max_{\\theta} P(\\theta|X)\\\\\n",
    "             &= arg \\ max_{\\theta} P(X|\\theta)P(\\theta)\n",
    "}$$\n",
    "\n",
    "<br>\n",
    "- \\\\(P(\\theta)\\\\) is Prior distribution.\n",
    "- \\\\(P(\\theta|X)\\\\) is posterior distribution.\n",
    "- \\\\(P(\\theta)\\\\) need to be defined before compute \\\\(P(\\theta|X)\\\\).\n",
    "- **Bayes rule** tells us about corelation between joint probability and conditional probability:<br>\n",
    "$$P(X|Y)P(Y) = P(X,Y) = P(Y|X)P(X)$$\n",
    "<br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Additional Readings and Resources\n",
    "\n",
    "* C. Zhai and S. Massung. Text Data Management and Analysis: A Practical Introduction to Information Retrieval and Text Mining, ACM and Morgan & Claypool Publishers, 2016. Chapters 13, 17."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}