Skip to content

Latest commit

 

History

History
280 lines (208 loc) · 18.2 KB

Задание_2._Извлечение_информации_из_текста.mediawiki

File metadata and controls

280 lines (208 loc) · 18.2 KB
Raw
layout title
default
Задание 2. Извлечение информации из текста

Table of Contents

Извлечение информации из текста / Information Extraction (IR)

Ссылки на online-демонстрации IR систем

Результаты работы систем IR

Ссылки на IR программы

Дополнительные ссылки

Задания на семинар

Задание для выполнения

Провести извлечение именованных сущностей из текста используя HMM (Hidden Markov Model).

Исходные данные

Для выполнения задания необходимо выбрать небольшой текст (ок. 10 предложений), включающий в себя несколько видов сущностей, например, имена и даты. Хорошими текстами будут биографии людей, например, выдержка из биографии Дугласа Енгельбарта:

Douglas Carl Engelbart has a life-long track record in predicting, designing, and implementing the future of organizational computing. The grandson of early pioneers of the West, he grew up during the Great Depression on a small farmstead near Portland, Oregon. After graduating from high school in 1942, he went on to study electrical engineering at Oregon State University. World War II interrupted his studies for the Navy, where he served for two years in the Philipines as an electronic/radar technician. After completing his B.S. in electrical engineering in 1948, he settled contentedly on the San Francisco peninsula as an electrical engineer at NACA Ames Laboratory (forerunner of NASA).

Порядок выполнения задания

  1. Выделить классы именованных сущностей в тексте
  2. Построить HMM для определения выделенных классов сущностей на основе выбранного текста
  3. Применить полученную HMM для определения сущностей в новом предложении

Выделение классов именованных сущностей в тексте

В нашем примере можно выделить следующие сущности:

  • Person
    Douglas, Carl, Engelbart,
  • City
    Portland, San, Francisco
  • Location
    West, Oregon, Phillipines
  • Organization
    Oregon, State, University, NACA, Ames, Laboratory, NASA, Navy
  • Event
    Great, Depression, Word, War, II
  • Date
    1942, 1948
Выбор и наименование сущностей необходимо производить на собственное усмотрение. Так, для простоты я объединил в примере названия штатов в США, названия государств и географическое расположение в одну сущность Location. При этом квалификации, научные степени и профессии (B.S., electronic/radar technitian) опущены вообще.

Douglas Carl Engelbart has a life-long track record in predicting, designing, and implementing the future of organizational computing. The grandson of early pioneers of the West, he grew up during the Great Depression on a small farmstead near Portland, Oregon. After graduating from high school in 1942, he went on to study electrical engineering at Oregon State University. World War II interrupted his studies for the Navy, where he served for two years in the Philipines as an electronic/radar technician. After completing his B.S. in electrical engineering in 1948, he settled contentedly on the San Francisco peninsula as an electrical engineer at NACA Ames Laboratory (forerunner of NASA).

Для простоты расчета возьмем только две сущности - Person и City. Студентам также рекомендуется брать минимальное количество сущностей.

Также для простоты будем считать San Francisco одним словом.

Построение HMM для определения выделенных классов сущностей

Hidden Markov Model состоит из набора формул для вычисления вероятности того, что какое-либо слово wi является какой-нибудь именованной сущностью Ej либо "не именованной сущностью" - NaN (Not a Name).

Как и в любом статистическом методе, вероятности вычисляются на основе статистических данных. В нашем случае это выбранные для анализа предложения.

Формулы для расчета вероятностей

