Sunday, August 25, 2013

ReVerb: Open Information Extraction


Предыдущий пост о семантических связях между словами представил открытый инструмент word2vec, позволяющий строить или выявлять в некотором смысле семантические сети слов и словосочетаний.

В этом посте мы рассмотрим систему, выявляющую связи между запросом и документами по тройке: Объект1-Связь-Объект2, где объекты {Объект1, Объект2} представлены в виде существительного либо семантического класса существительного, Связь -- в виде глагола или падежного типа.

Система называется ReVerb (от Relataion=связь, Verb=глагол). Её исходный код доступен на github. Система поддерживает только английский язык.
С попыткой представить знание в виде приведённых троек можно встретиться довольно часто где (например, этот подход упоминался в докладе Gerhard Weikum на RuSSIR'2011). Первое впечатление от такого подхода: слишком узкий взгляд на семантику и что ничего путного с этим не сделать. Однако это не совсем так. Часто перед решением задачи компьютерной лингвистики (будь то машинный перевод, анализ тональности или информационный поиск) нужно сделать первые шаги в изучении имеющихся данных. Эти шаги могут включать построение частотных таблиц слов или словосочетаний (N-грамм), выявление ключевых слов, представляющих документ и т.д. Кстати, многие начальные шаги можно оптимально сделать при помощи инструментов Linux, таких как cat, cut, grep, awk, sed, wc (от word count, а не то, что можно подумать) и других. Таким образом, воспользовавшись существующими инструментами обработки текста, можно решить начальные задачи, даже не написав строчки кода!

Демонстрация системы извлечения знаний из 500 млн веб-страниц находится здесь. Что в ней примечательного?
Например, можно получить список стран Африки, задав запрос:

Argument1: type:Country
Relation: is located in
Argument2: Africa

Система выводит список из 45 государств, видимо тех, о которых что-то публикуется в Сети (вообще, официально признанных суверенных государств в Африке 54, согласно Википедии).
Можно задавать общие вопросы: например, какие актёры играли в каких фильмах:

Argument1: what/who
Relation: starred in
Argument2: what/who

Например, Barbra Streisand снималась в фильме "Yentl", Jessica Alba в "Sin City", а Johny Depp в "Pirates of the Caribbean".
Воспользовавшись падежной связкой "symbol of", мы получаем список символов разных стран.

Argument1: what/who
Relation: symbol of
Argument2: type:Country

У Шотландии -- это единорог.

Индексировать и искать документы с мета-информацией можно, например, при помощи Apache Solr. Но это уже отдельная история.

Машинное обучение без учителя для определения смысла слов: open source инструмент от Google word2vec

Кросспост моего поста с http://mathlingvo.ru/

В блоге Google Open Source Blog появилось сообщение о новом open source инструменте word2vec. Исследователи Google утверждают, что при его помощи можно получить смысл слов, лишь прочитав огромные массивы данных. Инструмент применяет "распределённые представления" текстовых данных для обнаружения связей между концептами -- и всё это при помощи машинного обучения без учителя (unsupervised machine learning) на основе нейронных сетей (neural networks).
Интересно, что модель помещает близкие страны рядом, как и близкие столицы. Похожие связи возникают автоматически во время тренировки алгоритма.
У исходного кода хорошая лицензия: Apache License 2.0, которая позволяет менять его без опубликования изменений и встраивать его в том числе в коммерческие приложения.
В статье также упоминается ставший популярным в последнее время метод Deep Learning, дающий результаты, лучшие на порядок предыдущих методов. Кстати, большинство победителей конкурсов по машинному обучению на kaggle (ваш покорный слуга также имел честь участвовать) применяет либо ансамбли методов на Decision Trees, либо методы Deep Learning.
// ./demo_word.sh
Enter word or sentence (EXIT to break): machine translation

Word: machine  Position in vocabulary: 799

Word: translation  Position in vocabulary: 1206

          Word       Cosine distance
------------------------------------------------------------------------
          mmix              0.485542
    translator              0.484659
          msil              0.483476
        manual              0.479708
        turing              0.462978
  introduction              0.458771
      readable              0.449272
    unabridged              0.448343
      machines              0.447570
       rosetta              0.443270
      compiler              0.438949
    dictionary              0.437040
  translations              0.436334
    translated              0.429008
 specification              0.422286
    typewriter              0.422246
           awk              0.420415
       version              0.417623
   interpreter              0.415583
        itrans              0.414944
         tools              0.413505
     annotated              0.413150
        lincos              0.411448
      abridged              0.411152
          text              0.407197
      language              0.404664
        freedb              0.403896
       vulgate              0.402863
         xpath              0.401687
    calculator              0.397689
        enigma              0.394239
       klingon              0.394041
       opencyc              0.393687
       systran              0.391636
       multics              0.391623
           kli              0.389196
           apl              0.386948
      editions              0.383799
        skybox              0.383791
         algol              0.383730
Enter word or sentence (EXIT to break): weather

Word: weather  Position in vocabulary: 2693

          Word       Cosine distance
------------------------------------------------------------------------
          warm              0.634004
      humidity              0.611526
         humid              0.605240
       summers              0.594220
 thunderstorms              0.591256
      snowfall              0.590065
 precipitation              0.582246
       climate              0.580110
       winters              0.577238
      rainfall              0.570583
         rainy              0.566492
below_freezing              0.566140
  rainy_season              0.561857
        cooler              0.558795
         winds              0.558283
        colder              0.557494
  cold_winters              0.545980
           wet              0.545650
        frosts              0.539969
         drier              0.539645
      climatic              0.537766
        warmer              0.535417
        winter              0.532653
  warm_summers              0.530857
         el_ni              0.530692
  temperatures              0.528191
relative_humidity           0.527605
        summer              0.527042
  mild_winters              0.526249
       monsoon              0.524260
   trade_winds              0.523211
       daytime              0.523093
      seasonal              0.520377
           dry              0.519703
    hurricanes              0.517527
     subarctic              0.514771
    visibility              0.514740
     snowfalls              0.513660
     monsoonal              0.513538
   hot_summers              0.513050

Saturday, August 17, 2013

What is it like to study mathematics at Saint Petersburg State University? (my answer on quora.com)

As it turns out, not all of my readers are on quora. So because of this and in the spirit of posting non-technical blogs too, I'm reposting an answer I gave to the question there: "What is it like to study mathematics at Saint Petersburg State University?"




I have studied math and other subjects (like physics, computer science and others) during 2002-2005 in Saint Petersburg State University (SPbU) for a Specialist program (comparable to that of Master's degree).

My experience was constantly comparative in the beginning: as I was advancing further into teaching style of SPbU professors and docents I was viewing it side by side with the style of another State University of my home city (10x smaller in population than Saint Petersburg that time).

So perhaps I can approach answering your question from the perspective of comparison.

1. (a) In my home university we were taught to learn long theorem proofs in the fashion that would enable a student to easily reproduce it on an (pre-)exam. I remember only one occasion, when a theorem was so long that learning all the low-level details was impossible (despite how many days I tried), therefore really deriving the proof was the only option. Of course you would learn the fundamental constructs and apparatus for deriving the proof, that is you wouldn't be doing it completely from scratch and finding your ways into it.

  (b) In SPbU, in contrast, you wouldn't be expected to learn the entire theorem proof at all, but instead be ready to derive it. Some of the practical tasks given along the theoretical proofs would require the same: derive a solution as you go. This was the first thing that struck me as largely different.

2. (a) In my home university I was expected to learn about 80% of definitions, theorem formulations, their proofs.
    (b) It was my first exam on Control Theory in SPbU where its professor told me, a student should learn about 35% (or even less): the _most_ important theorem formulations and their proofs plus the _most_ important definitions. The rest is derivable as explained in (1) (b)

3. (a) The highlight of fun part of studying in my home university that comes to mind was that once a professor of mathematical analysis came to the class and asked: "Do you want theory and tasks today or talk about life?" "Life" was the answer, and the first question from the audience was: "Girls of which country were the most beautiful?".

   (b) In SPbU there have been all sorts of surprises that opened student's mind or made studying more fun. One example: during one of the exams on electrodynamics (complex theory with integral calculus, Lie algebra and so on), a professor said 10 minutes past the start: "The ones who would like to get C mark (3 or "satisfactory" in Russia)" can get it right now without answering their questions. Few people rushed towards him and exited the exam room. About 10 mins later he continued: "The ones who would like to get B mark (4 or "good" in Russia)" can get it now, but you have to show me, what you have written. Some more people rushed towards him. 15 min later (and a few drops of sweat on our brave necks) he said: "The rest just get A's, because you have survived and didn't know in advance what to expect. " (5 or "excellent", the best mark). What I have learnt was that it is not always necessary to be an egg head and learn everything to be always ready to stand up. Sometimes it is important to be a good person, brave and keep courage in your heart. That may lead to more adventures and opportunities in the future!

With a few exceptions I would say, that studying math was both fun and rather instructive in that, it developed some fundamental skills of reasoning and attacking a problem at hand without having trained yourself specifically to solve that class of problems before -- what you need in real life, be it further PhD studies or solving other complex problems, including those occurring in life.