Сравнение нескольких алгоритмов

Я Грег Рафферти, специалист по обработке данных из района Залива. Вы можете посмотреть код этого проекта на моем гитхабе. Не стесняйтесь обращаться ко мне с любыми вопросами!

В этой серии публикаций я рассматриваю несколько удобных техник НЛП через призму Гарри Поттера. В предыдущих статьях этой серии, посвященных основам НЛП, были рассмотрены Тематическое моделирование со скрытым распределением Дирихле и Регулярные выражения, а в следующем моем сообщении будет рассмотрен анализ настроений.

Гермиона прервала их. «Вы двое никогда не собираетесь читать« Хогвартс »,« Историю »?»

Сколько раз на протяжении всего сериала о Гарри Поттере Гермиона досаждала Гарри и Рону, чтобы прочитать огромный фолиант История Хогвартса? Подсказка: это много. Сколько ночей они втроем проводят в библиотеке, читая каждую книгу, которую они могут найти, чтобы выяснить, кто такой Николас Фламель, или как выжить под водой, или готовясь к своим O.W.L.? Ошибка, которую они все совершают, состоит в том, что они пытаются все прочитать сами.

Помните, когда вы учились в школе и наткнулись на краткое содержание книги CliffsNotes, которую вы никогда не читали, но должны были написать эссе? Это в основном то, что делает резюмирование текста: предоставляет версию CliffsNotes для любого большого документа. Теперь CliffsNotes написаны довольно образованными людьми, которые знакомы с книгой, которую они резюмируют. Но сейчас двадцать первый век, разве компьютеры не должны лишать людей работы? Я изучил несколько алгоритмов реферирования текста, чтобы увидеть, готовы ли мы избавиться от старого бедного Клифтона.

Есть два типа алгоритмов реферирования текста: экстрактивные и абстрактные. Все алгоритмы извлекающего реферирования пытаются оценивать фразы или предложения в документе и возвращать только наиболее информативные блоки текста. Резюмирование абстрактного текста фактически создает новый текст, которого нет в данной форме в документе. Абстрактное обобщение - это то, что вы можете сделать, объясняя прочитанную книгу своему другу, и для компьютера это сделать намного сложнее, чем извлекающее обобщение. Компьютеры не так хороши в процессе творчества. На сегодняшний день не существует методов абстрактного реферирования, которые подходили бы для длинных документов. Самые эффективные из них просто создают предложение, основанное на одном абзаце, или сокращают длину предложения пополам, сохраняя при этом как можно больше информации. Часто грамматика ужасно страдает. Обычно они основаны на моделях нейронных сетей. Этот пост будет посвящен гораздо более простым методам резюмирования извлекающего текста.

Большинство алгоритмов, которые я представлю, объединены в пакет sumy для Python, но я также использую один сумматор из пакета Gensim и еще один метод, который я написал сам, используя ключевые слова LDA для обогащения sumy EdmundsonSummarizer. Все примеры выводят краткое изложение из пяти предложений первой главы Гарри Поттер и философский камень. Полный код см. В моем Блокноте Jupyter. И одно предостережение: не судите о результатах слишком строго. Они не очень хороши ... (резюмирование текста, кажется, лучше работает с более сухими произведениями научно-популярной литературы)

LexRank Summarizer

LexRank - это неконтролируемый подход, основанный на тех же идеях, что и алгоритм Google PageRank. Авторы говорят, что он основан на концепции центральности собственного вектора в графическом представлении предложений с использованием матрицы связности, основанной на косинусном сходстве внутри предложения. Итак, вкратце, он находит относительную важность всех слов в документе и выбирает предложения, которые содержат наибольшее количество этих высоко оцененных слов.

"The Potters, that's right, that's what I heard —" "— yes, their son, Harry —" Mr. Dursley stopped dead.
Twelve times he clicked the Put-Outer, until the only lights left on the whole street were two tiny pinpricks in the distance, which were the eyes of the cat watching him.
Dumbledore slipped the Put-Outer back inside his cloak and set off down the street toward number four, where he sat down on the wall next to the cat.
"But I c-c-can't stand it — Lily an' James dead — an' poor little Harry off ter live with Muggles —" "Yes, yes, it's all very sad, but get a grip on yourself, Hagrid, or we'll be found," Professor McGonagall whispered, patting Hagrid gingerly on the arm as Dumbledore stepped over the low garden wall and walked to the front door.
Dumbledore turned and walked back down the street.

Luhn Summarizer

Один из первых алгоритмов реферирования текстов был опубликован в 1958 году Гансом Петером Луном, работающим в IBM Research. Алгоритм Луна - это наивный подход, основанный на TF-IDF и учитывающий размер окна неважных слов между важными словами. Он также присваивает более высокий вес предложениям, встречающимся в начале документа.

