main3_optimized_witth_question2_question3.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 100,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "HMM creating with: \n",
      "676 states 2\n",
      "26 states\n",
      "26 observations\n",
      "(676, 26)\n",
      "85866\n",
      "('indices_backs ', [0, 26, 52, 78, 104, 130, 156, 182, 208, 234, 260, 286, 312, 338, 364, 390, 416, 442, 468, 494, 520, 546, 572, 598, 624, 650])\n",
      "[ 0.0737595   0.03358292  0.01445854  0.12636204  0.03171798  0.01911042\n",
      "  0.02360164  0.07666518  0.04667943  0.00412103  0.00075436  0.02635365\n",
      "  0.04482147  0.0833636   0.06829738  0.00104772  0.02247011  0.06818563\n",
      "  0.05760365  0.02745725  0.09692808  0.01556912  0.01345971  0.02084963\n",
      "  0.00191384  0.00086612]\n",
      "init \n",
      "{'a': 3093, 'c': 1210, 'b': 1429, 'e': 880, 'd': 853, 'g': 490, 'f': 1035, 'i': 2352, 'h': 1048, 'k': 79, 'j': 54, 'm': 1171, 'l': 675, 'o': 2291, 'n': 757, 'q': 34, 'p': 1535, 's': 2172, 'r': 758, 'u': 288, 't': 5058, 'w': 1582, 'v': 136, 'y': 74, 'x': 3}\n",
      "'test'\n",
      "[('l', 'l'), ('e', 'e'), ('f', 'f'), ('t', 't'), ('i', 'i'), ('s', 's'), ('t', 't')]\n"
     ]
    }
   ],
   "source": [
    "import nltk\n",
    "from numpy import array, ones, zeros, multiply\n",
    "import numpy as np\n",
    "import sys\n",
    "import operator\n",
    "\n",
    "UNK = \"<unk>\"  # token to map all out-of-vocabulary words (OOVs)\n",
    "UNKid = 0      # index for UNK\n",
    "epsilon=1e-100\n",
    "special = \"<s>\"\n",
    "smoothing_trans = 1e-2\n",
    "smoothing_trans_2 = 1e-5\n",
    "\n",
    "class HMM:\n",
    "        def __init__(self, state_list, observation_list,\n",
    "                 transition_proba = None,\n",
    "                 observation_proba = None,\n",
    "                 initial_state_proba = None,\n",
    "                    transition_proba_2 = None,smoothing_obs = 0.01):\n",
    "            \n",
    "            '''\n",
    "            Debut taux erreur de 10% : (par pair)\n",
    "            Avec hmm ordre 1 : 7%\n",
    "            Avec hmm ordre 2 => 4%\n",
    "            HMM ordre 3 => 3%'''\n",
    "            \"\"\"\n",
    "            Builds a Hidden Markov Model\n",
    "            * state_list is the list of state symbols [q_0...q_(N-1)]\n",
    "            * observation_list is the list of observation symbols [v_0...v_(M-1)]\n",
    "            * transition_proba is the transition probability matrix\n",
    "                [a_ij] a_ij = Pr(Y_(t+1)=q_i|Y_t=q_j)\n",
    "            * observation_proba is the observation probablility matrix\n",
    "                [b_ki] b_ki = Pr(X_t=v_k|Y_t=q_i)\n",
    "            * initial_state_proba is the initial state distribution\n",
    "                [pi_i] pi_i = Pr(Y_0=q_i)\"\"\"\n",
    "            print \"HMM creating with: \"\n",
    "            self.N = len(state_list)       # number of states\n",
    "            self.M = len(observation_list) # number of possible emissions\n",
    "            #utile pour calcule la proba d un elelement en conaissant la classe observation_list\n",
    "            self.state_liste_2 = []\n",
    "            for e in state_list:\n",
    "                for f in state_list:\n",
    "                      self.state_liste_2.append((e,f))\n",
    "            self.N2 = len(self.state_liste_2)\n",
    "            print(str(self.N2) +\" states 2\")\n",
    "            print str(self.N)+\" states\"\n",
    "            print str(self.M)+\" observations\"\n",
    "            self.omega_Y_2 = self.state_liste_2\n",
    "            self.omega_Y = state_list\n",
    "            self.omega_X = observation_list\n",
    "            if transition_proba is None:\n",
    "                self.transition_proba = zeros( (self.N2, self.N), float) \n",
    "            else:\n",
    "                self.transition_proba=transition_proba\n",
    "            if transition_proba_2 is None:\n",
    "                self.transition_proba2 = zeros( (self.N, self.N), float) \n",
    "            else:\n",
    "                self.transition_proba2=transition_proba_2\n",
    "            print(self.transition_proba.shape)\n",
    "            if observation_proba is None:\n",
    "                self.observation_proba = zeros( (self.M, self.N), float) \n",
    "            else:\n",
    "                self.observation_proba=observation_proba\n",
    "            if initial_state_proba is None:\n",
    "                self.initial_state_proba = zeros( (self.N,), float ) \n",
    "            else:\n",
    "                self.initial_state_proba=initial_state_proba\n",
    "            self.make_indexes() # build indexes, i.e the mapping between token and int\n",
    "            self.smoothing_obs = smoothing_obs \n",
    "            \n",
    "        def make_indexes(self):\n",
    "            \"\"\"Creates the reverse table that maps states/observations names\n",
    "            to their index in the probabilities array\"\"\"\n",
    "            self.Y_index_2 = {}\n",
    "            self.Y_index = {}\n",
    "            for i in range(self.N2):\n",
    "                self.Y_index_2[self.omega_Y_2[i]] = i\n",
    "            for i in range(self.N):\n",
    "                self.Y_index[self.omega_Y[i]] =i\n",
    "            self.X_index = {}\n",
    "            for i in range(self.M):\n",
    "                self.X_index[self.omega_X[i]] = i\n",
    "      \n",
    "        def get_observationIndices( self, observations ):\n",
    "            \"\"\"return observation indices, i.e \n",
    "            return [self.O_index[o] for o in observations]\n",
    "            and deals with OOVs\n",
    "            \"\"\"\n",
    "            indices = zeros( len(observations), int )\n",
    "            k = 0\n",
    "            for o in observations:\n",
    "                if o in self.X_index:\n",
    "                    indices[k] = self.X_index[o]\n",
    "                else:\n",
    "                    indices[k] = UNKid\n",
    "                k += 1\n",
    "            return indices\n",
    "\n",
    "    \n",
    "        def data2indices(self, sent): \n",
    "            \"\"\"From one tagged sentence of the brown corpus: \n",
    "            - extract the words and tags \n",
    "            - returns two list of indices, one for each\n",
    "            -> (wordids, tagids)\n",
    "            \"\"\"\n",
    "            wordids = list()\n",
    "            tagids  = list()\n",
    "            for couple in sent:\n",
    "                wrd = couple[0]\n",
    "                tag = couple[1]\n",
    "                if wrd in self.X_index:\n",
    "                    wordids.append(self.X_index[wrd])\n",
    "                else:\n",
    "                    wordids.append(UNKid)\n",
    "                tagids.append(self.Y_index[tag])\n",
    "            return wordids,tagids\n",
    "            \n",
    "        def observation_estimation(self, pair_counts):\n",
    "            \"\"\" Build the observation distribution: \n",
    "                observation_proba is the observation probablility matrix\n",
    "                    [b_ki],  b_ki = Pr(X_t=v_k|Y_t=q_i)\"\"\"\n",
    "            # fill with counts\n",
    "            for pair in pair_counts:\n",
    "                wrd=pair[0]\n",
    "                tag=pair[1]\n",
    "                cpt=pair_counts[pair]\n",
    "                k = 0 # for <unk>\n",
    "                if wrd in self.X_index: \n",
    "                    k=self.X_index[wrd]\n",
    "                i = self.Y_index[tag]\n",
    "                self.observation_proba[k,i]=cpt\n",
    "            # normalize\n",
    "            self.observation_proba=self.observation_proba+self.smoothing_obs\n",
    "            self.observation_proba=self.observation_proba/self.observation_proba.sum(axis=0).reshape(1,self.N)\n",
    "            \n",
    "        \n",
    "        def transition_estimation(self, trans_counts):\n",
    "            print(sum(trans_counts.values()))\n",
    "            \"\"\" Build the transition distribution: \n",
    "                transition_proba is the transition matrix with : \n",
    "                [a_ij] a[i,j] = Pr(Y_(t+1)=q_i|Y_t=q_j)\n",
    "            \"\"\"\n",
    "            self.indices_backs = {}\n",
    "            # fill with counts\n",
    "            for pair in trans_counts:\n",
    "                i=self.Y_index[pair[1]]\n",
    "                j=self.Y_index_2[pair[0]]\n",
    "                self.transition_proba[j,i]=trans_counts[pair]\n",
    "            # normalize\n",
    "            self.transition_proba=self.transition_proba+smoothing_trans\n",
    "            self.transition_proba=self.transition_proba/self.transition_proba.sum(axis=0).reshape(1,self.N)\n",
    "            #construit les indices a vister en fonction de l etat actuel\n",
    "            for i in range(self.N2):\n",
    "                nouveau = self.omega_Y_2[i]\n",
    "                if not nouveau[1] in self.indices_backs:\n",
    "                    self.indices_backs[nouveau[1]] = []\n",
    "                self.indices_backs[nouveau[1]].append(i)\n",
    "            print(\"indices_backs \" , self.indices_backs['a'])\n",
    "            \n",
    "        #estime la proa \n",
    "        def transition_estimation_2(self, trans_counts):\n",
    "            for pair in trans_counts:\n",
    "                i=self.Y_index[pair[1]]\n",
    "                j=self.Y_index[pair[0]]\n",
    "                self.transition_proba2[j,i]=trans_counts[pair]\n",
    "            self.transition_proba2=self.transition_proba2+smoothing_trans_2\n",
    "            self.transition_proba2=self.transition_proba2/self.transition_proba2.sum(axis=0).reshape(1,self.N)\n",
    "            \n",
    "        def init_estimation(self, init_counts):\n",
    "            \"\"\"Build the init. distribution\"\"\"\n",
    "            # fill with counts\n",
    "            for tag in init_counts:\n",
    "                i=self.Y_index[tag]\n",
    "                self.initial_state_proba[i]=init_counts[tag]\n",
    "            # normalize\n",
    "            self.initial_state_proba=self.initial_state_proba/sum(self.initial_state_proba)\n",
    "             \n",
    "        \n",
    "        def supervised_training(self, pair_counts, trans_counts,init_counts,ctrans2,ctags):\n",
    "            \"\"\" Train the HMM's parameters. This function wraps everything\"\"\"\n",
    "            self.observation_estimation(pair_counts)\n",
    "            self.transition_estimation(trans_counts)\n",
    "            self.init_estimation(init_counts)\n",
    "            self.transition_estimation_2(ctrans2) \n",
    "            #print ctags\n",
    "            self.solo = zeros( (self.N,), float ) \n",
    "            for tags in ctags:\n",
    "                self.solo[self.Y_index[tags]] = ctags[tags]\n",
    "            self.solo=self.solo/sum(self.solo)\n",
    "            print(self.solo)\n",
    "                \n",
    "        def get_trans(self,k,indi_2):\n",
    "            #indi_2 : vers nouvel etat\n",
    "            # k :ancien etat\n",
    "            return  self.transition_proba[k,indi_2]\n",
    "            '''index_old = self.Y_index[self.omega_Y_2[k][1]]\n",
    "            if self.transition_proba[k,indi_2] > 0.0:\n",
    "                return (1/3.0) * self.transition_proba[k,indi_2] + (1/3.0) * self.transition_proba2[index_old,indi_2]+  (1/3.0)  * self.solo[indi_2]\n",
    "            index_old = self.Y_index[self.omega_Y_2[k][1]]\n",
    "            return (1/2.0) *self.transition_proba2[index_old,indi_2] + (1/2.0) * self.solo[indi_2]'''\n",
    "        \n",
    "        def viverbit(self,mots):\n",
    "            if(len(mots)==1):\n",
    "                return [(mots[0],mots[0])]\n",
    "            alpha = np.zeros((self.N2,len(mots)))\n",
    "            xi = np.zeros((self.N2,len(mots)))\n",
    "            #ajout unk\n",
    "            #init\n",
    "            #print(self.observation_estimation)\n",
    "            #--------------- Modele ordre 0 ----------------------------------------------------------\n",
    "            i = 0\n",
    "            if mots[0] in self.X_index:\n",
    "                i = self.X_index[mots[0]]\n",
    "            #remplissage de la toute premiere colonne naivement\n",
    "            #normalement c'est bon\n",
    "            test = [self.initial_state_proba[self.Y_index[p2]] * self.observation_proba[i,self.Y_index[p2]] for p1,p2 in self.omega_Y_2]\n",
    "            alpha[:,0] = test\n",
    "            #remplissage de la seconde colonne avec un modele de markov d ordre 1\n",
    "            #----------------Modele markov ordre 1 ---------------------------------------------------   \n",
    "            for j in range(self.N2):\n",
    "                i = 1\n",
    "                indi = 0\n",
    "                if mots[i] in self.X_index:\n",
    "                    indi = self.X_index[mots[i]]\n",
    "                indi_2 = 0\n",
    "                indi_2 = self.Y_index[self.omega_Y_2[j][1]]\n",
    "                \n",
    "                indi_trans = self.Y_index[self.omega_Y_2[j][0]]\n",
    "                maxs = 0\n",
    "                indi_max = 0\n",
    "                for k in self.indices_backs[self.omega_Y_2[j][0]]:\n",
    "                    tmp = alpha[k,i-1] * self.observation_proba[indi,self.Y_index[self.omega_Y_2[j][1]]] * self.transition_proba2[indi_trans,indi_2] \n",
    "                    if tmp > maxs:\n",
    "                        maxs = tmp\n",
    "                        indi_max = k\n",
    "                alpha[j,i] = maxs\n",
    "                xi[j,i] = indi_max\n",
    "            #---------------- Modele de markov d ordre 2 -----------------------------------------------\n",
    "            for i in range(2,len(mots)):\n",
    "                for j in range(self.N2):\n",
    "                    indi = 0\n",
    "                    if mots[i] in self.X_index:\n",
    "                        indi = self.X_index[mots[i]]\n",
    "                    indi_2 = 0\n",
    "                    indi_2 = self.Y_index[self.omega_Y_2[j][1]]\n",
    "                    maxs = 0\n",
    "                    indi_max = 0\n",
    "                    for k in self.indices_backs[self.omega_Y_2[j][0]]:\n",
    "                        #self.transition_proba[k,indi_2]\n",
    "                        tmp = alpha[k,i-1] * self.get_trans(k,indi_2)* self.observation_proba[indi,self.Y_index[self.omega_Y_2[j][1]]]\n",
    "                        if tmp > maxs:\n",
    "                            maxs = tmp\n",
    "                            indi_max = k\n",
    "                    alpha[j,i] = maxs\n",
    "                    xi[j,i] = indi_max\n",
    "            tags = []\n",
    "            debut = len(xi)\n",
    "            starting = np.argmax(alpha[:,len(xi[0])-1])\n",
    "            #print(self.omega_Y_2[starting],xi[self.Y_index_2[self.omega_Y_2[starting]],len(xi[0])-1])\n",
    "            #print(\"IMPRT \", self.omega_Y_2[int(xi[starting,len(xi[0])-1])])\n",
    "            #tags.append(starting)\n",
    "            #count = len(xi[0])\n",
    "            '''while len(tags) != len(mots):\n",
    "                count -= 1\n",
    "                new_index = xi[starting,count]\n",
    "                tags.append(new_index)\n",
    "                starting = new_index'''\n",
    "            tags = []\n",
    "            debut = len(xi)\n",
    "            starting = np.argmax(alpha[:,len(xi[0])-1])\n",
    "            tags.append(starting)\n",
    "            count = len(xi[0])\n",
    "            while len(tags) != len(mots):\n",
    "                count -= 1\n",
    "                new_index = xi[starting,count]\n",
    "                tags.append(new_index)\n",
    "                #print(self.omega_Y_2[int(starting)])\n",
    "                starting = new_index\n",
    "            tags = tags[::-1]\n",
    "            to_return  = []\n",
    "            count = 0\n",
    "            for i in tags:\n",
    "                to_return.append((mots[count],self.Y_index_2.keys()[self.Y_index_2.values().index(i)][1]))\n",
    "                count +=1\n",
    "            return to_return\n",
    "                 \n",
    "        def evaluate(self,test_data):\n",
    "            errors = 0\n",
    "            total = 0\n",
    "            erreur_false = 0\n",
    "            total_false = 0\n",
    "            erreur_2 = 0\n",
    "            \n",
    "            correction = 0\n",
    "            correction_totale = 0\n",
    "            \n",
    "            correction_ajout = 0\n",
    "            correction_ajout_totale = 0\n",
    "            \n",
    "            \n",
    "            for i in range(len(test_data)):\n",
    "                if i%50==0:\n",
    "                    print(i)\n",
    "                res = self.viverbit(map(operator.itemgetter(0), test_data[i]))\n",
    "      \n",
    "                \n",
    "#                 print \"Mot: \", test_data[i]\n",
    "#                 print \"Correction: \", res\n",
    "#                 print \n",
    "                \n",
    "                if sum([a!=b for a,b in test_data[i]])>0:\n",
    "                    total_false +=1 \n",
    "                    erreur_false += sum([a[1]!=b[1] for a,b in zip(res,test_data[i])])\n",
    "                for a,b in zip(res,test_data[i]):\n",
    "                    if(b[0] != b[1] and b[1]==a[1]):\n",
    "                        correction +=1\n",
    "                    if(b[1] == ''):\n",
    "                        correction_ajout += 1 if b[1] == a[1] else 0\n",
    "                        correction_ajout_totale += 1\n",
    "                        \n",
    "                    correction_totale +=1\n",
    "                erreur_2 += sum([a!=b for a,b in test_data[i]])\n",
    "                errors += sum([a[1]!=b[1] for a,b in zip(res,test_data[i])])\n",
    "                total += len(res)\n",
    "            print(\"Percentage of errors : \" ,  (errors/float(total))*100.0)\n",
    "            print(\"Pourcentage de correction  : \", (erreur_false/float(total_false)))\n",
    "            #print(\"taux de correction d'ajout : \", ((correction_ajout/float(correction_ajout_totale))*100.0))\n",
    "            print(\"Taux d erreur brut \" , ((erreur_2/float(total))*100.0))\n",
    "            print(total)\n",
    "            print(\"taux correction calcul  2 \" , correction, ((correction/float(correction_totale))*100.0),correction_totale)\n",
    "      \n",
    "            \n",
    "hmm = HMM(state_list=ctags.keys(), observation_list=vocab,\n",
    "                 transition_proba = None,\n",
    "                 observation_proba = None,\n",
    "                 initial_state_proba = None,\n",
    "                  transition_proba_2 = None,\n",
    "                 smoothing_obs = 0.01)\n",
    "hmm.supervised_training(cpairs,ctrans,cinits,ctrans2,ctags)\n",
    "print(\"init \")\n",
    "print(cinits)\n",
    "pprint(\"test\")\n",
    "'''for i in range(10):\n",
    "    print(test[i])\n",
    "    print(hmm.viverbit(map(operator.itemgetter(0), test[i])))'''\n",
    "\n",
    "'''\n",
    "ordre 2 basique\n",
    "('Percentage of errors : ', 6.147540983606557)\n",
    "('Pourcentage de correction  : ', 0.6606822262118492)\n",
    "('Taux d erreur brut ', 10.1775956284153)\n",
    "7320\n",
    "('taux correction calcul  2 ', 485, 6.62568306010929, 7320)\n",
    "\n",
    "\n",
    "sur 100 donnees:\n",
    "('Percentage of errors : ', 7.578947368421053)\n",
    "('Pourcentage de correction  : ', 0.8292682926829268)\n",
    "('Taux d erreur brut ', 11.157894736842106)\n",
    "'''\n",
    "\n",
    "'''\n",
    "('max : ', 0.0)\n",
    "0\n",
    "('max : ', 2.3713728451263007e-14)\n",
    "0\n",
    "('max : ', 1.8837501326215639e-13)\n",
    "0\n",
    "('max : ', 5.2683448452173056e-12)\n",
    "0\n",
    "('max : ', 1.7515599865523543e-10)\n",
    "0\n",
    "('max : ', 3.5099521454297783e-14)\n",
    "0\n",
    "('max : ', 5.4719708639882633e-15)\n",
    "0\n",
    "('max : ', 3.0561403772736174e-15)\n",
    "0\n",
    "('max : ', 1.0706123521905198e-16)\n",
    "0\n",
    "('max : ', 6.8508450216642249e-13)\n",
    "0\n",
    "'''\n",
    "\n",
    "# hmm.evaluate(test)\n",
    "#pprint(ctrans)\n",
    "print(test[1])\n",
    "# print(hmm.viverbit(map(operator.itemgetter(0), test[1])))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/usr/local/lib/python2.7/dist-packages/ipykernel/__main__.py:275: VisibleDeprecationWarning: using a non-integer number instead of an integer will result in an error in the future\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "50\n",
      "100\n",
      "150\n",
      "200\n",
      "250\n",
      "300\n",
      "350\n",
      "400\n",
      "450\n",
      "500\n",
      "550\n",
      "600\n",
      "650\n",
      "700\n",
      "750\n",
      "800\n",
      "850\n",
      "900\n",
      "950\n",
      "1000\n",
      "1050\n",
      "1100\n",
      "1150\n",
      "1200\n",
      "1250\n",
      "1300\n",
      "1350\n",
      "1400\n"
     ]
    }
   ],
   "source": [
    "hmm.evaluate(test_modify)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[('t', 't'), ('h', 'h'), ('e', 'e'), ('z', 's'), ('e', 'e')]\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/usr/local/lib/python2.7/dist-packages/ipykernel/__main__.py:275: VisibleDeprecationWarning: using a non-integer number instead of an integer will result in an error in the future\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[('t', 't'), ('h', 'h'), ('e', 'e'), ('z', 's'), ('e', 'e')]"
      ]
     },
     "execution_count": 76,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print test_modify[79]\n",
    "\n",
    "hmm.viverbit(map(operator.itemgetter(0), test_modify[79]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Compter les mots et les tags"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def make_counts(corpus):\n",
    "    \"\"\" \n",
    "    Build different count tables to train a HMM. Each count table is a dictionnary. \n",
    "    Returns: \n",
    "    * c_words: word counts\n",
    "    * c_tags: tag counts\n",
    "    * c_pairs: count of pairs (word,tag)\n",
    "    * c_transitions: count of tag bigram \n",
    "    * c_inits: count of tag found in the first position\n",
    "    \"\"\"\n",
    "    c_words = dict()\n",
    "    c_tags = dict()\n",
    "    c_pairs= dict()\n",
    "    c_transitions = dict()\n",
    "    c_transitions2 = dict()\n",
    "    c_inits = dict()\n",
    "    for sent in corpus:\n",
    "        # we use i because of the transition counts\n",
    "        for i in range(len(sent)):\n",
    "            couple=sent[i]\n",
    "            wrd = couple[0]\n",
    "            tag = couple[1]\n",
    "            # word counts\n",
    "            if wrd in c_words:\n",
    "                c_words[wrd]=c_words[wrd]+1\n",
    "            else:\n",
    "                c_words[wrd]=1\n",
    "            # tag counts\n",
    "            if tag in c_tags:\n",
    "                c_tags[tag]=c_tags[tag]+1\n",
    "            else:\n",
    "                c_tags[tag]=1\n",
    "            # observation counts\n",
    "            if couple in c_pairs:\n",
    "                c_pairs[couple]=c_pairs[couple]+1\n",
    "            else:\n",
    "                c_pairs[couple]=1\n",
    "            # i >  0 -> transition counts\n",
    "            if i > 0:\n",
    "                trans = (sent[i-1][1],tag)\n",
    "                if trans in c_transitions2:\n",
    "                    c_transitions2[trans]=c_transitions2[trans]+1\n",
    "                else:\n",
    "                    c_transitions2[trans]=1\n",
    "            if i > 1:\n",
    "                trans = ((sent[i-2][1],sent[i-1][1]),tag)\n",
    "                if trans in c_transitions:\n",
    "                    c_transitions[trans]=c_transitions[trans]+1\n",
    "                else:\n",
    "                    c_transitions[trans]=1\n",
    "            # i == 0 -> counts for initial states\n",
    "            if i==0:\n",
    "                if tag in c_inits:\n",
    "                    c_inits[tag]=c_inits[tag]+1\n",
    "                else:\n",
    "                    c_inits[tag]=1\n",
    "                    \n",
    "    return c_words,c_tags,c_pairs, c_transitions, c_inits, c_transitions2\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Création du vocabulaire (filtrage selon le nombre d'occurence)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def make_vocab(c_words, threshold):\n",
    "    \"\"\" \n",
    "    return a vocabulary by thresholding word counts. \n",
    "    inputs: \n",
    "    * c_words : a dictionnary that maps word to its counts\n",
    "    * threshold: count must be >= to the threshold to be included\n",
    "    \n",
    "    returns: \n",
    "    * a word list\n",
    "    \"\"\"\n",
    "    voc = list()\n",
    "    for w in c_words:\n",
    "        if c_words[w] >= threshold:\n",
    "            voc.append(w)\n",
    "    return voc\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# les données\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "# START"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Nombre de phrases de train = 29057\n",
      "Nombre de phrases de test  = 1501\n"
     ]
    }
   ],
   "source": [
    "import cPickle\n",
    "from pprint import pprint\n",
    "\n",
    "with open(\"typos-data/test10.pkl\", \"rb\") as input_file:\n",
    "    test = cPickle.load(input_file)\n",
    "    \n",
    "with open(\"typos-data/train10.pkl\", \"rb\") as input_file:\n",
    "    train = cPickle.load(input_file)\n",
    "print \"Nombre de phrases de train = \"+str(len(train))\n",
    "print \"Nombre de phrases de test  = \"+str(len(test))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 98,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Nombre de mots  : 26\n",
      "Nombre de tags  : 26\n",
      "Nombre de paires: 127\n",
      "Nombre de trans : 2489 / 144\n",
      "Nombre de init. : 25\n",
      "Vocabulaire :26\n"
     ]
    }
   ],
   "source": [
    "cwords,ctags,cpairs,ctrans,cinits, ctrans2 = make_counts(train)\n",
    "print \"Nombre de mots  : \"+str(len(cwords))\n",
    "print \"Nombre de tags  : \"+str(len(ctags))\n",
    "print \"Nombre de paires: \"+str(len(cpairs))\n",
    "print \"Nombre de trans : \"+str(len(ctrans))+ \" / \"+ str(12*12)\n",
    "print \"Nombre de init. : \"+str(len(cinits))\n",
    "vocab = make_vocab(cwords,10)\n",
    "print \"Vocabulaire :\"+str(len(vocab))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Création du HMM"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 99,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "HMM creating with: \n",
      "676 states 2\n",
      "26 states\n",
      "26 observations\n",
      "(676, 26)\n"
     ]
    }
   ],
   "source": [
    "hmm = HMM(state_list=ctags.keys(), observation_list=vocab,\n",
    "                 transition_proba = None,\n",
    "                 observation_proba = None,\n",
    "                 initial_state_proba = None)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Apprentissage pas à pas "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "ename": "NameError",
     "evalue": "name 'hmm' is not defined",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mNameError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-6-907e02427acd>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mhmm\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mobservation_estimation\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mcpairs\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      2\u001b[0m \u001b[0;32mprint\u001b[0m \u001b[0mhmm\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mobservation_proba\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0msum\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0maxis\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mNameError\u001b[0m: name 'hmm' is not defined"
     ]
    }
   ],
   "source": [
    "hmm.observation_estimation(cpairs)\n",
    "print hmm.observation_proba.sum(axis=0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "ename": "NameError",
     "evalue": "name 'hmm' is not defined",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mNameError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-7-1380d3505522>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mhmm\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mtransition_estimation\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mctrans\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      2\u001b[0m \u001b[0;32mprint\u001b[0m \u001b[0mhmm\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mtransition_proba\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0msum\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0maxis\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mNameError\u001b[0m: name 'hmm' is not defined"
     ]
    }
   ],
   "source": [
    "hmm.transition_estimation(ctrans)\n",
    "print hmm.transition_proba.sum(axis=0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "ename": "NameError",
     "evalue": "name 'hmm' is not defined",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mNameError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-8-248c915f2f2c>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mhmm\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0minit_estimation\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mcinits\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      2\u001b[0m \u001b[0;32mprint\u001b[0m \u001b[0msum\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mhmm\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0minitial_state_proba\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mNameError\u001b[0m: name 'hmm' is not defined"
     ]
    }
   ],
   "source": [
    "hmm.init_estimation(cinits)\n",
    "print sum(hmm.initial_state_proba)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Apprentissage en une fois"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "ename": "NameError",
     "evalue": "name 'HMM' is not defined",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mNameError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-9-feb6b0b00848>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m hmm = HMM(state_list=ctags.keys(), observation_list=vocab,\n\u001b[0m\u001b[1;32m      2\u001b[0m                  \u001b[0mtransition_proba\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mNone\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      3\u001b[0m                  \u001b[0mobservation_proba\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mNone\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      4\u001b[0m                  \u001b[0minitial_state_proba\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mNone\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      5\u001b[0m                  smoothing_obs = 0.001)\n",
      "\u001b[0;31mNameError\u001b[0m: name 'HMM' is not defined"
     ]
    }
   ],
   "source": [
    "hmm = HMM(state_list=ctags.keys(), observation_list=vocab,\n",
    "                 transition_proba = None,\n",
    "                 observation_proba = None,\n",
    "                 initial_state_proba = None,\n",
    "                 smoothing_obs = 0.001)\n",
    "hmm.supervised_training(cpairs,ctrans,cinits)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Modification données pour prendre en compte l'ajout de caractère"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import random\n",
    "from copy import deepcopy\n",
    "\n",
    "# On ajoute le caractère \"\" pour l'etiquette, pour signifiern que cette lettre n'était pas sensé être là\n",
    "\n",
    "# On ajoute un caractère a 10% des données d'entrainement et a 10% des données de test\n",
    "def add_caracter(data, letters):\n",
    "    nb_word_train = len(data)\n",
    "    nb_modif = int(np.floor(0.1 * nb_word_train))\n",
    "    word_to_modify = random.sample(range(0, nb_word_train), nb_modif)\n",
    "\n",
    "    data_modify = deepcopy(data)\n",
    "    for i in word_to_modify:\n",
    "        word = data_modify[i]\n",
    "        indice_add = random.randint(0, len(word))\n",
    "        letter = random.choice(letters)\n",
    "        if indice_add != len(word):\n",
    "            word = word[:indice_add] + [(letter,'')] + word[indice_add:]\n",
    "        else:\n",
    "            word = word[:indice_add] + [(letter,'')]\n",
    "        data_modify[i] = word\n",
    "    return data_modify\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "def remove_caracter(data):\n",
    "    nb_word_train = len(data)\n",
    "    nb_modif = int(np.floor(0.1 * nb_word_train))\n",
    "    word_to_modify = random.sample(range(0, nb_word_train), nb_modif)\n",
    "    data_modify = deepcopy(data)\n",
    "    for i in word_to_modify:\n",
    "        word = data_modify[i]\n",
    "        indice_remove = random.randint(0, len(word)-1)\n",
    "        if indice_remove <= len(word)-1 and indice_remove != 0:\n",
    "            word = word[0:indice_remove] + [('',word[indice_remove][1])] + word[indice_remove+1:]\n",
    "        elif indice_remove == len(word)-1 :\n",
    "            word = word[:indice_remove-1] + [('',word[indice_remove][1])]\n",
    "        else:\n",
    "            word = [('',word[indice_remove][1])] + word[indice_remove+1:]\n",
    "        data_modify[i] = word\n",
    "    return data_modify\n",
    "\n",
    "\n",
    "def remove_caracter2(data):\n",
    "    nb_word_train = len(data)\n",
    "    nb_modif = int(np.floor(0.1 * nb_word_train))\n",
    "    word_to_modify = random.sample(range(0, nb_word_train), nb_modif)\n",
    "    data_modify = deepcopy(data)\n",
    "    for i in word_to_modify:\n",
    "        word = data_modify[i]\n",
    "   \n",
    "        indice_remove = random.randint(0, len(word)-1)\n",
    "        \n",
    "        if indice_remove < len(word)-1 :\n",
    "            word2 = word[:indice_remove] #+ [('',word[indice_remove][1])] + word[indice_remove+1:]\n",
    "            #faire une boucle de decalage\n",
    "            i = indice_remove\n",
    "            while i < len(word)-1: #s'arrêter à l'avant dernier indice\n",
    "                word2 = word2 + [(word[i+1][1],word[i][1])]\n",
    "                i = i + 1\n",
    "            word2 = word2 + [(\"\",word[i][1])]\n",
    "        \n",
    "        else:   \n",
    "            word2 = word[:indice_remove] + [('',word[indice_remove][1])]\n",
    "     \n",
    "        data_modify[i] = word2\n",
    "            \n",
    "    return data_modify\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "#train_modify = add_caracter(train, list(vocab))\n",
    "#test_modify = add_caracter(test, list(vocab))\n",
    "\n",
    "train_modify = remove_caracter2(train)\n",
    "test_modify = remove_caracter2(test)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[('a', 'a'), ('b', 'b'), ('o', 'o'), ('u', 'u'), ('t', 't')]\n",
      "[('i', 'i'), ('s', 's')]\n"
     ]
    }
   ],
   "source": [
    "print train_modify[2]\n",
    "print test[2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Nombre de mots  : 27\n",
      "Nombre de tags  : 26\n",
      "Nombre de paires: 148\n",
      "Nombre de trans : 2565 / 144\n",
      "Nombre de init. : 25\n",
      "Vocabulaire :27\n"
     ]
    }
   ],
   "source": [
    "cwords,ctags,cpairs,ctrans,cinits, ctrans2 = make_counts(train_modify)\n",
    "print \"Nombre de mots  : \"+str(len(cwords))\n",
    "print \"Nombre de tags  : \"+str(len(ctags))\n",
    "print \"Nombre de paires: \"+str(len(cpairs))\n",
    "print \"Nombre de trans : \"+str(len(ctrans))+ \" / \"+ str(12*12)\n",
    "print \"Nombre de init. : \"+str(len(cinits))\n",
    "vocab = make_vocab(cwords,10)\n",
    "print \"Vocabulaire :\"+str(len(vocab))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "HMM creating with: \n",
      "676 states 2\n",
      "26 states\n",
      "27 observations\n",
      "(676, 26)\n"
     ]
    }
   ],
   "source": [
    "hmm = HMM(state_list=ctags.keys(), observation_list=vocab,\n",
    "                 transition_proba = None,\n",
    "                 observation_proba = None,\n",
    "                 initial_state_proba = None)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'\\nProjet : variable n est plus mot mais caractere\\nobserver un mot => sequence d etats la version correcte\\nXik = convluwion\\nYik = conclusion\\n\\npour que ce soit plus dur => modele de second ordre\\n\\ndonnees (bon char, mauvais char)\\n\\n deux version : 10 : 10% d erreurs\\n                 20 : 20%  d erreurs\\n                 \\n3 points : hmm et biterdi : taux d erreurs du modele\\n\\nmodele markov ordre deux : => proba  d un etat depend des deux etats precedents P(Yt|Yt-1,Yt2)\\n\\ndans viberti : on propage (dans delta) la proba du meilleur chemin pour arriver a un instant t dans un etat donne\\n=> quand rempli t on peut remplir t+1 (par hypothese) markov d ordre 1 => donc a ordre 2 il faut faire changement de varibale\\nbesoin de garder la trace de tout ce qui est contionnement (Yt garde trace de ce qui est en t-1 et t-2 )\\ntaille devient s\\xc2\\xb2 => delta de taille (K*N^2)\\n\\n3 novembre : finir partie 1\\n'"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "'''\n",
    "(u'Some', u'DET'), (u'ten', u'NUM'), (u'years', u'NOUN'), (u'ago', u'ADV'), (u'that', u'DET'),\n",
    "(u'page', u'NOUN'), (u'was', u'VERB'), (u'torn', u'VERB'), (u'out', u'PRT'), (u',', u'.'), \n",
    "(u'I', u'PRON'), (u\"don't\", u'VERB'), (u'know', u'VERB'), (u'by', u'ADP'), (u'whom', u'PRON'), (u'.', u'.')]\n",
    "'''\n",
    "\n",
    "\n",
    "'''\n",
    "Projet : variable n est plus mot mais caractere\n",
    "observer un mot => sequence d etats la version correcte\n",
    "Xik = convluwion\n",
    "Yik = conclusion\n",
    "\n",
    "pour que ce soit plus dur => modele de second ordre\n",
    "\n",
    "donnees (bon char, mauvais char)\n",
    "\n",
    " deux version : 10 : 10% d erreurs\n",
    "                 20 : 20%  d erreurs\n",
    "                 \n",
    "3 points : hmm et biterdi : taux d erreurs du modele\n",
    "\n",
    "modele markov ordre deux : => proba  d un etat depend des deux etats precedents P(Yt|Yt-1,Yt2)\n",
    "\n",
    "dans viberti : on propage (dans delta) la proba du meilleur chemin pour arriver a un instant t dans un etat donne\n",
    "=> quand rempli t on peut remplir t+1 (par hypothese) markov d ordre 1 => donc a ordre 2 il faut faire changement de varibale\n",
    "besoin de garder la trace de tout ce qui est contionnement (Yt garde trace de ce qui est en t-1 et t-2 )\n",
    "taille devient s² => delta de taille (K*N^2)\n",
    "\n",
    "3 novembre : finir partie 1\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}