notebooks/other/MEMM_viterbi.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Семинар 5. Определение части речи. Алгоритм Витерби."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Одной из основых задач NLP является sequence labeling (т.е. разметка последовтельности). Такой задачей является определение части речи, определение именованных сущностей, преобразование звука в текст. \n",
    "\n",
    "Задача состоит в том, чтобы для данной последовательности (слов или чего-то ещё) определить лучшую последовательность тэгов.\n",
    "\n",
    "Например, для предложения найти соответсвующую последовательность частей речи. \n",
    "\n",
    "Отличие от простой классификации в том, что каждое слово связано с другими (обычно с предыдущими, но может и с последующими).\n",
    "\n",
    "Посмотрим на задачу определения частей речи поподробнее."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from sklearn.preprocessing import LabelEncoder\n",
    "from sklearn.preprocessing import OneHotEncoder\n",
    "from sklearn.feature_extraction.text import CountVectorizer\n",
    "from scipy.sparse import hstack\n",
    "from sklearn.linear_model import LogisticRegression\n",
    "from sklearn.metrics import classification_report\n",
    "import warnings\n",
    "warnings.filterwarnings('ignore')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Возьмем данные Dialog Evaluation 2016 по предсказанию морфологических тэгов. Я заранее вытащил из данных только слово, лемму и часть речи (остальное нам не понадобится)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# так как данных много, возьмем только небольшой кусок\n",
    "train = open('data/train_pos.out').read().split('\\n\\n')[:500]\n",
    "test = open('data/test_pos.out').read().split('\\n\\n')[:100]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Данные в формате CONLL - на каждой строке отдельное слово (+лемма и часть речи отделенные табами), предложения отделены двойной новой строкой."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Такую задачу можно решать с помощью скрытых марковских цепей (части речи будут скрытыми переменными). Для этого нужно построить две матрицы (перехода и попрождения), а затем использовать их, чтобы расчитать самую вероятностную последовательность. Это достаточно муторно и к тому же, чтобы добавить какие-то дополнительные признаки в модель (суффиксы или префиксы например), нужно будет считать сложные вероятности.\n",
    "\n",
    "Поэтому мы воспользуемся другим подходом - обучим обычный классификатор (логрег) предсказывать тэг по слову и предыдущему тэгу. И будем последовательно применять его к предложению подавая выдачу на предыдущем слове в текущий классификатор. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# добавим к кажому предложению специальный символ начала, чтобы можно было начать классифицировать\n",
    "train_data = []\n",
    "for sent in train:\n",
    "    sent_list = [['<START>', '<START>', '<START>']]\n",
    "    for line in sent.split('\\n'):\n",
    "        sent_list.append(line.split('\\t'))\n",
    "    \n",
    "    train_data.append(sent_list)\n",
    "\n",
    "test_data = []\n",
    "for sent in test:\n",
    "    sent_list = [['<START>', '<START>', '<START>']]\n",
    "    for line in sent.split('\\n'):\n",
    "        sent_list.append(line.split('\\t'))\n",
    "    \n",
    "    test_data.append(sent_list)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Выделим нужные нам части в отдельные переменные, чтобы удобнее было преобразовывать их в векторы."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "train_current_word = []\n",
    "train_previous_pos = []\n",
    "train_target = []\n",
    "\n",
    "for sent in train_data:\n",
    "    \n",
    "    for i in range(1, len(sent)):\n",
    "        current_w, current_l, target_pos = sent[i]\n",
    "        previous_w, previous_l, previous_pos = sent[i-1]\n",
    "        \n",
    "        train_target.append(target_pos)\n",
    "        train_current_word.append(current_w)\n",
    "        train_previous_pos.append(previous_pos)\n",
    "        \n",
    "\n",
    "test_current_word = []\n",
    "test_previous_pos = []\n",
    "test_target = []\n",
    "\n",
    "for sent in test_data:\n",
    "    \n",
    "    for i in range(1, len(sent)):\n",
    "        current_w, current_l, target_pos = sent[i]\n",
    "        previous_w, previous_l, previous_pos = sent[i-1]\n",
    "        \n",
    "        test_target.append(target_pos)\n",
    "        test_current_word.append(current_w)\n",
    "        test_previous_pos.append(previous_pos)  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "train_target[:10]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Для преобразования предыдущего тэга используем One-hot encoding, а для слов - Count_Vectorizer на символьных нграммах."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# PREVIOUS POS ENCODING\n",
    "lenc_prev_pos = LabelEncoder()\n",
    "int_prev_pos_enc = lenc_prev_pos.fit_transform(train_previous_pos)\n",
    "onehot_prev_pos = OneHotEncoder(sparse=True)\n",
    "int_prev_pos = int_prev_pos_enc.reshape(len(int_prev_pos_enc), 1)\n",
    "\n",
    "X_prev_pos_train = onehot_prev_pos.fit_transform(int_prev_pos)\n",
    "\n",
    "int_prev_pos_enc_test = lenc_prev_pos.transform(test_previous_pos)\n",
    "int_prev_pos_test = int_prev_pos_enc_test.reshape(\n",
    "                                     len(int_prev_pos_enc_test),1)\n",
    "\n",
    "X_prev_pos_test = onehot_prev_pos.transform(int_prev_pos_test)\n",
    "\n",
    "# WORD ENCODING\n",
    "cv_word = CountVectorizer(ngram_range=(1,3), analyzer='char', max_features=3000)\n",
    "cv_word.fit(train_current_word)\n",
    "\n",
    "X_current_word_train = cv_word.transform(train_current_word)\n",
    "\n",
    "X_current_word_test = cv_word.transform(test_current_word)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Склеим полученные матрицы в одну."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "\n",
    "X_train = hstack([X_prev_pos_train,\n",
    "                  X_current_word_train])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "X_test = hstack([X_prev_pos_test,\n",
    "                  X_current_word_test])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Посмотрим на размерности"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "print(X_train.shape)\n",
    "print(X_test.shape)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "len(train_target)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Обучим обычную логистическую регрессиию."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "clf = LogisticRegression()\n",
    "clf.fit(X_train, train_target)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Проверим что получается."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "pred_pos = clf.predict(X_test)\n",
    "print(classification_report(test_target, pred_pos))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Определяя качество таким образом мы однако может ошибиться. Сейчас в тестовой выборке у нас для каждого примера есть правильная часть речи с предыдущего шага. По честному мы должным предсказывать часть речи первого слова и дальше подавать её в следующий шаг."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# PREVIOUS POS ENCODING\n",
    "\n",
    "pred_pos_fair = []\n",
    "true_pos = []\n",
    "\n",
    "\n",
    "# напишем специальную функцию для удобства\n",
    "def vectorize_word(word, prev_pos):\n",
    "    int_prev_pos_enc = lenc_prev_pos.transform(\n",
    "                                   [prev_pos])\n",
    "    int_prev_pos = int_prev_pos_enc.reshape(\n",
    "                                         len(int_prev_pos_enc),1)\n",
    "\n",
    "    X_prev_pos = onehot_prev_pos.transform(int_prev_pos)\n",
    "\n",
    "    X_current_word = cv_word.transform([word])\n",
    "\n",
    "\n",
    "    X = hstack([X_prev_pos,\n",
    "              X_current_word])\n",
    "\n",
    "    pred = clf.predict(X)[0]\n",
    "    \n",
    "    return pred\n",
    "\n",
    "for sent in test_data[:100]:\n",
    "    previous_pos = sent[0][2]\n",
    "    pos_sequence = []\n",
    "    \n",
    "    for i in range(1, len(sent)):\n",
    "        current_w, current_l, target_pos = sent[i]\n",
    "        previous_w, previous_l, _ = sent[i-1]\n",
    "        true_pos.append(target_pos)\n",
    "        \n",
    "        pred = vectorize_word(current_w, previous_pos)\n",
    "        previous_pos = pred\n",
    "        pos_sequence.append(pred)\n",
    "        \n",
    "    pred_pos_fair += pos_sequence\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "print(classification_report(true_pos, pred_pos_fair))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Качество на самом деле не ухудшилось. НО не факт, что на другой задаче этого не произойдет."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Посмотрим на ошибки."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "\n",
    "errors = []\n",
    "for i in range(len(true_pos)):\n",
    "    if true_pos[i] != pred_pos_fair[i]:\n",
    "        errors.append((true_pos[i], pred_pos_fair[i], test_current_word[i]))\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "errors"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Алгоритм витерби."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "С предсказанием одного тэга на самом деле тоже есть (или может быть) проблема. \n",
    "Допустим на первом шаге у нас есть 2 почти одинаковых варианта, но из них следуют совершенно разные следующие тэги - один из которых подходит следующему слову, а другой не очень. Поэтому выбрав незначительно превосходящий по вероятности отдельный тэг мы можем испортить всю последующую цепочку."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Просчитать все комбинации тэгов мы не можем (слишком много вариантов). Но есть алгоритм витерби."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Это динамический алгоритм, то есть суть в том, чтобы по ходу накапливать информацию в отдельную переменную, из коготой потом можно вывести самый лучший вариант."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# сделаем отдельную функцию, которая выдает вероятности всех тэгов\n",
    "# преобразуем вероятности в логарифмы, чтобы чего не вышло\n",
    "# дальше поэтому вероятности будут складываться, а не перемножаться\n",
    "\n",
    "def predict_pos_proba(word, prev_pos):\n",
    "    int_prev_pos_enc = lenc_prev_pos.transform(\n",
    "                                   [prev_pos])\n",
    "    int_prev_pos = int_prev_pos_enc.reshape(\n",
    "                                         len(int_prev_pos_enc),1)\n",
    "\n",
    "    X_prev_pos = onehot_prev_pos.transform(int_prev_pos)\n",
    "\n",
    "    X_current_word = cv_word.transform([word])\n",
    "\n",
    "\n",
    "    X = hstack([X_prev_pos,\n",
    "              X_current_word])\n",
    "\n",
    "    pred = np.log(clf.predict_proba(X))[0]\n",
    "    \n",
    "    return pred"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Алгоритм работает так:\n",
    "\n",
    "1. На первом шаге считаем вероятности частей речи первого слова.\n",
    "2. На последующих шагах перебираем все возможные части речи текущего слова, сгенерированных из всех возможным предыдущих тэгов. \n",
    "3. Для каждой части речи на текущем шаге сохраняем самую высокую вероятность и умножаем её на вероятность состояния, породившего эту часть речи.\n",
    "4. Дойдя до конца, идем в обратную сторону - выбираем самую вероятную часть речи и идем в предыдую часть речи (которую мы сохранили).\n",
    "\n",
    "Таким образом на каждом шаге мы накапливаем вероятность, сохраняя предыдущее состояние которое дает самый лучший результат, а затем проходим по самому вероятному пути."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def viterbi(obs, states):\n",
    "    # шаги будет хранить в переменой V\n",
    "    V = [{}]\n",
    "    \n",
    "    # посчитаем вероятности части речи первого слова\n",
    "    pred_init_states = predict_pos_proba(obs[0], '<START>')\n",
    "    for i in range(len(states)):\n",
    "        V[0][states[i]] = {\"prob\": pred_init_states[i], \"prev\": None}\n",
    "    \n",
    "    \n",
    "    for t in range(1, len(obs)):\n",
    "        V.append({})\n",
    "            \n",
    "        \n",
    "        # Версия 1 (побыстрее)\n",
    "        # для ускорения работы подойдем с обратной стороны\n",
    "        # пройдемся во всем предыдущим тэгам и предскажем вероятности тэгов текущего шага\n",
    "        # прибавим вероятность предыдущего тэга ко всем вероятностям\n",
    "        # сохраним для каждого состояние максимальную сумму и соответ. пред.состояние\n",
    "        for prev_st in states:\n",
    "            proba_st_given_prev_st = V[t-1][prev_st][\"prob\"] + \\\n",
    "                                    predict_pos_proba(obs[t], prev_st)\n",
    "            \n",
    "            for i in range(len(states)):\n",
    "                \n",
    "                if V[t].get(states[i]):\n",
    "                    if proba_st_given_prev_st[i] > V[t][states[i]]['prob']:\n",
    "                        V[t][states[i]] = {'prob':proba_st_given_prev_st[i], \n",
    "                                           'prev':prev_st}\n",
    "                else:\n",
    "                    V[t][states[i]] = {'prob':proba_st_given_prev_st[i], \n",
    "                                           'prev':prev_st}\n",
    "\n",
    "        \n",
    "        # версия 2 (попонятнее)\n",
    "        # проходим по всем возможным состояниям на текущем шаге\n",
    "        # для каждого состояния проходим во всем предыдущим тэгам и получаем вероятности\n",
    "        # находим максимальную сумму пред.состояния и текущего состояния, порожденного им\n",
    "        # сохраняем максимумы и соответ. пред. состояния\n",
    "        \n",
    "#         for i in range(len(states)):\n",
    "#             max_tr_proba = float('-inf')\n",
    "#             prev_state = None\n",
    "#             for prev_st in states:\n",
    "#                 prob_st_given_prev_st = predict_pos_proba(obs[t], prev_st)[i]\n",
    "#                 prod_proba = V[t-1][prev_st][\"prob\"] + prob_st_given_prev_st\n",
    "#                 if prod_proba > max_tr_proba:\n",
    "#                     max_tr_proba = prod_proba\n",
    "#                     prev_state = prev_st\n",
    "#             V[t][states[i]] = {'prob':max_tr_proba, 'prev':prev_state}\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "    # Эта часть проходит в обратную сторону и сохраняет в список самые вероятные тэги\n",
    "    # можно тут ничего не трогать\n",
    "    opt = []\n",
    "    max_prob = max(value[\"prob\"] for value in V[-1].values())\n",
    "    previous = None\n",
    "    for st, data in V[-1].items():\n",
    "        if data[\"prob\"] == max_prob:\n",
    "            opt.append(st)\n",
    "            previous = st\n",
    "            break\n",
    "    for t in range(len(V) - 2, -1, -1):\n",
    "        opt.insert(0, V[t + 1][previous][\"prev\"])\n",
    "        previous = V[t + 1][previous][\"prev\"]\n",
    "\n",
    "    return opt\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Первый вариант реализации работает побыстрее, но его труднее понять."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "true_pos = []\n",
    "pred_viterbi_pos = []\n",
    "words = []\n",
    "for sent in test_data[:500]:\n",
    "    words += [x[0] for x in sent[1:]]\n",
    "    true_pos += [x[2] for x in sent[1:]]\n",
    "    pred_viterbi_pos += viterbi([x[0] for x in sent[1:]], clf.classes_)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Качество на самом деле практически не увеличилось."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "print(classification_report(true_pos, pred_viterbi_pos))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "\n",
    "errors = []\n",
    "for i in range(len(true_pos)):\n",
    "    if true_pos[i] != pred_viterbi_pos[i]:\n",
    "        errors.append((true_pos[i], pred_pos_fair[i], words[i]))\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "errors"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Дальше можно попробовать:\n",
    "\n",
    "1. Обучить классификатор на всех данных\n",
    "2. Добавить или улучшить признаки (можно добавить в предсказание предыдущее слово)\n",
    "3. Попробовать найти ошибку в моём коде алгоритма витерби (может её там и нет)\n",
    "4. Попробовать такой же подход на другой задаче (или усложнить эту задачу, добавив к части речи ещё какую-то грамм. информацию (например, предсказывать существительное в таком-то падеже)\n"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [Root]",
   "language": "python",
   "name": "Python [Root]"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}