поразительная ватка

раз два три

November 19, 2013 at 10:54pm
0 notes

Обзор работ по непараметрическим методам в машинном обучении

Есть такая неприятная повинность для аспирантов РАН - писать рефераты по истории и философии науки. К счастью, дозволяется (даже требуется), чтобы тема этих рефератов была связана с темой диссера. 

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

Знающие люди одобрили и призвали к распространению, так что распространяю.

December 13, 2012 at 4:46pm
1 note

Setting up GPU cluster instance on Amazon EC2 for a little play with Theano

Hi there! I’m writing this post in English with hope that it would be useful for many people which are just like me getting trouble with their first steps on Amazon GPU instances.

The final goal of this text is to set up everything for playing with Theano. So let’s begin.

You should start from launching new amazon ec2 gpu cluster instance. Personally I preffered to choose Ubuntu 11.10 server for cloud instances AMI because I’m more famailiar with Ubuntu then any linux distributive. An important detail is that CUDA currently supports only ubuntu 11.10, so do not choose fresher distributive, otherwise you may get something wrong.

Now do some standard things to update your system:

sudo apt-get update
sudo apt-get upgrade
sudo apt-get dist-upgrade

Probably you need to reboot after that.

Now install all prequisites for theano:

sudo apt-get install python-dev python-setuptools libblas-dev liblapack3gf-dev gfortran g++

I’m writing this from my memory, so I could make a mistake. Hope you’re mature enough to fix everything at this point :)

In order to get mmmaximum perforance you may also download and install GotoBLAS2 library. Probably you will face bug in the makefile. It could be fixed this way.

After that do

sudo easy_install pip
pip install ipython nose numpy scipy theano

Yes, we do install them by pip, not by easy_install because not everything is ok in python world and easy_install makes some buggy installations (many thanks to Fred and Pascal from theano mailing list for pointing on that).

Now we should have been reached an important checkpoint. Let’s verify that numpy was installed with support of blas, lapack and atlas:

python
import numpy.distutils.system_info as sysinfo
sysinfo.get_info('atlas')
sysinfo.get_info('blas')
sysinfo.get_info('lapack')

It’s important because otherwise numpy and scipy would be really slow and that means our deep learning may never end.

Hope everything is ok up to now. So you may run theano-test and check your RSS or whatever while theano tests itself. 

Now let’s fuck deal with CUDA. Download cuda toolkit 5.0 from nvidia website:

wget http://developer.download.nvidia.com/compute/cuda/5_0/rel-update-1/installers/cuda_5.0.35_linux_64_ubuntu11.10-1.run
chmod a+x cuda_5.0.35_linux_64_ubuntu11.10-1.run
./cuda_5.0.35_linux_64_ubuntu11.10-1.run --verbose

Sad news dude, driver installation failed, right? Thanks to “—verbose” option, we know why. So install kernel headers:

sudo apt-get install linux-headers-`uname -r`

This installs headers for exactly your version of kernel as suggested by this thread.

Unfortunately this is not enough to install CUDA samples, because them require libglut

sudo apt-get install freeglut3 freeglut3-dev

Don’t know how about you, but personally I’m really tired after that. So let’s finish this story with last two things: getting running driver (reboot may be required) and setting up environment variables (don’t be scared by previous version of cuda, it’s still the same for cuda 5).

Last sanity check is:

cd ~/NVIDIA_CUDA-5.0_Samples/1_Utilities/deviceQuery
make
./deviceQuery

It must show that you have two GPUs and so you’re very cool. The latter also can be proven by this benchmark:

THEANO_FLAGS=floatX=float32,device=gpu0 python /usr/local/lib/python2.7/dist-packages/theano/misc/check_blas.py

That’s all folks! I’ll keep posting on playing with theano.

October 7, 2012 at 6:08pm
0 notes

