Пометка части речи на основе скользящего окна

Пометка части речи на основе скользящего окна используется для части- of-speech тег текст.

Высокий процент слов в естественном языке - это слова, которые вне контекста могут быть отнесены к более чем одной части речи. Процент этих неоднозначных слов обычно составляет около 30%, хотя это сильно зависит от языка. Решение этой проблемы очень важно во многих областях обработки естественного языка. Например, в машинном переводе изменение части речи слова может резко изменить его перевод.

Тегеры части речи на основе скользящего окна - это программы, которые назначают одну часть речи данной лексической форме слова, просматривая «окно» фиксированного размера слов вокруг слова, чтобы быть устранена неоднозначность.

Двумя основными преимуществами этого подхода являются:

• Можно автоматически обучать тегировщик, избавляясь от необходимости вручную добавлять теги к корпусу.
• Тегер может быть реализован как конечный автомат (машина Мили )

Пусть

$\Gamma \; =\; \{\gamma \; 1,\; \gamma \; 2,\dots ,\; \gamma \; |\; \Gamma \; |\}\; \{\; \backslash \; displaystyle\; \backslash \; Gamma\; =\; \backslash \; \{\backslash \; gamma\; \_\; \{1\},\; \backslash \; gamma\; \_\; \{2\},\; \backslash \; ldots,\; \backslash \; gamma\; \_\; \{|\; \backslash \; Gamma\; |\}\; \backslash \}\}$

- набор грамматических тегов приложения, которые - это набор всех возможных тегов, которые могут быть назначены слову, и пусть

$W\; =\; \{w\; 1,\; w\; 2,\dots \}\; \{\backslash \; displaystyle\; W\; =\; \backslash \; \{w1,\; w2,\; \backslash \; ldots\; \backslash \}\}$

- словарь приложения. Пусть

$T:\; W\; \to \; P\; (\Gamma )\; \{\backslash \; displaystyle\; T:\; W\; \backslash \; rightarrow\; P\; (\backslash \; Gamma)\}$

- функция для морфологического анализа, которая присваивает каждому $w\; \{\backslash \; displaystyle\; w\}$его набор возможных тегов, $T\; (w)\; \subseteq \; \Gamma \; \{\backslash \; displaystyle\; T\; (w)\; \backslash \; substeq\; \backslash \; Gamma\}$, это может быть реализуется полной лексикой или морфологическим анализатором. Пусть

$\Sigma \; =\; \{\sigma \; 1,\; \sigma \; 2,\dots ,\; \sigma \; |\; \Sigma \; |\; \}\; \{\backslash \; displaystyle\; \backslash \; Sigma\; =\; \backslash \; \{\backslash \; sigma\; \_\; \{1\},\; \backslash \; sigma\; \_\; \{2\},\; \backslash \; ldots,\; \backslash \; sigma\; \_\; \{|\; \backslash \; Sigma\; |\}\; \backslash \}\}$

набор классов слов, которые в общим будет раздел из $W\; \{\backslash \; displaystyle\; W\}$с ограничением, что для каждого $\sigma \; \in \; \Sigma \; \{\backslash \; displaystyle\; \backslash \; sigma\; \backslash \; in\; \backslash \; Sigma\}$все слова $w,\; \Sigma ,\; \sigma \; \{\backslash \; displaystyle\; w,\; \backslash \; Sigma,\; \backslash \; sigma\}$получат один и тот же набор тегов, то есть все слова в каждый класс слов $\sigma \; \{\backslash \; displaystyle\; \backslash \; sigma\}$принадлежит к одному и тому же классу неоднозначности.

Обычно $\Sigma \; \{\backslash \; displaystyle\; \backslash \; Sigma\}$строится таким образом, что для часто встречающихся слов каждый класс слов содержит одно слово, а для низкочастотных слов каждое слово class соответствует одному классу неоднозначности. Это обеспечивает хорошую производительность для часто встречающихся неоднозначных слов и не требует слишком большого количества параметров для теггера.

