Программа курса
"Интеллектуальные информационные системы"

18.04.06

Тема Слайды Литература
Цели и задачи курса. Данные, информация, знания. Интеллектуальные системы. История развития дисциплины "Искусственный интеллект", основные направления исследований и разработок. Автоматическая обработка текстов. Информационный поиск. PDF [ИИ1, ИИ2, Пенроуз]
Модели и методы информационного поиска. Прямой поиск. Поиск по индексу. Предварительная обработка. Булевская модель поиска. Векторная модель поиска. Подход TF*IDF. Оценка методов поиска. PDF [Храмцов, Добрынин, Некрестьянов, Сегалович, Brin]
Лемматизация, морфологическая разметка. Цели и виды морфологического анализа. Принципы работы морфологического анализатора. Процедурный, табличный и вероятностный подходы. PDF [Попов 1982, Перспективы, Коваленко, Segalovich, Сокирко]
Cинтаксический анализ. Основные формализмы описания синтаксической структуры предложения: дерево зависимостей, непосредственные составляющие. Формальные грамматики. Контекстно-свобдная грамматика. Поверхностный синтаксический анализ: parsing by chunks. PDF [Попов 1982, Гладкий, Леонтьева]
Выделение ключевых слов: графические подсказки, морфологические ограничения, частотные критерии. Закон Ципфа. Использование глобальной статистики: подход tf*idf.
Автоматическое реферирование документов: задачи и подходы. Основные методы извлечения предложений: важные слова; учет положения предложения в тексте; учет "сигнальных" слов и фраз; учет связей между предложениями.		 PDF [Хан, Солтон, Браславский 2005]
Выделение устойчивых словосочетаний. Что такое "устойчивое словосочетание"? Зачем нужно выделять устойчивые словосочетания? Методы выделения. Частота + морфологические шаблоны. Статистическая проверка гипотез: t-тест, хи-квадрат критерий Пирсона (анализ таблиц сопряженности 2х2), отношение функций правдоподобия. PDF [FSNLP, Добров, Статистика]
Выделение терминов и связей между ними; тезаурусы. Что такое термин? Что такое семантическая связь (семантическое отношение)? Что такое тезаурус/онтология? Области приложения. Первичные источники. Классификация методов. Обзор методов. Методы нахождения семантически близких терминов. PDF [Добров, Bourigault, Jacquemin, Hearst, Grefenstette, Sato]
Автоматическая категоризация документов ("классификация с учителем"). Постановка задачи. Примеры приложений. Представление документов. Проблема высокой размерности пространства классификации. Методы снижения размерности: выбор признаков, агрегация признаков. Формулы для вычисления важности термина для классификации. Кластеризация терминов. Латенто-семантическое индексирование (LSI). Методы построения классификаторов: параметрические, на основе образцов. Байесовский классификатор. Support Vector Machine (SVM). Метод Rocchio. Центроиды классов. K ближайших соседей (kNN). PDF [Sebastiani, IIR, Добрынин]
Автоматическая кластеризация документов ("классификация без учителя"). Постановка задачи. Примеры приложений. Представление входной информации. Иерархические агломеративные методы (метод одиночной связи, метод полной связи, метод группового среднего). Метод k средних. Кластеризация на основе суффиксных деревьев (suffix tree clustering, STC). PDF [Zamir]
Стилистический анализ документов. Что такое "стиль документа"? Стиль в MS Word. Проблема определения авторства: постановка задачи, автоматические методы, подходы, примеры. Функциональные стили. Стилистическая категоризация. Стлистические признаки. Индексы удобочитаемости. Ранжирование с учетом стиля. PDF [Karlgren, Браславский 2002, Braslavski 2005, Хмелев, Кукушкина]
Экспертные системы. Структура экспертной системы: база знаний, машина вывода, механизмы приобретения и объяснения знаний, интеллектуальный интерфейс. Декларативная и процедурная формы представления знаний. Модели представления знаний. Продукции. Фреймы. Семантические сети. Формальные логические модели. Методы извлечения знаний.   [Осуга, ИИ2, Гаврилова 1992, Попов 1996]
Этапы проектирования экспертной системы: идентификация, концептуализация, формализация, реализация, тестирование, опытная эксплуатация. Участники процесса проектирования: эксперты, инженеры по знаниям, разработчики, конечные пользователи.   [Гаврилова 2000, Попов 1996]

Литература

