Loading...

​​Задача 4

​​Пусть ​​$G(V, E)$​ — некоторый ориентированный граф, являющийся объектом сложной структуры ​​$y$​. Здесь ​​$y$​ является графом морфологического разбора некоторого предложения (граф зависимостей слов в предложении ограниченной длины). Известно, что оптимальным графом, если таковой существует, является деревом (аналогия с деревом разбора). 

​​

​​​​$a: X \to Y$​

​​

​​Пусть ​​$M$​ — матрица смежности взвешенного графа ​​$G$​. ​​$m_{ij} \ne 0$​ если есть дуга из ​​$i$​-го слова в ​​$j$​-е. Тогда критерием того, что ​​$G$​ — дерево является

1. ​​​​$\exists k:\sum_{j=1}^l [M_{kj} \ne 0] = 0$​ — то есть есть корень дерева

2. ​​​​$\sum_{j=1}^l [M_{ij} \ne 0] \leq 1 \;\;\;\forall i \in 1, 2\ldots l: i \ne k$​ — то есть все остальные вершины имеют ровно одного родителя

​​

​​При этом есть еще следующее соображение: если в столбце один вес сильно перевешивает все остальные, это лучше, чем если есть веса одинакового масштаба, так как в некотором смысле в первом случае мы сильно уверены, что перевешивающий вес является родителем.

​​

​​Предлагается использовать функцию потерь, основанную на модифицированном расстояние Хэмминга, определенного для матриц. Пусть ​​$l$​ — максимальная длина предложения, то есть ​​$M \in \mathbb{R}^{l\times l}$​, пусть ​​$f: \mathbb{R}^{l\times l}\to \mathbb{R}^{l\times l}$​ — функция, которая по матрице ​​$M$​ получает ​​$M^*$​ — матрицу смежности некоторого дерева получающегося следующим образом

​​

1. ​​​​$k = \arg\min_{i \in [1, l]}\max_{j \in [1, l]} |m_{ij}|$​ — находим столбец с минимальными весами, он будет корнем.

2. ​​В ​​$M^*$​ ​​$k$​-й столбец состоит из нулей, а все остальные состоят из нулей кроме максимального по модулю значения в столбце.

​​Тогда функцией ошибки будет 

​​

​​​​$L(x, a) = \rho_{H}(a(x), f(a(x))$​

​​Где ​​$\rho_H$​ — модифицированное расстояние Хэмминга, где в месте замены веса на ноль расстояние увеличивается на квадрат заменяемого веса. Тогда постановка задачи заключается

​​в 

​​

​​​​$L(X, a(\theta)) \rightarrow \min_{\theta}$​

​​

​​При этом понятно, что функция ошибки является непрерывно дифференцируемой.

​​

​​