Управление данными и информационные системы

Научный семинар отдела Информационных систем Института системного программирования им. В.П. Иванникова РАН

Archive for the ‘Аннотации’ Category

Извлечение информации из Веб. Подход Wrapper Induction (25.02.14)

Интернет — повседневный источник самых разнообразных данных для множества людей уже многие годы. Поиск товаров и услуг, анализ отзывов на них — эти и многие другие варианты использования интернета могут быть автоматизированы. Однако, несмотря на то, что большая часть данных в интернете представлена в виде HTML разметки, это мало помогает автоматическому извлечению семантики. HTML веб-страниц написан таким образом, чтобы размещенная на ней информация была легко доступна человеку, но она не является машинно-читаемой. HTML — язык разметки, но не язык описания семантики. С начала 2000-х годов консорциумом WWW разрабатываются стандарты так называемого Semantic Web, однако они не нашли существенного применения на практике. Задача извлечения информации из Веб продолжает оставаться актуальной.

В докладе будет сделан обзор одного из подходов к автоматическому извлечению информации из Интернета: Wrapper Induction. Будут рассмотрены как классические, так и современные системы.

Докладчик: Ярослав Недумов

Презентация (pdf)

  • Chang, C.-H., Mohammed Kayed, R. Girgis, и Khaled F. Shaalan. «A survey of web information extraction systems». Knowledge and Data Engineering, IEEE Transactions on 18, № 10 (2006 г.): 1411–1428.
  • Ferrara, Emilio, Pasquale De Meo, Giacomo Fiumara, и Robert Baumgartner. «Web data extraction, applications and techniques: a survey». arXiv preprint arXiv:1207.0246 (2012 г.). http://arxiv.org/abs/1207.0246.
  • Furche, Tim, Georg Gottlob, Giovanni Grasso, Omer Gunes, Xiaoanan Guo, Andrey Kravchenko, Giorgio Orsi, Christian Schallhart, Andrew Sellers, and Cheng Wang. 2012. “DIADEM: Domain-Centric, Intelligent, Automated Data Extraction Methodology.” In Proceedings of the 21st International Conference Companion on World Wide Web, 267–70. http://dl.acm.org/citation.cfm?id=2188025.
  • Crescenzi, Valter, Giansalvatore Mecca, and Paolo Merialdo. 2001. “Roadrunner: Towards Automatic Data Extraction from Large Web Sites.” In VLDB, 1:109–18. http://www.vldb.org/conf/2001/P109.pdf.
  • Kushmerick, Nicholas. 1997. “Wrapper Induction for Information Extraction”. University of Washington. http://www.icst.pku.edu.cn/course/mining/11-12spring/%E5%8F%82%E8%80%83%E6%96%87%E7%8C%AE/10-01%20Wrapper%20Induction%20for%20Information%20Extraction.pdf.
  • Muslea, Ion, Steve Minton, and Craig Knoblock. 1998. “Stalker: Learning Extraction Rules for Semistructured, Web-Based Information Sources.” In Proceedings of AAAI-98 Workshop on AI and Information Integration, 74–81. http://www.aaai.org/Papers/Workshops/1998/WS-98-14/WS98-14-011.pdf.
  • Dalvi, Nilesh, Ashwin Machanavajjhala, and Bo Pang. 2012. “An Analysis of Structured Data on the Web.” Proceedings of the VLDB Endowment 5 (7): 680–91.

Ускорение тематических моделей (18.02.14)

Будет произведён обзор тематической модели PLSA , рассмотрен генеративный
процесс и метод восстановления параметров на основе EM алгоритма. Рассмотренны
два метода ускорения работы PLSA: за счет аппроксимации с незначительной
потерей качества и за счёт выбора начального приближения без потери
качества.

Докладчик: Илья Козлов

Презентация (pdf)

Зачет (24.12.2013, 18:00, 110 каб.)

Зачет для всех курсов начнется завтра, во вторник, 24 декабря, в 18:00. Обратите внимание, время начала сдвинуто на час раньше!