Видео с нашего внутреннего семинара про Latent Dirichlet Allocation. Собственно, не обошлось без легкой кривизны вследствие моей неопытности и волнения, но в комментариях к видео я постарался привести список опечаток. На всякий случай пусть он будет и здесь:

  1. Постоянное повторение фразы “условно независимы при известном z” вместо “независимы при известном z”
  2. На слайде с accuracy не поместился второй график, на котором бинарный классификатор-таки переобучился. Этот слайд взят из оригинальной статьи Blei et. al. 2003
  3. Не совсем внятное объяснение про теорему Де Финетти и симметричную зависимость. Вот более лучшее объяснение: пусть нам известна большая часть слов в документе, и эти слова относятся к теме “футбол”. Тогда компонента футбола в тета по значению превышает остальные компоненты и, следовательно, оставшиеся слова в документе вероятнее всего относятся к футболу.
  4. Неправильная картинка с графической моделью (исправлено в слайдах)

Что я могу еще сказать? Я выкладываю это видео в интернет исключительно для студентов, которые только-только начали разбираться со всеми этими байесовскими вещами, откуда-то услышали про LDA, ничего не поняли, испугались и забили. Конечно, никакой это не туториал, тут есть неприятные формулы и вообще обсуждение довольно неприятных вещей. Но на мой взгляд для тех студентов, которые не просто расширяют кругозор, а стремятся понять тему на уровне, достаточном хотя бы для реализации, это как раз то, что нужно. За вычетом ошибок и невнятностей.

Презентацию вместе с теховскими исходниками можно скачать здесь: https://www.sharelatex.com/project/50656f68e22a75b14201ba76

September 3, 2012 at 5:03pm
0 notes

Machine Learning Summer School - Sample from poster sessions

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

Что тут сказать - уровень очень разный, в частности есть в наличии работы, опубликованные на AAAI, так что хотя бы ради интереса посмотреть стоит. Ну и немножечко треша, он бывает не только на конференции Ломоносов.

Read More

August 20, 2012 at 4:56pm
0 notes

SIGKDD 2012 - второй день

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

Итак, второй день начался с очень классного доклада самого Майкла Джордана (нет, не баскетболиста) про принцип “разделяй и властвуй” в обработке больших данных. Да, стоит заметить, что на конференции царила обстановка легкой истерии вокруг БОЛЬШИХ ДАННЫХ и ГЕТЕРОГЕННЫХ СОЦИАЛЬНЫХ СЕТЕЙ. Тем не менее, доклад Джордана был, возможно, наименее истеричным и наиболее теоритическим среди всех прочих приглашенных. 

Первая часть была про бутстреппинг и проблемы с ним. Проблемы, насколько я понял, заключаются в следующем: раз уж мы работаем с большими данными, то и выборки (сэмплы) основной выборки (датасета) получаются немаленькими, а сгенерировать и обработать таких подвыборок нужно очень много для уверенности в результатах. Для преодоления этих трудностей Джордан с коллегами предложил модель с говорящим названием Bag of Little Bootstraps, которая требует генерации сильно меньших по размеру выборок (сэмплов), считает на них то, что нам нужно, и правильным образом усредняет с доказательствами своей правоты. 

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

Например, если эта матрица представляет из себя что-то осмысленное, значит, скорее всего у неё низкий ранг. Ну, интуитивно это можно понять так - раз матрица осмысленная, значит имеет структуру, а структура это ейный базис, через который её строчки/столбцы выражаются, а базис обычно невелик. Таким образом, самое тупое, что можно предложить, это заполнить пустые места так, чтобы ранк получившийся матрицы был как можно меньше. Спорно, но для начала сойдет.

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

Ну и, собственно, вклад Джордана с коллегами заключался в универсальной процедуре (универсальной - в смысле работающей с любым (?) алгоритмом дополнения матриц) по распараллеливанию этого дела, гарантирующей адекватный результат. То есть, разбиваем матрицу на подматрицы, дополняем их независимо, потом совмещаем, если вкрайце. Очевидно, сложность здесь представляет теоритическое обоснование происходящего.

В третьей же части доклада рассказывалось про всякие непараметрические штуки и про dp-means в частности, о котором я уже писал.

Вдохновленный докладом Джордана я далее проследовал на секцию Community Mining, однако мне там совершенно не понравилось. Существует 100500 алгоритмов по поиску сообществ и еще 100500 так или иначе связанных с этим работ, вопрос в том, какие из них действительно проливают свет на то, как устроены эти несчастные социальные графы, или еще что, а изучение свойств чего-то, что мы априорно предположили сообществом, и обмусоливанеи этого всего без четких и ясных приложений, я не интересным не нахожу.

