Диссертация (1090484), страница 4
Текст из файла (страница 4)
Для поиска оптимальной разделяющей гиперплоскости надо минимизировать сумму:kwk2 + CXξ.(1.38)Будем решать эту задачу с помощью метода Лагранжа [67]. Чтобы использовать стандартные методы поиска минимума функции нужно формировать задачу поиска безусловного минимума. Для этого преобразуем целевую функцию,PPкоторую необходимо минимизировать 12 w.w+C i ξ− i λi (ξi + yi (w.xi − b) − 1).Формулируем задачу: найти минимум по w, b, ξi и максимум по λi функции:XX1w.w + Cξ−λi (ξi + yi (w.xi − b) − 1).2ii(1.39)При ограниченных условиях:ξi ≥ 0, λi ≥ 0.(1.40)В работе [68] был применен метод опорных векторов для классификациитекстов, преимущества метода опорных векторов состоят в следующем:1.
Большое количество признаков текстов подходит для метода опорных векторов так как этот метод способен работать с многомерными данными.2. Тексты - векторы являются разрежёнными, они содержат много нулевыхэлементов.273. Большинство текстовых задач классификации линейно разделимые [69].1.61.6.1Логистическая регрессияБинарная логистическая регрессияЛогистическая регрессия [70] - это метод линейной классификации по оценкевероятности принадлежности объектов классам.
В отличие от обычной регрессии, в методе логистической регрессии не производится предсказание значениячисловой переменной исходя из выборки исходных значений. Вместо этого, значением функции является вероятность того, что данное исходное значение принадлежит к определенному классу [71].Выходные вероятности для бинарной классификации:P(y = 1|x) = hθ (x) =1≡ σ(θ| x),|1 + exp(−θ x)P(y = 0|x) = 1 − P(y = 1|x) = 1 − hθ (x).(1.41)(1.42)Функция потерь:J(θ) = −X(y (i) log(hθ (x(i) )) + (1 − y (i) ) log(1 − hθ (x(i) ))).(1.43)iПроизводные и градиент функции потерь:∂J(θ) X (i)=xj (hθ (x(i) ) − y (i) ),∂θji28(1.44)∇θ J(θ) =Xx(i) (hθ (x(i) ) − y (i) ),(1.45)i1.6.2Мультиномиальная логистическая регрессия - SoftmaxРассмотрим мультиномиальную логистическую регрессию [72].
Выходное распределение вероятностей для K-классовой классификации:exp(θ(1)| x),P(y = 1|x; θ), P(y = 2|x; θ), exp(θ(2)| x),1=P.hθ (x) = ....K(j)|..x) j=1 exp(θ(K)|exp(θx)P(y = K|x; θ)(1.46)Функция потерь [25]:XKm X (i)exp(θ(k)| x(i) )y = k log PKJ(θ) = −.(j)| x(i) )exp(θj=1i=1 k=1(1.47)Производные и градиент функции потерь [25]:exp(θ(k)| x(i) )(i)P(y = k|x ; θ) = PK(j)| x(i) )j=1 exp(θ∇θ(k) J(θ) = −mX,x(i) (1{y (i) = k} − P(y (i) = k|x(i) ; θ)) .(1.48)(1.49)i1.7EM-алгоритмEM-алгоритм (англ.
Expectation-Maximization) - алгоритм для оценки максимального правдоподобия параметров вероятностных моделей при условии, что29в них существуют скрытые признаки [73].1.7.1Функция правдоподобияl(θ) =mXlog p(x; θ)i=1=mX(1.50)Xlogzi=11.7.2p(x, z; θ).EM-алгоритмДля каждого i, пусть Q - некое распределение над zРассмотрим:Xlog p(x(i) ; θ) =i=XlogXiz (i)XXlogi≥z (i)XXiPzQi (z) = 1, Qi (z) ≥ 0.p(x(i) , z (i) ; θ)p(x(i) , z (i) ; θ)Qi (z )Qi (z (i) )(i)Qi (z (i) ) logz (i)(1.51)p(x(i) , z (i) ; θ).Qi (z (i) )В последнем неравенстве было использовано неравенство Женшена [74] сf (x) = log(x) - вогнутой функцией, так как f 00 (x) = −1/x2 < 0.
Чтобы это былоравенством:p(x(i) , z (i) ; θ)= c,Qi (z (i) )где c - константа, не зависящая от z (i) .PПоскольку z Qi (z (i) ) = 1, так как это распределение, имеем:30(1.52)p(x(i) , z (i) ; θ)Qi (z (i) ) = P(i)z p(x , z; θ)p(x(i) , z (i) ; θ)=p(x(i) ; θ)(1.53)= p(z (i) |x(i) ; θ).Повторять: {E-шаг: Qi (z (i) ) = p(z (i) |x(i) ; θ(t)).P P(i) (i)M-шаг: θ(t + 1) = argmax i z (i) Qi (z (i) ) log p(xQi (z,z(i) );θ) .θ}1.81.8.1Скрытая марковская модельМарковская модельМарковская модель [75] — это последовательность случайных событий, в которой вероятность каждого события зависит только от предыдущего события.Марковская модель была названа в честь русского математика А. А. Маркова.Значение наблюдаемого вектора zt , взятого в момент времени t, зависиттолько от состояния в предыдущий момент времени zt−1 [76]:P(zt |zt−1 , zt−2 , .
. . , z1 ) = P(zt |zt−1 ).(1.54)Условное распределение наблюдаемого состояния при состоянии в предыдущий момент времени не меняется:P(zt |zt−1 ) = P(z2 |z1 ); t ∈ 2 . . . T.(1.55)Обозначим Aij - вероятность перехода наблюдаемого состояния zt из значения i в значение j в любой момент t. Вероятность последовательности ~z вычис31ляется как:P(~z) = P(zt , zt−1 , . . . , z1 ; A)= P(zt , zt−1 , . . . , z1 , z0 ; A)= P(zt |zt−1 , . . . , z1 ; A) P(zt−1 , zt−2 , . . . , z1 ; A) .
. . P(z1 |z0 ; A)= P(zt |zt−1 ; A) P(zt−1 , zt−2 ; A) . . . P(z1 |z0 ; A)==TYt=1TY(1.56)P(zt ; zt−1 ; A)Azt−1 zt .t=1Логарифм функции правдоподобия марковской модели:log P(~z; A) = logTYAzt−1 ztt=1=TXlog Azt−1 zt(1.57)t=1|S| |S|=TXXX1{zt−1 = si ∧ zt = sj } log Aij .i=1 j=1 t=1Задачу можно решить с помощью метода множителей Лагранжа:max l(A),A|S|XAij = 1, i = 1..|S|,j=1Aij ≥ 0, i, j = 1..|S|.Записываем лагранжиан [77]:32(1.58)L(A, α) =|S| |S| TXXX1{zt−1 = si ∧ zt = sj } log Aij +i=1 j=1 t=1|S|Xi=1αi (1 −|S|XAij ). (1.59)j=1Записываем частные производные и приравняем их к нулям:|S|TX∂L(A, α)∂ X∂=(1{zt−1 = si ∧ zt = sj } log Aij ) +αi (1 −Aij )∂Aij∂Aij t=1∂Aijj=|T |1 X1{zt−1 = si ∧ zt = sj } − αi = 0.=Aij t=1(1.60)|T |1 XAij =1{zt−1 = si ∧ zt = sj }.αi t=1(1.61)Поставим Aij обратно в лагранжиан и приравняем производную по α к нулю:|S|X∂L(A, β)=1−Aij∂αij=1|S|X1=1−1{zt−1 = si ∧ zt = sj } − αi = 0,αij=1αi =|S| TXX1{zt−1 = si ∧ zt = sj }j=1 t=1=TX(1.62)(1.63)1{zt−1 = si }.t=1Поставив αi в (1.51) получим:33PTÂij =1.8.2t=1 1{zt−1 = siPTt=1 1{zt−1∧ zt = sj }= si }.(1.64)Скрытая марковская модельСкрытая марковская модель [78] — это вероятностная модель последовательности, которая состоит из набора наблюдаемых переменных x = {x1 , x2 , ..., xT }, xt ∈V = {v1 , v2 , ..., v|V | } и латентных (скрытых) переменных z = {z1 , z2 , ..., zT }, zt ∈S = {s1 , s2 , ..., s|S| }.Рис.
1.6: Скрытая марковская модель.1.8.3Алгоритм прямого-обратного ходаРассмотрим алгоритм прямого-обратного хода для вычисления апостериорныхвероятностей последовательности состояний при наличии последовательностинаблюдений [79].34Обозначим Bjk = P(xt = vk |zt = sj ) - вероятность того, что наблюдаемое состояние xt принимает значение vk при условии, что скрытое состояние zt принялзначение sj в любой момент t. Заданы матрицы A и B, вероятность последовательности ~x вычисляется как:P(~x; A, B) ==X~zXP(~x, ~z; A, B)P(~x|~z; A, B) P(~z; A, B)~zTTXYY=( P(xt |zt ; B))( P(zt |zt−1 ; A))~z=Xt=1TY(~z(1.65)t=1TYBzt xt )(t=1P(Azt−1 zt )).t=1Обозначивαi (t) = P(x1 , x2 , .
. . , xt , zt = si ; A, B),(1.66)αi (0) = A0i , i = 1..|S|,(1.67)αj (t) =|S|Xαi (t − 1)Aij Bjxt , j = 1..|S|, t = 1..T,(1.68)i=1переписываем вероятность последовательности ~xP(~x; A, B) = P(x1 , x2 , . . . , xT ; A, B)=|S|XP(x1 , x2 , . . . , xT ; zT = si ; A, B)i=1|S|=Xαi (T ).i=135(1.69)Аналогично для вероятности обратной последовательности:βi (t) = P(xT , xT −1 , .
. . , xt+1 , zt = si ; A, B).1.8.4(1.70)Алгоритм ВитербиАлгоритм Витерби — алгоритм поиска наиболее подходящего списка состояний(называемого путём Витерби), который в контексте цепей Маркова получаетнаиболее вероятную последовательность произошедших событий [80].Наша задача - найти наиболее вероятную последовательность скрытых состояний ~z ∈ S T при наблюдаемой последовательности ~x ∈ V T :P(~x, ~z; A, B)= argmax P(~x, ~z; A, B). (1.71)argmax P(~z|~x; A, B) = argmax P~z~z~zP(~x,~z;A,B)~zРешаем задачу используя динамическое программирование [81],αi (0) = A0i , i = 1..|S|,(1.72)αj (t) = max αi (t − 1)Aij Bjxt , j = 1..|S|, t = 1..T(1.73)|S|i=1EM-алгоритм [82] для скрытой марковской модели:Q(~z) = p(~z|~x; A, B),A, B = argmaxA,BXQ(~z) log~zP(~x, ~z; A, B),Q(~z)(1.74)(1.75)|S|XAij , i = 1..|S|; Aij ≥ 0; i, j = 1..|S|,(1.76)Bik , i = 1..|S|; Bik ≥ 0; i = 1..|S|, k = 1..|V |,(1.77)j=1|V |Xj=136A, B = argmaxA,B= argmaxA,B~zXP(~x, ~z; A, B)Q(~z)Q(~z) logQ(~z) log P(~x, ~z; A, B)~z= argmaxA,BXQ(~z) logTYA,BXQ(~z)TXlog Bzt xt + log Azt−1 ztt=1~z= argmaxP(xt |zt ; B)(zt |zt−1 ; A)t=1~z= argmaxA,BXXQ(~z)|S| |S| |V | TXXXX1{zt = sj ∧ xt = vk } log Bjk + 1{zt−1 = si ∧ zt =i=1 j=1 k=1 t=1~z(1.78)Записываем лагранжиан:L(A, B, δ, ) =XQ(~z)~z|S| |S| |V | TXXXX1{zt = sj ∧ xt = vk } log Bjk + 1{zt−1 = si ∧ zt =i=1 j=1 k=1 t=1(1.79)|S|Xj=1j (1 −|V |Xk=1Bjk ) +|S|Xi=1δi (1 −|S|XAij ).j=1Записываем частные производные и приравняем их к нулям:37(1.80)T∂L(A, B, δ, ) X1 X=Q(~z)1{zt−1 = si ∧ zt = sj } − δi = 0,∂AijAij t=1~zTX1XAij =Q(~z)1{zt−1 = si ∧ zt = sj },δit=1~zT1 X∂L(A, B, δ, ) X=Q(~z)1{zt = sj ∧ xt = vk } − j = 0,∂BjkBjk t=1(1.81)~zBjkTX1X=Q(~z)1{zt = sj ∧ xt = vk }.jt=1~zПоставим Aij и Bij обратно в лагражиан и приравняем производную по δi кнулю:38|S|X∂L(A, B, δ, )=1−Aij∂δij=1|S|TXX1X=1−Q(~z)1{zt−1 = si ∧ zt = sj } = 0δit=1j=1~zδi =|S|XXj=1=XQ(~z)TX1{zt−1 = si ∧ zt = sj }t=1~zQ(~z)TX1{zt−1 = si }t=1~z(1.82)|V |X∂L(A, B, δ, )=1−Bjk∂jk=1|V |TX1XX=1−Q(~z)1{zt = sj ∧ xt = vk } = 0jt=1k=1j =|V |XXk=1=X~zQ(~z)TX1{zt = sj ∧ xt = vk }t=1~zQ(~z)TX1{zt = sj }.t=1~zПараметры Â B̂, которые максимизируют вероятность последовательностискрытых состояний:PQ(~z) Tt=1 1{zt−1 = si ∧ zt = sj }Âij =,PPTQ(~z)1{z=s}t−1i~zt=1PPTQ(~z) t=1 1{zt = sj ∧ xt = vk }.B̂jk = ~z PPTQ(~z)1{z=s}tj~zt=1P~z(1.83)Чтобы вычислять Â через прямой и обратной вероятностей αi (t) и βj (t),сначала переписываем числитель:39XQ(~z)=1{zt−1 = si ∧ zt = sj }t=1~z=TXT XXt=1 ~zT XXt=11{zt−1 = si ∧ zt = sj }Q(~z)1{zt−1 = si ∧ zt = sj } P(~z|~x; A, B)(1.84)~zTXX11{zt−1 = si ∧ zt = sj } P(~z, ~x; A, B)=P(~x; A, B) t=1~zTX1αi (t)Aij Bjxt βj (t + 1).=P(~x; A, B) t=1Аналогично для знаменателя:XQ(~z)TX1{zt−1 = si }t=1~z|S|=XXj=1Q(~z)TX1{zt−1 = si ∧ zt = sj }(1.85)t=1~z|S|TXX1αi (t)Aij Bjxt βj (t + 1).=P(~x; A, B) j=1 t=1Переписываем выражения для Âij :PTαi (t)Aij Bjxt βj (t + 1)Âij = P|S| t=1.PTα(t)ABβ(t+1)iijjxjtj=1t=1Аналогично для B̂jk40(1.86)XQ(~z)TX1{zt = sj ∧ xt = vk }t=1~zTXX11{zt = sj ∧ xt = vk } P(~z, ~x; A, B)=P(~x; A, B) t=1~z==1P(~x; A, B)1P(~x; A, B)X~zQ(~z)|S|T XXXi=1 t=1|S| TXX(1.87)1{zt−1 = si ∧ zt = sj ∧ xt = vk } P(~z, ~x; A, B)~z1{xt = vk }αi (t)Aij Bjxt βj (t + 1),i=1 t=1TX1{zt = sj }t=1|S|TXXX1=1{zt−1 = si ∧ zt = sj } P(~z, ~x; A, B)P(~x; A, B) i=1 t=1(1.88)~z|S|TXX1αi (t)Aij Bjxt βj (t + 1),=P(~x; A, B) i=1 t=1P|S| PTB̂jk =i=1t=1 1{xt = vk }αi (t)Aij Bjxt βj (t + 1).P|S| PTi=1t=1 αi (t)Aij Bjxt βj (t + 1)(1.89)Прямой - обратный алгоритм [83] для скрытых марковских моделей:Инициализация: A и B - случайные матрицы вероятности, где Ai0 = 0 дляi = 1..|S| и B0k = 0 для k = 1..|V |.Обозначим:Итеративно выполняется следующая пара процедур:E-шаг: вычислять αi и βj используя прямой - обратный алгоритм и обозначим:γt (i, j) = αi (t)Aij Bjxt βj (t + 1).41(1.90)M-шаг: перечислять параметры:PTγt (i, j)Âij = P|S| t=1,PTγ(i,j)j=1t=1 tP|S| PTt=1 1{xt = vk }γt (i, j)B̂jk = i=1 P|S|.PTγ(i,j)i=1t=1 t1.9(1.91)Латентно-семантический анализЛатентно-семантический анализ [84] — это методы анализа взаимосвязь междутекстами и словами в них встречающимися.
Эти методы способны изучать латентные (скрытые) тематики текстов, которые позволяют снижать количествохарактеристик при классификации или кластеризации [85]. Благодаря этомуполезному свойству латентно-семантический анализ является одной из важнейших задач обработки текстов и имеет применение в технологиях анализа больших данных [86]. Латентно-семантический анализ часто реализуется на основеискусственных нейронных сетей [87].42Рис. 1.7: Семантические связи.Для реализации метода латентно-семантического анализа используются принципы факторного анализа [88], которые заключаются в поиске латентных связей объектов (в нашем случае термины в текстах). При классификации текстовэтот метод используется для поиска зависимости терминов от контекста с использованием статистической обработки больших баз текстов [89].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
