Cross Language Information Retrieval.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# Cross Language Information Retrieval\n",
    "\n",
    "#### Overview\n",
    "\n",
    "The aim of this project is to build a cross language information retrieval system (CLIR) which, given a query in German, will be capable of searching text documents written in English and displaying the results in German.\n",
    "\n",
    "We're going to use machine translation, information retrieval using a vector space model, and then assess the performance of the system using IR evaluation techniques.\n",
    "\n",
    "Parts of the project are explained as we progress.\n",
    "\n",
    "#### Data Used\n",
    "\n",
    "- bitext.(en,de): A sentence aligned, parallel German-English corpus, sourced from the Europarl corpus (which is a collection of debates held in the EU parliament over a number of years). We'll use this to develop word-alignment tools, and build a translation probability table. \n",
    "\n",
    "- newstest.(en,de): A separate, smaller parallel corpus for evaulation of the translation system.\n",
    "\n",
    "- devel.(docs,queries,qrel): A set of documents in English (sourced from Wikipedia), queries in German, and relevance judgement scores for each query-document pair. \n",
    "\n",
    "The files are available to check out in the data/clir directory of the repo. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Housekeeping: File encodings and tokenisation\n",
    "\n",
    "Since the data files we use is utf-8 encoded text, we need to convert the strings into ASCII by escaping the special symbols. We also import some libraries in this step as well."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from nltk.tokenize import word_tokenize\n",
    "from __future__ import division #To properly handle floating point divisions.\n",
    "import math\n",
    "\n",
    "#Function to tokenise string/sentences.\n",
    "def tokenize(line, tokenizer=word_tokenize):\n",
    "    utf_line = line.decode('utf-8').lower()\n",
    "    return [token.encode('ascii', 'backslashreplace') for token in tokenizer(utf_line)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we can test out our tokenize function. Notice how it converts the word Über."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['seit',\n",
       " 'damals',\n",
       " 'ist',\n",
       " 'er',\n",
       " 'auf',\n",
       " '\\\\xfcber',\n",
       " '10.000',\n",
       " 'punkte',\n",
       " 'gestiegen',\n",
       " '.']"
      ]
     },
     "execution_count": 77,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tokenize(\"Seit damals ist er auf über 10.000 Punkte gestiegen.\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's store the path of the data files as easily identifiable variables for future access. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "DEVELOPMENT_DOCS = 'data/clir/devel.docs' #Data file for IR engine development\n",
    "\n",
    "DEVELOPMENT_QUERIES = 'data/clir/devel.queries' #Data file containing queries in German\n",
    "\n",
    "DEVELOPMENT_QREL = 'data/clir/devel.qrel' #Data file containing a relevance score or query-doc pairs\n",
    "\n",
    "BITEXT_ENG = 'data/clir/bitext.en' #Bitext data file in English for translation engine and language model development\n",
    "\n",
    "BITEXT_DE = 'data/clir/bitext.de' #Bitext data file in German\n",
    "\n",
    "NEWSTEST_ENG = 'data/clir/newstest.en' #File for testing language model"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "With that out of the way, lets get to the meat of the project. \n",
    "\n",
    "As mentioned earlier, we're going to build a CLIR engine consisting of information retrieval and translation components, and then evaluate its accuracy.\n",
    "\n",
    "The CLIR system will:\n",
    "- **translate queries** from German into English (because our searcheable corpus is in English), using word-based translation, a rather simplistic approach as opposed to the sophistication you might see in, say, *Google Translate*.\n",
    "- **search over the document corpus** using the Okapi BM25 IR ranking model, a variation of the traditional TF-IDF model.\n",
    "- **evaluate the quality** of ranked retrieval results using the query relevance judgements."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Information Retrieval using [Okapi BM25](https://en.wikipedia.org/wiki/Okapi_BM25)\n",
    "\n",
    "We'll start by building an IR system, and give it a test run with some English queries. \n",
    "\n",
    "Here's an overview of the tasks involved:\n",
    "- Loading the data files, and tokenizing the input.\n",
    "- Preprocessing the lexicon by stemming, removing stopwords.\n",
    "- Calculating the TF/IDF representation for all documents in our wikipedia corpus.\n",
    "- Storing an inverted index to efficiently documents, given a query term.\n",
    "- Implementing querying with BM25.\n",
    "- Test runs.\n",
    "\n",
    "So for our first task, we'll load the devel.docs file, extract and tokenize the terms, and store them in a python dictionary with the document ids as keys. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import nltk\n",
    "import re\n",
    "\n",
    "stopwords = set(nltk.corpus.stopwords.words('english')) #converting stopwords to a set for faster processing in the future.\n",
    "stemmer = nltk.stem.PorterStemmer() \n",
    "\n",
    "#Function to extract and tokenize terms from a document\n",
    "def extract_and_tokenize_terms(doc):\n",
    "    terms = []\n",
    "    for token in tokenize(doc):\n",
    "        if token not in stopwords: # 'in' and 'not in' operations are faster over sets than lists\n",
    "            if not re.search(r'\\d',token) and not re.search(r'[^A-Za-z-]',token): #Removing numbers and punctuations \n",
    "                #(excluding hyphenated words)\n",
    "                terms.append(stemmer.stem(token.lower()))\n",
    "    return terms\n",
    "\n",
    "documents = {} #Dictionary to store documents with ids as keys."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "#Reading each line in the file and storing it documents dictionary\n",
    "f = open(DEVELOPMENT_DOCS)\n",
    "\n",
    "for line in f:\n",
    "    doc = line.split(\"\\t\")\n",
    "    terms = extract_and_tokenize_terms(doc[1])\n",
    "    documents[doc[0]] = terms\n",
    "f.close()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To check if everything is working till now, let's access a document from the dictionary, with the id '290'. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[u'name',\n",
       " u'plural',\n",
       " u'ae',\n",
       " u'first',\n",
       " u'letter',\n",
       " u'vowel',\n",
       " u'iso',\n",
       " u'basic',\n",
       " u'latin',\n",
       " u'alphabet',\n",
       " u'similar',\n",
       " u'ancient',\n",
       " u'greek',\n",
       " u'letter',\n",
       " u'alpha',\n",
       " u'deriv',\n",
       " u'upper',\n",
       " u'case',\n",
       " u'version',\n",
       " u'consist']"
      ]
     },
     "execution_count": 81,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "documents['290'][:20] #To keep things short, we're only going to check out 20 tokens."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we'll build an inverted index for the documents, so that we can quickly access documents for the terms we need. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 115,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#Building an inverted index for the documents\n",
    "\n",
    "from collections import defaultdict\n",
    "    \n",
    "inverted_index = defaultdict(set)\n",
    "\n",
    "for docid, terms in documents.items():\n",
    "    for term in terms:\n",
    "        inverted_index[term].add(docid)    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To test it out, the list of documents containing the word 'pizza':"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 116,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'121569',\n",
       " '16553',\n",
       " '212541',\n",
       " '228211',\n",
       " '261023',\n",
       " '265975',\n",
       " '276433',\n",
       " '64083',\n",
       " '69930',\n",
       " '72701',\n",
       " '73441',\n",
       " '74323'}"
      ]
     },
     "execution_count": 116,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "inverted_index['pizza']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On to the BM25 TF-IDF representation, we'll create the td-idf matrix for terms-documents, first without the query component. \n",
    "\n",
    "The query component is dependent on the terms in our query. So we'll just calculate that, and multiply it with the overall score when we want to retreive documents for a particular query."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 117,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#Building a TF-IDF representation using BM25 \n",
    "\n",
    "NO_DOCS = len(documents) #Number of documents\n",
    "\n",
    "AVG_LEN_DOC = sum([len(doc) for doc in documents.values()])/len(documents) #Average length of documents\n",
    "\n",
    "#The function below takes the documentid, and the term, to calculate scores for the tf and idf\n",
    "#components, and multiplies them together.\n",
    "def tf_idf_score(k1,b,term,docid):  \n",
    "    \n",
    "    ft = len(inverted_index[term]) \n",
    "    term = stemmer.stem(term.lower())\n",
    "    fdt =  documents[docid].count(term)\n",
    "    \n",
    "    idf_comp = math.log((NO_DOCS - ft + 0.5)/(ft+0.5))\n",
    "    \n",
    "    tf_comp = ((k1 + 1)*fdt)/(k1*((1-b) + b*(len(documents[docid])/AVG_LEN_DOC))+fdt)\n",
    "    \n",
    "    return idf_comp * tf_comp\n",
    "\n",
    "#Function to create tf_idf matrix without the query component\n",
    "def create_tf_idf(k1,b):\n",
    "    tf_idf = defaultdict(dict)\n",
    "    for term in set(inverted_index.keys()):\n",
    "        for docid in inverted_index[term]:\n",
    "            tf_idf[term][docid] = tf_idf_score(k1,b,term,docid)\n",
    "    return tf_idf"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 118,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#Creating tf_idf matrix with said parameter values: k1 and b for all documents.\n",
    "tf_idf = create_tf_idf(1.5,0.5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We took the default values for k1 and b (1.5 and 0.5), which seemed to give good results. Although these parameters may be altered depending on the type of data being dealth with. \n",
    "\n",
    "Now we create a method to retrieve the query component, and another method that will use the previous ones and retrieve the relevant documents for a query, sorted on the basis of their ranks. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 119,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#Function to retrieve query component\n",
    "def get_qtf_comp(k3,term,fqt):\n",
    "    return ((k3+1)*fqt[term])/(k3 + fqt[term])\n",
    "\n",
    "\n",
    "#Function to retrieve documents || Returns a set of documents and their relevance scores. \n",
    "def retr_docs(query,result_count):\n",
    "    q_terms = [stemmer.stem(term.lower()) for term in query.split() if term not in stopwords] #Removing stopwords from queries\n",
    "    fqt = {}\n",
    "    for term in q_terms:\n",
    "        fqt[term] = fqt.get(term,0) + 1\n",
    "    \n",
    "    scores = {}\n",
    "    \n",
    "    for word in fqt.keys():\n",
    "        #print word + ': '+ str(inverted_index[word])\n",
    "        for document in inverted_index[word]:\n",
    "            scores[document] = scores.get(document,0) + (tf_idf[word][document]*get_qtf_comp(0,word,fqt)) #k3 chosen as 0 (default)\n",
    "    \n",
    "    return sorted(scores.items(),key = lambda x : x[1] , reverse=True)[:result_count]        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's try and retrieve a document for a query. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 120,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('19961', 12.570721363284687),\n",
       " ('83266', 12.500367334396838),\n",
       " ('266959', 12.46418348068098),\n",
       " ('20206', 12.324327863972716),\n",
       " ('253314', 12.008548114449386)]"
      ]
     },
     "execution_count": 120,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "retr_docs(\"Manchester United\",5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Checking out the terms in the top ranked document.."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 121,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[u'manchest',\n",
       " u'unit',\n",
       " u'manchest',\n",
       " u'unit',\n",
       " u'footbal',\n",
       " u'club',\n",
       " u'english',\n",
       " u'profession',\n",
       " u'footbal',\n",
       " u'club',\n",
       " u'base',\n",
       " u'old',\n",
       " u'trafford',\n",
       " u'greater',\n",
       " u'manchest',\n",
       " u'play',\n",
       " u'premier',\n",
       " u'leagu',\n",
       " u'found',\n",
       " u'newton',\n",
       " u'heath',\n",
       " u'lyr',\n",
       " u'footbal',\n",
       " u'club',\n",
       " u'club',\n",
       " u'chang',\n",
       " u'name',\n",
       " u'manchest',\n",
       " u'unit',\n",
       " u'move']"
      ]
     },
     "execution_count": 121,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "documents['19961'][:30]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The information retrieval engine has worked quite well in this case. The top ranked document for the query is a snippet of the wikipedia article for Manchester United Football Club. \n",
    "\n",
    "On further inspection, we can see that the documents ranked lower are, for example, for The University of Manchester, or even just articles with the words 'Manchester' or 'United' in them.\n",
    "\n",
    "Now we can begin translating the German queries to English."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Query Translation: "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For translation, we'll implement a simple word-based translation model in a noisy channel setting. This means that we'll use both a language model over English, and a translation model.\n",
    "\n",
    "We'll use a unigram language model for decoding/translation, but also create a model with trigram to test the improvement in performace). \n",
    "\n",
    "Our aim is to find the string, $\\vec{e}$ which maximises $p(\\vec{e}) p(\\vec{g} | \\vec{e})$, given English output string $\\vec{e}$ and German input string $\\vec{g}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Language Model:\n",
    "\n",
    "[From Wikipedia](https://en.wikipedia.org/wiki/Language_model): A statistical language model is a probability distribution over sequences of words. Given such a sequence, say of length m, it assigns a probability P(w1,....,wm) to the whole sequence. \n",
    "\n",
    "The models will be trained on the 'bitext.en' file, and tested on 'newstest.en'.\n",
    "\n",
    "As we'll train the model on different files, it's obvious that we'll run into words (unigrams) and trigrams what we hadn't seen in the file we trained the model on. To account for these unknown information, we'll use add-k or [laplace smoothing](https://en.wikipedia.org/wiki/Additive_smoothing) for the unigram and [Katz-Backoff smoothing](https://en.wikipedia.org/wiki/Katz%27s_back-off_model) for the trigram model.\n",
    "\n",
    "Let's start with calculating the unigram, bigram and trigram counts (we need the bigram counts for trigram smoothing). The sentences are also converted appropriately by adding sentinels at the start and end of sentences."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#Calculating the unigram, bigram and trigram counts. \n",
    "\n",
    "f = open(BITEXT_ENG)\n",
    "\n",
    "train_sentences = []\n",
    "\n",
    "for line in f:\n",
    "    train_sentences.append(tokenize(line))\n",
    "\n",
    "f.close()    \n",
    "\n",
    "#Function to mark the first occurence of words as unknown, for training.\n",
    "def check_for_unk_train(word,unigram_counts):\n",
    "    if word in unigram_counts:\n",
    "        return word\n",
    "    else:\n",
    "        unigram_counts[word] = 0\n",
    "        return \"UNK\"\n",
    "\n",
    "#Function to convert sentences for training the language model.    \n",
    "def convert_sentence_train(sentence,unigram_counts):\n",
    "    #<s1> and <s2> are sentinel tokens added to the start and end, for handling tri/bigrams at the start of a sentence.\n",
    "    return [\"<s1>\"] + [\"<s2>\"] + [check_for_unk_train(token.lower(),unigram_counts) for token in sentence] + [\"</s2>\"]+ [\"</s1>\"]\n",
    "\n",
    "#Function to obtain unigram, bigram and trigram counts.\n",
    "def get_counts(sentences):\n",
    "    trigram_counts = defaultdict(lambda: defaultdict(dict))\n",
    "    bigram_counts = defaultdict(dict)\n",
    "    unigram_counts = {}\n",
    "    for sentence in sentences:\n",
    "        sentence = convert_sentence_train(sentence, unigram_counts)\n",
    "        for i in range(len(sentence) - 2):\n",
    "            trigram_counts[sentence[i]][sentence[i+1]][sentence[i+2]] = trigram_counts[sentence[i]][sentence[i+1]].get(sentence[i+2],0) + 1\n",
    "            bigram_counts[sentence[i]][sentence[i+1]] = bigram_counts[sentence[i]].get(sentence[i+1],0) + 1\n",
    "            unigram_counts[sentence[i]] = unigram_counts.get(sentence[i],0) + 1\n",
    "    unigram_counts[\"</s1>\"] = unigram_counts[\"<s1>\"]\n",
    "    unigram_counts[\"</s2>\"] = unigram_counts[\"<s2>\"]\n",
    "    bigram_counts[\"</s2>\"][\"</s1>\"] = bigram_counts[\"<s1>\"][\"<s2>\"]\n",
    "    return unigram_counts, bigram_counts, trigram_counts"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "unigram_counts, bigram_counts,trigram_counts = get_counts(train_sentences)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can calculate the [perplexity](https://en.wikipedia.org/wiki/Perplexity) of our language models to see how well they predict a sentence."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "#Constructing unigram model with 'add-k' smoothing\n",
    "token_count = sum(unigram_counts.values())\n",
    "\n",
    "#Function to convert unknown words for testing. \n",
    "#Words that don't appear in the training corpus (even if they are in the test corpus) are marked as UNK.\n",
    "def check_for_unk_test(word,unigram_counts):\n",
    "    if word in unigram_counts and unigram_counts[word] > 0:\n",
    "        return word\n",
    "    else:\n",
    "        return \"UNK\"\n",
    "\n",
    "\n",
    "def convert_sentence_test(sentence,unigram_counts):\n",
    "    return [\"<s1>\"] + [\"<s2>\"] + [check_for_unk_test(word.lower(),unigram_counts) for word in sentence] + [\"</s2>\"]  + [\"</s1>\"]\n",
    "\n",
    "#Returns the log probability of a unigram, with add-k smoothing. We're taking logs to avoid probability underflow.\n",
    "def get_log_prob_addk(word,unigram_counts,k):\n",
    "    return math.log((unigram_counts[word] + k)/ \\\n",
    "                    (token_count + k*len(unigram_counts)))\n",
    "\n",
    "#Returns the log probability of a sentence.\n",
    "def get_sent_log_prob_addk(sentence, unigram_counts,k):\n",
    "    sentence = convert_sentence_test(sentence, unigram_counts)\n",
    "    return sum([get_log_prob_addk(word, unigram_counts,k) for word in sentence])\n",
    "\n",
    "\n",
    "def calculate_perplexity_uni(sentences,unigram_counts, token_count, k):\n",
    "    total_log_prob = 0\n",
    "    test_token_count = 0\n",
    "    for sentence in sentences:\n",
    "        test_token_count += len(sentence) + 2 # have to consider the end token\n",
    "        total_log_prob += get_sent_log_prob_addk(sentence,unigram_counts,k)\n",
    "    return math.exp(-total_log_prob/test_token_count)\n",
    "\n",
    "\n",
    "f = open(NEWSTEST_ENG)\n",
    "\n",
    "test_sents = []\n",
    "for line in f:\n",
    "    test_sents.append(tokenize(line))\n",
    "f.close()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we'll calculate the [perplexity](https://en.wikipedia.org/wiki/Perplexity) for the model, as a measure of performance i.e. how well they predict a sentence. To find the optimum value of k, we can just calculate the perplexity multiple times with different k(s). "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.0001: 613.918691403\n",
      "0.01: 614.027477551\n",
      "0.1: 615.06903252\n",
      "1: 628.823994251\n",
      "10: 823.302441447\n"
     ]
    }
   ],
   "source": [
    "#Calculating the perplexity for different ks\n",
    "ks = [0.0001,0.01,0.1,1,10]\n",
    "\n",
    "for k in ks:\n",
    "    print str(k) +\": \" + str(calculate_perplexity_uni(test_sents,unigram_counts,token_count,k))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Using add-k smoothing, perplexity for the unigram model increases with the increase in k. So 0.0001 is the best choice for k.\n",
    "\n",
    "Moving on to tri-grams."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#Calculating the N1/N paramaters for Trigrams/Bigrams/Unigrams in Katz-Backoff Smoothing\n",
    "\n",
    "TRI_ONES = 0 #N1 for Trigrams\n",
    "TRI_TOTAL = 0 #N for Trigrams\n",
    "\n",
    "for twod in trigram_counts.values():\n",
    "    for oned in twod.values():\n",
    "        for val in oned.values():\n",
    "            if val==1:\n",
    "                TRI_ONES+=1 #Count of trigram seen once\n",
    "            TRI_TOTAL += 1 #Count of all trigrams seen\n",
    "\n",
    "BI_ONES = 0 #N1 for Bigrams\n",
    "BI_TOTAL = 0 #N for Bigrams\n",
    "\n",
    "for oned in bigram_counts.values():\n",
    "    for val in oned.values():\n",
    "        if val==1:\n",
    "            BI_ONES += 1 #Count of bigram seen once\n",
    "        BI_TOTAL += 1 #Count of all bigrams seen\n",
    "        \n",
    "UNI_ONES = unigram_counts.values().count(1)\n",
    "UNI_TOTAL = len(unigram_counts)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#Constructing trigram model with backoff smoothing\n",
    "\n",
    "TRI_ALPHA = TRI_ONES/TRI_TOTAL #Alpha parameter for trigram counts\n",
    "    \n",
    "BI_ALPHA = BI_ONES/BI_TOTAL #Alpha parameter for bigram counts\n",
    "\n",
    "UNI_ALPHA = UNI_ONES/UNI_TOTAL\n",
    "    \n",
    "def get_log_prob_back(sentence,i,unigram_counts,bigram_counts,trigram_counts,token_count):\n",
    "    if trigram_counts[sentence[i-2]][sentence[i-1]].get(sentence[i],0) > 0:\n",
    "        return math.log((1-TRI_ALPHA)*trigram_counts[sentence[i-2]][sentence[i-1]].get(sentence[i])/bigram_counts[sentence[i-2]][sentence[i-1]])\n",
    "    else:\n",
    "        if bigram_counts[sentence[i-1]].get(sentence[i],0)>0:\n",
    "            return math.log(TRI_ALPHA*((1-BI_ALPHA)*bigram_counts[sentence[i-1]][sentence[i]]/unigram_counts[sentence[i-1]]))\n",
    "        else:\n",
    "            return math.log(TRI_ALPHA*BI_ALPHA*(1-UNI_ALPHA)*((unigram_counts[sentence[i]]+0.0001)/(token_count+(0.0001)*len(unigram_counts)))) \n",
    "        \n",
    "        \n",
    "def get_sent_log_prob_back(sentence, unigram_counts, bigram_counts,trigram_counts, token_count):\n",
    "    sentence = convert_sentence_test(sentence, unigram_counts)\n",
    "    return sum([get_log_prob_back(sentence,i, unigram_counts,bigram_counts,trigram_counts,token_count) for i in range(2,len(sentence))])\n",
    "\n",
    "\n",
    "def calculate_perplexity_tri(sentences,unigram_counts,bigram_counts,trigram_counts, token_count):\n",
    "    total_log_prob = 0\n",
    "    test_token_count = 0\n",
    "    for sentence in sentences:\n",
    "        test_token_count += len(sentence) + 2 # have to consider the end token\n",
    "        total_log_prob += get_sent_log_prob_back(sentence,unigram_counts,bigram_counts,trigram_counts,token_count)\n",
    "    return math.exp(-total_log_prob/test_token_count)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "461.64686176451505"
      ]
     },
     "execution_count": 95,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#Calculating the perplexity \n",
    "calculate_perplexity_tri(test_sents,unigram_counts,bigram_counts,trigram_counts,token_count)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For unigram language model, the perplexity for different values of k were as follow:\n",
    "<table>\n",
    "<tr>\n",
    "<th>k</th>\n",
    "<th>Perplexity</th>\n",
    "</tr>\n",
    "<tr>\n",
    "<td>0.0001</td>\n",
    "<td>613.92</td>\n",
    "</tr>\n",
    "<tr>\n",
    "<tr>\n",
    "<td>0.01</td>\n",
    "<td>614.03</td>\n",
    "</tr>\n",
    "<tr>\n",
    "<td>0.1</td>\n",
    "<td>628.82</td>\n",
    "</tr>\n",
    "<tr>\n",
    "<td>1</td>\n",
    "<td>823.302</td>\n",
    "</tr>\n",
    "</table>\n",
    "\n",
    "For tri-gram model, Katz-Backoff smoothing was chosen as it takes a discounted probability for things only seen once, and backs off to a lower level n-gram for unencountered n-grams.\n",
    "\n",
    "Compared with the trigram model, the perplexity was as follows:\n",
    "<table>\n",
    "<tr>\n",
    "<th>Model</th>\n",
    "<th>Perplexity</th>\n",
    "</tr>\n",
    "<tr>\n",
    "<td>Unigram (Best K)</td>\n",
    "<td>613.92</td>\n",
    "</tr>\n",
    "<tr>\n",
    "<td>Trigram (Katz Backoff)</td>\n",
    "<td>461.65</td>\n",
    "</tr>\n",
    "</table>\n",
    "\n",
    "As can be seen, the trigram model with 'Katz Backoff' smoothing seems to perform better than the best unigram model (with k = 0.0001). Thus we can say that this model is better for predicting the sequence of a sentence than unigram, which should is obvious if you think about it. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Translation model\n",
    "\n",
    "Next, we'll estimate translation model probabilities. For this, we'll use IBM1 from the NLTK library. IBM1 learns word based translation probabilities using expectation maximisation. \n",
    "\n",
    "We'll use both 'bitext.de' and 'bitext.en' files for this purpose; extract the sentences from each, and then use IBM1 to build the translation tables."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "#Creating lists of English and German sentences from bitext.\n",
    "\n",
    "from nltk.translate import IBMModel1\n",
    "from nltk.translate import AlignedSent, Alignment\n",
    "\n",
    "eng_sents = []\n",
    "de_sents = []\n",
    "\n",
    "f = open(BITEXT_ENG)\n",
    "for line in f:\n",
    "    terms = tokenize(line)\n",
    "    eng_sents.append(terms)\n",
    "f.close()\n",
    "\n",
    "f = open(BITEXT_DE)\n",
    "for line in f:\n",
    "    terms = tokenize(line)\n",
    "    de_sents.append(terms)\n",
    "f.close()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#Zipping together the bitexts for easier access\n",
    "paral_sents = zip(eng_sents,de_sents)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 98,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#Building English to German translation table for words (Backward alignment)\n",
    "eng_de_bt = [AlignedSent(E,G) for E,G in paral_sents]\n",
    "eng_de_m = IBMModel1(eng_de_bt, 5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#Building German to English translation table for words (Backward alignment)\n",
    "de_eng_bt = [AlignedSent(G,E) for E,G in paral_sents]\n",
    "de_eng_m = IBMModel1(de_eng_bt, 5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can take the intersection of the dual alignments to obtain a combined alignment for each sentence in the bitext."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 101,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#Script below to combine alignments using set intersections\n",
    "combined_align = []\n",
    "\n",
    "for i in range(len(eng_de_bt)):\n",
    "\n",
    "    forward = {x for x in eng_de_bt[i].alignment}\n",
    "    back_reversed = {x[::-1] for x in de_eng_bt[i].alignment}\n",
    "    \n",
    "    combined_align.append(forward.intersection(back_reversed))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we can create translation dictionaries in both English to German, and German to English directions. \n",
    "\n",
    "Creating dictionaries for occurence counts first."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 102,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#Creating German to English dictionary with occurence count of word pairs\n",
    "de_eng_count = defaultdict(dict)\n",
    "\n",
    "for i in range(len(de_eng_bt)):\n",
    "    for item in combined_align[i]:\n",
    "        de_eng_count[de_eng_bt[i].words[item[1]]][de_eng_bt[i].mots[item[0]]] =  de_eng_count[de_eng_bt[i].words[item[1]]].get(de_eng_bt[i].mots[item[0]],0) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#Creating a English to German dict with occ count of word pais\n",
    "eng_de_count = defaultdict(dict)\n",
    "\n",
    "for i in range(len(eng_de_bt)):\n",
    "    for item in combined_align[i]:\n",
    "        eng_de_count[eng_de_bt[i].words[item[0]]][eng_de_bt[i].mots[item[1]]] =  eng_de_count[eng_de_bt[i].words[item[0]]].get(eng_de_bt[i].mots[item[1]],0) + 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Creating dictionaries for translation probabilities."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#Creating German to English table with word translation probabilities\n",
    "de_eng_prob = defaultdict(dict)\n",
    "\n",
    "for de in de_eng_count.keys():\n",
    "    for eng in de_eng_count[de].keys():\n",
    "        de_eng_prob[de][eng] = de_eng_count[de][eng]/sum(de_eng_count[de].values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 105,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#Creating English to German dict with word translation probabilities \n",
    "eng_de_prob = defaultdict(dict)\n",
    "\n",
    "for eng in eng_de_count.keys():\n",
    "    for de in eng_de_count[eng].keys():\n",
    "        eng_de_prob[eng][de] = eng_de_count[eng][de]/sum(eng_de_count[eng].values())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's look at some examples of translating individual words from German to English."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 106,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'question': 0.970873786407767, 'issue': 0.019417475728155338, 'matter': 0.009708737864077669}\n",
      "{'rush': 1.0}\n",
      "{'begins': 0.058823529411764705, 'house': 0.9411764705882353}\n"
     ]
    }
   ],
   "source": [
    "#Examples of translating individual words from German to English\n",
    "print de_eng_prob['frage']\n",
    "\n",
    "print de_eng_prob['handlung']\n",
    "\n",
    "print de_eng_prob['haus']\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Building the noisy channel translation model, which uses the english to german translation dictionary and the unigram language model to add \"noise\". "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 107,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#Building noisy channel translation model\n",
    "def de_eng_noisy(german):\n",
    "    noisy={}\n",
    "    for eng in de_eng_prob[german].keys():\n",
    "        noisy[eng] = eng_de_prob[eng][german]+ get_log_prob_addk(eng,unigram_counts,0.0001)\n",
    "    return noisy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's check out the translation using the noise channel approach."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 108,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'father': -8.798834996562721}\n",
      "{'begins': -10.2208672198799, 'house': -8.163007778647888}\n",
      "{'this': -5.214590799418497, 'the': -3.071527829335362, 'that': -4.664995720177421}\n",
      "{'excuse': -11.870404868087332, 'apology': -12.39683538573032, 'comprehend': -11.89683538573032}\n"
     ]
    }
   ],
   "source": [
    "#Test block to check alignments\n",
    "print de_eng_noisy('vater')\n",
    "print de_eng_noisy('haus')\n",
    "print de_eng_noisy('das')\n",
    "print de_eng_noisy('entschuldigung')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translations for 'vater', 'hause', 'das' seem to be pretty good, with the max score going to the best translation. \n",
    "For the word 'entschuldigung', the best possible translation is 'excuse', while 'comprehend' being close. But in real world use, the most common translation for 'entschuldigung' is 'sorry'."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Checking the reverse translation for 'sorry', "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 109,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'bereue': 1.0}"
      ]
     },
     "execution_count": 109,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "eng_de_prob['sorry']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The word 'bereue', which Google translates as 'regret'. This is one example of a 'bad' alignment.\n",
    "\n",
    "Let's try tanslating some queries now. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 122,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "82\n",
      "German: der ( von engl . action : tat , handlung , bewegung ) ist ein filmgenre des unterhaltungskinos , in welchem der fortgang der äußeren handlung von zumeist spektakulär inszenierten kampf - und gewaltszenen vorangetrieben und illustriert wird .\n",
      "\n",
      "English: the ( , guises . action : indeed , rush , movement ) is a filmgenre the unterhaltungskinos , in much the fortgang the external rush , zumeist spektakul\\xe4r inszenierten fight - and gewaltszenen pushed and illustriert will .\n",
      "\n",
      "\n",
      "116\n",
      "German: die ( einheitenzeichen : u für unified atomic mass unit , veraltet amu für atomic mass unit ) ist eine maßeinheit der masse .\n",
      "\n",
      "English: the ( einheitenzeichen : u for unified atomic mass unit , obsolete amu for atomic mass unit ) is a befuddled the mass .\n",
      "\n",
      "\n",
      "240\n",
      "German: der von lateinisch actualis , \" wirklich \" , auch aktualitätsprinzip , uniformitäts - oder gleichförmigkeitsprinzip , englisch uniformitarianism , ist die grundlegende wissenschaftliche methode in der .\n",
      "\n",
      "English: the , lateinisch actualis , `` really `` , , aktualit\\xe4tsprinzip , uniformit\\xe4ts - or gleichf\\xf6rmigkeitsprinzip , english uniformitarianism , is the fundamental scientific method in the .\n",
      "\n",
      "\n",
      "320\n",
      "German: die ( griechisch el , von altgriechisch grc , - \" zusammen - \" , \" anbinden \" , gemeint ist \" die herzbeutel angehängte \" ) , ist ein blutgefäß , welches das blut vom herz wegführt .\n",
      "\n",
      "English: the ( griechisch el , , altgriechisch grc , - `` together - `` , `` anbinden `` , meant is `` the herzbeutel angeh\\xe4ngte `` ) , is a blutgef\\xe4\\xdf , welches the blood vom heart wegf\\xfchrt .\n",
      "\n",
      "\n",
      "540\n",
      "German: unter der bezeichnung fasst man die drei im nördlichen alpenvorland liegenden gewässereinheiten obersee , untersee und seerhein zusammen .\n",
      "\n",
      "English: under the bezeichnung summarizes one the three , northern alpenvorland liegenden gew\\xe4ssereinheiten obersee , untersee and seerhein together .\n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "#Translating first 5 queries into English\n",
    "\n",
    "#Function for direct translation\n",
    "def de_eng_direct(query):\n",
    "    query_english = [] \n",
    "    query_tokens = tokenize(query)\n",
    "    \n",
    "    for token in query_tokens:\n",
    "        try:\n",
    "            query_english.append(max(de_eng_prob[token], key=de_eng_prob[token].get))\n",
    "        except:\n",
    "            query_english.append(token) #Returning the token itself when it cannot be found in the translation table.\n",
    "            #query_english.append(\"NA\") \n",
    "    \n",
    "    return \" \".join(query_english)\n",
    "\n",
    "#Function for noisy channel translation\n",
    "def de_eng_noisy_translate(query):  \n",
    "    query_english = [] \n",
    "    query_tokens = tokenize(query)\n",
    "    \n",
    "    for token in query_tokens:\n",
    "        try:\n",
    "            query_english.append(max(de_eng_noisy(token), key=de_eng_noisy(token).get))\n",
    "        except:\n",
    "            query_english.append(token) #Returning the token itself when it cannot be found in the translation table.\n",
    "            #query_english.append(\"NA\") \n",
    "    \n",
    "    return \" \".join(query_english)\n",
    "            \n",
    "f = open(DEVELOPMENT_QUERIES)\n",
    "\n",
    "lno = 0\n",
    "plno = 0\n",
    "\n",
    "#Also building a dictionary of query ids and query content (only for the first 100s)\n",
    "german_qs = {}\n",
    "\n",
    "test_query_trans_sents = [] #Building a list for perplexity checks.\n",
    "\n",
    "for line in f:\n",
    "    lno+=1\n",
    "    query_id = line.split('\\t')[0]\n",
    "    query_german = line.split('\\t')[1]  \n",
    "    \n",
    "    german_qs[query_id] = query_german.strip()\n",
    "    \n",
    "    translation = str(de_eng_noisy_translate(query_german))\n",
    " \n",
    "    if plno<5:\n",
    "        print query_id + \"\\n\" + \"German: \" + str(query_german) + \"\\n\" + \"English: \" + translation +\"\\n\\n\"\n",
    "        plno+=1\n",
    "    test_query_trans_sents.append(translation)\n",
    "    if lno==100:\n",
    "        break\n",
    "\n",
    "f.close()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The translations of the first 5 queries according to Google translate are as follows: \n",
    "\n",
    "82 of ( . Of eng action : act, action , movement, ) is a film genre of entertainment cinema , in which the continued transition of the external action of mostly spectacularly staged battle - and violent scenes is advanced and illustrated .\n",
    "\n",
    "116 ( unit sign : u for unified atomic mass unit , amu outdated for atomic mass unit ) is a unit of measure of mass .\n",
    "\n",
    "240 of actualis from Latin , \"real\" , even actuality principle , uniformity - or gleichförmigkeitsprinzip , English uniformitarianism , is the basic scientific method in .\n",
    "\n",
    "320 (Greek el , from Ancient Greek grc , - \" together - \" , \" tie \" , is meant \" the heart bag attached\" ) is a blood vessel that leads away the blood from the heart .\n",
    "\n",
    "540 under the designation one summarizes the three lying in the northern waters alpenvorland units obersee , subsea and Seerhein together .\n",
    "\n",
    "---\n",
    "\n",
    "\n",
    "Translations obtained through Google Translate are obviously better. It's interesting to note that our own translation engine works well if a 'word-word' translation is considered, and if the word-pair has been encountered enough times in the bi-lingual corpora. \n",
    "\n",
    "Google Translate also seems to perform better as it's considering phrase based translation, which is more sophisticated and accurate than word-word translation. \n",
    "\n",
    "Our engine also seems to work better for function words rather than content words as those would have been the one encountered a lot in the bi-corpora and are better aligned.\n",
    "\n",
    "\n",
    "The alignments were combined by taking the intersection of the forward and reverse alignments in this case. Combining the two alignments improved things in the sense that the intersection got rid of all the extra 'noise' in the alignments, so that the most likely ones remained (that existed both in the forward and reverse direction)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Combining, and Evaluation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For the final bit, we'll create a function that translates a query, and retrieves the relevant documents for it. \n",
    "\n",
    "Then, to evaluate the results of our CLIR engine, we'll use the [Mean Average Precision](https://www.youtube.com/watch?v=pM6DJ0ZZee0) to judge the performance of the CLIR system. MAP is a standard evaluation metric used in IR."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 123,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "#Building a dictionary for queryids and relevant document ids\n",
    "qrel = defaultdict(list)\n",
    "\n",
    "f = open(DEVELOPMENT_QREL)\n",
    "\n",
    "for line in f:\n",
    "    item = line.split('\\t')\n",
    "    qrel[item[0]].append(item[2])\n",
    "    \n",
    "f.close()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 124,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#Single function to retreive documents for a German query\n",
    "def trans_retr_docs(german_query,no_of_results,translation_function):\n",
    "    \n",
    "    trans_query = \" \".join(extract_and_tokenize_terms(translation_function(german_query)))\n",
    "    return [item[0] for item in retr_docs(trans_query,no_of_results)] #Retriving 100 documents\n",
    "\n",
    "#Calculating the map score\n",
    "def calc_map(no_of_results,translation_function):\n",
    "    \n",
    "    average_precision = []\n",
    "    \n",
    "    for gq in german_qs.keys():\n",
    "        \n",
    "        relevant_docs = qrel[gq]\n",
    "        incremental_precision = []\n",
    "        resulting_docs = trans_retr_docs(german_qs[gq],no_of_results,translation_function)\n",
    "        \n",
    "        total_counter = 0\n",
    "        true_positive_counter = 0\n",
    "        \n",
    "        for doc in resulting_docs:\n",
    "            total_counter+=1\n",
    "            if doc in relevant_docs:\n",
    "                true_positive_counter += 1\n",
    "                incremental_precision.append(true_positive_counter/total_counter)\n",
    "        \n",
    "        #For no relevant retreivals, the average precision will be considered 0.\n",
    "        try:\n",
    "            average_precision.append(sum(incremental_precision)/len(incremental_precision))\n",
    "        except:\n",
    "            average_precision.append(0)\n",
    "        \n",
    "    return (sum(average_precision)/len(average_precision))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To keep runtime at a minimum, we'll only consider the top 100 returned results (documents) when "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 125,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.356571675599\n"
     ]
    }
   ],
   "source": [
    "#Printing the map score for direct translations\n",
    "print calc_map(100,de_eng_direct)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 126,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.364795198505\n"
     ]
    }
   ],
   "source": [
    "#Printing the map score for noisy channel translations\n",
    "print calc_map(100,de_eng_noisy_translate)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "With that, our basic CLIR system is complete. Improvements could be made, expecially in the translation component by using a phrase based model. Or we could use Google to translate the queries for us, and see how well the IR system performs. But that's another area of exploration."
   ]
  }
 ],
 "metadata": {
  "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.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}