Поэтому оттуда я свалил на рекомендацию и персонализацию. Из того, что хотелось бы отметить, работа “Playlist Prediction via Metric Embedding" про обучение виртуального dj на основе плейлистов, составленных живыми dj’ями. Помимо того, что сама постановка задачи меня очень прикалывает (есть, где применить, если вы понимаете о чем я), все это было еще очень хорошо сделано. 

Тут следует подчеркнуть, что просто порекомендовать какие песни бы еще послушать, и сгенерировать плейлист, это все-таки не одно и то же, что авторы и подчеркивают. Потому как плейлист - это направленный последовательный поток композиций. То есть, важен порядок следствия и последовательность проигрывания. Авторы предложили для этого свою хитрую марковскую модель, поэксперементировали с дополнительными фичами вроде тегов с ласт.фм и т.п. и получили вполне адекватные результаты; ну, если посмотреть на метрическое (?) пространство песен/артистов, которое потом получилось. Так сказать, человеческие ожидания подтвердились.

После я решил быстренько проспать очередное кококо про БОЛЬШИЕ ДАННЫЕ и ГЕТЕРОГЕННЫЕ СОЦИАЛЬНЫЕ СЕТИ, но вместе с ним проспал еще и секцию, на которую хотел сходить, о чем сожалею и проклинаю будильник, который меня и подвел. Тем не менее, для прочтения я рекомендую еще “Discovering Value from Community Activity on Focused Question Answering Sites: A Case Study of Stack Overflow”. Удивительно, что люди еще не разорвали на части stackoverflow, который столь любезно открыл свои данные. Сам я весьма заинтересовал в его скорейшем разрывании, так что если кто-то тоже хочет, то давайте вместе его драконить. А вторая статья, которую я даже толком еще и не прочел, “Random Forests for Metric Learning with Implicit Pairwise Position Dependence”, но в ней, кажется, сделали то, что я хотел сделать.

До пятницы обязуюсь написать про третий, заключительный день KDD, ибо в пятницу я улетаю на 21-ую летнюю школу по машинному обучению в Киото, и дальше писать буду уже про неё.

August 15, 2012 at 6:33am
0 notes

SIGKDD 2012 - первый день

Ну, собственно, после дня воркшопов началась основная часть конференции. После т.н. континентального завтрака мы слушали речь основателя и CEO Bauidu, в котором он предлагал присутствующим в зале решить не то 8, не то 10 задач, которые они пока в Bauidu (да и не только) решить не могут. Во-первых, было бы хорошо распознавать текст на изображениях и уметь потом по нему искать, к тому же местный китайский аналог flickr’а поставляет их в таком темпе, что через год картинок в китайских интернетах будет больше чем веб-страниц, а это что-то да означает. Во-вторых, улучшить распознавание речи на смартфонах и вывести его на принципиально новый диалоговый уровень, то бишь, прокачать сири, которого у них в китае и так пока нет.

Далее был рассказ про очень занятную фишку Bauidu как поисковика под названием box computing. Я не то чтобы очень понял, о чем идет речь, но в частности box computing это такой специальный интерфейс, предоставляемый baidu всем желающим (?) для индексирования и последующего поиска предоставленных структурированных данных, грубо говоря, через то же окошко поиска, что и все остальное. Очень круто, я считаю. А вообще же box computing это про встраивание каких бы то ни было данных/приложений вот прямо в baidu, чтобы все утекло в ихнее китайское облако и взаимодействывало с пользователями, будучи не более кастомной “коробкой” на странице с поиском.

Другой интересной задачей (из запомнившихся) было придумать, как же-таки зарабатывать владельцам социальных сетей. Он же, Робин Ли, сам не знает, то ли заставлять платить за подписку, то ли показывать рекламу. Но проблема в том, что люди сидят в соц. сетях с целью поразвлечься, и поэтому реклама им не так интересна, как тем, кто ищет в гугле. Я читал похожих проблемах СУПа после покупки ЖЖ, так что вполне возможно.

