notebooks/lm_intro/Language_model_intro.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Языковое моделирование"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Языковые модели - важнейшая часть современного NLP. Практически во всех задачах, связанных с обработкой текста, напрямую или косвенно используются языковые модели. А наиболее известные недавние прорывы в области - это по большей части новые подходы к языковому моделированию. ELMO, BERT, GPT - это языковые модели."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Это достаточно сложная тема, поэтому будем разбирать постепенно. Сегодня разберём самые основы. Научимся приписывать вероятность последовательности слов и попробуем генерировать текст."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "# !pip install razdel"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from string import punctuation\n",
    "from razdel import sentenize\n",
    "from razdel import tokenize as razdel_tokenize\n",
    "import numpy as np\n",
    "from IPython.display import Image\n",
    "from IPython.core.display import HTML "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Возьмем два разных корпуса: новостной и сообщения с 2ch."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# !!! двач не самое приятное место, большое количество текстов в этом корпусе токсичные\n",
    "dvach = open('2ch_corpus.txt').read()\n",
    "news = open('lenta.txt').read()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "По длине они сопоставимы."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Длина 1 - 11638405\n",
      "Длина 2 - 11536552\n"
     ]
    }
   ],
   "source": [
    "print(\"Длина 1 -\", len(dvach))\n",
    "print(\"Длина 2 -\", len(news))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Напишем простую функцию для нормализации. Удалять пунктуацию и приводить к нижнему регистру, строго говоря не стоит, сгенерированный текст так будет не похож на настоящий. Но это немного упростит нам работу. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def normalize(text):\n",
    "    normalized_text = [word.text.strip(punctuation) for word \\\n",
    "                                                            in razdel_tokenize(text)]\n",
    "    normalized_text = [word.lower() for word in normalized_text if word and len(word) < 20 ]\n",
    "    return normalized_text\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Сравним тексты по токенам"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "norm_dvach = normalize(dvach)\n",
    "norm_news = normalize(news)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Длина корпуса токсичных постов в токенах - 1858941\n",
      "Длина корпуса новостных текстов в токенах -  1505789\n"
     ]
    }
   ],
   "source": [
    "print(\"Длина корпуса токсичных постов в токенах -\", len(norm_dvach))\n",
    "print(\"Длина корпуса новостных текстов в токенах - \", len(norm_news))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "И по уникальным токенам"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Уникальных токенов в корпусе токсичных постов - 189515\n",
      "Уникальный токенов в корпусе новостных текстов -  116302\n"
     ]
    }
   ],
   "source": [
    "print(\"Уникальных токенов в корпусе токсичных постов -\", len(set(norm_dvach)))\n",
    "print(\"Уникальный токенов в корпусе новостных текстов - \", len(set(norm_news)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Посчитаем, сколько раз встречаются слова и выведем самые частотные."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "vocab_dvach = Counter(norm_dvach)\n",
    "vocab_news = Counter(norm_news)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('и', 55892),\n",
       " ('в', 48853),\n",
       " ('не', 46602),\n",
       " ('на', 29660),\n",
       " ('что', 26668),\n",
       " ('я', 21734),\n",
       " ('а', 21310),\n",
       " ('с', 21080),\n",
       " ('это', 17727),\n",
       " ('ты', 15469)]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "vocab_dvach.most_common(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('в', 72412),\n",
       " ('и', 33290),\n",
       " ('на', 28434),\n",
       " ('по', 19490),\n",
       " ('что', 17031),\n",
       " ('с', 15921),\n",
       " ('не', 12702),\n",
       " ('из', 7727),\n",
       " ('о', 7515),\n",
       " ('как', 7514)]"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "vocab_news.most_common(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Для того, чтобы превратить абсолютные частоты в вероятности, разделим на общее число слов в каждом корпусе."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "vocab_news['ваываываываываыва']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('и', 0.030066580918921042),\n",
       " ('в', 0.02628001641794979),\n",
       " ('не', 0.02506911192985684),\n",
       " ('на', 0.015955320798239428),\n",
       " ('что', 0.014345802260534357),\n",
       " ('я', 0.011691602907246653),\n",
       " ('а', 0.011463516055646737),\n",
       " ('с', 0.011339789697467536),\n",
       " ('это', 0.009536074571489897),\n",
       " ('ты', 0.008321404498582796),\n",
       " ('как', 0.007882444897390503),\n",
       " ('у', 0.006848522895562581),\n",
       " ('но', 0.005786090037284669),\n",
       " ('так', 0.005383172462170666),\n",
       " ('по', 0.005060945990217011),\n",
       " ('то', 0.005049649235774562),\n",
       " ('все', 0.0046537248896011225),\n",
       " ('за', 0.004583792600195488),\n",
       " ('же', 0.004228751746289958),\n",
       " ('если', 0.004209385881531474)]"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "probas_dvach = Counter({word:c/len(norm_dvach) for word, c in vocab_dvach.items()})\n",
    "probas_dvach.most_common(20)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('в', 0.04808907489694771),\n",
       " ('и', 0.0221080111489724),\n",
       " ('на', 0.018883123731146926),\n",
       " ('по', 0.012943380513471676),\n",
       " ('что', 0.011310349590812525),\n",
       " ('с', 0.01057319451795703),\n",
       " ('не', 0.008435444806676101),\n",
       " ('из', 0.005131529052211166),\n",
       " ('о', 0.00499073907433246),\n",
       " ('как', 0.0049900749706632205),\n",
       " ('к', 0.00407161959610543),\n",
       " ('за', 0.0040125143695431435),\n",
       " ('россии', 0.0036751497055696383),\n",
       " ('для', 0.003325831175549828),\n",
       " ('его', 0.003260084912295149),\n",
       " ('он', 0.0031704309169478593),\n",
       " ('от', 0.003066830744546547),\n",
       " ('сообщает', 0.003050228152815567),\n",
       " ('а', 0.0029180715226369697),\n",
       " ('также', 0.002716184007188258)]"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "probas_news = Counter({word:c/len(norm_news) for word, c in vocab_news.items()})\n",
    "probas_news.most_common(20)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Эти вероятности уже можно использовать, чтобы ответить на вопрос - это предложение больше подходит для новостей или для анонимного форума?\n",
    "\n",
    "В теории вероятностей для того, чтобы найти общую вероятность нескольких независимых событий произойти одновременно, нужно перемножить вероятности отдельных событий. В нашем случае мы хотим найти вероятность получить данное предложение. Для этого мы перемножаем вероятности слов в этом предложении. \n",
    "\n",
    "(Если бы мы сложили вероятности, то мы бы получили вероятность выбрать из корпуса 1 из слов в данном предложении)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Напишем простую функцию, которая расчитает обшую вероятность. В прошлом семинаре мы говорили о том, что вместо умножения вероятностей можно складывать логарифмы от них. Еще нам нужно учесть одну деталь - некоторых слов может не быть в словаре и, соответственно, вероятность будет нулевая. Можно использовать в таких случаях небольшое значение вероятности, например 1/длина корпуса. Исправить это по-нормальному - сложно, придется подробнее разбираться с вероятностями, сглаживаниями и заменой неизвестных слов."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "def compute_joint_proba(text, word_probas):\n",
    "    prob = 0\n",
    "    for word in normalize(text):\n",
    "        if word in word_probas:\n",
    "            prob += (np.log(word_probas[word]))\n",
    "        else:\n",
    "            prob += (np.log(1/len(norm_dvach)))\n",
    "    \n",
    "    return np.exp(prob)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "phrase = 'Технические возможности устаревшего российского судна не позволили разгрузить его у терминала'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Расчитаем вероятность встретить такой текст в каждом из корпусов (для таких маленьких чисел нужно смотреть на степень после e: чем больше степень, тем больше вероятность; но тут легко запутаться так как степень будет отрицательная и больше будет число, которое ближе к нулю (-5 больше -10 например)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3.8958314050721132e-50"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "compute_joint_proba(phrase, probas_dvach)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4.573351371331133e-45"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "compute_joint_proba(phrase, probas_news)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Можно просто доверится функции больше/меньше, чтобы не запутаться"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "compute_joint_proba(phrase, probas_news) > compute_joint_proba(phrase, probas_dvach)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Вероятность встретить такой текст в новостном корпусе выше. Попробуем другой текст:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "phrase = 'Безграмотное быдло с дубляжом, войсовером, порнографией и котикам'\n",
    "compute_joint_proba(phrase, probas_news) > compute_joint_proba(phrase, probas_dvach)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Тут получается обратная ситуация."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Однако такая оценка вероятности предложения черезчур упрощает действительность. Слова в предложении - это не независимые события, выбор первого слова сильно влияет на вероятности выбрать второе, третье и так далее."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Такие события можно оценивать по формуле полной вероятности:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<img src=\"https://i.ibb.co/sC7CKzQ/image.png\" width=\"500\" height=\"500\"/>"
      ],
      "text/plain": [
       "<IPython.core.display.Image object>"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Image(url=\"https://i.ibb.co/sC7CKzQ/image.png\",\n",
    "     width=500, height=500)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "А если простыми словами, то для того, чтобы получить вероятность предложения, нужно перемножить вероятность первого слова, вероятность второго слова, при условии первого, вероятность третьего при условии первого и второго, вероятность четвертого слова, при условии первого, второго и третьего и так далее до вероятности последнего слова при условии всех предшешевствующих.\n",
    "\n",
    "Условные вероятности для слов можно также вычислить по частотностям. Вероятность слова А при условии слова Б равна отношению количества раз, которое встретились слова А и Б вместе, к количеству раз, которое встретилось слово Б. Вероятность слова В при условии А и Б равна отношению количества раз, которое встретились слова А,Б и В вместе к количеству раз, которое встретились слова А и Б.\n",
    "И так далее. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Но тут появляется проблема. Для того, чтобы расчитать полную вероятность предложения нужно, чтобы такое предложение уже встретилось в корпусе хотя бы 1 раз. Очевидно, что даже огромный корпус всего написанного текста не включает в себя все возможные тексты (тем более маленький корпус). Поэтому один из множителей в произведении будет нулевым, а значит и все произведение станет нулевым."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Для того, чтобы этого избежать можно поубавить строгости и предположить, что вероятность слова зависит только от предыдущего слова. Это предположение называется марковским (в честь математика Андрея Маркова). Такую модель еще можно назвать биграммной."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Чтобы расчитать вероятность с таким предположением, нам достаточно найти количество вхождений для каждого биграмма. А частоты отдельных слов у нас уже есть. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "from nltk.tokenize import sent_tokenize\n",
    "def ngrammer(tokens, n=2):\n",
    "    ngrams = []\n",
    "    for i in range(0,len(tokens)-n+1):\n",
    "        ngrams.append(' '.join(tokens[i:i+n]))\n",
    "    return ngrams"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Вероятность первого слово можно по идее считать просто как вероятность униграмма, но можно сделать небольшое добавление в нашу модель - поставить в начала каждого предложения технический токен начала предложения, а вероятность первого слова рассчитывать как вероятность биграма старт-первое слово поделить на частоту старта. Дальше мы будем генерировать текст с помощью языковой модели и это поможет нам генерировать более красивые предложения.\n",
    "\n",
    "\n",
    "Для того, чтобы у нас получились честные вероятности и можно было посчитать вероятность первого слова, нам нужно добавить тэг маркирующий начало предложений \\< start \\>\n",
    "\n",
    "Дальше мы попробуем сгенерировать текст, используя эти вероятности, и нам нужно будет когда-то остановится. Для этого добавим тэг окончания \\< end \\>\n",
    "\n",
    "Ну и поделим все на предложения"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "sentences_dvach = [['<start>'] + normalize(text) + ['<end>'] for text in sent_tokenize(dvach[:5000000])]\n",
    "sentences_news = [['<start>'] + normalize(text) + ['<end>'] for text in sent_tokenize(news[:5000000])]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "unigrams_dvach = Counter()\n",
    "bigrams_dvach = Counter()\n",
    "\n",
    "for sentence in sentences_dvach:\n",
    "    unigrams_dvach.update(sentence)\n",
    "    bigrams_dvach.update(ngrammer(sentence))\n",
    "\n",
    "\n",
    "unigrams_news = Counter()\n",
    "bigrams_news = Counter()\n",
    "\n",
    "for sentence in sentences_news:\n",
    "    unigrams_news.update(sentence)\n",
    "    bigrams_news.update(ngrammer(sentence))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Чтобы посчитать условную вероятность мы можем поделить количество вхождений на количество вхождений первого слова. Обновим нашу функцию"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "def compute_joint_proba_markov_assumption(text, word_counts, bigram_counts):\n",
    "    prob = 0\n",
    "    for ngram in ngrammer(['<start>'] + normalize(phrase) + ['<end>']):\n",
    "        word1, word2 = ngram.split()\n",
    "        if word1 in word_counts and ngram in bigram_counts:\n",
    "            prob += np.log(bigram_counts[ngram]/word_counts[word1])\n",
    "        else:\n",
    "            prob += np.log(2e-5)\n",
    "    \n",
    "    return np.exp(prob)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Эта фраза более вероятна в корпусе двача\n",
    "phrase = 'Безграмотное быдло с дубляжом, войсовером, порнографией и котикам'\n",
    "\n",
    "compute_joint_proba_markov_assumption(phrase, unigrams_dvach, bigrams_dvach) > \\\n",
    "compute_joint_proba_markov_assumption(phrase, unigrams_news, bigrams_news)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Эта фраза более вероятна в корпусе новостей\n",
    "phrase = 'Технические возможности устаревшего российского судна не позволили разгрузить его у терминала'\n",
    "\n",
    "compute_joint_proba_markov_assumption(phrase, unigrams_dvach, bigrams_dvach) > \\\n",
    "compute_joint_proba_markov_assumption(phrase, unigrams_news, bigrams_news)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Генерация текста"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Попробуем теперь генерировать текст с помощью биграмной языковой модели. Принцип генерации очень простой - на каждом шаге мы случайно выбираем следующее слово согласно вероятностям, расчитанным по 1 предыдущему слову."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "В генерации мы можем выбирать только из уже известных слов. Можно заранее расчитать все вероятности и сохранить их в матрицу. Размерность матрицы слова на слова. В каждой ячееке будет лежать вероятность получить слово б, после слова а. Слово а будет в строке, а б в колонке."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Матрицы получатся очень большими, но большинство значений будет нулевыми, поэтому можно воспользоваться разреженным форматом."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [],
   "source": [
    "from scipy.sparse import lil_matrix, csr_matrix, csc_matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [],
   "source": [
    "# матрица слова на слова (инициализируем нулями)\n",
    "matrix_dvach = lil_matrix((len(unigrams_dvach), \n",
    "                         len(unigrams_dvach)))\n",
    "\n",
    "# к матрице нужно обращаться по индексам\n",
    "# поэтому зафиксируем порядок слов в словаре и сделаем маппинг id-слово и слово-id\n",
    "id2word_dvach = list(unigrams_dvach)\n",
    "word2id_dvach = {word:i for i, word in enumerate(id2word_dvach)}\n",
    "\n",
    "# заполняем матрицу\n",
    "for ngram in bigrams_dvach:\n",
    "    word1, word2 = ngram.split()\n",
    "    # на пересечение двух слов ставим вероятность встретить второе после первого\n",
    "    matrix_dvach[word2id_dvach[word1], word2id_dvach[word2]] =  (bigrams_dvach[ngram]/\n",
    "                                                                     unigrams_dvach[word1])\n",
    "    \n",
    "# matrix_dvach = csc_matrix(matrix_dvach)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [],
   "source": [
    "# то же самое для другого корпуса\n",
    "matrix_news = lil_matrix((len(unigrams_news), \n",
    "                        len(unigrams_news)))\n",
    "\n",
    "id2word_news = list(unigrams_news)\n",
    "word2id_news = {word:i for i, word in enumerate(id2word_news)}\n",
    "\n",
    "\n",
    "\n",
    "for ngram in bigrams_news:\n",
    "    word1, word2 = ngram.split()\n",
    "    matrix_news[word2id_news[word1], word2id_news[word2]] =  (bigrams_news[ngram]/\n",
    "                                                                     unigrams_news[word1])\n",
    "    \n",
    "# matrix_news = csc_matrix(matrix_news)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Для генерации нам понадобится функция np.random.choice , которая выбирает случайный объект из заданных. Ещё в неё можно подать вероятность каждого объекта и она будет доставать по ним (не только максимальный по вероятности)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 135,
   "metadata": {},
   "outputs": [],
   "source": [
    "def generate(matrix, id2word, word2id, n=100, start='<start>'):\n",
    "    text = []\n",
    "    current_idx = word2id[start]\n",
    "    \n",
    "    for i in range(n):\n",
    "        \n",
    "        chosen = np.random.choice(matrix.shape[1], p=matrix[current_idx].toarray()[0])\n",
    "        # просто выбирать наиболее вероятное продолжение не получится\n",
    "        # можете попробовать раскоментировать следующую строчку и посмотреть что получается\n",
    "#         chosen = matrix[current_idx].argmax()\n",
    "        text.append(id2word[chosen])\n",
    "        \n",
    "        if id2word[chosen] == '<end>':\n",
    "            chosen = word2id['<start>']\n",
    "        current_idx = chosen\n",
    "    \n",
    "    return ' '.join(text)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 136,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "в отправляется непотребство прочее и прочих аутистов \n",
      " а утилит всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех всех\n"
     ]
    }
   ],
   "source": [
    "print(generate(matrix_dvach, id2word_dvach, word2id_dvach).replace('<end>', '\\n'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 137,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "в главной военной службы пожар в трех объединений минюста на тверской и именнона этом сообщил риа новости в москве в оон на след \n",
      " по месту взрыва школы цигун \n",
      " как отмечают что такая система ориентации в деле важным элементом комплексной системы обладающей достоинствами некоммерческих аналогов в другой экологический проект судебного иска против проводниц возбуждено уголовное дело рук может быть поставлено 20 процентов повышается производительность труда в среднем на своем заявлении президент аргентины \n",
      " днемона пряталась опасаясь что в 225 евро \n",
      " как утверждают в русском сегменте интернета в тот же этого можно сделать его людей среди сайтов на юге\n"
     ]
    }
   ],
   "source": [
    "print(generate(matrix_news, id2word_news, word2id_news).replace('<end>', '\\n'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Beam Search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Выше мы попробовали два способа выбирать предсказания на основе имеющихся вероятностей - 1) брать самое вероятное и 2) семплировать согласно распределению. К этому можно добавлять еще много других настроек и со многими мы еще поработаем, когда дойдем до больших языковых моделей. Сейчас давайте разберем еще один алгоритм, который можно применять для улучшения генерации. Он называется beam search (поиск лучом? лучевой поиск?).\n",
    "\n",
    "![](https://opennmt.net/OpenNMT/img/beam_search.png)\n",
    "\n",
    "Идея тут в том, чтобы на каждом шаге генерировать несколько вариантов продолжений, а затем несколько вариантов и для каждого из предыдуших продолжений. Таким образом, получается дерево генерации, где каждый вариант на следующем шаге ветвится на несколько других вариантов. Чтобы дерево не разрасталось слишком сильно в beam search есть параметр, которым задает максимальное количество вариантов на каждом шаге. Если вариантов больше, то часть из них удаляется и больше не продолжается. Чтобы отранжировать варианты, для каждого из них расчитывается общая вероятность (всей последовательности!) и выбираются самые вероятные. Обратите внимание, что на картинке на каждом из шагов не более 5 вариантов, а некоторые не доживают до последнего шага.\n",
    "\n",
    "При простой генерации по одному слову есть вероятность сделать неправильный выбор и закрыть возможность для других хороших продолжений. А beam search позволяет рассматривать сразу несколько вариантов и вероятность пойти не туда, значительно снижается. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Давайте напишем функцию для генерации с помощью beam search"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 127,
   "metadata": {},
   "outputs": [],
   "source": [
    "# сделаем класс чтобы хранить каждый из лучей\n",
    "class Beam:\n",
    "    def __init__(self, sequence: list, score: float):\n",
    "        self.sequence: list = sequence\n",
    "        self.score: float = score "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 139,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "def generate_with_beam_search(matrix, id2word, word2id, n=100, max_beams=5, start='<start>'):\n",
    "    # изначально у нас один луч с заданным началом (start по дефолту)\n",
    "    initial_node = Beam(sequence=[start], score=np.log1p(0))\n",
    "    beams = [initial_node]\n",
    "    \n",
    "    for i in range(n):\n",
    "        # делаем n шагов генерации\n",
    "        new_beams = []\n",
    "        # на каждом шаге продолжаем каждый из имеющихся лучей\n",
    "        for beam in beams:\n",
    "            # лучи которые уже закончены не продолжаем (но и не удаляем)\n",
    "            if beam.sequence[-1] == '<end>':\n",
    "                new_beams.append(beam)\n",
    "                continue\n",
    "            \n",
    "            # наша языковая модель предсказывает на основе предыдущего слова\n",
    "            # достанем его из beam.sequence\n",
    "            last_id = word2id[beam.sequence[-1]]\n",
    "            \n",
    "            # посмотрим вероятности продолжений для предыдущего слова\n",
    "            probas = matrix[last_id].toarray()[0]\n",
    "            \n",
    "            # возьмем топ самых вероятных продолжений\n",
    "            top_idxs = probas.argsort()[:-(max_beams+1):-1]\n",
    "            for top_id in top_idxs:\n",
    "                # иногда вероятности будут нулевые, такое не добавляем\n",
    "                if not probas[top_id]:\n",
    "                    break\n",
    "                \n",
    "                # создадим новый луч на основе текущего и варианта продолжения\n",
    "                new_sequence = beam.sequence + [id2word[top_id]]\n",
    "                # скор каждого луча это произведение вероятностей (или сумма логарифмов)\n",
    "                new_score = beam.score + np.log1p(probas[top_id])\n",
    "                new_beam = Beam(sequence=new_sequence, score=new_score)\n",
    "                new_beams.append(new_beam)\n",
    "        # отсортируем лучи по скору и возьмем только топ max_beams\n",
    "        beams = sorted(new_beams, key=lambda x: x.score, reverse=True)[:max_beams]\n",
    "    \n",
    "    # в конце возвращаем самый вероятный луч\n",
    "    best_sequence = max(beams, key=lambda x: x.score).sequence\n",
    "\n",
    "    \n",
    "    return ' '.join(best_sequence)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 140,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "куда хинштейн предъявил вашингтону ультиматум предъявленный жителям а также отметил что в связи с 1 января 2000 года в том что в связи с 1 января 2000 года в том что в связи с 1 января 2000 года в том что в связи с 1 января 2000 года в том что в связи с 1 января 2000 года в том что в связи с 1 января 2000 года в том что в связи с 1 января 2000 года в том что в связи с 1 января 2000 года в том что в связи с 1 января 2000 года в том что\n"
     ]
    }
   ],
   "source": [
    "print(generate_with_beam_search(matrix_news, id2word_news, word2id_news, start='куда'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Перплексия"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Генерировать текст полностью требуется достаточно редко. И к тому же с этим более менее адекватно справляются только самые современные огромные модели. Гораздно более практичное применения языковой модели - выбрать наиболее вероятное продолжение уже введенной фразы. Вы все сталкивались с этим в своих телефонах. Если попытаться сгенировать текст только на основе предложенных слов, то получится не сильно лучше чем в текстах выше. Также языковую модель можно использовать, чтобы выбрать наиболее подходящее по контексту исправление опечатки и в этом случае совсем не важно, насколько красивые тексты она генерирует.\n",
    "\n",
    "Но как тогда оценивать качество языковой модели? Для этого стандартно используется перплексия (на русский обычно не переводят). У перплексии есть теоретическое обоснование в теории информации и даже какая-то интерпретация, но они достаточо сложные и непонятные. На практике можно просто считать, что перплексия показывает насколько хорошо языковая модель предсказывает корпус. Чем она ниже, тем лучше.\n",
    "\n",
    "Считается перплексия по вот такой формуле:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 107,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<img src=\"https://i.ibb.co/Ph3sNMp/image.png\" width=\"500\" height=\"500\"/>"
      ],
      "text/plain": [
       "<IPython.core.display.Image object>"
      ]
     },
     "execution_count": 107,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Image(url=\"https://i.ibb.co/Ph3sNMp/image.png\",\n",
    "     width=500, height=500)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Простыми словами - нам нужно расчитать вероятность текста (мы это уже научились делать выше) и возвести ее в степень (-1/N), где N это количество слов в тексте."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 140,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Мы уже видели что произведение вероятностей можно заменить на экспоненту суммы логарифмов\n",
    "# С возведением в степень тоже есть удобное правило - log(x^y) = y * log(x)\n",
    "# можно заменить вот такую функцию (она ожидает вероятность)\n",
    "# def perplexity(p, N):\n",
    "#     return p**(-1/N) \n",
    "\n",
    "\n",
    "# на вот такую (результат должен совпадать)\n",
    "# функция ожидает логарифм вероятности\n",
    "def perplexity(logp, N):\n",
    "    return np.exp((-1/N) * logp)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Нам нужно немного изменить функцию для расчета вероятности, чтобы возвращать N"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 141,
   "metadata": {},
   "outputs": [],
   "source": [
    "# функции возвращают лог (чтобы проверить с первой функцией можно добавить np.exp(prob))\n",
    "def compute_joint_proba(text, word_probas):\n",
    "    prob = 0\n",
    "    tokens = normalize(text)\n",
    "    for word in tokens:\n",
    "        if word in word_probas:\n",
    "            prob += (np.log(word_probas[word]))\n",
    "        else:\n",
    "            prob += np.log(2e-4)\n",
    "    \n",
    "    return prob, len(tokens)\n",
    "\n",
    "\n",
    "def compute_join_proba_markov_assumption(text, word_counts, bigram_counts):\n",
    "    prob = 0\n",
    "    tokens = normalize(phrase)\n",
    "    for ngram in ngrammer(['<start>'] + tokens + ['<end>']):\n",
    "        word1, word2 = ngram.split()\n",
    "        if word1 in word_counts and ngram in bigram_counts:\n",
    "            prob += np.log(bigram_counts[ngram]/word_counts[word1])\n",
    "        else:\n",
    "            prob += np.log(2e-5)\n",
    "    \n",
    "    return prob, len(tokens)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "У нас есть две функции для генераци вероятности последовательности. По сути каждая функция - это языковая модель. Первая - униграмная, а вторая биграмная.\n",
    "\n",
    "Таким образом мы можем сравнить две языковые модели расчитанные на одном корпусе."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 142,
   "metadata": {},
   "outputs": [],
   "source": [
    "phrase = 'Безграмотное быдло с дубляжом, войсовером, порнографией и котикам'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 143,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "17738.135055632363"
      ]
     },
     "execution_count": 143,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "perplexity(*compute_joint_proba(phrase, probas_dvach))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 144,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "233.85763830789224"
      ]
     },
     "execution_count": 144,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "perplexity(*compute_join_proba_markov_assumption(phrase, unigrams_dvach, bigrams_dvach))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Перплексия второй (биграмной модели) сильно меньше. Значит она лучше предсказывает корпус"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Со вторым текстом, который мы рассматривали до этого такое не сработает, потому что слишком много биграммов нет в словарях. Поэтому перплексия биграммной модели будет выше. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 145,
   "metadata": {},
   "outputs": [],
   "source": [
    "phrase = 'Технические возможности устаревшего российского судна не позволили разгрузить его у терминала'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 146,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10737.11899899257"
      ]
     },
     "execution_count": 146,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "perplexity(*compute_joint_proba(phrase, probas_news))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 147,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "12287.558729162867"
      ]
     },
     "execution_count": 147,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "perplexity(*compute_join_proba_markov_assumption(phrase, unigrams_news, bigrams_news))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Но лучше оценивать качество языковой модели не на 1 тексте, а сразу на целом корпусе. Мы можем посчитать перплексию на всех предложениях и усреднить, чтобы получить общую перплексию"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Униграмная модель:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 148,
   "metadata": {},
   "outputs": [],
   "source": [
    "ps = []\n",
    "for sent in sent_tokenize(dvach[:5000000]):\n",
    "    prob, N = compute_joint_proba(sent, probas_dvach)\n",
    "    if not N:\n",
    "        continue\n",
    "    ps.append(perplexity(prob, N))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 149,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "31331.84236533948"
      ]
     },
     "execution_count": 149,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.mean(ps)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Бигрмная модель:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 151,
   "metadata": {},
   "outputs": [],
   "source": [
    "ps = []\n",
    "for sent in sent_tokenize(dvach[:5000000]):\n",
    "    prob, N = compute_join_proba_markov_assumption(sent, unigrams_dvach, bigrams_dvach)\n",
    "    if not N:\n",
    "        continue\n",
    "    ps.append(perplexity(prob, N))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 152,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "82659.58358943973"
      ]
     },
     "execution_count": 152,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.mean(ps)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.14"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}