Для расчета вероятностей:

  • в начало каждого предложения добавляется специальная сущность Start
  • берется рядом стоящая пара слов A и B в предложении и для нее расчитывается 3 вероятности:
  1. Вероятность того, что любое слово является сущностью F если оно находится в предложении после слова A, которое в свою очередь является сущностью E:
    p1(F | E[A]) = Count(E[A], F) / Count(E[A])
    p1 - это отношение между количеством случаев, когда после слова A с сущностью E следует любое слово с сущностью F и количеством слов А c сущностью E в тексте
  2. Вероятность того, что слово B является сущностью F если оно находится в предложении после любого слова, которое является сущностью E:
    p2([B] | E,F) = Count(E, F[B]) / Count(E, F)
    p2 - это отношение между количеством случаев, когда после любого слова с сущностью E следует слово B с сушностью F и количеством пар слов c сущностями E и F в тексте
  3. Вероятность того, что слово B является той же сущностью E, что и предыдущее слово A:
    p3(E[B] | E[A]) = Count(E[A], E[B]) / Count(E[A])
    p3 - это отношение между количеством случаев, когда слова A и B встречаются последовательно и оба означают одну и ту же сущность E и количеством слов А c сущностью E в тексте

Пример расчета вероятностей

p1(Person | Start[]) = 1/5 = 0.2
1 - количество сущностей Person в начале предложения
5 - количество "начал предложений", т.е. количество предложений

p2([Douglas] | Start,Person) = 1/1 = 1.0
1 - количество слов "Douglas", стоящих в начале предложения и являющихся Person
1 - количество пар (Start - "начало предложения", Person) в предложениях

p3(Start[Douglas] | Start[]) = 0/5 = 0
0 - количество слов "Douglas", являющихся началом предложения (Start) и стоящих после начала предложения
5 - количество "начал предложений", т.е. количество предложений

--------------------------------------------------------------------------------

p1(Person | Person[Douglas]) = 1/1 = 1.0
1 - количество сущностей Person после слова Douglas, являющегося Person
1 - количество слов Douglas, являющихся Person

p2([Carl] | Person, Person) = 1/2 = 0.5
1 - количество слов "Carl", стоящих после сущности Person и являющихся Person
2 - количество пар (Person, Person) в предложениях

p3(Person[Carl] | Person[Douglas]) = 1/1 = 1.0
1 - количество слов "Carl", являющихся Person и стоящих после слова "Douglas",
    также являющихся Person
1 - количество слов "Douglas", являющихся Person

--------------------------------------------------------------------------------

p1(Person | Person[Carl]) = 1/1 = 1.0
1 - количество сущностей Person после слова Carl, являющегося Person
1 - количество слов Carl, являющихся Person

p2([Engelbart] | Person, Person) = 1/2 = 0.5
1 - количество слов "Engelbart", стоящих после сущности Person и являющихся Person
2 - количество пар (Person, Person) в предложениях

p3(Person[Engelbart] | Person[Carl]) = 1/1 = 1.0
1 - количество слов "Engelbart", являющихся Person и стоящих после слова "Carl",
    также являющихся Person
1 - количество слов "Carl", являющихся Person

--------------------------------------------------------------------------------

p1(City | NaN[near]) = 1/1 = 1.0
1 - количество сущностей City после слова "near", являющегося NaN
1 - количество слов "near", являющихся NaN

p2([Portland] | NaN, City) = 1/2 = 0.5
1 - количество слов "Portland", стоящих после сущности NaN и являющихся City
2 - количество пар (NaN, City) в предложениях

p3(NaN[Portland] | Nan[near]) = 0/1 = 0.0
0 - количество слов "Portland", являющихся NaN и стоящих после слова "near",
    также являющихся NaN
1 - количество слов "near", являющихся NaN

--------------------------------------------------------------------------------

p1(City | NaN[the]) = 1/1 = 1.0
1 - количество сущностей City после слова "the", являющегося NaN
7 - количество слов "the", являющихся NaN

p2([SanFrancisco] | NaN, City) = 1/2 = 0.5
1 - количество слов "SanFrancisco", стоящих после сущности NaN и являющихся City
2 - количество пар (NaN, City) в предложениях