Далее я сходил на секцию по вероятностным моделям. Из запомнившихся докладов для себя отметил “Multi-View Clustering Using Mixture Models in Subspace Projections”. Идея этой работы для меня очень близка и полезна: пусть у нас есть многомерные данные, которые могут при проекции на разные подмножества измерений, давать разные и потенциальные осмысленные разбиения, тогда хорошо бы научиться разделять интересные подпространства от неинтересных и зашумленных. 

Остальные работы были все дружно про LDA, где-то про очередной агрейженный inference, где-то про более наличествующий учет контекста документов (типа, статья + авторы, если речь идет о научных статьях), где-то про вычисление вероятности перехода от одного топика к другому в твиттере. 

Касательно Practical Collapsed Variational Bayes Inference for Hierarchical Dirichlet Process я мало чего понял, т.к. для меня все это пока еще ну не то чтобы темный лес, но и не ясная поляна, надо бы на месяцок как-нибудь плотно во все это закопаться. У них там какой-то свой кружок, где все соревнуется, кто точнее, кто быстрее.

Учет контекста же, по мнению авторов The Contextual Focused Topic Model, нужен для того, чтобы получить более сфокусированные топики у документов. То есть, нам не нужны документы обо всем по-немножку, нам нужны жирные вероятности у нормальных топиков и околонулевые у остальных. Справедливо, товарищи. 

Паренек же с твиттером (TM-LDA: Efficient Online Modeling of Latent Topic Transitions in Social Media) наглядно показал в своих полугодовых экспериментах всякие там забавные вещи, что люди когда видят аварию сначала пишут, какой ужас, а потом ругают правительство, ну или что по праздникам люди в основном про одно и то же пишут и т.д.

Далее же я ходил на секции про матрицы, т.к. остальное показось мне либо неинтересным, либо печальным кококо. Презентации про матрицы оказались очень ядреными, я не все везде понимал. Но, в частности, благодаря GigaTensor: Scaling Tensor Analysis Up By 100 Times - Algorithms and Discoveries я узнал об аналоге SVD для тензоров, а также из статьи Fast Bregman Divergence NMF using Taylor Expansion and Coordinate Descent про то, что Bregman Divergence это общий случай очень много чего, например, нормы Фробениуса и KL-дивергенции. Статья Active Learning for Online Bayesian Matrix Factorization также показалась мне очень интересной, она была про то, как делать разложение матрицы в олнайне, не имея возможности обозревать всю матрицу, в данном случае для задачи коллаборативной фильтрации через факторный анализ. В статье очень многое умешано, мне определенно следует её почитать по-подробнее. Из того, что запомнилось - для определения следующего куска обозреваемой информации предлагалось выбирать кусок, котоырй будет наиболее информативен относительно неизвестных пока данных в терминах mutual information,а это функция, значить-с, субмодулярная, поэтому согласно известному прикольному факту можно жадным алгоритмом её максимизировать с $(1-1/e)$-точностью.

August 12, 2012 at 6:04pm
0 notes

SIGKDD 2012 - Немного про воркшоп по социальным сетям

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

Сегодня вообще день воркшопов и туториалов. И, если честно, туториалы круче воркшопов, и не пошел я на них только потому что решил, что это будет непатриотично по отношению к собственному воркшопу, но судя по всему напрасно. Очень хотелось послушать про матричные и тензорные разложения, но теперь придется ждать, пока это все появится на videolectures.net.

На нашем же воркшопе из того, что я слышал, меня вштырил только один пока доклад, содержащий в соавторах небезызвестного Лесковца (теперь, когда в dute free я натыкаюсь на виски Jure, я сразу вспоминаю Лесковца). Помимо зайчаток очередного многообещающего алгоритма поиска сообществ, двумя стенфордскими товарищами был обнародован факт, что сообщества пересекаются плотно, а не разреженно, и что вероятность быть друзьями, имея k общих сообществ, очень быстро растет вместе с k.