С помощью этих определений можно сформулировать проблему следующим образом: Для данного текста $w\; [1]\; w\; [2]\dots \; w\; [L]\; \in \; W\; \ast \; \{\backslash \; displaystyle\; w\; [1]\; w\; [2]\; \backslash \; ldots\; w\; [L]\; \backslash \; in\; W\; ^\; \{*\}\}$каждому слову $w\; [t]\; \{\backslash \; displaystyle\; w\; [t]\}$присваивается слово class $T\; (w\; [t])\; \in \; \Sigma \; \{\backslash \; displaystyle\; T\; (w\; [t])\; \backslash \; in\; \backslash \; Sigma\}$(либо с помощью лексики, либо с помощью морфологического анализатора), чтобы получить неоднозначное текст с тегами $\sigma \; [1]\; \sigma \; [2]\dots \; \sigma \; [L]\; \in \; W\; \ast \; \{\backslash \; displaystyle\; \backslash \; sigma\; [1]\; \backslash \; sigma\; [2]\; \backslash \; ldots\; \backslash \; sigma\; [L]\; \backslash \; in\; W\; ^\; \{*\}\}$. Задача теггера - получить текст с тегами $\gamma \; [1]\; \gamma \; [2]\dots \; \gamma \; [L]\; \{\backslash \; displaystyle\; \backslash \; gamma\; [1]\; \backslash \; gamma\; [2]\; \backslash \; ldots\; \backslash \; gamma\; [L]\}$(с $\gamma \; [t]\; \in \; T\; (\sigma \; [t])\; \{\backslash \; displaystyle\; \backslash \; gamma\; [t]\; \backslash \; in\; T\; (\backslash \; sigma\; [t])\}$) так же правильно, как возможный.

Статистический теггер ищет наиболее вероятный тег для текста с неоднозначными тегами $\sigma \; [1]\; \sigma \; [2]\dots \; \sigma \; [L]\; \{\backslash \; displaystyle\; \backslash \; sigma\; [1]\; \backslash \; sigma\; [2]\; \backslash \; ldots\; \backslash \; sigma\; [L]\}$:

$\gamma \; \ast \; [1]\dots \; \gamma \; \ast \; [L]\; =\; arg\; max\; \gamma \; [t]\; \in \; T\; (\sigma \; [t])\; \; p\; (\gamma \; [1]\dots \; \gamma \; [L]\; \sigma \; [\; 1]\dots \; \sigma \; [L])\; \{\backslash \; displaystyle\; \backslash \; gamma\; ^\; \{*\}\; [1]\; \backslash \; ldots\; \backslash \; gamma\; ^\; \{*\}\; [L]\; =\; \backslash \; operatorname\; \{\backslash \; arg\; \backslash ,\; max\}\; \_\; \{\backslash \; gamma\; [t]\; \backslash \; in\; T\; (\backslash \; sigma\; [t])\}\; p\; (\backslash \; gamma\; [1]\; \backslash \; ldots\; \backslash \; gamma\; [L]\; \backslash \; sigma\; [1]\; \backslash \; ldots\; \backslash \; sigma\; [L])\}$

Используя формулу Байеса, это преобразуется в:

$\gamma \; \ast \; [1]\dots \; \gamma \; \ast \; [L]\; =\; arg\; max\; \gamma \; [t]\; \in \; T\; (\sigma \; [t])\; \; p\; (\gamma \; [1]\dots \; \gamma \; [L])\; p\; (\sigma \; [1]\dots \; \sigma \; [L]\; \gamma \; [1]\dots \; \gamma \; [L])\; \{\backslash \; displaystyle\; \backslash \; gamma\; ^\; \{*\}\; [1]\; \backslash \; ldots\; \backslash \; gamma\; ^\; \{*\}\; [L]\; =\; \backslash \; operatorname\; \{\backslash \; arg\; \backslash ,\; max\; \}\; \_\; \{\backslash \; gamma\; [t]\; \backslash \; in\; T\; (\backslash \; sigma\; [t])\}\; p\; (\backslash \; gamma\; [1]\; \backslash \; ldots\; \backslash \; gamma\; [L])\; p\; (\backslash \; sigma\; [1]\; \backslash \; ldots\; \backslash \; sigma\; [L]\; \backslash \; gamma\; [1]\; \backslash \; ldots\; \backslash \; gamma\; [L])\}$

где $p\; (\gamma \; [1]\; \gamma \; [2]\dots \; \gamma \; [L])\; \{\backslash \; displaystyle\; p\; (\backslash \; gamma\; [1]\; \backslash \; gamma\; [2]\; \backslash \; ldots\; \backslash \; gamma\; [L])\}$- вероятность того, что конкретный тег (синтаксический вероятность) и $п\; (\sigma \; [1]\dots \; \sigma \; [L]\; \gamma \; [1]\dots \; \gamma \; [L])\; \{\backslash \; displaystyle\; p\; (\backslash \; sigma\; [1]\; \backslash \; dots\; \backslash \; sigma\; [L]\; \backslash \; gamma\; [1]\; \backslash \; ldots\; \backslash \; gamma\; [L])\}$- вероятность того, что этот тег соответствует тексту $\sigma \; [1]\dots \; \sigma \; [L]\; \{\backslash \; displaystyle\; \backslash \; sigma\; [1]\; \backslash \; ldots\; \backslash \; sigma\; [L\; ]\}$(лексическая вероятность).

В модели Маркова эти вероятности аппроксимируются как произведения. Синтаксические вероятности моделируются марковским процессом первого порядка:

