n_gram_model.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# library\n",
    "import math"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Lidstone Smoothing\n",
    "class Lidstone_smoothing:\n",
    "    def __init__(self, dev_data, k):\n",
    "\n",
    "        self.dev_data = dev_data\n",
    "\n",
    "        # log10 probability of each 3 words phase\n",
    "        self.hash = {}\n",
    "\n",
    "        # para, k=1 is Laplacian Smoothing\n",
    "        self.k = k\n",
    "\n",
    "        # len of dev_data\n",
    "        self.len = len(self.dev_data)\n",
    "\n",
    "    def smoothing(self, hash2):\n",
    "        for i in range(2, self.len):\n",
    "            # the previous two words\n",
    "            prefix = self.dev_data[i-2] + ' ' + self.dev_data[i-1]\n",
    "            # 3 words phase\n",
    "            tmp = self.dev_data[i-2] + ' ' + self.dev_data[i-1] + ' '  + self.dev_data[i]\n",
    "            # prefix not in hash2\n",
    "            if (prefix not in hash2):\n",
    "                pass\n",
    "            elif (tmp not in hash2[prefix]):\n",
    "                hash2[prefix][tmp] = 0\n",
    "\n",
    "        for key2 in hash2:\n",
    "            # number of str start in prefix \"key2\"\n",
    "            v = len(hash2[key2].keys())\n",
    "            m = sum(hash2[key2].values())\n",
    "            for key3 in hash2[key2]:\n",
    "                # Lidstone Smoothing\n",
    "                self.hash[key3] = math.log10((hash2[key2][key3] + self.k) / (m + v*self.k))\n",
    "\n",
    "    def calculate_PPL(self):\n",
    "        # calculate the PPL\n",
    "        ppl = 0\n",
    "\n",
    "        # number of 3 words phase\n",
    "        cnt = 0\n",
    "\n",
    "        for i in range(2, self.len):\n",
    "            # 3 words phase\n",
    "            tmp = self.dev_data[i-2] + ' ' + self.dev_data[i-1] + ' '  + self.dev_data[i]\n",
    "            if (tmp not in self.hash):\n",
    "                continue\n",
    "            ppl += self.hash[tmp]\n",
    "            cnt += 1\n",
    "    \n",
    "        ppl *= -1\n",
    "        ppl /= cnt\n",
    "        ppl = 10**ppl\n",
    "\n",
    "        return ppl"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Jelinek-Mercer Smoothing\n",
    "class Interpolation_smoothing:\n",
    "    def __init__(self, dev_data, test_data, lambda_1, lambda_2):\n",
    "        self.dev_data = dev_data\n",
    "        self.test_data = test_data\n",
    "\n",
    "        # para lambda, learn from dev_set\n",
    "        self.lambda_1 = lambda_1\n",
    "        self.lambda_2 = lambda_2\n",
    "\n",
    "        # len of dev_data\n",
    "        self.len = len(self.dev_data)\n",
    "\n",
    "    # maxiter, stepSize and tol represent maxDepth of iteration, update step size and stop flag respectively\n",
    "    def train_paras(self, hash1, hash2, hash3, dev_data, maxiter, stepSize, tol):\n",
    "    \n",
    "        # gradient decent for lambda_2\n",
    "        def gd2(lambda_1, lambda_2):\n",
    "            res = 0\n",
    "\n",
    "            # number of derivative\n",
    "            cnt = 0\n",
    "\n",
    "            for i in range(2, len(dev_data)):\n",
    "                word3 = dev_data[i-2] + ' ' + dev_data[i-1] + ' '  + dev_data[i]\n",
    "                word2 = dev_data[i-1] + ' '  + dev_data[i]\n",
    "                word1 = dev_data[i]\n",
    "\n",
    "                # probability of different length phase\n",
    "                p3 = hash3[word3][1] if word3 in hash3 else 0\n",
    "                p2 = hash2[word2][1] if word2 in hash2 else 0\n",
    "                p1 = hash1[word1] if word1 in hash1 else 1           \n",
    "\n",
    "                # sum the derivative of each phase\n",
    "                res += (p3-lambda_1*p2-(1-lambda_1)*p1)/(lambda_2*p3 + lambda_1*(1-lambda_2)*p2 + (1-lambda_1)*(1-lambda_2)*p1)\n",
    "                cnt += 1\n",
    "\n",
    "            # get the avg of PPL derivative\n",
    "            res /= -cnt\n",
    "    \n",
    "            return res\n",
    "\n",
    "        # gradient decent for lambda_1\n",
    "        def gd1(lambda_1, lambda_2):\n",
    "            res = 0\n",
    "\n",
    "            # number of derivative\n",
    "            cnt = 0\n",
    "\n",
    "            for i in range(2, len(dev_data)):\n",
    "                word3 = dev_data[i-2] + ' ' + dev_data[i-1] + ' '  + dev_data[i]\n",
    "                word2 = dev_data[i-1] + ' '  + dev_data[i]\n",
    "                word1 = dev_data[i]\n",
    "\n",
    "                # probability of different length phase\n",
    "                p3 = hash3[word3][1] if word3 in hash3 else 0\n",
    "                p2 = hash2[word2][1] if word2 in hash2 else 0\n",
    "                p1 = hash1[word1] if word1 in hash1 else 1           \n",
    "\n",
    "                # sum the derivative of each phase\n",
    "                res += ((1-lambda_2)*p2-(1-lambda_2)*p1)/(lambda_2*p3 + lambda_1*(1-lambda_2)*p2 + (1-lambda_1)*(1-lambda_2)*p1)\n",
    "                cnt += 1\n",
    "\n",
    "            # get the avg of PPL derivative\n",
    "            res /= -cnt\n",
    "\n",
    "            return res\n",
    "\n",
    "\n",
    "        # fst train para lambda_1 and lambda2 on the dev_set\n",
    "\n",
    "        # EM algorithm - fst fix one var and update another, then fix another var and update the previous one\n",
    "        while (gd2(self.lambda_1, self.lambda_2)**2 >= tol or gd1(self.lambda_1, self.lambda_2)**2 >= tol):\n",
    "            # update lambda_2\n",
    "            cnt = 0\n",
    "            gd = gd2(self.lambda_1, self.lambda_2)\n",
    "            while (cnt <= maxiter and gd**2 >= tol):\n",
    "                # update lambda_2 based on the gradient\n",
    "                self.lambda_2 -= gd*stepSize\n",
    "\n",
    "                gd = gd2(self.lambda_1, self.lambda_2)\n",
    "                cnt += 1\n",
    "\n",
    "            # update lambda_1\n",
    "            cnt = 0\n",
    "            gd = gd1(self.lambda_1, self.lambda_2)\n",
    "            while (cnt <= maxiter and gd**2 >= tol):\n",
    "                # update lambda_1 based on the gradient\n",
    "                self.lambda_1 -= gd*stepSize\n",
    "\n",
    "                gd = gd1(self.lambda_1, self.lambda_2)\n",
    "                cnt += 1\n",
    "\n",
    "\n",
    "        print(\"--------------------------------------\")\n",
    "        print(\"lambda_1: {}\".format(self.lambda_1))\n",
    "        print(\"lambda_2: {}\".format(self.lambda_2))\n",
    "\n",
    "\n",
    "    def calculate_PPL(self, hash1, hash2, hash3):\n",
    "        # calculate the PPL\n",
    "        ppl = 0\n",
    "\n",
    "        for i in range(2,self.len):\n",
    "            word3 = self.test_data[i-2] + ' ' + self.test_data[i-1] + ' '  + self.test_data[i]\n",
    "            word2 = self.test_data[i-1] + ' '  + self.test_data[i]\n",
    "            word1 = self.test_data[i]\n",
    "\n",
    "            # probability of different length phase\n",
    "            p3 = hash3[word3][1] if word3 in hash3 else 0\n",
    "            p2 = hash2[word2][1] if word2 in hash2 else 0\n",
    "            p1 = hash1[word1] if word1 in hash1 else 1         \n",
    "\n",
    "            # interpolation\n",
    "            # lambda_1 and lambda_2 are learned from dev_set\n",
    "            ppl += math.log10(self.lambda_2*p3 + self.lambda_1*(1-self.lambda_2)*p2 + (1-self.lambda_1)*(1-self.lambda_2)*p1)\n",
    "\n",
    "        ppl *= -1\n",
    "        ppl /= (self.len-2)\n",
    "        ppl = 10**ppl\n",
    "        \n",
    "        return ppl\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Good Turing Discounting\n",
    "class discounting:\n",
    "    def __init__(self, hash2, test2, count):\n",
    "        # train_set\n",
    "        self.hash2 = hash2\n",
    "\n",
    "        # test_set\n",
    "        self.test2 = test2\n",
    "\n",
    "        # define the number of low frequency word\n",
    "        self.numlow = count\n",
    "\n",
    "        # record probability of 3 word phase\n",
    "        self.hash3 = {}\n",
    "\n",
    "    def discounting(self):\n",
    "        for key2 in hash2:\n",
    "            if (key2 not in self.test2):\n",
    "                continue\n",
    "\n",
    "            # find the maximum number of occurrences in train_set\n",
    "            values = list(self.hash2[key2].values())\n",
    "            m = max(values)\n",
    "\n",
    "            # vocabulary size\n",
    "            v = sum(self.hash2[key2].values())\n",
    "\n",
    "            # probability array\n",
    "            p = [0 for _ in range(m+1)]\n",
    "\n",
    "            # record the number of words of the same occurrences\n",
    "            cnt = [0 for _ in range(m+1)]\n",
    "\n",
    "            # record the number of words of the same occurrences\n",
    "            for word3 in self.test2[key2]:\n",
    "                if (word3 not in self.hash2[key2]):\n",
    "                    cnt[0] += 1\n",
    "                else:\n",
    "                    cnt[self.hash2[key2][word3]] += 1\n",
    "\n",
    "            # Good Turing Discounting for lower frequency word\n",
    "            n = min(m, self.numlow)\n",
    "            for i in range(n):\n",
    "                if (cnt[i] == 0):\n",
    "                    p[i] = 0\n",
    "                else:\n",
    "                    j = i+1\n",
    "                    while (j < n-1 and cnt[j]==0):\n",
    "                        j += 1\n",
    "                    p[i] = (j)*cnt[j]/cnt[i] / v\n",
    "\n",
    "            # the higher item retains the original probability\n",
    "            if (n < m+1): \n",
    "                for i in range(n, m+1):\n",
    "                    p[i] = cnt[i] / v\n",
    "\n",
    "            # normalize to ensure the sum of probability is 1\n",
    "            ss = sum(p)\n",
    "            if (ss == 0):\n",
    "                continue\n",
    "            for i in range(m+1):\n",
    "                p[i] /= ss\n",
    "\n",
    "            # record probability of 3 word phase\n",
    "            for word3 in self.test2[key2]:\n",
    "                if (word3 not in self.hash2[key2]):\n",
    "                    self.hash3[word3] = p[0]\n",
    "                else:\n",
    "                    self.hash3[word3] = p[self.hash2[key2][word3]]\n",
    "\n",
    "    def calculate_PPL(self):\n",
    "        # calculate the PPL\n",
    "        ppl = 0\n",
    "\n",
    "        cnt = 0\n",
    "\n",
    "        for key2 in self.test2:\n",
    "            for word3 in self.test2[key2]:\n",
    "                if (word3 not in self.hash3 or self.hash3[word3]==0):\n",
    "                    continue\n",
    "                ppl += math.log10(self.hash3[word3])\n",
    "                cnt += 1\n",
    "\n",
    "        ppl /= -cnt\n",
    "        ppl = 10**ppl\n",
    "        \n",
    "        return ppl"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "ename": "FileNotFoundError",
     "evalue": "[Errno 2] No such file or directory: 'hw1_dataset\\\\train_set.txt'",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mFileNotFoundError\u001b[0m                         Traceback (most recent call last)",
      "\u001b[1;32m~\\AppData\\Local\\Temp/ipykernel_7444/2308744538.py\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[0;32m      5\u001b[0m     \u001b[0mtrain_data\u001b[0m \u001b[1;33m=\u001b[0m \u001b[1;33m[\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      6\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 7\u001b[1;33m     \u001b[1;32mwith\u001b[0m \u001b[0mopen\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;34mr\"hw1_dataset\\train_set.txt\"\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;34m\"r\"\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;32mas\u001b[0m \u001b[0mf\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m      8\u001b[0m         \u001b[1;31m# read by line\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      9\u001b[0m         \u001b[1;32mfor\u001b[0m \u001b[0mline\u001b[0m \u001b[1;32min\u001b[0m \u001b[0mf\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;31mFileNotFoundError\u001b[0m: [Errno 2] No such file or directory: 'hw1_dataset\\\\train_set.txt'"
     ]
    }
   ],
   "source": [
    "# align\n",
    "length = 30\n",
    "if __name__ == '__main__':\n",
    "\n",
    "    train_data = []\n",
    "\n",
    "    with open(r\"hw1_dataset\\train_set.txt\", \"r\") as f:\n",
    "        # read by line\n",
    "        for line in f:\n",
    "            train_data.append(line)\n",
    "\n",
    "    # split by whitespace\n",
    "    train_data = train_data[0].split(\" \")\n",
    "\n",
    "    # begin and end symbol\n",
    "    train_data.insert(0, '<s>')\n",
    "    train_data.append('</s>')\n",
    "\n",
    "    dev_data = []\n",
    "\n",
    "    with open(r\"hw1_dataset\\dev_set.txt\",'r') as f:\n",
    "        # read by line\n",
    "        for line in f:\n",
    "            dev_data.append(line)\n",
    "\n",
    "    # split by whitespace\n",
    "    dev_data = dev_data[0].split(\" \")\n",
    "        \n",
    "    # insert begin and end symbols\n",
    "    dev_data.insert(0, '<s>')\n",
    "    dev_data.append('</s>')\n",
    "\n",
    "    test_data = []\n",
    "\n",
    "    with open(r\"hw1_dataset\\test_set.txt\",'r') as f:\n",
    "        # read by line\n",
    "        for line in f:\n",
    "            test_data.append(line)\n",
    "\n",
    "    # split by whitespace\n",
    "    test_data = test_data[0].split(\" \")\n",
    "        \n",
    "    # insert begin and end symbols\n",
    "    test_data.insert(0, '<s>')\n",
    "    test_data.append('</s>')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "40.482017237459445\n"
     ]
    }
   ],
   "source": [
    "    # test the Lidstone Smoothing algorithm\n",
    "\n",
    "    # record 3 words phase with its prefix\n",
    "    hash2 = {}\n",
    "\n",
    "    # 2-gram\n",
    "    for i in range(1,len(train_data)):\n",
    "        # concatenate two words \n",
    "        tmp = train_data[i-1] + ' ' + train_data[i]\n",
    "\n",
    "        # record the previous word\n",
    "        if (tmp not in hash2):\n",
    "            hash2[train_data[i-1] + ' ' + train_data[i]] = {}\n",
    "\n",
    "    # 3-gram\n",
    "    for i in range(2,len(train_data)):\n",
    "        # the previous two words\n",
    "        prefix = train_data[i-2] + ' ' + train_data[i-1]\n",
    "        tmp = train_data[i-2] + ' ' + train_data[i-1] + ' ' + train_data[i]\n",
    "        if (tmp not in hash2[prefix]):\n",
    "            hash2[prefix][tmp] = 1\n",
    "        else:\n",
    "            hash2[prefix][tmp] += 1\n",
    "    \n",
    "    # pass in the initial value of para k\n",
    "    instance1 = Lidstone_smoothing(dev_data, k=0.5)\n",
    "\n",
    "    # smoothing\n",
    "    instance1.smoothing(hash2)\n",
    "\n",
    "    # calculate the PPL of test_set\n",
    "    res1 = instance1.calculate_PPL()\n",
    "    print(res1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "--------------------------------------\n",
      "lambda_1: 0.5818039058034233\n",
      "lambda_2: 0.18286565390627954\n",
      "PPL of test_set: 410.50279117052855\n"
     ]
    }
   ],
   "source": [
    "    # fst train paras lambda_1 and lambda_2 on dev_set\n",
    "\n",
    "    # 1-gram\n",
    "    hash1 = {}\n",
    "\n",
    "    # 2-gram\n",
    "    hash2 = {}\n",
    "\n",
    "    # 3-gram\n",
    "    hash3 = {}\n",
    "\n",
    "    # 1-gram\n",
    "    for word in train_data:\n",
    "        if (word not in hash1):\n",
    "            hash1[word] = 1\n",
    "        else:\n",
    "            hash1[word] += 1\n",
    "\n",
    "    # 2-gram\n",
    "    for i in range(1,len(train_data)):\n",
    "        # concatenate two words \n",
    "        tmp = train_data[i-1] + ' ' + train_data[i]\n",
    "\n",
    "        # record the previous word\n",
    "        if (tmp not in hash2):\n",
    "            hash2[train_data[i-1] + ' ' + train_data[i]] = [train_data[i-1], 1]\n",
    "        else:\n",
    "            hash2[train_data[i-1] + ' ' + train_data[i]][1] += 1\n",
    "\n",
    "    # 3-gram\n",
    "    for i in range(2,len(train_data)):\n",
    "        # concatenate three words\n",
    "        tmp =  train_data[i-2] + ' ' + train_data[i-1] + ' ' + train_data[i]\n",
    "\n",
    "        if (tmp not in hash3):\n",
    "            hash3[tmp] = [train_data[i-2] + ' ' + train_data[i-1], 1]\n",
    "        else:\n",
    "            hash3[tmp][1] += 1\n",
    "    \n",
    "    # proportion\n",
    "    for key in hash3:\n",
    "        hash3[key][1] /= hash2[hash3[key][0]][1]\n",
    "\n",
    "    for key in hash2:\n",
    "        hash2[key][1] /= hash1[hash2[key][0]]\n",
    "\n",
    "    for key in hash1:\n",
    "        hash1[key] /= len(train_data)\n",
    "\n",
    "    # snd test the model on the test_set with paras lambda_1 and lambda_2\n",
    "\n",
    "    # pass in the initial values of lambda_1 and lambda_2 \n",
    "    instance2 = Interpolation_smoothing(dev_data, test_data, lambda_1=0.5, lambda_2=0.5)\n",
    "\n",
    "    # train lambda_1 and lambda_2 on the dev_set\n",
    "    instance2.train_paras(hash1, hash2, hash3, dev_data, maxiter=1000, stepSize=0.05, tol=1e-5)\n",
    "\n",
    "    # calculate PPL on the test_set\n",
    "    res2 = instance2.calculate_PPL(hash1, hash2, hash3)\n",
    "    print(\"PPL of test_set: {}\".format(res2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ppl for discounting: 68.0130117421328\n"
     ]
    }
   ],
   "source": [
    "    # test the Good Turing Discounting algorithm\n",
    "\n",
    "    # record 3 words phase with its prefix\n",
    "    hash2 = {}\n",
    "\n",
    "    # 2-gram\n",
    "    for i in range(len(train_data)-1):\n",
    "        # concatenate two words \n",
    "        tmp = train_data[i]\n",
    "\n",
    "        # record the previous word\n",
    "        if (tmp not in hash2):\n",
    "            hash2[train_data[i]] = {}\n",
    "\n",
    "    # 3-gram\n",
    "    for i in range(1,len(train_data)):\n",
    "        # the previous two words\n",
    "        prefix = train_data[i-1]\n",
    "        tmp = train_data[i-1] + ' ' + train_data[i]\n",
    "        if (tmp not in hash2[prefix]):\n",
    "            hash2[prefix][tmp] = 1\n",
    "        else:\n",
    "            hash2[prefix][tmp] += 1\n",
    "\n",
    "    # record 3 words phase with its prefix\n",
    "    test2 = {}\n",
    "\n",
    "    # 2-gram\n",
    "    for i in range(len(test_data)-1):\n",
    "        # concatenate two words \n",
    "        tmp = test_data[i]\n",
    "\n",
    "        # record the previous word\n",
    "        if (tmp not in test2):\n",
    "            test2[test_data[i]] = {}\n",
    "\n",
    "    # 3-gram\n",
    "    for i in range(1,len(test_data)):\n",
    "        # the previous two words\n",
    "        prefix = test_data[i-1]\n",
    "        tmp = test_data[i-1] + ' ' + test_data[i]\n",
    "        if (tmp not in test2[prefix]):\n",
    "            test2[prefix][tmp] = 1\n",
    "        else:\n",
    "            test2[prefix][tmp] += 1\n",
    "\n",
    "    # pass in the train_set, the test_set and the number of low frequency word\n",
    "    instance3 = discounting(hash2, test2, count=10)\n",
    "\n",
    "    # Good Turing Discounting\n",
    "    instance3.discounting()\n",
    "\n",
    "    # calculate the PPL of test_set\n",
    "    res3 = instance3.calculate_PPL()\n",
    "    print(\"ppl for discounting: {}\".format(res3))"
   ]
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "91383ca01c745ff4f6ec61074eff8198c75652caf775a5c5ee2312577bd67511"
  },
  "kernelspec": {
   "display_name": "Python 3.8.7 64-bit",
   "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.8.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}