Регламент зачета следующий:

  1. выступления 3 курса,
  2. выступления 4 курса,
  3. выступления 5 курса,
  4. проставление зачетов тем, кто их заработал.

Формат выступлений был описан ранее.

Консультация (17.12.2013)

Сегодня вместо доклада будет консультация перед зачетом. Если у вас есть вопросы, как готовить презентацию результатов работы в семестре, вы можете сегодня их обсудить.

Допуск к зачету

Для допуска к зачету необходимо подготовить краткую презентацию (около 5-7 минут) результатов работы в семестре.

Из презентации должно быть понятно (в скобках указаны соответствующие части текста курсовой/диплома):

  1. Что конкретно планируется достичь в результате выполнения работы и почему это важно? (Примерно введение + постановка).
  2. Что уже сделано в этой области? (Обзор).
  3. Как планируется решать задачу? (Исследование и построение решения).
  4. Был ли реализован прототип и что он показал? (Описание практической части).

Прогресс (или отсутствие оного) по каждому из направлений (постановка задачи, обзор, исследование, программирование) в течение семестра должен быть явно обозначен.

Для всех допущенных студентов критерии получения зачета определяются научным руководителем (и самое время их прояснить, если вы этого еще не сделали).

Методы решения задачи исследования/использования (02.12.13)

В задачах «обучения с подкреплением» часто возникает необходимость соблюдать баланс между исследованием и использованием  (exploration vs. exploitation trade-off). Здесь исследование — это получение новых знаний о мире путем выполнения действий, которые могут оказаться неоптимальными с точки зрения общего результата, а эксплуатация — выполнение действий, которые являются наилучшими с точки зрения знаний, имеющихся на данный момент. Баланс исследования/использования особенно подробно изучен в задачах о конечных марковских процессах (Markov decision process, MDP) и о многоруком бандите (multi-armed bandit).

В формулировке задачи многорукого бандита за одно действие агент среды может выбирать из конечного множества альтернатив, получая за действие заранее неизвестную награду (reward). Распределение наград среди альтернатив («ручек» бандита) заранее неизвестно. Цель агента — получить как можно большую награду в результате своих действий.

Один из примеров применения задачи исследования/использования — задача показа баннеров рекламы, в которой среди рекламных баннеров нужно выбрать для показа баннер с максимальным CTR (click-through ratio).

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

Докладчик: Татьяна Борисова

Презентация (pdf)

Distance-dependent Chinese Restaurant Process (26.11.13)

Так называемые непараметрические байесовские методы представляют из себя элегантный метод решения проблем контроля сложности и подбора структурных параметров для вероятностных моделей в машинном обучении. Часто применяемые непараметрические распределения вроде процесса Дирихле или процесса индийского буфета предполагают, что моделируемые данные являются симметрично зависимыми (англ. exchangeable), то есть, что порядок, в котором они обрабатываются, не имеет значения. Тем не менее, во многих приложениях, например, в анализе изображений или текстов на естественном языке, данные, как правило, имеют внутренние
зависимости, использование которых может значительно улучшить качество получаемых результатов. ddCRP — относительно новый непараметрический процесс, обобщающий широко применяемый процесс китайского ресторана и позволяющий учитывать произвольные зависимости в данных. В докладе будет подробно рассмотрен ddCRP, различные его свойства, включая недавно открытые и пока не опубликованные, а также возможные приложения.

Докладчик: Сергей Бартунов.

Вычислительная геномика. Задачи. (19.11.13)

Вычислительная геномика — сфера исследований, опирающихся на применение методов вычислительного и статистического анализа для извлечения биологически значимого знания из результатов расшифровки фрагментов генома (цепей ДНК) и связанных с ним молекулярных структур клетки. В настоящее время, когда в биологии накоплена информация о расшифрованных геномах для совершенно разных организмов, по-настоящему актуальным становится вопрос об алгоритмах для автоматического анализа этой информации: в силу больших объёмов данных ручной анализ здесь невозможен. В рамках данного доклада будут рассмотрены некоторые из задач данной сферы исследований, которые наиболее близки тематике семинара.

Докладчик: Илья Филоненко