$p\; (\gamma \; [1]\; \gamma \; [2]\dots \; \gamma \; [L])\; =\; \prod \; t\; =\; 1\; t\; =\; L\; p\; (\gamma \; [t\; +\; 1]\; \gamma \; [t\; ])\; \{\backslash \; Displaystyle\; п\; (\backslash \; гамма\; [1]\; \backslash \; гамма\; [2]\; \backslash \; ldots\; \backslash \; гамма\; [L])\; =\; \backslash \; prod\; \_\; \{т\; =\; 1\}\; ^\; \{т\; =\; L\}\; р\; (\backslash \; гамма\; [т\; +\; 1]\; \backslash \; гамма\; [t])\}$

где $\gamma \; [0]\; \{\backslash \; displaystyle\; \backslash \; gamma\; [0]\}$и $\gamma \; [L\; +\; 1]\; \{\backslash \; displaystyle\; \backslash \; gamma\; [L\; +\; 1]\}$- символы-разделители.

Лексические вероятности не зависят от контекста:

$p\; (\sigma \; [1]\; \sigma \; [2]\dots \; \sigma \; [L]\; \gamma \; [1]\; \gamma \; [2]\dots \; \gamma \; [L])\; =\; \prod \; t\; =\; 1\; T\; знак\; равно\; L\; п\; (\sigma \; [T]\; \gamma \; [T])\; \{\backslash \; Displaystyle\; p\; (\backslash \; Sigma\; [1]\; \backslash \; Sigma\; [2]\; \backslash \; ldots\; \backslash \; sigma\; [L]\; \backslash \; gamma\; [1]\; \backslash \; gamma\; [2]\; \backslash \; ldots\; \backslash \; gamma\; [L])\; =\; \backslash \; prod\; \_\; \{t\; =\; 1\}\; ^\; \{t\; =\; L\}\; p\; (\backslash \; sigma\; [t]\; \backslash \; gamma\; [t])\}$

Одной из форм тегирования является аппроксимация первой формулы вероятности:

$p\; (\sigma \; [1]\; \sigma \; [2]\dots \; \sigma \; [L]\; \gamma \; [1]\; \gamma \; [2]\dots \; \gamma \; [L])\; =\; \prod \; t\; =\; 1\; t\; =\; L\; p\; (\gamma \; [t]\; C\; (-)\; [t\; ]\; \sigma \; [T]\; С\; (+)\; [T])\; \{\backslash \; Displaystyle\; p\; (\backslash \; Sigma\; [1]\; \backslash \; sigma\; [2]\; \backslash \; ldots\; \backslash \; sigma\; [L]\; \backslash \; gamma\; [1]\; \backslash \; gamma\; [2]\; \backslash \; ldots\; \backslash \; gamma\; [\; L])\; =\; \backslash \; prod\; \_\; \{t\; =\; 1\}\; ^\; \{t\; =\; L\}\; p\; (\backslash \; gamma\; [t]\; C\; \_\; \{(-)\}\; [t]\; \backslash \; sigma\; [t]\; C\; \_\; \{(+)\}\; [t])\}$

где $C\; (-)\; [t]\; =\; \sigma \; [t\; -\; N\; (-)]\; \sigma \; [t\; -\; N\; (-)]\dots \; \sigma \; [t\; -\; 1]\; \{\backslash \; displaystyle\; C\; \_\; \{(-)\}\; [\; t]\; =\; \backslash \; sigma\; [t-N\; \_\; \{(-)\}]\; \backslash \; sigma\; [t-N\; \_\; \{(-)\}]\; \backslash \; ldots\; \backslash \; sigma\; [t-1]\}$- правильный контекст размера $N\; (+)\; \{\backslash \; displaystyle\; N\; \_\; \{(+)\}\}$.

Таким образом, алгоритм скользящего окна должен учитывать только контекст размером $N\; (-)\; +\; N\; (+)\; +\; 1\; \{\backslash \; displaystyle\; N\; \_\; \{(-)\}\; +\; N\; \_\; \{(+)\}\; +\; 1\}$. Для большинства приложений $N\; (-)\; =\; N\; (+)\; =\; 1\; \{\backslash \; displaystyle\; N\; \_\; \{(-)\}\; =\; N\; \_\; \{(+)\}\; =\; 1\}$. Например, чтобы пометить неоднозначное слово «беги» в предложении «Он бежит от опасности», необходимо учитывать только теги слов «Он» и «от».

• Санчес-Вильямил, Э., Форкада, М. Л., и Карраско, Р. С. (2005). «Неконтролируемое обучение конечного тега части речи с скользящим окном ». Lecture Notes in Computer Science / Lecture Notes in Artificial Intelligence, vol. 3230, стр. 454-463