p3(NaN[SanFrancisco] | Nan[the]) = 0/7 = 0.0
0 - количество слов "SanFrancisco", являющихся NaN и стоящих после слова "the",
    также являющихся NaN
7 - количество слов "the", являющихся NaN

--------------------------------------------------------------------------------

Для всех остальных слов, не являющихся сущностями (т.е. NaN) можно выдвинуть гипотезу,
что вероятности p1, p2, p3 будут близки к 1.0.

Например,
p1(Nan | ЛюбойКласс[любое слово]) = 
    = (количество слов с классом NaN) / (общее количество слов) =
    = 102/107 = 0.95

Т.о. предполагаем, что вероятность того, что слово не является сущностью (т.е. является NaN)
равна 1.0 и в расчетах не учитываем.

Алгоритм извлечения именованных сущностей

Для каждого предложения из текста:

  1. Поставить сущность Start в начало предложения
  2. Начать с первого слова в предложении
  3. Расчитать произведение вероятностей p1 * p2 для текущего слова для каждого из возможных классов сущностей
  4. Расчитать вероятность p3 того, что текущее слово принадлежит тому же классу, что и предыдущее.
  5. Назначить класс с наибольшей вероятностью для текущего слова и перейти к следующему

Пример извлечения именованных сущностей

Пример предложения для извлечения именованных сущностей:
Douglas Engelbart was born near Portland.

Добавляем Start в начало предложения:
Start Douglas Engelbart was born near Portland.

Начинаем с первого слова:

Douglas:
    p1(Person | Start[]) = 0.2
    p2([Douglas] | Start, Person) = 1.0
    p(Person) = p1*p2 = 0.2

    p1(City | Start[]) = 0
    p2([Douglas] | Start, City) = 0
    p(City) = p1*p2 = 0

    p3(Start[Douglas], Start[]) = 0

    Итак, "Douglas" - Person с вероятностью 20%


Engelbart:
    p1(Person | Person[Douglas]) = 1.0
    p2([Engelbart] | Person, Person) = 0.5
    p(Person) = p1*p2 = 0.5

    p1(City | Person[Douglas]) = 0
    p2([Engelbart] | Person, City) = 0
    p(City) = p1*p2 = 0

    p3(Person[Engelbart] | Person[Douglas]) = 0

    Итак, "Engelbart" - Person с вероятностью 50%


was:
    p1(Person | Person[Engelbart]) = 0
    p2([was] | Person, Person) = 0
    p(Person) = 0

    p1(City | Person[Engelbart]) = 0
    p2([was] | Person, City) = 0
    p(City) = 0

    p3(Person[was] | Person[was]) = 0

    Итак, "was" - не сущность, т.е. NaN

born:
    p1(Person | NaN[was]) = 0
    p2([born] | Nan, Person) = 0
    p(Person) = 0

    p1(City | NaN[was]) = 0
    p2([was] | NaN, City) = 0
    p(City) = 0

    p3(NaN[born] | NaN[was]) = 1.0 (согласно гипотезе)

    Итак, "born" - не сущность, т.е. NaN

near:
    p1(Person | NaN[born]) = 0
    p2([near] | Nan, Person) = 0
    p(Person) = 0

    p1(City | NaN[born]) = 0
    p2([near] | NaN, City) = 0
    p(City) = 0

    p3(NaN[near] | NaN[born]) = 1.0 (согласно гипотезе)

    Итак, "near" - не сущность, т.е. NaN

Portland:
    p1(Person | NaN[near]) = 0
    p2([Portland] | Nan, Person) = 0
    p(Person) = 0

    p1(City | NaN[near]) = 1.0
    p2([Portland] | NaN, City) = 0.5
    p(City) = 0.5

    p3(NaN[Portland] | NaN[near]) = 0

    Итак, "Portland" - City с вероятностью 0.5

Решение задачи извлечения именованных сущностей:
Douglas[Person,] Engelbart[Person,] was born near Portland[City,].