[Айвазян] Прикладная статистика: Классификация и снижение размерности: Справ. изд. / Под. ред. С.А. Айвазяна. - М.: Финансы и статистика, 1989.

[Браславский 2002] Браславский П.И., Вовк Е.А., Маслов М.Ю. Фасетная организация интернет-каталога и автоматическая жанровая классификация документов //Компьютерная лингвистика и интеллектуальные технологии. Тр. междунар. семинара "Диалог-2002". Т. 2. - М.: Наука, 2002. - С.83-93. (Электронная версия: http://company.yandex.ru/articles/article8.html)

[Браславский 2005] Брасласвский П., Колычев И. eXtragon: экспериментальная система для автоматического реферирования веб-документов //Труды РОМИП-2005. СПб., 2005. С. 40-53. (Эл. версия: http://www.romip.narod.ru/romip2005/03_extragon.pdf)

[Гаврилова 1992] Гаврилова Т.А., Червинская К.Р. Извлечение и структурирование знаний для экспертных систем. - М.: Радио и связь, 1992.

[Гаврилова 2000] Гаврилова Т.А., Хорошевский В.Ф. Базы знаний интеллектуальных систем. - СПб.: Питер, 2000.

[Гладкий] Гладкий А. В. Синтаксические структуры естественного языка в автоматизированных системах общения. - М.: Наука, 1985.

[Добров] Добров Б.Н., Лукашевич Н.В., Сыромятников С.В. Формирование базы терминологических свловосочетаний по текстам предметной области // Электронные библиотеки: Труды конференции RCDL'2003. СПб, 2003. С. 201-210. (Элетронная версия: см. http://rcdl2003.spbu.ru)

