Слайды со всех лекций (1126919), страница 2
Текст из файла (страница 2)
. . qN −18 октября 2011 г.конечное множество из N состоянийΣконечный входной алфавитq0начальное состояниеFмножество конечных состоянийδ(q, i) : Q × Σ → Qфункция перехода или матрицаперехода между состояниямиАлгоритм распознавания длядетерминированного КА#encoding=CP1251def recognize(tape, machine, acceptStates):index = 0 # Beginning of tape0currentState = 0 # Initial state of machinewhile True:1if index == len(tape):2if currentState in acceptStates:return True3else:4return Falseelif machine[currentState].has_key(tape[index]):currentState = machine[currentState][tape[index]]index+=1else:return FalseВходб1э∅ ∅∅ 2 ∅∅ 3 ∅∅ 3 4∅ ∅ ∅machineSheep = {0:{"б":1}, 1:{"э":2}, 2:{"э":3}, 3:{"э":3,"!":4}, 4:{}}print recognize("бээээээ!",machineSheep, [4])8 октября 2011 г.!Формальные языки"!q0"q1"q2!q3q4• формальный язык — это множествоконечных слов (строк, цепочек) надконечным алфавитомΣ = {a, b, !}L(m) = {baa!, baaa!, baaaa!, .
. .}8 октября 2011 г.Пример формального языка!"#$")%'+#,*'-+*./'(0*1'(1*2()!1*2("*)/'("*1/'(q0")%"&%'('+#"&%'(1!+!3./'("*1/'8 октября 2011 г../'$%"&%'(!"#$$%"&%'(0*1'$%"&%'(")*$%"&%'(1*2$%"&%'('+#$%"&%'()!1*2$%"&%'(,*'-+$%"&%'("*)/'$%"&%'(q10*1'("*1/'1*2("*1/')!1*2("*1/'"*)/$!1'!q2!"#$")%'+#,*'-+*./'(0*1'(1*2()!1*2("*)/'(Недетерминированные КА• Обобщение ДКА• Недетерминизм двух типов"!Тип 1q0"q1!Тип 2q0"q2q3""q1q2q4!q3!8 октября 2011 г.!q4Распознование для НКА• Подходы к решению проблемынедетерминизма–Сохранение состояний (backup)•поиск в глубину и ширину–Просмотр будующих состояний (look-ahead)–ПараллелизмСостояние012348 октября 2011 г.б1∅∅∅∅Входэ!∅ ∅2∅2,3 ∅∅ 4∅ ∅!∅∅∅∅∅ДКА и НКА• ДКА и НКА эквивалентны• Существует простой алгоритм дляпреобразования НКА в ДКА• Идея:–взять все параллельные ветки НКА–в них взять все состояния, в которыходновременно может находиться НКА–объединить их в новое состояние ДКА• В худшем случае НКА с N состояниямиN2преобразуется в ДКА с состояниями8 октября 2011 г.Регулярные языки и ДКА1.
∅ - регулярный язык2.∀a ∈ Σ ∪ !, {a} - регулярный язык3. Для любых регулярных языков L1 и L2 , такими также являются:· L2 = {xy | x ∈ L1 , y ∈ L2 } , соединение L1 и L2(b) L1 ∪ L2 , объединение или дизъюнкция L1 и L2(c) L∗1 , замыкание (Клини) языка L1(a) L1•.• регулярные языки также замкнутыотносительно операций• пересечения• разности• дополнения• инверсии8 октября 2011 г.Построение автомата длярегулярных выраженийq0qfr=!q0qfr=∅qfr=aaq08 октября 2011 г.Построение автомата длярегулярных выражений!qfq0qfq0!" 1!" 2Последовательное соединение двух конечных автоматов8 октября 2011 г.Построение автомата длярегулярных выраженийqf!!q0!" 1q0qf!!q0qf!" 2Объединение двух конечных автоматов8 октября 2011 г.Построение автомата длярегулярных выражений!q0!q0qf!" 1!Замыкание конечного автомата8 октября 2011 г.qfРезюме• Изучены важная фундаментальнаяконцепция конечных автоматов ипрактический инструмент, основанный наней - регулярные выражения–регулярные выражения - мощный инструментдля обработки текстов–любое регулярное выражение может бытьреализовано с помощью КА (кроме памяти)–автомат неявно определяет формальный язык–для любого НКА существует ДКА8 октября 2011 г.Задания для тренировки• Написать аналог ELIZA• Реализовать конечный автомат дляраспознавания всех русских числительных• Спроектировать КА для дат: March 12, the22nd of November, Christmas• Расширить предыдущий автоматотносительными датами: yesterday,tomorrow, a week from tomorrow, the daybefore yesterday, three weeks fromSaturday, next Monday, ...8 октября 2011 г.Дополнительная литература• Kleene S.C.
Representation of events innerve nets and finite automata. (1951,1956)• Rabin M.O. and Scott D. Finite automataand their decision problems. (1959)• Hopcroft J.E. and Ulman J.D. Introductionto Automata Theory, Languages, andComputations. (1979)8 октября 2011 г.Следующая лекция• N-граммы• Задача определения частей речи слов8 октября 2011 г.Введение в обработкутекстовЛекция 3Языковые модели и задача определения частей речи18 октября 2011 г.N-граммы• Формализация процессапредсказания с помощьюмоделей N-грамм• N-грамма–последоватьельность из Nслов–модель предсказания... на одном из этапов для ......
одном на из для этапов ...18 октября 2011 г.Мотивация• Определение языка• Распознавание речи• Распознавание письменного текста• Машинный перевод• Определение частей речи• Определение авторства текста• Генерация текстов• Поиск семантических ошибок–Hi is trying to fine out18 октября 2011 г.Яндекс рефератыТема: «Естественный позитивизм: сомнение илиощущение мира?»Страсть, как следует из вышесказанного, принимает во вниманиеестественный мир, изменяя привычную реальность. Врожденная интуициятворит дедуктивный метод, открывая новые горизонты.
Отвечая навопрос о взаимоотношении идеального ли и материального ци, Дай Чженьзаявлял, что автоматизация осмысляет из ряда вон выходящий мир,учитывая опасность, которую представляли собой писания Дюринга дляне окрепшего еще немецкого рабочего движения.Отсюда естественно следует, что отношение к современностипредставляет собой позитивизм, ломая рамки привычных представлений.18 октября 2011 г.Тренировочный и проверочныйкорпуса• Корпус - собрание текстов, объединенныхобщим признаком• Тренировать и тестировать модель надона различных данных• Перекрестная проверка (cross-validation)18 октября 2011 г.Доступные корпуса• Текстовые–Project Guttenberg–Reuters corpora–lib.ru–Web• Размеченные–Brown corpus–Linguistic Data Consortium–NLTK corpora–Национальный корпус русского языка (НКРЯ)18 октября 2011 г.Примеры N-грамм• Юниграммы–кошка, собака, лошадь–а, и, о• Биграммы–пушистая кошка, большая собака–ал, ин, оп• Триграммы–пушистая кошка мурчит, большая собака лает–али, инт, опа18 октября 2011 г.Подсчет вероятности N-грамм• В обучающем корпусе те или иные nграммы встречаются с разной частотой.• Для каждой n-граммы мы можемпосчитать, сколько раз она встретилась вкорпусе.• На основе полученных данных можнопостроить вероятностную модель, котораязатем может быть использована дляоценки вероятности n-грамм в некоторомтестовом корпусе.18 октября 2011 г.Оценка вероятностиP("Дубровский принужден был выйти в отставку")=?nP (w1 )==n−12P (w1 )P (w2 |w1 )P (w3 |w1 ) .
. . P (wn |w1 )n!k−1P (wk |w1 )k=1• Предположение Марковаn−1P (wn |w1 )• ТогдаnP (w1 )=n!k=118 октября 2011 г.≈ P (wn |wn−1 )P (wk |wk−1 )А. А. Марков=Оценка вероятности• Метод максимального правдоподобияC(wn−1 wn )p(wn |wn−1 ) = !w C(wn−1 w)C(wn−1 wn )p(wn |wn−1 ) =C(wn−1 )18 октября 2011 г.Пример• Пусть корпус состоит из тех предложений–<s> I am Sam </s>–<s> Sam I am </s>–<s> I do not like green eggs and ham </s>21P (I| < s >) = = .67 P (< /s > |Sam) = = .53221P (am|I) = = .67P (do|I) = = .333311P (Sam|am) = = .5 P (Sam| < s >) = = .333218 октября 2011 г.Генератор текста#coding=CP1251import nltkf=open("../data/pushkin.txt")train=nltk.PunktWordTokenizer().tokenize(f.read())f.close()for i in range(3):model = nltk.NgramModel(i+1,train)print i+1, " ".join(model.generate(10))# 1 случай .
.# 2 Несколько лет тому назад в неделю страдал от коихбывал# 3 Несколько лет тому назад в одном сословии ,воспитанные одинаково18 октября 2011 г.Сглаживание• Разреженность языка• Огранниченность корпуса–занижена вероятность–вероятность равна нулю• Сглаживание - повышение вероятностинекоторых n-грам, за счет понижениявероятности других–Сглаживание Лапласа–Откат (backoff)18 октября 2011 г.Методы сглаживания• Сглаживание Лапласа (add-one)• Сглаживание Кнесера-Нея (Kneser-Ney)• Сглаживание Виттена-Белла (Witten-Bell)• Сглаживание Гуда-Тьюринга (Good-Turing)• Интерполяция• Откат (backoff)18 октября 2011 г.Сглаживание Лапласа• Добавим 1 к встречаемости каждой nграммы• Пусть в словаре V слов, тогда∗PLaplace(wn |wn−1 )18 октября 2011 г.C(wn−1 wn ) + 1=C(wn−1 ) + VСглаживание Лапласа(практическое применение)• Метод провоцирует сильную погрешностьв вычислениях• Тесты показали, что unsmoothed-модельчасто показывает более точныерезультаты• Следовательно, метод интересен только стеоретической точки зрения18 октября 2011 г.Откат (backoff)• Основная идея: можно оценивать вероятностиN-грамм с помощью вероятностей (N-k)-грамм(0<k<N).• Особенность: метод можно сочетать с другимиалгоритмами сглаживания (Witten-Bell, GoodTuring и т.
д.)• Оценка вероятности в случае триграмм:18 октября 2011 г.Коэффициент α• Коэффициент α необходим длякорректного распределения остаточнойвероятности N-грамм в соответствии сраспределением вероятности (N-1)-грамм.• Если не вводить α, оценка будетошибочной, т.к. не будет выполнятьсяравенство:18 октября 2011 г.Методы оценки качества моделей• Как понять, что одна модель лучшедругой?• Внешняя оценка (in vivo)–как изменение параметра модели влияет накачество решения задачи• Внутренняя оценка (in vitro)–коэффициент неопределенности (perplexity)18 октября 2011 г.Коэффициент неопределенности• Лучше та модель, которая лучшепредсказывает детали тестовойколлекцииP P (w)1−N= P (w1 w2 . . . wN )!1N=P (w1 w2 ...wN )• Для биграмм!" n"$#P P (w) = N1P(w|w)ii−1i=118 октября 2011 г.Коэффициент неопределенности• Средний взвешенный коэффициентветвистости–рассмотрим язык цифр [0-9]–пусть цифры равновероятны, тогда1−NP P (w) = P (w1 w2 . . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
