cws_maxent.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Chinese Word Segmentation\n",
    "\n",
    "Exploratory notebook for CWS.\n",
    "\n",
    "Segment a standardly written Chinese sentence into words.\n",
    "\n",
    "For example, give the following Chinese sentence:\n",
    "\n",
    "**星期天我们去吃重庆火锅**\n",
    "\n",
    "It produces the output with proper segmentation:\n",
    "\n",
    "**星期天 我们 去 吃 重庆 火锅**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# util libs\n",
    "import numpy as np\n",
    "import time\n",
    "from itertools import izip\n",
    "#from __future__ import division\n",
    "\n",
    "# model libs\n",
    "from sklearn.linear_model import LogisticRegression\n",
    "from sklearn.externals import joblib\n",
    "from nltk.classify.scikitlearn import SklearnClassifier\n",
    "\n",
    "# in-house libs\n",
    "import string_util\n",
    "#reload(string_util)\n",
    "StringUtil = string_util.StringUtil()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Tagging"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag for a sentence. Input a segmented sentence, and output a list of tags.\n",
    "\n",
    "Types of tags:\n",
    "- **s** single character as a word\n",
    "- **b** beginning of a word\n",
    "- **m** middle of a word\n",
    "- **e** end of a word\n",
    "\n",
    "Punctuations (either English or Chinese) will be tagged as **s**.\n",
    "\n",
    "For example, the sample sentence will be tagged as following:\n",
    "\n",
    "**星&nbsp;期&nbsp;天&nbsp;&nbsp;&nbsp;&nbsp;我&nbsp;们&nbsp;&nbsp;&nbsp;&nbsp;去&nbsp;&nbsp;&nbsp;&nbsp;吃&nbsp;&nbsp;&nbsp;重&nbsp;庆&nbsp;&nbsp;&nbsp;火&nbsp;锅 &nbsp;&nbsp;&nbsp;！**\n",
    "\n",
    "**b&nbsp;&nbsp;&nbsp;m&nbsp;&nbsp;&nbsp;e&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;b&nbsp;&nbsp;e&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;s&nbsp;&nbsp;&nbsp;&nbsp;s&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;b&nbsp;&nbsp;&nbsp;e&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;b&nbsp;&nbsp;&nbsp;e&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;s**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def tag_for_sentence(sentence):\n",
    "    words = sentence.decode('utf-8').strip().split()\n",
    "    tags = []\n",
    "    for word in words:\n",
    "        if len(word) > 1:\n",
    "            tags.append('b')\n",
    "            for char in word[1:(len(word) - 1)]:\n",
    "                tags.append('m')\n",
    "            tags.append('e')\n",
    "        else: \n",
    "            tags.append('s')\n",
    "            \n",
    "    return tags"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag for a corpus, and output the tags to a file with each line is a tag"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def tag_for_file(input_path, output_path):\n",
    "    print 'Tagging for %s and output to %s...' % (input_path, output_path)\n",
    "    start = time.time()\n",
    "    \n",
    "    with open(output_path, \"w+\") as output_file:\n",
    "        for line in open(input_path, \"r\").readlines():\n",
    "            line = line.strip().decode(\"utf-8\")\n",
    "            tags = tag_for_sentence(line)\n",
    "            for tag in tags:\n",
    "                output_file.writelines(tag + StringUtil.NEWLINE)\n",
    "    \n",
    "    print 'Done. Total time taken %d seconds' % (time.time() - start)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag for test corpus"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Tagging for data/training/test.utf8 and output to data/preprocessed/tag_test.utf8...\n",
      "Tagging done. Total time taken 0 seconds\n"
     ]
    }
   ],
   "source": [
    "tag_for_file(\"data/training/test.utf8\", \"data/preprocessed/tag_test.utf8\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag for PKU and MSR corpora"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Tagging for data/training/pku_training.utf8 and output to data/preprocessed/tag_pku.utf8...\n",
      "Tagging done. Total time taken 11 seconds\n",
      "Tagging for data/training/msr_training.utf8 and output to data/preprocessed/tag_msr.utf8...\n",
      "Tagging done. Total time taken 25 seconds\n"
     ]
    }
   ],
   "source": [
    "tag_for_file(\"data/training/pku_training.utf8\", \"data/preprocessed/tag_pku.utf8\")\n",
    "tag_for_file(\"data/training/msr_training.utf8\", \"data/preprocessed/tag_msr.utf8\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Features Extraction"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Extract features for a sentence. In case of window size 5, the features are defined as following:\n",
    "\n",
    "- **(a)** $C_{n}$, where $n$ if from -2 to 2\n",
    "- **(b)** $C_{n}C_{n+1}$, where $n$ is from -2 to 1\n",
    "- **(c)** $C_{-1}C_{1}$\n",
    "- **(d)** $Pu$, a boolean value (0 or 1) representing if the current character is a punctuation\n",
    "- **(e)** $T(C_{-2})T(C_{-1})T(C_{0})T(C_{1})T(C_{2})$, type seq of the char seq\n",
    "\n",
    "Sentence boundary: the start-of-sentence character is defined as **< s >**, while the end-of-sentence character is defined as **< /s >**\n",
    "\n",
    "Types are defined as following:\n",
    "- **0** sentence boundary\n",
    "- **1** number char\n",
    "- **2** date char\n",
    "- **3** English letter \n",
    "- **4** others"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def extract_feature_for_sentence(sentence, window_size=5):\n",
    "    if window_size % 2 == 0 or not window_size > 1:\n",
    "        raise ValueError('Window size must be odd number and larger than 1')\n",
    "    \n",
    "    sentence = StringUtil.remove_whitespace(sentence)\n",
    "    total_len = len(sentence)\n",
    "    context_size = window_size / 2\n",
    "    \n",
    "    feature_dict_list = []\n",
    "    \n",
    "    for i, c in enumerate(sentence):\n",
    "        feature_dict = dict()\n",
    "        \n",
    "        c_features = dict()\n",
    "        c_features[\"c0\"] = c\n",
    "        \n",
    "        t_features = dict()\n",
    "        t_features[\"t0\"] = StringUtil.get_character_type(c)\n",
    "        \n",
    "        for context_i in range(1, context_size+1):\n",
    "            c_features[\"c_\"+str(context_i)] = sentence[i-context_i] if i-context_i >=0 \\\n",
    "                                                else StringUtil.SENTENCE_START.decode(\"utf-8\")\n",
    "            c_features[\"c\"+str(context_i)] = sentence[i+context_i] if i+context_i < total_len \\\n",
    "                                                else StringUtil.SENTENCE_END.decode(\"utf-8\")\n",
    "            \n",
    "            t_features[\"t_\"+str(context_i)] = StringUtil.get_character_type(c_features[\"c_\"+str(context_i)])\n",
    "            t_features[\"t\"+str(context_i)] = StringUtil.get_character_type(c_features[\"c\"+str(context_i)])\n",
    "        \n",
    "        # feature a\n",
    "        feature_dict.update(c_features)\n",
    "        \n",
    "        # feature b\n",
    "        for context_i in reversed(range(1, context_size+1)):\n",
    "            if context_i-1 == 0:\n",
    "                feature_dict[\"c_\"+str(context_i)+\"c0\"] = \\\n",
    "                    c_features[\"c_\"+str(context_i)] + c_features[\"c0\"]\n",
    "                    \n",
    "                feature_dict[\"c0\"+\"c\"+str(context_i)] = \\\n",
    "                    c_features[\"c0\"] + c_features[\"c\"+str(context_i)]    \n",
    "                \n",
    "            else:\n",
    "                feature_dict[\"c_\"+str(context_i)+\"c_\"+str(context_i-1)] = \\\n",
    "                    c_features[\"c_\"+str(context_i)] + c_features[\"c_\"+str(context_i-1)]\n",
    "                    \n",
    "                feature_dict[\"c\"+str(context_i-1)+\"c\"+str(context_i)] = \\\n",
    "                    c_features[\"c_\"+str(context_i-1)] + c_features[\"c_\"+str(context_i)]\n",
    "        \n",
    "        # feature c\n",
    "        feature_dict[\"c_1c1\"] = c_features[\"c_1\"] + c_features[\"c1\"]\n",
    "        \n",
    "        # feature d\n",
    "        feature_dict[\"p\"] = \"1\" if StringUtil.is_punctuation(c) else \"0\"\n",
    "        \n",
    "        # feature e\n",
    "        type_feature = reduce(lambda x,y: x+y, t_features.itervalues())\n",
    "        feature_dict[\"t\"] = type_feature\n",
    "        \n",
    "        feature_dict_list.append(feature_dict)\n",
    "        \n",
    "    return feature_dict_list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Quick test"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[{'c0': u'\\u4e00',\n",
       "  'c0c1': u'\\u4e00\\u5e74',\n",
       "  'c1': u'\\u5e74',\n",
       "  'c_1': u'<s>',\n",
       "  'c_1c0': u'<s>\\u4e00',\n",
       "  'c_1c1': u'<s>\\u5e74',\n",
       "  'p': '0',\n",
       "  't': '012'},\n",
       " {'c0': u'\\u5e74',\n",
       "  'c0c1': u'\\u5e741',\n",
       "  'c1': u'1',\n",
       "  'c_1': u'\\u4e00',\n",
       "  'c_1c0': u'\\u4e00\\u5e74',\n",
       "  'c_1c1': u'\\u4e001',\n",
       "  'p': '0',\n",
       "  't': '121'},\n",
       " {'c0': u'1',\n",
       "  'c0c1': u'1y',\n",
       "  'c1': u'y',\n",
       "  'c_1': u'\\u5e74',\n",
       "  'c_1c0': u'\\u5e741',\n",
       "  'c_1c1': u'\\u5e74y',\n",
       "  'p': '0',\n",
       "  't': '213'},\n",
       " {'c0': u'y',\n",
       "  'c0c1': u'y\\u3002',\n",
       "  'c1': u'\\u3002',\n",
       "  'c_1': u'1',\n",
       "  'c_1c0': u'1y',\n",
       "  'c_1c1': u'1\\u3002',\n",
       "  'p': '0',\n",
       "  't': '134'},\n",
       " {'c0': u'\\u3002',\n",
       "  'c0c1': u'\\u3002</s>',\n",
       "  'c1': u'</s>',\n",
       "  'c_1': u'y',\n",
       "  'c_1c0': u'y\\u3002',\n",
       "  'c_1c1': u'y</s>',\n",
       "  'p': '1',\n",
       "  't': '340'}]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "extract_feature_for_sentence(\"一年1y。\".decode(\"utf-8\"), 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def extract_feature_for_file(input_path, output_path, window_size=5):\n",
    "    print 'Extracting features for %s and output to %s...' % (input_path, output_path)\n",
    "    start = time.time()\n",
    "    \n",
    "    with open(output_path, \"w+\") as output_file:\n",
    "        for line in open(input_path, \"r\").readlines():\n",
    "            line = line.strip().decode(\"utf-8\")\n",
    "            feature_dict_list = extract_feature_for_sentence(line, window_size)\n",
    "            for feature_dict in feature_dict_list:\n",
    "                output_file.writelines(StringUtil.to_json(feature_dict) + StringUtil.NEWLINE)\n",
    "    \n",
    "    print 'Done. Total time taken %d seconds' % (time.time() - start)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Extract features for test corpus"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Extracting features for data/training/test.utf8 and output to data/preprocessed/feature_test.utf8...\n",
      "Done. Total time taken 0 seconds\n"
     ]
    }
   ],
   "source": [
    "extract_feature_for_file(\"data/training/test.utf8\", \"data/preprocessed/feature_test.utf8\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Extract features for PKU and MSR corpora with window size = 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 204,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Extracting features for data/training/pku_training.utf8 and output to data/preprocessed/feature_pku.utf8...\n",
      "Done. Total time taken 61 seconds\n",
      "Extracting features for data/training/msr_training.utf8 and output to data/preprocessed/feature_msr.utf8...\n",
      "Done. Total time taken 138 seconds\n"
     ]
    }
   ],
   "source": [
    "extract_feature_for_file(\"data/training/pku_training.utf8\", \"data/preprocessed/feature_pku.utf8\")\n",
    "extract_feature_for_file(\"data/training/msr_training.utf8\", \"data/preprocessed/feature_msr.utf8\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Improvements: Use of External Dictionary\n",
    "\n",
    "Additional features to use external dictionary. We want to find a word in the dictionary with maximum length that contains the current character.\n",
    "\n",
    "Let $W$ be the matched word containing $C_{0}$, $t_{0}$ be the tag for $C_{0} in $W$, $and $L$ be the length of $W$. Then we can add the following additional features:\n",
    "- **(f)** $Lt_{0}$\n",
    "- **(g)** $C_{n}t_{0}$, where $n$ = -1, 0, 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def load_dict(dict_path):\n",
    "    ref_dict = dict()\n",
    "    for line in open(dict_path, 'r').readlines():\n",
    "        word = line.strip().decode('utf-8')\n",
    "        ref_dict[word] = len(word)\n",
    "        \n",
    "    return ref_dict"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def extract_dict_feature(sentence, curr_i, ref_dict, window_size=10):\n",
    "    start_index = curr_i - (window_size - 1)\n",
    "    if start_index < 0:\n",
    "        start_index = 0\n",
    "        \n",
    "    end_index = curr_i + window_size\n",
    "    if end_index > len(sentence):\n",
    "        end_index = len(sentence)\n",
    "    \n",
    "    t0 = 's'\n",
    "    L = 0\n",
    "    \n",
    "    for i in range(start_index, curr_i+1):\n",
    "        for j in range(curr_i+1, end_index+1):\n",
    "            if sentence[i:j] in ref_dict and j-i > L:\n",
    "                L = j - i\n",
    "                \n",
    "                if j-i == 1:\n",
    "                    t0 = 's'\n",
    "                if i == curr_i:\n",
    "                    t0 = 'b'\n",
    "                elif j-1 == curr_i:\n",
    "                    t0 = 'e'\n",
    "                else:\n",
    "                    t0 = 'm'\n",
    "                \n",
    "    return (L, t0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Quick test"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "ref_dict = load_dict(\"data/dict/processed.utf8\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(4, 'm')"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "extract_dict_feature(\"争分夺秒\".decode('utf-8'), 2, ref_dict)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Updated feature extraction function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def extract_feature_for_sentence_v2(sentence, ref_dict, window_size=5):\n",
    "    if window_size % 2 == 0 or not window_size > 1:\n",
    "        raise ValueError('Window size must be odd number and larger than 1')\n",
    "    \n",
    "    sentence = StringUtil.remove_whitespace(sentence)\n",
    "    total_len = len(sentence)\n",
    "    context_size = window_size / 2\n",
    "    \n",
    "    feature_dict_list = []\n",
    "    \n",
    "    for i, c in enumerate(sentence):\n",
    "        feature_dict = dict()\n",
    "        \n",
    "        c_features = dict()\n",
    "        c_features[\"c0\"] = c\n",
    "        \n",
    "        t_features = dict()\n",
    "        t_features[\"t0\"] = StringUtil.get_character_type(c)\n",
    "        \n",
    "        for context_i in range(1, context_size+1):\n",
    "            c_features[\"c_\"+str(context_i)] = sentence[i-context_i] if i-context_i >=0 \\\n",
    "                                                else StringUtil.SENTENCE_START.decode(\"utf-8\")\n",
    "            c_features[\"c\"+str(context_i)] = sentence[i+context_i] if i+context_i < total_len \\\n",
    "                                                else StringUtil.SENTENCE_END.decode(\"utf-8\")\n",
    "            \n",
    "            t_features[\"t_\"+str(context_i)] = StringUtil.get_character_type(c_features[\"c_\"+str(context_i)])\n",
    "            t_features[\"t\"+str(context_i)] = StringUtil.get_character_type(c_features[\"c\"+str(context_i)])\n",
    "        \n",
    "        # feature a\n",
    "        feature_dict.update(c_features)\n",
    "        \n",
    "        # feature b\n",
    "        for context_i in reversed(range(1, context_size+1)):\n",
    "            if context_i-1 == 0:\n",
    "                feature_dict[\"c_\"+str(context_i)+\"c0\"] = \\\n",
    "                    c_features[\"c_\"+str(context_i)] + c_features[\"c0\"]\n",
    "                    \n",
    "                feature_dict[\"c0\"+\"c\"+str(context_i)] = \\\n",
    "                    c_features[\"c0\"] + c_features[\"c\"+str(context_i)]    \n",
    "                \n",
    "            else:\n",
    "                feature_dict[\"c_\"+str(context_i)+\"c_\"+str(context_i-1)] = \\\n",
    "                    c_features[\"c_\"+str(context_i)] + c_features[\"c_\"+str(context_i-1)]\n",
    "                    \n",
    "                feature_dict[\"c\"+str(context_i-1)+\"c\"+str(context_i)] = \\\n",
    "                    c_features[\"c_\"+str(context_i-1)] + c_features[\"c_\"+str(context_i)]\n",
    "        \n",
    "        # feature c\n",
    "        feature_dict[\"c_1c1\"] = c_features[\"c_1\"] + c_features[\"c1\"]\n",
    "        \n",
    "        # feature d\n",
    "        feature_dict[\"p\"] = \"1\" if StringUtil.is_punctuation(c) else \"0\"\n",
    "        \n",
    "        # feature e\n",
    "        type_feature = reduce(lambda x,y: x+y, t_features.itervalues())\n",
    "        feature_dict[\"t\"] = type_feature\n",
    "        \n",
    "        matched = extract_dict_feature(sentence, i, ref_dict)\n",
    "        \n",
    "        # feature f\n",
    "        feature_dict[\"Lt0\"] = str(matched[0]) + matched[1]\n",
    "\n",
    "        # feature g\n",
    "        feature_dict[\"c_1t0\"] = c_features[\"c_1\"] + matched[1]\n",
    "        feature_dict[\"c0t0\"] = c_features[\"c0\"] + matched[1]\n",
    "        feature_dict[\"c1t0\"] = c_features[\"c1\"] + matched[1]\n",
    "\n",
    "        feature_dict_list.append(feature_dict)\n",
    "        \n",
    "    return feature_dict_list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Quick test"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[{'Lt0': '0s',\n",
       "  'c0': u'\\u4e00',\n",
       "  'c0c1': u'\\u4e00\\u5e74',\n",
       "  'c0t0': u'\\u4e00s',\n",
       "  'c1': u'\\u5e74',\n",
       "  'c1t0': u'\\u5e74s',\n",
       "  'c_1': u'<s>',\n",
       "  'c_1c0': u'<s>\\u4e00',\n",
       "  'c_1c1': u'<s>\\u5e74',\n",
       "  'c_1t0': u'<s>s',\n",
       "  'p': '0',\n",
       "  't': '012'},\n",
       " {'Lt0': '0s',\n",
       "  'c0': u'\\u5e74',\n",
       "  'c0c1': u'\\u5e74\\u4e89',\n",
       "  'c0t0': u'\\u5e74s',\n",
       "  'c1': u'\\u4e89',\n",
       "  'c1t0': u'\\u4e89s',\n",
       "  'c_1': u'\\u4e00',\n",
       "  'c_1c0': u'\\u4e00\\u5e74',\n",
       "  'c_1c1': u'\\u4e00\\u4e89',\n",
       "  'c_1t0': u'\\u4e00s',\n",
       "  'p': '0',\n",
       "  't': '124'},\n",
       " {'Lt0': '4b',\n",
       "  'c0': u'\\u4e89',\n",
       "  'c0c1': u'\\u4e89\\u5206',\n",
       "  'c0t0': u'\\u4e89b',\n",
       "  'c1': u'\\u5206',\n",
       "  'c1t0': u'\\u5206b',\n",
       "  'c_1': u'\\u5e74',\n",
       "  'c_1c0': u'\\u5e74\\u4e89',\n",
       "  'c_1c1': u'\\u5e74\\u5206',\n",
       "  'c_1t0': u'\\u5e74b',\n",
       "  'p': '0',\n",
       "  't': '244'},\n",
       " {'Lt0': '4m',\n",
       "  'c0': u'\\u5206',\n",
       "  'c0c1': u'\\u5206\\u593a',\n",
       "  'c0t0': u'\\u5206m',\n",
       "  'c1': u'\\u593a',\n",
       "  'c1t0': u'\\u593am',\n",
       "  'c_1': u'\\u4e89',\n",
       "  'c_1c0': u'\\u4e89\\u5206',\n",
       "  'c_1c1': u'\\u4e89\\u593a',\n",
       "  'c_1t0': u'\\u4e89m',\n",
       "  'p': '0',\n",
       "  't': '444'},\n",
       " {'Lt0': '4m',\n",
       "  'c0': u'\\u593a',\n",
       "  'c0c1': u'\\u593a\\u79d2',\n",
       "  'c0t0': u'\\u593am',\n",
       "  'c1': u'\\u79d2',\n",
       "  'c1t0': u'\\u79d2m',\n",
       "  'c_1': u'\\u5206',\n",
       "  'c_1c0': u'\\u5206\\u593a',\n",
       "  'c_1c1': u'\\u5206\\u79d2',\n",
       "  'c_1t0': u'\\u5206m',\n",
       "  'p': '0',\n",
       "  't': '444'},\n",
       " {'Lt0': '4e',\n",
       "  'c0': u'\\u79d2',\n",
       "  'c0c1': u'\\u79d2\\u3002',\n",
       "  'c0t0': u'\\u79d2e',\n",
       "  'c1': u'\\u3002',\n",
       "  'c1t0': u'\\u3002e',\n",
       "  'c_1': u'\\u593a',\n",
       "  'c_1c0': u'\\u593a\\u79d2',\n",
       "  'c_1c1': u'\\u593a\\u3002',\n",
       "  'c_1t0': u'\\u593ae',\n",
       "  'p': '0',\n",
       "  't': '444'},\n",
       " {'Lt0': '0s',\n",
       "  'c0': u'\\u3002',\n",
       "  'c0c1': u'\\u3002</s>',\n",
       "  'c0t0': u'\\u3002s',\n",
       "  'c1': u'</s>',\n",
       "  'c1t0': u'</s>s',\n",
       "  'c_1': u'\\u79d2',\n",
       "  'c_1c0': u'\\u79d2\\u3002',\n",
       "  'c_1c1': u'\\u79d2</s>',\n",
       "  'c_1t0': u'\\u79d2s',\n",
       "  'p': '1',\n",
       "  't': '440'}]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "extract_feature_for_sentence_v2(\"一年争分夺秒。\".decode(\"utf-8\"), ref_dict, 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def extract_feature_for_file_v2(input_path, output_path, ref_dict, window_size=5):\n",
    "    print 'Extracting features (v2) for %s and output to %s...' % (input_path, output_path)\n",
    "    start = time.time()\n",
    "    \n",
    "    with open(output_path, \"w+\") as output_file:\n",
    "        for line in open(input_path, \"r\").readlines():\n",
    "            line = line.strip().decode(\"utf-8\")\n",
    "            feature_dict_list = extract_feature_for_sentence_v2(line, ref_dict, window_size)\n",
    "            for feature_dict in feature_dict_list:\n",
    "                output_file.writelines(StringUtil.to_json(feature_dict) + StringUtil.NEWLINE)\n",
    "    \n",
    "    print 'Done. Total time taken %d seconds' % (time.time() - start)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Train a MaxEnt Model (nltk)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Use nltk MaxEnt model"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import nltk\n",
    "import pickle"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def train_model(feature_path, tag_path, model_path, iteration=100):\n",
    "    print 'Loading training data..'\n",
    "    train_data = []\n",
    "    with open(feature_path, 'r') as feature_file, open(tag_path, 'r') as tag_file:\n",
    "        for feature_line, tag_line in izip(feature_file, tag_file):\n",
    "            feature_json = feature_line.strip()\n",
    "            tag = tag_line.strip()\n",
    "            #print(\"{0}\\t{1}\".format(feature_json, tag))\n",
    "            \n",
    "            feature_dict = StringUtil.from_json(feature_json)\n",
    "            train_data.append((feature_dict, tag))\n",
    "    print 'Done'\n",
    "            \n",
    "    algorithm = nltk.classify.MaxentClassifier.ALGORITHMS[0] #GIS Algorithm  \n",
    "    print(\"Start to train the model with {0}...\".format(algorithm))\n",
    "    start = time.time()\n",
    "    \n",
    "    classifier = nltk.MaxentClassifier.train(train_data, algorithm, max_iter=iteration)\n",
    "    \n",
    "    print('Done. Total time taken {0} seconds'.format(time.time() - start))\n",
    "    \n",
    "    # save the model to a file\n",
    "    f = open(model_path, 'wb')\n",
    "    pickle.dump(classifier, f)\n",
    "    f.close()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Test with small dataset"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 247,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Start to train the model with GIS...\n",
      "  ==> Training (100 iterations)\n",
      "\n",
      "      Iteration    Log Likelihood    Accuracy\n",
      "      ---------------------------------------\n",
      "             1          -1.38629        0.278\n",
      "             2          -0.19100        1.000\n",
      "             3          -0.08377        1.000\n",
      "             4          -0.05237        1.000\n",
      "             5          -0.03788        1.000\n",
      "             6          -0.02961        1.000\n",
      "             7          -0.02429        1.000\n",
      "             8          -0.02058        1.000\n",
      "             9          -0.01785        1.000\n",
      "            10          -0.01576        1.000\n",
      "            11          -0.01411        1.000\n",
      "            12          -0.01277        1.000\n",
      "            13          -0.01167        1.000\n",
      "            14          -0.01074        1.000\n",
      "            15          -0.00995        1.000\n",
      "            16          -0.00926        1.000\n",
      "            17          -0.00867        1.000\n",
      "            18          -0.00815        1.000\n",
      "            19          -0.00768        1.000\n",
      "            20          -0.00727        1.000\n",
      "            21          -0.00690        1.000\n",
      "            22          -0.00657        1.000\n",
      "            23          -0.00626        1.000\n",
      "            24          -0.00599        1.000\n",
      "            25          -0.00573        1.000\n",
      "            26          -0.00550        1.000\n",
      "            27          -0.00529        1.000\n",
      "            28          -0.00509        1.000\n",
      "            29          -0.00491        1.000\n",
      "            30          -0.00473        1.000\n",
      "            31          -0.00458        1.000\n",
      "            32          -0.00443        1.000\n",
      "            33          -0.00429        1.000\n",
      "            34          -0.00416        1.000\n",
      "            35          -0.00403        1.000\n",
      "            36          -0.00392        1.000\n",
      "            37          -0.00381        1.000\n",
      "            38          -0.00370        1.000\n",
      "            39          -0.00361        1.000\n",
      "            40          -0.00351        1.000\n",
      "            41          -0.00343        1.000\n",
      "            42          -0.00334        1.000\n",
      "            43          -0.00326        1.000\n",
      "            44          -0.00319        1.000\n",
      "            45          -0.00311        1.000\n",
      "            46          -0.00304        1.000\n",
      "            47          -0.00298        1.000\n",
      "            48          -0.00292        1.000\n",
      "            49          -0.00285        1.000\n",
      "            50          -0.00280        1.000\n",
      "            51          -0.00274        1.000\n",
      "            52          -0.00269        1.000\n",
      "            53          -0.00264        1.000\n",
      "            54          -0.00259        1.000\n",
      "            55          -0.00254        1.000\n",
      "            56          -0.00249        1.000\n",
      "            57          -0.00245        1.000\n",
      "            58          -0.00240        1.000\n",
      "            59          -0.00236        1.000\n",
      "            60          -0.00232        1.000\n",
      "            61          -0.00228        1.000\n",
      "            62          -0.00225        1.000\n",
      "            63          -0.00221        1.000\n",
      "            64          -0.00218        1.000\n",
      "            65          -0.00214        1.000\n",
      "            66          -0.00211        1.000\n",
      "            67          -0.00208        1.000\n",
      "            68          -0.00205        1.000\n",
      "            69          -0.00202        1.000\n",
      "            70          -0.00199        1.000\n",
      "            71          -0.00196        1.000\n",
      "            72          -0.00193        1.000\n",
      "            73          -0.00191        1.000\n",
      "            74          -0.00188        1.000\n",
      "            75          -0.00185        1.000\n",
      "            76          -0.00183        1.000\n",
      "            77          -0.00181        1.000\n",
      "            78          -0.00178        1.000\n",
      "            79          -0.00176        1.000\n",
      "            80          -0.00174        1.000\n",
      "            81          -0.00172        1.000\n",
      "            82          -0.00169        1.000\n",
      "            83          -0.00167        1.000\n",
      "            84          -0.00165        1.000\n",
      "            85          -0.00163        1.000\n",
      "            86          -0.00162        1.000\n",
      "            87          -0.00160        1.000\n",
      "            88          -0.00158        1.000\n",
      "            89          -0.00156        1.000\n",
      "            90          -0.00154        1.000\n",
      "            91          -0.00153        1.000\n",
      "            92          -0.00151        1.000\n",
      "            93          -0.00149        1.000\n",
      "            94          -0.00148        1.000\n",
      "            95          -0.00146        1.000\n",
      "            96          -0.00145        1.000\n",
      "            97          -0.00143        1.000\n",
      "            98          -0.00142        1.000\n",
      "            99          -0.00140        1.000\n",
      "         Final          -0.00139        1.000\n",
      "Done. Total time taken 1.23600006104 seconds\n"
     ]
    }
   ],
   "source": [
    "train_model(\"data/preprocessed/feature_test.utf8\", \"data/preprocessed/tag_test.utf8\", \"data/model/test.pickle\", 100)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 235,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['b', 'e', 's', 's', 'b', 'e', 's', 'b', 'm', 'e', 's']\n"
     ]
    }
   ],
   "source": [
    "f = open('data/model/test.pickle', 'rb')\n",
    "classifier = pickle.load(f)\n",
    "f.close()\n",
    "\n",
    "feature_list = extract_feature_for_sentence(\"测试一！通过：333。\".decode(\"utf-8\"))\n",
    "results = classifier.classify_many(feature_list)\n",
    "print results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 238,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['m', 's', 'b', 'e']\n",
      "-6.43708881328\n"
     ]
    }
   ],
   "source": [
    "tests = classifier.prob_classify(feature_list[0])\n",
    "print tests.samples()\n",
    "print tests.logprob('b')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Train with corpus"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "train_model(\"data/preprocessed/feature_pku.utf8\", \"data/preprocessed/tag_pku.utf8\", \"data/model/pku.pickle\", 100)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![GIS model diagram](img/GIS nltk.PNG)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The nltk implementation is too slow. Almost 1 hour for 10 iterations. It is not practical to use in production."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Train a MaxEnt Model (scikit-learn)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Use model from scikit-learn package for better performance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def train_model_sklearn(feature_path, tag_path, model_path):\n",
    "    print 'Loading training data..'\n",
    "    train_data = []\n",
    "    with open(feature_path, 'r') as feature_file, open(tag_path, 'r') as tag_file:\n",
    "        for feature_line, tag_line in izip(feature_file, tag_file):\n",
    "            feature_json = feature_line.strip()\n",
    "            tag = tag_line.strip()\n",
    "            #print(\"{0}\\t{1}\".format(feature_json, tag))\n",
    "            \n",
    "            feature_dict = StringUtil.from_json(feature_json)\n",
    "            train_data.append((feature_dict, tag))\n",
    "    print 'Done'\n",
    "            \n",
    "    model = SklearnClassifier(LogisticRegression())\n",
    "    print \"Start to train the model...\"\n",
    "    start = time.time()\n",
    "    \n",
    "    classifier = model.train(train_data)\n",
    "    \n",
    "    print('Done. Total time taken {0} seconds'.format(time.time() - start))\n",
    "    \n",
    "    # save the model to a file\n",
    "    joblib.dump(classifier, model_path, compress=0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Test with small dataset"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Loading training data..\n",
      "Done\n",
      "Start to train the model...\n",
      "[LibLinear]Done. Total time taken 0.0090000629425 seconds\n"
     ]
    }
   ],
   "source": [
    "train_model_sklearn(\"data/preprocessed/feature_test.utf8\", \"data/preprocessed/tag_test.utf8\", \"data/model/test_sklearn\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['b', 'e', 's', 's', 'b', 'e', 's', 'b', 'm', 'e', 's']\n"
     ]
    }
   ],
   "source": [
    "classifier = joblib.load(\"data/model/test_sklearn\", mmap_mode='r')\n",
    "\n",
    "feature_list = extract_feature_for_sentence(\"测试一！通过：333。\".decode(\"utf-8\"))\n",
    "results = classifier.classify_many(feature_list)\n",
    "print results"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Train with corpus"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Train with PKU corpus"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Loading training data..\n",
      "Done\n",
      "Start to train the model...\n",
      "Done. Total time taken 647.667000055 seconds\n"
     ]
    }
   ],
   "source": [
    "train_model_sklearn(\"data/preprocessed/feature_pku.utf8\", \"data/preprocessed/tag_pku.utf8\", \"data/model/pku_sklearn\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Model Evaluation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Dynamic programming to make sure the correct tag sequence.\n",
    "\n",
    "List of invalid tag sequences:\n",
    "- m -> s\n",
    "- m -> b\n",
    "- s -> m\n",
    "- s -> e\n",
    "- b -> s\n",
    "- e -> m\n",
    "- b -> b\n",
    "- e -> e\n",
    "- m -> m\n",
    "\n",
    "Also, a sentence should never start with tag **m** or **e**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def get_best_tag_seq(feature_list, classifier):\n",
    "    \n",
    "    # Map of (index, tag) -> log probability\n",
    "    delta = dict()\n",
    "    # Backpointers, map of (index, tag) -> previous tag\n",
    "    bp = dict()\n",
    "    \n",
    "    for i, feature_dict in enumerate(feature_list):\n",
    "        prob_distribution = classifier.prob_classify(feature_dict)\n",
    "        \n",
    "        if i == 0:\n",
    "            for t in StringUtil.TAG_SET:\n",
    "                if not t == 'm' and not t == 'e':\n",
    "                    delta[(i, t)] = prob_distribution.logprob(t)\n",
    "\n",
    "        else:\n",
    "            for t in StringUtil.TAG_SET:\n",
    "                max_term = max([(prob_distribution.logprob(t) + delta[(i - 1, t_1)], t_1)\n",
    "                                    if not t_1 + t in StringUtil.INVALID_TAG_SEQ and (i - 1, t_1) in delta else (-np.inf, t_1)\n",
    "                                        for t_1 in StringUtil.TAG_SET])\n",
    "                \n",
    "                delta[(i, t)] = max_term[0]\n",
    "                bp[(i, t)] = max_term[1]\n",
    "    \n",
    "    n = len(feature_list)\n",
    "    end_score, end_tag = max([(delta[(n-1, t)], t) if (n-1, t) in delta else (-np.inf, t) for t in StringUtil.TAG_SET])\n",
    "\n",
    "    # Follow backpointers to obtain sequence with the highest score.\n",
    "    tags = [end_tag]\n",
    "    for i in reversed(range(0, n-1)):\n",
    "        tags.append(bp[(i + 1, tags[-1])])\n",
    "    return list(reversed(tags))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Quick test for valid sequence function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['b', 'e', 's', 's', 'b', 'e', 's', 'b', 'm', 'e', 's']\n"
     ]
    }
   ],
   "source": [
    "test_classifier = joblib.load(\"data/model/test_sklearn\", mmap_mode='r')\n",
    "feature_list = extract_feature_for_sentence(\"测试一！通过：333。\".decode(\"utf-8\"))\n",
    "print get_best_tag_seq(feature_list, test_classifier)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Test tagging against another corpus"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Function to output predicted tags to a file"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def get_tags_and_output_to_file(input_file_path, result_output_path, model_path):\n",
    "    classifier = joblib.load(model_path, mmap_mode='r')\n",
    "        \n",
    "    with open(result_output_path, \"w+\") as output_file:\n",
    "        count = 1\n",
    "        for line in open(input_file_path, \"r\").readlines():\n",
    "            line = line.strip().decode(\"utf-8\")\n",
    "            feature_list = extract_feature_for_sentence(line)\n",
    "            predicted_tags = get_best_tag_seq(feature_list, classifier)\n",
    "            for tag in predicted_tags:\n",
    "                output_file.writelines(tag + StringUtil.NEWLINE)\n",
    "\n",
    "            # for evaluation purpose, only take first 1K sentences\n",
    "            count += 1\n",
    "            if count == 1000:\n",
    "                break"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Function to compare predicted tags against gold standard tags and print model accuracy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "def print_model_accuracy(result_file_path, gold_standard_file_path):\n",
    "    count = 0\n",
    "    correct = 0\n",
    "    with open(gold_standard_file_path, 'r') as expect_file, open(result_file_path, 'r') as result_file:\n",
    "        for expect_line, result_line in izip(expect_file, result_file):\n",
    "            count += 1\n",
    "            if expect_line.strip() == result_line.strip():\n",
    "                correct +=1\n",
    "\n",
    "    print \"Accuracy: {0}\".format(float(correct)/count)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Test model trained with PKU corpus against MSR corpus"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 134,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Accuracy: 0.911795996002\n"
     ]
    }
   ],
   "source": [
    "get_tags_and_output_to_file(\"data/training/msr_training.utf8\", \"data/result/msr.utf8\", \"data/model/pku_sklearn\")\n",
    "\n",
    "print_model_accuracy(\"data/result/msr.utf8\", \"data/preprocessed/tag_msr.utf8\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Comparing the model with window size = 3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Extract features for PKU and MSR corpora with window size = 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Extracting features for data/training/pku_training.utf8 and output to data/preprocessed/feature_w3_pku.utf8...\n",
      "Done. Total time taken 41 seconds\n",
      "Extracting features for data/training/msr_training.utf8 and output to data/preprocessed/feature_w3_msr.utf8...\n",
      "Done. Total time taken 97 seconds\n"
     ]
    }
   ],
   "source": [
    "extract_feature_for_file(\"data/training/pku_training.utf8\", \"data/preprocessed/feature_w3_pku.utf8\", 3)\n",
    "extract_feature_for_file(\"data/training/msr_training.utf8\", \"data/preprocessed/feature_w3_msr.utf8\", 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 106,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Loading training data..\n",
      "Done\n",
      "Start to train the model...\n",
      "Done. Total time taken 537.802000046 seconds\n"
     ]
    }
   ],
   "source": [
    "train_model_sklearn(\"data/preprocessed/feature_w3_pku.utf8\", \"data/preprocessed/tag_pku.utf8\", \"data/model/pku_w3_sklearn\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 110,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Accuracy: 0.911247944808\n"
     ]
    }
   ],
   "source": [
    "get_tags_and_output_to_file(\"data/training/msr_training.utf8\", \"data/result/msr_w3.utf8\", \"data/model/pku_w3_sklearn\")\n",
    "\n",
    "print_model_accuracy(\"data/result/msr_w3.utf8\", \"data/preprocessed/tag_msr.utf8\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Comparing the model with window size = 7"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Extract features for PKU and MSR corpora with window size = 7"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Extracting features for data/training/pku_training.utf8 and output to data/preprocessed/feature_w7_pku.utf8...\n",
      "Done. Total time taken 86 seconds\n"
     ]
    }
   ],
   "source": [
    "extract_feature_for_file(\"data/training/pku_training.utf8\", \"data/preprocessed/feature_w7_pku.utf8\", 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Loading training data..\n",
      "Done\n",
      "Start to train the model...\n",
      "Done. Total time taken 770.940000057 seconds\n"
     ]
    }
   ],
   "source": [
    "train_model_sklearn(\"data/preprocessed/feature_w7_pku.utf8\", \"data/preprocessed/tag_pku.utf8\", \"data/model/pku_w7_sklearn\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Accuracy: 0.909313646475\n"
     ]
    }
   ],
   "source": [
    "get_tags_and_output_to_file(\"data/training/msr_training.utf8\", \"data/result/msr_w7.utf8\", \"data/model/pku_w7_sklearn\")\n",
    "\n",
    "print_model_accuracy(\"data/result/msr_w7.utf8\", \"data/preprocessed/tag_msr.utf8\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Comparing the accuracies:\n",
    "- window size 5: **0.911795996002**\n",
    "- window size 3: **0.911247944808**\n",
    "- window size 7: **0.909313646475**\n",
    "\n",
    "Looks like the model with window size **5** is the best."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Test model with external dictionary features"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "ref_dict = load_dict(\"data/dict/processed.utf8\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Extracting features (v2) for data/training/pku_training.utf8 and output to data/preprocessed/feature_pku_v2.utf8...\n",
      "Done. Total time taken 100 seconds\n"
     ]
    }
   ],
   "source": [
    "extract_feature_for_file_v2(\"data/training/pku_training.utf8\", \"data/preprocessed/feature_pku_v2.utf8\", ref_dict)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Loading training data..\n",
      "Done\n",
      "Start to train the model...\n",
      "Done. Total time taken 844.114000082 seconds\n"
     ]
    }
   ],
   "source": [
    "train_model_sklearn(\"data/preprocessed/feature_pku_v2.utf8\", \"data/preprocessed/tag_pku.utf8\", \"data/model/pku_sklearn_v2\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def get_tags_and_output_to_file_v2(input_file_path, result_output_path, model_path, ref_dict):\n",
    "    classifier = joblib.load(model_path, mmap_mode='r')\n",
    "        \n",
    "    with open(result_output_path, \"w+\") as output_file:\n",
    "        count = 1\n",
    "        for line in open(input_file_path, \"r\").readlines():\n",
    "            line = line.strip().decode(\"utf-8\")\n",
    "            feature_list = extract_feature_for_sentence_v2(line, ref_dict)\n",
    "            predicted_tags = get_best_tag_seq(feature_list, classifier)\n",
    "            for tag in predicted_tags:\n",
    "                output_file.writelines(tag + StringUtil.NEWLINE)\n",
    "\n",
    "            # for evaluation purpose, only take first 1K sentences\n",
    "            count += 1\n",
    "            if count == 1000:\n",
    "                break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Accuracy: 0.920339146974\n"
     ]
    }
   ],
   "source": [
    "get_tags_and_output_to_file_v2(\"data/training/msr_training.utf8\", \"data/result/msr_v2.utf8\", \"data/model/pku_sklearn_v2\",\n",
    "                               ref_dict)\n",
    "\n",
    "print_model_accuracy(\"data/result/msr_v2.utf8\", \"data/preprocessed/tag_msr.utf8\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Comparing the accuracies:\n",
    "- Model without external dictionary: **0.911795996002**\n",
    "- Model with external dictionary: **0.920339146974**\n",
    "\n",
    "The model with external dictionary has improved."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Output Segmented Sentence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Output tags"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def get_tags_for_sentence(sentence, classifier):\n",
    "    feature_list = extract_feature_for_sentence(sentence)\n",
    "    return get_best_tag_seq(feature_list, classifier)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Output the segmented result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def do_segmentation_for_partial_sentence(sentence, classifier):\n",
    "    tags = get_tags_for_sentence(sentence, classifier)\n",
    "    \n",
    "    output = []\n",
    "    total_len = len(tags)\n",
    "    \n",
    "    for i, t in enumerate(tags):\n",
    "        output.append(sentence[i])\n",
    "        if i < total_len -1:\n",
    "            if t == 's' or t == 'e':\n",
    "                output.append(StringUtil.SPACE)\n",
    "                \n",
    "    return StringUtil.EMPTY.join(output)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If the original sentence contains white spaces, take the spaces as natural segmentations"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def do_segmentation_for_sentence(sentence, classifier):\n",
    "    sentence = sentence.strip().decode(\"utf-8\")\n",
    "    segments = sentence.split()\n",
    "    \n",
    "    return StringUtil.SPACE.join([do_segmentation_for_partial_sentence(s, classifier) for s in segments])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Quick test\n",
    "\n",
    "Load a model"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "pku_classifier = joblib.load(\"data/model/pku_sklearn\", mmap_mode='r')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Test file i/o with Chinese characters"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "星期天 我们 去 吃 重庆 火锅\n"
     ]
    }
   ],
   "source": [
    "result = do_segmentation_for_sentence(\"星期天我们去吃重庆火锅\", pku_classifier)\n",
    "with open(\"data/result/test_segmentation.utf8\", \"w+\") as output_file:\n",
    "    output_file.writelines(result.encode('utf-8'))\n",
    "for line in open(\"data/result/test_segmentation.utf8\", \"r\").readlines():\n",
    "    print line"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "With V2 feature extraction:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def get_tags_for_sentence_v2(sentence, classifier, ref_dict):\n",
    "    feature_list = extract_feature_for_sentence_v2(sentence, ref_dict)\n",
    "    return get_best_tag_seq(feature_list, classifier)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def do_segmentation_for_partial_sentence_v2(sentence, classifier, ref_dict):\n",
    "    tags = get_tags_for_sentence_v2(sentence, classifier, ref_dict)\n",
    "    \n",
    "    output = []\n",
    "    total_len = len(tags)\n",
    "    \n",
    "    for i, t in enumerate(tags):\n",
    "        output.append(sentence[i])\n",
    "        if i < total_len -1:\n",
    "            if t == 's' or t == 'e':\n",
    "                output.append(StringUtil.SPACE)\n",
    "                \n",
    "    return StringUtil.EMPTY.join(output)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def do_segmentation_for_sentence_v2(sentence, classifier, ref_dict):\n",
    "    sentence = sentence.strip().decode(\"utf-8\")\n",
    "    segments = sentence.split()\n",
    "    \n",
    "    return StringUtil.SPACE.join([do_segmentation_for_partial_sentence_v2(s, classifier, ref_dict) for s in segments])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Test for any sentence"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "ref_dict = load_dict(\"data/dict/processed.utf8\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "v2_classifier = joblib.load(\"data/model/pku_sklearn_v2\", mmap_mode='r')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "苹果 6S 通用 手机 防尘 塞 金属\n",
      "苹果 6S 通用 手机 防尘塞 金属\n"
     ]
    }
   ],
   "source": [
    "print do_segmentation_for_sentence(\"苹果6S通用手机防尘塞金属\", pku_classifier)\n",
    "print do_segmentation_for_sentence_v2(\"苹果6S通用手机防尘塞金属\", v2_classifier, ref_dict)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "男韩版 宽松 短袖 T恤 圆领 日 系 五 分袖 学生 上衣\n",
      "男 韩版 宽松 短袖 T恤 圆领 日系 五分袖 学生 上衣\n"
     ]
    }
   ],
   "source": [
    "print do_segmentation_for_sentence(\"男韩版宽松短袖T恤 圆领日系五分袖学生上衣\", pku_classifier)\n",
    "print do_segmentation_for_sentence_v2(\"男韩版宽松短袖T恤 圆领日系五分袖学生上衣\", v2_classifier, ref_dict)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "美式 复古 豹子 卡通 短袖 T恤潮 男女 原宿 街头 滑板 宽松 圆领 体 恤半袖TE E\n",
      "美式 复古 豹子 卡通 短袖 T恤 潮 男女 原宿 街头 滑板 宽松 圆领 体恤 半袖 TEE\n"
     ]
    }
   ],
   "source": [
    "print do_segmentation_for_sentence(\"美式复古豹子卡通短袖T恤潮男女原宿街头滑板宽松圆领体恤半袖TEE\", pku_classifier)\n",
    "print do_segmentation_for_sentence_v2(\"美式复古豹子卡通短袖T恤潮男女原宿街头滑板宽松圆领体恤半袖TEE\", v2_classifier, ref_dict)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "上海 自来水 来自 海上\n",
      "上海 自来水 来自 海上\n"
     ]
    }
   ],
   "source": [
    "print do_segmentation_for_sentence(\"上海自来水来自海上\", pku_classifier)\n",
    "print do_segmentation_for_sentence_v2(\"上海自来水来自海上\", v2_classifier, ref_dict)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### Post processing\n",
    "\n",
    "Combine consecutive segments containing only English letters or digits into one segment.\n",
    "\n",
    "For example: \n",
    "- **su n d i py** will be combined as a single word **sundipy**\n",
    "- **01 235 8** will be combined as a single word **012358**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def post_processing(sentence):\n",
    "    segments = sentence.split()\n",
    "    results = []\n",
    "    \n",
    "    i = 0\n",
    "    while i < len(segments):\n",
    "        word = segments[i]\n",
    "        if StringUtil.is_digit_or_letter(word):\n",
    "            while i+1 < len(segments):\n",
    "                if StringUtil.is_digit_or_letter(segments[i+1]):\n",
    "                    word = word + segments[i+1]\n",
    "                    i += 1\n",
    "                else:\n",
    "                    break\n",
    "            results.append(word)\n",
    "            \n",
    "        else:\n",
    "            results.append(word)\n",
    "            \n",
    "        i += 1\n",
    "    \n",
    "    return StringUtil.SPACE.join(results)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Quick test"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "EKT 男士 纯色 V 领 半袖 T恤 012348\n"
     ]
    }
   ],
   "source": [
    "print post_processing(\"EK T 男士 纯色 V 领 半袖 T恤 01 234 8\".decode('utf-8'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def do_segmentation_for_partial_sentence_v3(sentence, classifier, ref_dict):\n",
    "    tags = get_tags_for_sentence_v2(sentence, classifier, ref_dict)\n",
    "    \n",
    "    output = []\n",
    "    total_len = len(tags)\n",
    "    \n",
    "    for i, t in enumerate(tags):\n",
    "        output.append(sentence[i])\n",
    "        if i < total_len -1:\n",
    "            if t == 's' or t == 'e':\n",
    "                output.append(StringUtil.SPACE)\n",
    "    \n",
    "    return post_processing(StringUtil.EMPTY.join(output))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def do_segmentation_for_sentence_v3(sentence, classifier, ref_dict):\n",
    "    sentence = sentence.strip().decode(\"utf-8\")\n",
    "    segments = sentence.split()\n",
    "    \n",
    "    return StringUtil.SPACE.join([do_segmentation_for_partial_sentence_v3(s, classifier, ref_dict) for s in segments])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "su n d i py 男士 拼接 短袖 T恤 夏季 男款 韩版 修身 圆领 休闲 青年 打底 衫 男潮\n",
      "sundipy 男士 拼接 短袖 T恤 夏季 男款 韩版 修身 圆领 休闲 青年 打底衫 男潮\n"
     ]
    }
   ],
   "source": [
    "print do_segmentation_for_sentence(\"sundipy男士拼接短袖T恤夏季男款韩版修身圆领休闲青年打底衫男潮\", pku_classifier)\n",
    "print do_segmentation_for_sentence_v3(\"sundipy男士拼接短袖T恤夏季男款韩版修身圆领休闲青年打底衫男潮\", v2_classifier, ref_dict)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "EK T 男士 纯色 V领 半 袖 T恤 韩版 修身 薄款 体恤衫 冰丝无痕 短袖 夏 装潮\n",
      "EKT 男士 纯色 V领 半袖T 恤 韩版 修身 薄款 体恤衫 冰丝 无痕 短袖 夏装潮\n"
     ]
    }
   ],
   "source": [
    "print do_segmentation_for_sentence(\"EKT男士纯色V领半袖T恤 韩版修身薄款体恤衫 冰丝无痕短袖夏装潮\", pku_classifier)\n",
    "print do_segmentation_for_sentence_v3(\"EKT男士纯色V领半袖T恤 韩版修身薄款体恤衫 冰丝无痕短袖夏装潮\", v2_classifier, ref_dict)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "波司 登 男装 短袖 T恤 夏装 男士 时尚 休闲 新款 po l o衫 中青年 免烫 百 搭\n",
      "波司登 男装 短袖 T恤 夏装 男士 时尚休闲 新款 polo衫 中青年 免烫 百搭\n"
     ]
    }
   ],
   "source": [
    "print do_segmentation_for_sentence(\"波司登男装短袖T恤夏装男士时尚休闲新款polo衫中青年免烫百搭\", pku_classifier)\n",
    "print do_segmentation_for_sentence_v3(\"波司登男装短袖T恤夏装男士时尚休闲新款polo衫中青年免烫百搭\", v2_classifier, ref_dict)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "华为 Ascend P8 ( 高 配版 ) 快捷 解锁 ， 超灵 敏 触摸屏 ， 超薄 全 铝合金\n"
     ]
    }
   ],
   "source": [
    "print do_segmentation_for_sentence_v3(\"华为 Ascend P8(高配版) 快捷解锁， 超灵敏触摸屏， 超薄全铝合金\", v2_classifier, ref_dict)"
   ]
  },
  {
   "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.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}