[Добрынин] Добрынин В. Теория информационно-логических систем. Информационный поиск. (Методичекие указания к курсу). - СПб., 2002. (Эл. версия: http://ir.apmath.spbu.ru/publications/dobrynin_ir_intro/ )

[ИИ1] Искусственный интеллект: Справочник: Кн.1: Системы общения и экспертные системы. - М.: Радио и связь, 1990.

[ИИ2] Искусственный интеллект: Справочник: Кн.2: Модели и методы. - М.: Радио и связь, 1990.

[Коваленко] Вероятностный морфологический анализатор русского и украинского языков, http://linguist.nm.ru/stemka/stemka.html

[Кукушкина] Кукушкина О.В., Поликарпов А.А., Хмелёв Д.В. Определение авторства текста с использованием буквенной и грамматической информации//Проблемы передачи информации, 2001, т.37, вып.2, с.96-108. (Электронная версия: http://www.math.toronto.edu/dkhmelev/PAPERS/published/gramcodes/gramcodes.pdf)

[Леонтьева] Леоньтьева Н.Н. Автоматическое понимание текстов: системы, модели, ресурсы. - М.: Издательский центр "Академия", 2006.

[Нейл] Нейл К., Шанмагантан Г. Web-инструмент для выявления плагиата//Открытые системы. 2005. №01. С. 40-44. (Эл. версия - http://www.osp.ru/os/2005/01/040_print.htm)

[Некрестьянов] Некрестьянов И., Пантелеева Н. Системы текстового поиска для Веб // Программирование. - 2002. - №28(4). С. 207-225. (Электронная версия: http://meta.math.spbu.ru/~nadejda/papers/web-ir/web-ir.html)

[Осуга] Осуга С. Обработка знаний. - М.: Мир, 1989.

[Пенроуз] Пенроуз Р. Новый ум короля: О компьютерах, мышлении и законах физики. – М.: УРСС, 2003.

[Перспективы] Перспективы развития вычислительной техники в 11 кн. Кн. 2. Интеллектуализация ЭВМ. - М.: Высшая школа, 1989.

[Попов 1982] Попов Э.В. Общение с ЭВМ на естественном языке. - М.: Наука, 1982.

[Попов 1996] Статические и динамические экспертные системы // Э.В. Попов, И.Б. Фоминых, Е.Б. Кисель, М.Д. Шапот. – М.: Финансы и статистика, 1996.

[Рао] Рао С.Р. Линейные статистические методы и их применения. М.: Наука, 1968.

[Сегалович] Сегалович И.В. Как работают поисковые системы //Мир Internet, - 2002. - №10. (Электронная версия: http://www.dialog-21.ru/directions/Segalovich_vorprint.doc)

[Сокирко] Сокирко А. В. Морфологические модули на сайте www.aot.ru //Материалы конференции "Диалог-2004". Эл. версия: http://www.dialog-21.ru/Archive/2004/Sokirko.htm

[Солтон] Солтон Дж. Динамические библиотечно-информационные системы. - М.: Мир, 1979.

[ФДКА] Факторный, дискриминантный и кластерный анализ: Пер. с англ. - М.: Финансы и статистика, 1989.

[Хан] Хан У., Мани И. Системы автоматического реферирования//Открытые системы, 2000. - №12. Эл. верия: http://www.osp.ru/os/2000/12/067_print.htm

[Хмелев] Хмелев Д. Распознавание автора текста с использованием цепей А.А. Маркова //Вестник МГУ, сер.9: Филология, N 2, 2000, с.115-126. (Электронная версия: http://www.rusf.ru/books/analysis/vestnik2000win.htm )

[Храмцов] Храмцов П. Информационно-поисковые системы Internet // Открытые системы, - 1996. - №3. (Электронная версия: http://www.osp.ru/os/1996/03/46_print.htm )

[Braslavski 2005] Braslavski P., Tselishchev A, Style-Dependent Document Ranking. In Proc. RCDL'2005. (Эл. версия: http://www.rcdl2005.uniyar.ac.ru/ru/RCDL2005/papers/sek7_1_paper.pdf)

[Brin] Brin S., Page L. The Anatomy of a Large-Scale Hypertextual Web Search Engine // Статья с WWW7, эл. версия http://www-db.stanford.edu/pub/papers/google.pdf

[Grefenstette] Grefenstette G. Automatic Thesaurus Generation from Raw Text using Knowledge-Poor Techniques // Proceedings of SIGIR, 1995.

[Hearst] Hearst M. A. Automatic Acquisition of Hyponyms from Large Text Corpora//Proc. of the 14th International Conference on Computational Linguistics, Nantes, France, 1992. Эл. версия http://acl.ldc.upenn.edu/C/C92/C92-2082.pdf.

[Karlgren] Karlgren, J. and Cutting, D. Recognizing Text Genres with Simple Metrics Using Discriminant Analysis. In Proceedings of the 15th International Conference on Computational Linguistics (COLING), Kyoto, 1994, vol. 2, p. 1071-1075. (Эл. версия: http://www.sics.se/~jussi/Papers/1994_Coling_Kyoto_l/cmplglixcol.ps)

[FSNLP] Manning C. D., Schutze H. Foundations of Statistical Natural Language Processing. Chapter 5: Collocations. Эл. версия главы.

[IIR] Christopher D. Manning, Prabhakar Raghavan and Hinrich Schutze, Introduction to Information Retrieval, Cambridge University Press. 2007. Главы будущей книги

[Sato] S. Sato and Y. Sasaki. 2003. Automatic collection ofrelated terms from the web. In Proc. 41st ACL, p. 121–124.

[Sebastiani] Sebastiani F. Machine Learning in Automated Text Categorization // ACM Computing Surveys, Vol. 34, No. 1, March 2002, pp. 1–47.

[Segalovich] Segalovich I. A fast morphological algorithm with unknown word guessing induced by a dictionary for a web search engine, http://company.yandex.ru/articles/iseg-las-vegas.html + обсуждение в форуме.

[Zamir] Zamir O., Etzioni O. Web Document Clustering: A Feasibility Demonstration. In Proc. SIGIR'98.

Ссылки

  1. Русский национальный корпус, http://www.ruscorpora.ru
  2. Частотный словарь Сергея Шарова, http://www.artint.ru/projects/frqlist.asp
  3. Поисковые машины и поисковая оптимизация, http://searchengines.ru
  4. РОМИП, http://romip.narod.ru
  5. Список стоп-слов, http://forum.searchengines.ru/showthread.php?postid=7670
  6. Станица Андрея Коваленко, http://linguist.nm.ru
  7. Cайт "Автоматическая Обработка Текста", http://www.aot.ru
  8. Грамматика русского языка, http://rusgram.narod.ru
  9. Библиотека на www.nigma.ru
  10. Лингвоанализатор Дмитрия Хмелева.
  11. Синтаксис языка запросов Яндекса на Livejournal.com
  12. Страница Леонида Бойцова
  13. Морфологический анализатор mystem
  14. TextAnalyst
  15. Учебные материалы на www.informationretrieval.org

Задания для практических занятий

  1. Поиск в Интернете. Изучите официальное и неофициальное описание языка запросов Яндекса. Изучите основы поиска и операторы языка запросов Google. Пройдите зачет на странице Кубка Яндекса ("тренировочная игра"). Попробуйте пользоваться разными машинами поиска. Оцените субъективно удобство и качество поиска. Чего не хватает? Что лишнее? Распечатайте диплом "Кубка Яндекса".
  2. Морфологический анализатор. Изучите опции и формат выходной информации морфологического анализатора mystem. Поэкспериментируйте с разными текстами: литературные/технические; русский/английский; Радищев/Пелевин. Как обрабатываются ошибки/опечатки? Как обрабатываются незнакомыве слова? Приведите примеры грамматической омонимии. Вычислите степень неоднозначности разбора на небольшом тексте (100-200 слов) - отношение разборы/слова. Предложите методы разрешения неоднозначностей.
  3. Частотный словарь. Написать программу составления частотного словаря текста. Замерить производительность программы на тексте Л.Н. Толстого "Война и мир". Составить три типа частотных словарей для текста: 1) как есть; 2) после удаления стоп-слов; 3) после обработки морфологическим анализатором. Подобрать функцию для зависимости частоты слова от ранга (закон Ципфа). Нарисовать графики: 1) рост словаря в зависимости от длины текста; 2) частота слова в зависимости от ранга.
  4. Бинарная классификация с помощью SVM. Ознакомиться с описанием реализации SVMlight. Ознакомиться с описанием примера 1. Построить классификатор на основе данных, провести тестирование. Редактировать данные: сократить число положиетельных примеров и т.п. Подготовить данные базы спама в формате SVM. Разделить данные на обучающее и тестовое множество. Построить и протестировать классификатор. (Программы и данные можно получить на практическом занятии.)
  5. Машинный перевод. Сравнить качесто двух-трех систем машинного перевода из списка: ПРОМТ, SYSTRAN, Babel Fish, Free Translation, ЭТАП. Сравните разультаты перевода художественных, технических, газетных тестов, личных электронных писем. Сравните результат работы автомата с переводом, выполненным человеком (например, инструкции, художественные тексты).
  6. Кластер-анализ. Для кластеризации используется набор данных, описанный в [Браславский 2002]. (NB: Там этот набор использовался для обучения, в данном случае мы не используем знание о структуре классов, а пытаемся разбить множество объектов на кластеры похожих, т.е. переменную GENRE в анализе не используем!) Использовать раздел программы STATISTICA: Statistics/Multivariate Exploratory Techniques/Cluster Analysis. Поэкспериментировать с разыными методами (K-means, Tree Clustering), для Tree Clustering - с разными схемами (Single Linkage, Complete Linkage, Unweighted pair-group average), используйте знание о целевом кол-ве кластеров - 4. Сравните результаты с эталонным разбиением (используйте значение переменной GENRE).