It was now reading the sign that said Privet Drive — no, looking at the sign; cats couldn't read maps or signs.
He didn't see the owls swooping past in broad daylight, though people down in the street did; they pointed and gazed open-mouthed as owl after owl sped overhead.
No one knows why, or how, but they're saying that when he couldn't kill Harry Potter, Voldemort's power somehow broke — and that's why he's gone."
"But I c-c-can't stand it — Lily an' James dead — an' poor little Harry off ter live with Muggles —" "Yes, yes, it's all very sad, but get a grip on yourself, Hagrid, or we'll be found," Professor McGonagall whispered, patting Hagrid gingerly on the arm as Dumbledore stepped over the low garden wall and walked to the front door.
G'night, Professor McGonagall — Professor Dumbledore, sir."

LSA Summarizer

Скрытый семантический анализ - это относительно новый алгоритм, который сочетает частоту терминов с разложением по сингулярным значениям.

He dashed back across the road, hurried up to his office, snapped at his secretary not to disturb him, seized his telephone, and had almost finished dialing his home number when he changed his mind.
It seemed that Professor McGonagall had reached the point she was most anxious to discuss, the real reason she had been waiting on a cold, hard wall all day, for neither as a cat nor as a woman had she fixed Dumbledore with such a piercing stare as she did now.
He looked simply too big to be allowed, and so wild — long tangles of bushy black hair and beard hid most of his face, he had hands the size of trash can lids, and his feet in their leather boots were like baby dolphins.
For a full minute the three of them stood and looked at the little bundle; Hagrid's shoulders shook, Professor McGonagall blinked furiously, and the twinkling light that usually shone from Dumbledore's eyes seemed to have gone out.
A breeze ruffled the neat hedges of Privet Drive, which lay silent and tidy under the inky sky, the very last place you would expect astonishing things to happen.

TextRank Summarizer

TextRank - это еще один составитель текстов, основанный на идеях PageRank, и он также был разработан одновременно с LexRank, но разными группами людей. TextRank немного проще, чем LexRank; хотя оба алгоритма очень похожи, LexRank применяет эвристический шаг постобработки для удаления предложений с высокой степенью двуличности.

Mr. and Mrs. Dursley, of number four, Privet Drive, were proud to say that they were perfectly normal, thank you very much.
They were the last people you'd expect to be involved in anything strange or mysterious, because they just didn't hold with such nonsense.
Mr. Dursley was the director of a firm called Grunnings, which made drills.
He was a big, beefy man with hardly any neck, although he did have a very large mustache.
Mrs. Dursley was thin and blonde and had nearly twice the usual amount of neck, which came in very useful as she spent so much of her time craning over garden fences, spying on the neighbors.

Эдмундсон Summarizer

В 1969 году Гарольд Эдмундсон разработал сумматор, носящий его имя. Алгоритм Эдмундсона был, наряду с алгоритмом Луна, одним из основополагающих методов резюмирования текста. Что отличает сумматор Edmundson от других, так это то, что он принимает во внимание бонусные слова, слова, указанные пользователем как очень важные; Стигматические слова, слова низкой или даже отрицательной важности; и стоп-слова, которые используются в других местах обработки НЛП. Эдмундсон предложил использовать слова в названии документа в качестве дополнительных слов. Используя название главы в качестве бонусных слов, Эдмундсон выводит вот что:

The Dursleys shuddered to think what the neighbors would say if the Potters arrived in the street.
When Dudley had been put to bed, he went into the living room in time to catch the last report on the evening news: "And finally, bird-watchers everywhere have reported that the nation's owls have been behaving very unusually today.
Twelve times he clicked the Put-Outer, until the only lights left on the whole street were two tiny pinpricks in the distance, which were the eyes of the cat watching him.
Dumbledore slipped the Put-Outer back inside his cloak and set off down the street toward number four, where he sat down on the wall next to the cat.
He couldn't know that at this very moment, people meeting in secret all over the country were holding up their glasses and saying in hushed voices: "To Harry Potter — the boy who lived!"

Еще одно дополнение, которое я сделал, заключалось в том, что я использовал LDA для извлечения ключевых слов темы, а затем снова добавлял эти ключевые слова в качестве дополнительных бонусных слов. С этой модификацией результаты Эдмундсона выглядят следующим образом:

At half past eight, Mr. Dursley picked up his briefcase, pecked Mrs. Dursley on the cheek, and tried to kiss Dudley good-bye but missed, because Dudley was now having a tantrum and throwing his cereal at the walls.
When Dudley had been put to bed, he went into the living room in time to catch the last report on the evening news: "And finally, bird-watchers everywhere have reported that the nation's owls have been behaving very unusually today.
Twelve times he clicked the Put-Outer, until the only lights left on the whole street were two tiny pinpricks in the distance, which were the eyes of the cat watching him.
One small hand closed on the letter beside him and he slept on, not knowing he was special, not knowing he was famous, not knowing he would be woken in a few hours' time by Mrs. Dursley's scream as she opened the front door to put out the milk bottles, nor that he would spend the next few weeks being prodded and pinched by his cousin Dudley.
He couldn't know that at this very moment, people meeting in secret all over the country were holding up their glasses and saying in hushed voices: "To Harry Potter — the boy who lived!"