Любопытно, что в качестве ground truth они брали сообщества в ЖЖ. Лично я пока не понял, хорошо ли так жить, ведь в эти сообщества люди вступают исключительно по интересам, а не с целью продолжить оффлайн-знакомство в интернете. Наверное, все-таки нехорошо.

Еще было два приглашенных доклада, кстати, довольно интересных. Первый делал дядя из местного Microsoft Research, рассказывал о своем видении БУДУЩЕГО СОЦИАЛЬНЫХ СЕТЕЙ, заключаюгося во всеобщем entity resolution, чтобы был один большой социальный граф, в котором оседала бы информация из всех остальных. (Что весьма кореллирует с нашей работой) Показывал демку какого-то из под-сервисов bing’а, где можно ответив на 20 вопросов найти нужного человека. Еще поднимал острую (наверное, исключительно для меня) тему - о недостаточности, например, одного только машинного обучения и одного только экспертного знания и необходимости объединения их вместе, а именно чтобы у нас был сплошной краудсорсинг, где толпа бы помогала дата майнингу, а он толпе (типа, симбиоз человека и машины), и всем было бы счастье. Как это было связано со всем прочим, я не очень понял, потмоу что как был того-с.

Второй доклад делал Кристос Фалустос, веселый и быстроговорящий на испанском английском дядя, поедающий собак по теме распространения информации и влияния в сетях. Кристос и его чудесные студенты с аспирантами брали различные модели, которые нам преподносили через эпидемиологические либо маркетинговые метафоры, и смотрели, при каких параметрах все погибают, а при каких нет. Параметрами могут быть вероятность чихнуть, вероятность заразиться, вылечиться, заболеть повторно и т.д. Оказалось, что для любого графа существует предельный набор параметров, грубо говоря, до достижения которого сообщество выживает, а после случается фазовый переход и все дохнут. Ну и был предложен соответствующий коэффициент, определяющий эту критическую точку, который считается по параметрам вируса и, внезапно, по наибольшему собственному значению матрицы смежности. В который раз убеждаюсь, что собственные значения это чуть ли не САМАЯ СУТЬ всего сущего.

На постерной сессии порадовал парень, который представлял свою довольно примитивную работу (тоже о поиске сообществ, но уже типа по интересам пользователей), где все было примитивно и печально, сам он это очень хорошо понимал и представлял, но знал при этом, куда LDA можно впихнуть, куда индийский буффет и т.д. Чего ж сразу не впихнул, интересно.

Я же лично выступил довольно так себе, наверное, сказалась дикая психологическая усталость от нашей работы и дикая физическая усталость от перелетов, почему-то всюду забывал подчеркивать удивительное и вместо этого объяснял и без того понятное. Радует, что эту нашу статью пригласили в специальный выпуск ACM TIST по социальным сетям, будет у меня теперь журнальная статья, но не очень радует то, что снова надо будет во все это погружаться.

Особо ни с кем почему-то не пообщался, только с одним уже почти экс-ассистентом с мехмата, который переезжает в Эмираты с женой. На обед давали много всего, но мясо (главное для меня) было каким-то невнятным, а в качестве напитков была только вода, кола и спрайт. Вроде как все.

Вывод как всегда очень простой - учиться-учиться-учиться и лечить нервную систему.

June 26, 2012 at 4:54pm
0 notes

dp-means - k-means с неизвестным числом кластеров

Есть такая проблема с очень попуялрным алгоритмом k-means - требуется знать заранее число кластеров. Об это много копий сломано, но вот на ICML приняли статью, в которой “переизобрели” алгоритм, названный dp-means (от dirichet process, видимо). Суть сего алгоритма формулируется в одном предложении: делаем обычные итерации как в k-means, но если минимальное расстояние от очередного объекта до кластеров превышает некоторый порог $\lambda$ (это я MathJax в тумблер прикрутил и решил попробовать), то выделить ему новый кластер.

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

January 6, 2012 at 4:30pm
0 notes
Аня подарила муравьиную матку (Taken with instagram)

Аня подарила муравьиную матку (Taken with instagram)

July 25, 2011 at 12:17pm
0 notes

Lateen EM: Unsupervised Training with Multiple Objectives, Applied to Dependency Grammar Induction →