Задания для лабораторных работ (второй полусеместр)

  1. Тематическая кластеризация документов (классификация без учителя).
  2. Тематическая категоризация документов (классификация с учителем).
  3. Выделение устойчивых словосочетаний из корпуса текстов (разные методы).
  4. Статистические методы снятия грамматической омонимии (метод, основанный на цепях Маркова).
  5. Автоматическое составление двуязычного словаря на основе анализа параллельных текстов.
  6. Макетная система машинного перевода.
  7. Преобразование ЕЯ-вопроса в запрос к машине поиска интернета.
  8. ЕЯ-интерфейс к базе данных.
  9. Автоматическое реферирование (выделение наиболее информативных предложений текста).
  10. Выделение синонимичных слов на основе анализа корпуса текстов.
  11. Выделение родовидовых отношений между словами на основе анализа корпуса текстов.
  12. Выделение терминов из корпуса научных / технических документов.
  13. Поиск дубликатов и "почти дубликатов" в большом текстовом массиве.
  14. Определение "консистентности" текста ("неконсистентный" текст - составленный из разных фрагментов или написанный несколькими людьми).
  15. Извлечение фактов определенного вида из корпуса текстов.
  16. Текствый ввод для сотового (aka T9).
  17. Фильтрация спама.

 

П.И.Браславский
e-mail: pb(at)imach(dot)uran(dot)ru

Адрес этого документа: http://www.kansas.ru/ai2006/index.html