Латентная семантическая модель для представления смыслов многозначных слов
Дмитрий Кондрашкин, научный руководитель: к.ф.-м.н. Ветров Д. П.
26 февраля 2015 г.
1/20
Skip-gram model
По слову w предсказывается слово из контекста v: p(v | w, θ) =
exp{Inw Outv }
,
V t=1 exp{Inw Outt }
где θ = {Inv , Outv }V . v=1 Каждому слову v соответствуют “входные” и “выходные” представления Inv , Outv ∈ RD .
(Mikolov 2013) Distributed representations of words and phrases and their compositionality. 2/20
Skip-gram model
Входной текст o = {o1 , . . . , oN }.
Обучающий объект (xi , yi ): x i = oi , yi = {oi−C/2 , . . . , oi−1 , oi+1 , . . . , oi+C/2 }.
Правдоподобие:
N
C
p(yij | xi , θ). i=1 j=1
Максимизировать будем лог-правдоподобие
N
C
log p(yij | xi , θ).
L(X, Y, θ) = i=1 j=1
3/20
Стохастическая оптимизация
Типичная задача в машинном обучении
N
l(xi , yi , θ) + λR(θ) → min
L(X, Y, θ) =
θ
i=1
Стохастический градиентный спуск: θ (t+1) = θ (t) − ηt g(θ (t) ),
L(X, Y, θ) ≈ g(θ).
Условия сходимости:
E g(θ) =
L(X, Y, θ),
2
ηt < ∞.
ηt = ∞, t t
Как правило, g(θ) = N l(xi , yi , θ) + λ R(θ).
4/20
Стохастическая оптимизация
В нашем случае:
N
C
log p(yij | xi , θ) → max .
L(X, Y, θ) =
θ
i=1 j=1 l(xi ,yi ,θ)
L(X, Y, θ) ≈ N
C j=1 log p(yij | xi , θ).
5/20
Hierarchical softmax
p(v | w, θ) =
exp{Inw Outv }
V
t=1 exp{Inw Outt }
Размер словаря V ≈ 105 , линейная сложность для подсчета функции и градиента — очень долго.
Нужна функция, такая что
V
p(v | w, θ) > 0 и v=1 p(v | w, θ) = 1,
Считалась быстрее, чем за O(V ).
6/20
Hierarchical softmax
p(v | w, θ) =
σ(ch(n) Inw Outn ). n∈path(v) Бинарное дерево: каждому листу соответствует слово из словаря.
Теперь “выходные” представления соответствуют не словам, а внутренним вершинам в дереве. path(v) — номера вершин на пути из корня в лист, соответствующий слову v. ch(n) — +1 или −1 в зависимости от того, что следующая вершина на пути — это правый или левый сын n.
Используем, что σ(x) + σ(−x) = 1.
7/20
Linguistic regularities
x
Berlin-Germany+Russia
Obama-USA+Russia king-man+woman argmaxw cos(w, x)
Moscow
Putin queen 8/20
Многозначные слова
Проблемы:
Смешивание смыслов.
Доминирование наиболее частотного смысла.
Ближайшие соседи по косинусному расстоянию: для слова apple: macintosh, iigs, ipad, ibook; для слова python: perl, php, molurus, c++, . . . , monty;
Как учесть то, что слова могут иметь больше одного смысла?
9/20
Наивная многосмысловая модель
Введем скрытую переменную z — номер смысла, тогда: p(v | z = k, w, θ) =
exp{Inw,k Outv }
V
t=1 exp{Inw,k
Outt }
,
Теперь каждому слову соответствуют K “входных” векторов.
Наблюдаемые данные (xi , yi ), скрытые переменные zi (неполная разметка!). Полное правдоподобие:
N
p(Y, Z | X, θ) =
C
p(yij | zi , xi , θ).
p(zi ) i=1 j=1
10/20
Обучение
Будем максимизировать логарифм неполного правдоподобия: p(Y, Z | X, θ) → max .
log p(Y | X, θ) = log
Z
θ
Его можно представить в виде: log p(Y | X, θ) = L(q(Z), θ) + KL(q(Z) p(Z | X, Y, θ)), где L вариационная нижняя оценка:
L(q(Z), θ) = Eq(Z) log
Нижняя, потому что KL(q p)
p(Y, Z | X, θ)
.
q(Z)
0.
11/20
Обучение
Перейдем к задаче максимизации нижней оценки:
L(q(Z), θ) → max . q(Z),θ N i=1 q(zi ).
Будем искать q(Z) в виде
Перепишем нижнюю оценку:
N
L(q(Z), θ) =
log p(yij | zi , xi , θ) −
Eq(zi ) log p(zi ) + i=1
C j=1 N
Eq(zi ) log q(zi ). i=1 12/20
EM-алгоритм
E-шаг:
C
q(zi = k) = p(zi = k | yi , xi , θ old ) ∝ exp
j=1
log p(yij | k, xi , θ old )
для k = 1, . . . , K и i = 1, . . . , N .
M-шаг:
L(q(Z), θ) → max θ или
N
C
Eq(zi ) log p(yij | zi , xi , θ) → max . i=1 j=1
θ
13/20
EM-алгоритм
Как найти Eq(zi ) log p(yij | zi , xi , θ)?
Стандартный прием:
K
p(yij | k, xi , θ)I[zi =k] .
p(yij | zi , xi , θ) = k=1 В результате:
K
Eq(zi ) log p(yij | zi , xi , θ) =
Eq(zi ) I[zi = k] log p(yij | k, xi , θ) = k=1 K
q(zi = k) log p(yij | k, xi , θ). k=1 14/20
Стохастический EM-алгоритм
Для i-го обучающего объекта (xi , yi ) выполняем Е-шаг для нахождения распределения q(zi ).
При выполнении M-шага делаем шаг по стохастическому градиенту нижней оценки:
C
K
L(q(Z), θ) ≈ N
q(zi = k)
log p(yij | k, xi , θ).
j=1 k=1
Сравним с градиентом Skip-gram:
C
L(X, Y, θ) ≈ N
log p(yij | xi , θ). j=1 15/20
Проблемы наивного подхода
Предположение о том, что все слова имеют K смыслов нереалистично. Как автоматически подбирать число смыслов для каждого слова?
Можно использовать процесс Дирихле.
См. нашу работу:
Breaking Sticks and Ambiguities with Adaptive Skip-gram.
Bartunov S., Kondrashkin D., Osokin A., Vetrov D. http://arxiv.org/abs/1502.07257 16/20
Примеры найденных смыслов
Смысл 1 almond cherry plum apricot orange Смысл 2 macintosh iifx iigs computers kaypro Для слова apple.
Смысл 1 monty spamalot cantsin zirkus circus Смысл 2 perl php java c++ objective-c Смысл 3 molurus pythons peafowl tortoise snake Для слова python.
17/20
Разрешение лексической многозначности
Определение смысла слова по контексту: argmaxk p(z = k | y, x, θ).
Примеры для слова apple p(z | (tasty, sweet), apple) = [0.99998, 0.00002], p(z | (announce, today), apple) = [0.121476, 0.878524].
Примеры для слова python p(z | (interesting, show), python) = [0.950317, 0.0327315, 0.0169517], p(z | (code), python) = [0.0219413, 0.976705, 0.00135406], p(z | (dangerous, animal), python) = [0.262747, 0.00012, 0.737133].
18/20
Основные идеи
Модель Skig-gram и иерархический soft-max.
Стохастическая оптимизация.
Введение скрытых переменных.
Непараметрический байес.
19/20
Библиография
(Mikolov 2013) Distributed representations of words and phrases and their compositionality. Mikolov T., Sutskever I., Chen K., Corrado G.,
Dean J. Advances in Neural Information Processing Systems.
(Hoffman 2013) Stochastic variational inference. Hoffman M., Blei D.,
Wang C., Paisley J. The Journal of Machine Learning Research.
20/20 