SumBasic Summarizer

Алгоритм SumBasic был разработан в 2005 году и использует только вероятностный подход для определения важности предложения. Извините, но с этим документом все плохо.

Mr. Dursley wondered.
"Harry.
The cat was still there.
"It certainly seems so," said Dumbledore.
"Yes," said Professor McGonagall.

Вот это да. Это ужасно. Кхм, идем дальше ...

KL Summarizer

Алгоритм KLSum - это жадный метод, который добавляет предложения к резюме, пока дивергенция KL (мера энтропии) уменьшается.

It was on the corner of the street that he noticed the first sign of something peculiar — a cat reading a map.
It grew steadily louder as they looked up and down the street for some sign of a headlight; it swelled to a roar as they both looked up at the sky — and a huge motorcycle fell out of the air and landed on the road in front of them.
He looked simply too big to be allowed, and so wild — long tangles of bushy black hair and beard hid most of his face, he had hands the size of trash can lids, and his feet in their leather boots were like baby dolphins.
"But I c-c-can't stand it — Lily an' James dead — an' poor little Harry off ter live with Muggles —" "Yes, yes, it's all very sad, but get a grip on yourself, Hagrid, or we'll be found," Professor McGonagall whispered, patting Hagrid gingerly on the arm as Dumbledore stepped over the low garden wall and walked to the front door.
He clicked it once, and twelve balls of light sped back to their street lamps so that Privet Drive glowed suddenly orange and he could make out a tabby cat slinking around the corner at the other end of the street.

Редукционный сумматор

Алгоритм редукции - это еще одна основанная на графах модель, которая оценивает предложения в соответствии с суммой весов их ребер по отношению к другим предложениям в документе. Этот вес вычисляется так же, как и в модели TexRank.

Mrs. Potter was Mrs. Dursley's sister, but they hadn't met for several years; in fact, Mrs. Dursley pretended she didn't have a sister, because her sister and her good-for-nothing husband were as unDursleyish as it was possible to be.
It seemed that Professor McGonagall had reached the point she was most anxious to discuss, the real reason she had been waiting on a cold, hard wall all day, for neither as a cat nor as a woman had she fixed Dumbledore with such a piercing stare as she did now.
Dumbledore took Harry in his arms and turned toward the Dursleys' house.
"But I c-c-can't stand it — Lily an' James dead — an' poor little Harry off ter live with Muggles —" "Yes, yes, it's all very sad, but get a grip on yourself, Hagrid, or we'll be found," Professor McGonagall whispered, patting Hagrid gingerly on the arm as Dumbledore stepped over the low garden wall and walked to the front door.
G'night, Professor McGonagall — Professor Dumbledore, sir."

Gensim Summarizer

Пакет Gensim для Python включает сумматор, который является модификацией алгоритма TextRank. Подход Генсима изменяет функцию подобия предложений.

It was now reading the sign that said Privet Drive — no, looking at the sign; cats couldn't read maps or signs.
Dumbledore slipped the Put-Outer back inside his cloak and set off down the street toward number four, where he sat down on the wall next to the cat.
They're a kind of Muggle sweet I'm rather fond of." "No, thank you," said Professor McGonagall coldly, as though she didn't think this was the moment for lemon drops.
All this 'You-Know-Who' nonsense — for eleven years I have been trying to persuade people to call him by his proper name: Voldemort." Professor McGonagall flinched, but Dumbledore, who was unsticking two lemon drops, seemed not to notice.
Professor McGonagall shot a sharp look at Dumbledore and said, "The owls are nothing next to the rumors that are flying around.
It seemed that Professor McGonagall had reached the point she was most anxious to discuss, the real reason she had been waiting on a cold, hard wall all day, for neither as a cat nor as a woman had she fixed Dumbledore with such a piercing stare as she did now.

Итак, какой алгоритм, по вашему мнению, обеспечивает наилучшее обобщение? Перед вынесением окончательного решения нужно настроить множество параметров. Некоторые могут лучше работать с более короткими резюме, некоторые с более длинными резюме. Стиль письма может иметь значение (я упоминал ранее, что мне больше повезло в обобщении научной литературы, чем в художественной литературе). Но если вы Гарри только что входите в библиотеку Хогвартса с намерением ответить на какой-то вопрос и вас пугает «огромный размер библиотеки; десятки тысяч книг; тысячи полок; сотни узких рядов », то не помешает получить несколько сводок с помощью нескольких щелчков мышью. Если бы только волшебники использовали такие глупые маггловские создания ...