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

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

Author Archive

Расчет семантической близости концепций с использованием связей в графе ссылок Википедии (08.04.14)

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

В связи с ростом популярности использования Википедии как базы знаний для различных приложений обработки текстов и, в частности, для расчёта семантической близости между концепциями, важно как можно более полно использовать содержащуюся в ней информацию о концепциях и связях между ними.

Данный доклад посвящен оценке семантической близости концепций с использованием длины кратчайшего пути между соответствующими им статьями в графе ссылок/категорий Википедии. Учитываются различные типы ссылок между концепциями. Методы на основе кратчайших путей сравниваются с мерой Дайса, используемой в системе Текстерра, как с помощью пар концепций, размеченных экспертными оценками близости, так и in vivo на примере задаче дизамбигуации.

Докладчик: Максим Варламов

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

Обзор современных прикладных методов сжатия данных (01.04.14)

Данный доклад будет посвящён прикладным утилитам для экономии дискового пространства. Речь пойдет о возможностях сжатия blosc, LZ4, LZO, xz(lzma2), ZFS и о способах их использования. Будет рассмотрено применение распространённых средств сжатия данных в контексте разных классов задач. Доклад не будет затрагивать серьёзных теоретических основ методов сжатия данных.

Докладчик: Олег Борисенко

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

Современные методы викификации (25.03.14)

Лексическая многозначность — неотъемлемое свойство естественного языка, заключающееся в том, что слова и словосочетания могут иметь различную смысловую нагрузку в зависимости от окружающего их контекста. В компьютерной лингвистике задача автоматического определения корректных значений слов называется задачей разрешения лексической многозначности (РЛМ). Данная задача является одной из важнейших проблем обработки текстов.
Центральной частью любого современного метода РЛМ является база знаний — источник терминов, их возможных значений (концептов) и связей между ними. В последнее время наибольшее развитие получили методы РЛМ, база знаний которых основана на Википедии — огромном быстрорастущий ресурсе, покрывающем множество предметных областей. В роли концептов в таких базах знаний обычно выступают статьи Википедии, а в роли терминов — текстовые ссылки на них.
Задача поиска терминов в заданном тексте и связывание их с соответствующими статьями Википедии называется задачей викификации. Данная задача имеет такие важные приложения, как семантический поиск, классификация текстов и др.

Докладчик: Денис Федоренко

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

Литература

* Milne D., Witten I. H. Learning to link with wikipedia //Proceedings of the 17th ACM conference on Information and knowledge management. – ACM, 2008. – С. 509-518.
* Ratinov L. et al. Local and global algorithms for disambiguation to wikipedia //Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies-Volume 1. – Association for Computational Linguistics, 2011. – С. 1375-1384.
* Cheng X., Roth D. Relational Inference for Wikification //Urbana. – 2013. – Т. 51. – С. 61801.
* Cai Z. et al. Wikification via link co-occurrence //Proceedings of the 22nd ACM international conference on Conference on information & knowledge management. – ACM, 2013. – С. 1087-1096.

Методы получения репрезентативной выборки пользователей социальной сети (18.03.14)

Для обучения и оценки качества методов анализа социальных сетей требуются данные: информация о пользователях реальных социальных сетей. Данный доклад посвящен одному из аспектов сбора таких данных — сэмплингу.
В рамках доклада будут рассмотрены различные способы получения репрезентативной выборки пользователей социальных сетей, так называемые, методы сэмплинга (англ. sampling). При этом будут освещены как классические подходы (поиск в ширину, случайные блуждания и др.), так и современные методы, которые «налету» используют извлекаемую в процессе скачивания информацию (например, сообщества пользователей) для повышения качества дальнейшего сбора.
От качества получаемой выборки сильно зависит качество алгоритмов, использующих эти данные. Поэтому будут рассмотрены различные критерии, по которым оценивается репрезентативность получаемой выборки пользователей. В конце доклада будет кратко рассказано о фреймворке MODIS Crawler, который предназначен для автоматического сбора данных из Интернета, в частности, из социальных сетей.

Докладчик: Андрей Гомзин

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

Список литературы:

1. Leskovec J., Faloutsos C. Sampling from large graphs //Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery
and data mining. — ACM, 2006. — С. 631-636.
http://www.stat.cmu.edu/~fienberg/Stat36-835/Leskovec-sampling-kdd06.pdf

2. PAKDD 2013 Tutorial: Sampling and Summarization for Social Networks
http://mslab.csie.ntu.edu.tw/tut-pakdd13/

3. Leskovec J., Kleinberg J., Faloutsos C. Graphs over time: densification laws, shrinking diameters and possible explanations
//Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining. — ACM, 2005. — С. 177-187.
http://eprints.pascal-network.org/archive/00001220/01/powergrowth-kdd05.pdf

4. Blenn N. et al. Crawling and detecting community structure in online social networks using local information //NETWORKING 2012. —
Springer Berlin Heidelberg, 2012. — С. 56-67.
http://repository.tudelft.nl/assets/uuid:61624ff0-d637-497a-9bf1-355638b63c7e/Crawling.pdf

Применение тематического моделирования для поиска агентов влияния в социальных сетях (11.03.14)

В рамках доклада планируется познакомить слушателей с тематическим моделированием (модели PLSA и RobustPLSA), с semi-supervised подходами к тематическому моделированию, с иерархическим тематическим моделированием (MASHA).

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

Докладчик: Валерий Аванесов

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

Distributed Generation of Billion-node Social Graphs with Overlapping Community Structure (04.03.14)

In the field of social community detection, it is commonly accepted to utilize graphs with reference community structure for accuracy evaluation. The resulting accuracy value is obtained by directly comparing the ground-truth set of communities with the one produced by the algorithm. Therefore, a generic tool capable of generating random social graphs with realistic community structure and diverse properties is required. As soon as populations of modern social networks reach billion users in size, the tool must be scalable enough to produce synthetic networks of similar scale.

The method for generating large random social graphs with realistic community structure is introduced in the paper. The resulting graphs have several of recently discovered properties of social community structure which run counter to conventional wisdom: dense community overlaps, superlinear growth of number of edges inside a community with its size, and power law distribution of user-community memberships. Further, the method is by-design distributable and showed near-linear scalability in Amazon EC2 cloud using Apache Spark implementation.

Speaker: Kyrylo Chykhradze

presentation (pdf)

Извлечение информации из Веб. Подход 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)

Методы решения задачи исследования/использования (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, различные его свойства, включая недавно открытые и пока не опубликованные, а также возможные приложения.

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