Ядро дерева
В машинном обучении ядра деревьев представляют собой применение более общей концепции положительно определенного ядра к древовидным структурам. Они находят применение в обработке естественного языка , где их можно использовать для машинного анализа или классификации предложений.
Мотивация
[ редактировать ]При обработке естественного языка часто необходимо сравнивать древовидные структуры (например, деревья синтаксического анализа ) на предмет сходства. Такие сравнения можно выполнить путем вычисления скалярного произведения векторов признаков деревьев, но эти векторы, как правило, очень велики: методы НЛП дошли до того, что простое отношение зависимости над двумя словами кодируется вектором из нескольких миллионов функции. [1] Представлять сложные структуры, такие как деревья, с векторами признаков может быть непрактично. Хорошо спроектированные ядра позволяют вычислять сходство деревьев без явного вычисления векторов признаков этих деревьев. Более того, методы ядра широко используются в задачах машинного обучения (например, SVM ), и поэтому множество алгоритмов изначально работают с ядрами или имеют расширения, которые обрабатывают кернеризацию .
Примером применения является классификация предложений, например, различные типы вопросов. [2]
Примеры
[ редактировать ]
Здесь представлены два примера ядра дерева, примененного к деревьям округов предложений «Кошка ест мышь». и «Мышь ест кошку». В этом примере «А» и «а» — одни и те же слова, и в большинстве приложений НЛП они будут представлены одним и тем же токеном.
Интерес этих двух ядер состоит в том, что они демонстрируют очень разную степень детализации (ядро дерева подмножеств гораздо более мелкозернистое, чем ядро поддерева) при одинаковой сложности вычислений. Оба могут быть вычислены рекурсивно за время O(|T 1 |.|T 2 |) . [3]
Ядро поддерева
[ редактировать ]В случае дерева избирательного округа поддерево определяется как узел и все его дочерние элементы (например, [NP [D [A]] [N [мышь]]] является поддеревом двух деревьев). Терминалы не считаются поддеревом (например, [a] не является поддеревом). Ядро поддерева подсчитывает количество общих поддеревьев между двумя заданными деревьями.
В этом примере имеется семь общих поддеревьев:
- [НП[Д[а]][Н[кот]]],
- [NP[D[a]][N[мышь]]],
- [Н [мышь]],
- [Н [кот]],
- [Ви [ест]],
- [D[a]] (засчитывается дважды, так как появляется дважды).
Ядро дерева подмножеств
[ редактировать ]Дерево подмножества представляет собой более общую структуру, чем поддерево. Основное определение то же самое, но в случае деревьев подмножеств листья не обязательно должны быть терминалами (например, [VP [V] [NP]] является деревом подмножества обоих деревьев), но здесь два отдельных узла не рассматриваются как деревья. Из-за этого более общего определения существует больше деревьев подмножеств, чем поддеревьев, и больше общих деревьев подмножеств, чем общих поддеревьев.
В этом примере имеется 54 общих дерева подмножества. Семь общих поддеревьев плюс, среди прочего:
- [NP[D][N]] (засчитывается дважды),
- [ВП [В [ест]] [НП]]...
См. также
[ редактировать ]Примечания
[ редактировать ]- ^ Макдональд, Райан; Перейра, Фернандо; Рыбаров Кирилл; Гаич, Ян (2005). Непроективный анализ зависимостей с использованием алгоритмов связующего дерева . HLT–EMNLP.
- ^ Чжан, Делл; Ли, Ви Сан (2003). Классификация вопросов с использованием машин опорных векторов . СИГИР.
- ^ Коллинз, Майкл ; Даффи, Найджел (2001). Ядра свертки для естественного языка . Достижения в области нейронных систем обработки информации .
Ссылки
[ редактировать ]- Цзюнь Сун, Мин Чжан и Чу Лим Тан. Ядро древовидной последовательности для естественного языка
- Алессандро Мошитти. Использование древовидных ядер на практике для изучения естественного языка
Внешние ссылки
[ редактировать ]- http://disi.unitn.it/moschitti/Tree-Kernel.htm — Применение ядра дерева к SVM, на веб-странице Алессандро Москитти.