После большого перерыва продолжаем цикл о графических вероятностных моделях (часть 1, часть 2). Сегодня мы наконец-то от постановок задач перейдём к алгоритмам; поговорим мы о самом простом, но часто полезном алгоритме вывода на фактор-графах – алгоритме передачи сообщений. Или, как его ещё можно назвать, алгоритме правильной расстановки скобок.


by sergey-lesiuk

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

С некоторой натяжкой именно так работает вращение с помощью углов Эйлера. Немного непредсказуемо и неудобно, не правда ли? Углы Эйлера имеют несколько недостатков, но есть одно особенно нехорошее свойство из-за которого вы не захотите с ними связываться. Его имя — Gimbal lock.

В русском языке gimbal lock называют по-разному: шарнирный замок, блокировка осей, складывание рамок. К сожалению, по запросам в поисковике с такими ключевыми словами выдаётся много мусора, а статья в Википедии оставляет желать лучшего, поэтому я сам расскажу вам об этом феномене и предложу как с ним бороться.

Внимание! Заходя под кат вы подвергаетесь риску поломать голову.

Большой бедой Узким местом статической типизации являются гетерогенные коллекции и вариадические функции. Поэтому в RPC-библиотеках часто встречается подход, когда входящие данные так и лежат одним ADT-куском, а для методов один такой же плоский тип "[Foo] -> IO Foo", реализации которого копипастят десериализацию/сериализацию, что неудобно и плодит ошибки, в т.ч. рантаймовые.

Решение этой задачи меня беспокоило практически с самого начала практического применения мной хаскеля и, наконец, вчера ночью на меня снизошло вдохновение аж в 6.5 миллиолега и после сеанса гадания на ошибках и беседы с ghci у меня всё получилось.

CMake — это система сборки ПО (точнее генерации файлов управления сборкой), широко используемая с Qt. При создании больших или сложных проектов, выбор CMake будет более предпочтительным, нежели использование qmake. KDE когда-то был переломным моментом в популярности CMake как таковой, после чего свою «лепту» внес Qt 4. В Qt 5 поддержка CMake была значительно улучшена.

Часть 1: Введение
Часть 2: Многопоточность
Часть 3: Рендеринг (Прим. пер. — в процессе перевода)
Часть 4: Doom classic — интеграция (Прим. пер. — в процессе перевода)

Движок для Doom III был написан в период с 2000 по 2004 год, в то время, когда большинство ПК были однопроцессорными. Хотя архитектура движка idTech4 разрабатывалась с учетом поддержки SMP, это закончилось тем, что поддержка многопоточности делалась в последнюю минуту (см. интревью с Джоном Кармаком).

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

Всем привет! Хочу показать общественности свой открытый движок вывода правил (forward chaining) с поддержкой нечеткой логики, под рабочим названием Scala inference engine (sie) (код).

UPD.
Библиотека выложена в центральный репозиторий maven-а:

    <dependency>
        <groupId>net.sf.brunneng.fusie</groupId>
        <artifactId>fusie</artifactId>
    </dependency>

Введение

После продолжительного перерыва мне пришлось вернуться к программированию на C++. После C# очень не хватало ключевого слова var и возможностей построения запросов linq. Однако как оказалось прогресс не стоит на месте и за время моего отсутствия вышла новая версия С++11, имеющая новые интересные возможности, к тому же реализованная в большинстве компиляторов. Я занимался кросс-платформенным проектом и меня интересовали компиляторы GCC для Linux, Visual Studio и mingw для мира Windows. Попытка найти linq-like библиотеку не увенчались успехом, все, что я находил, было нежизнеспособной поделкой на коленке. Смирившись, я бросил поиски, однако в апреле 2012 вышла обнадеживающая статья LINQ to Objects на языке C++, в которой описывалась библиотека, которая мне подходила. Попробовав ее в деле и разобравшись в ее устройстве, я был разочарован неэффективностью, но некоторые идеи я подчерпнул. Оставалось одно – написать такую же, только с блэк-джеком, что я и сделал github.com/drbasic/CppLinq, заодно разобравшись автоматическим выводом типа (auto) и лямбда выражениями.

Проектировалась библиотека так, что бы с помощью fluent-синтаксиса и лямбда выражений пользователь мог построить граф преобразований. Эти графы можно копировать, достраивать, объединять, т.е. реализовать поведение максимально близкое к прообразу Linq to Objects из мира C#. Функционал библиотеки, недолго думая, я позаимствовал из C#, добавив, явный left join и full join. Важным ограничением библиотеки является перемещение по графу преобразования не копий, а указателей на элементы исходной последовательности. Это позволяет эффективно обходиться со сложными элементами коллекций, ведь теперь не происходит накладных расходов на копирование, но исходная последовательность из-за этого не должна быть «виртуальной». Т.е. к началу работы у каждого элемента исходной последовательности должен быть уникальный адрес и элементы не должны перемещаться в памяти во время работы linq-преобразований. В общем, для этого подходят массивы, контейнеры Qt, все стандартные контейнеры, кроме std::bitset. Сложности возникли лишь с константными последовательностями, которые так и не доделал, так как мне они были не особо нужны. Библиотека проверена и успешно компилируется Visual Studio 2010 и 2012, gcc 4.8, mingw 4.8. Проще всего совладать оказалось с компилятором Microsoft, сделать счастливыми gcc было куда сложнее, причем с внутренней ошибкой бывало падали все компиляторы, порой даже без вразумительных криков.

В математике сети дорог (автомобильных и не только) представляются взвешенным графом. Населенные пункты (или перекрестки) — это вершины графа, ребра — дороги, веса ребер — расстояния по этим дорогам.

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

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

Мы не знаем эти правила, однако, работая с дорожными сетями, вполне можно использовать алгоритмы, которые эффективны для графов дорог, хотя и не подходят для графов в универсальном или математическом смысле. Рассмотрим здесь два таких алгоритма.

В предыдущих материалах этого цикла мы рассматривали методы предварительной обработки данных при помощи СУБД. Это может быть полезно при очень больших объемах обрабатываемой информации. В этой статье я продолжу описывать инструменты для интеллектуальной обработки больших объёмов данных, остановившись на использовании Python и Theano.

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

Более полугода назад в поисках что посмотреть, я листал топ произведений. Это занятие повторялось уже много раз и успело надоесть — постоянно приходилось пропускать то, что я смотреть не хочу. Имхонетами раньше не пользовался, да и не доверял им из-за специфики искомых произведений. На сайте, где я производил поиски, была возможность создать свой список просмотренных произведений и выставить оценку, также были доступны оценки других пользователей. Тут мне в голову пришла гениальная идея, как оказалось позднее банальная, — используя оценки других пользователей делать рекомендации. Данная деятельность называется коллаборативной фильтрацией, а программа её реализующая — Рекомендательной системой(РС). Оглядываясь назад я понимаю, что совершил множество ошибок из-за недостатка информации и её труднодоступности в данной тематике, а что самое главное — сильно переоценил РС. В данном посте я сделаю обзор основных типов и алгоритмов РС, а также постараюсь передать часть своих знаний и опыта.

В этом блоге мы уже много о чём поговорили: были краткие описания основных рекомендательных алгоритмов (постановка задачи, user-based и item-based, SVD: 1, 2, 3, 4), о нескольких моделях для работы с контентом (наивный Байес, LDA, обзор методов анализа текстов), был цикл статей о холодном старте (постановка задачи, текстмайнинг, теги), была мини-серия о многоруких бандитах (часть 1, часть 2).

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

Мастер Вэ Ку и разработчик под Вин Ды
Никакой разницы
Мастер Вэ Ку и прислужник Разметки
Мастер Вэ Ку и Мастер Ю Никс
Нет наилучшего инструмента
Сон мастера По У Пэ
Лучший редактор
Отчаяние медленного ученика
Постижение Vimscript
Посвящение Vim

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

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

Из этого поста вы узнаете:

1. Почему нам нужно подбирать новую формулу ранжирования очень часто, и как именно нам в этом помогает FML;
2. Как мы разрабатываем новые факторы и оцениваем их эффективность.

Undistract-Me — простая, но чрезвычайно полезная в хозяйстве утилита, которая делает одну вещь — выводит уведомление, когда длинная команда (по умолчанию 10 секунд, но можно настроить) завершила свое исполнение.



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

Сегодня мы начинаем публиковать серию постов о машинном обучении и его месте в Яндексе, а также инструментах, которые избавили разработчиков поисковой системы от рутинных действий и помогли сфокусироваться на главном — изобретении новых подходов к улучшению поиска. Основное внимание мы уделим применению этих средств для улучшения формулы релевантности, и более широко — для качества ранжирования.

Предыдущий мой пост был посвящен цикловым перестановочным оптимизациям, проблемам распознавания циклов, разрешению неоднозначности при работе с памятью, определению и важности зависимостей. Теперь я хочу сделать обзор одной из самых эффективных цикловых оптимизаций — автовекторизации. Хочется обсудить вопросы эффективности оптимизации, а также попытаться понять, какие факторы эту эффективность определяют. Всем, кому это интересно – добро пожаловать. При обсуждении я буду ориентироваться на интеловский автовекторизатор и автовекторизатор gcc 4.7.2. gcc я буду исследовать, чтобы подтвердить, что те принципы векторизации, которые я здесь пытаюсь сформулировать, имеют достаточно общую природу. Заодно мне, конечно, хочется понять уровень автовекторизации в gcc. Тут, конечно, есть некий элемент неравенства, поскольку я использую последний компилятор Интел, но не самую топовую версию gcc, но в основном я буду ориентироваться при сравнении на SSE инструкции. (Кстати, Intel активно участвует в разработке автовекторизатора gcc). Поскольку Intel и интеловский компилятор мне ближе, то ему я уделю кое-где больше внимания. Я не претендую на то, что я векторизаторный гуру и буду рад, если кто-то увидит мои ошибки и меня поправит. Букв будет много.

Этот пост снова посвящается цикловым оптимизациям. Почему вообще речь зашла о цикловых перестановочных оптимизациях? Дело в том, что это одна из самых эффективных частей оптимизирующего компилятора. В число цикловых перестановочных оптимизаций входит как автовекторизация так и автопараллелизация. У этих оптимизаций существует своя специфика, но в целом у всех цикловых оптимизаций общие проблемы и общие методы их решения.
Часто приходится слышать мнение, что компилятор во многих случаях «тупит». Мне хочется здесь побыть адвокатом компилятора, чтобы показать, что жизнь компилятора не так уж легка, возможно вызвать легкую долю сочувствия к его нелегкой доле и показать, какие существуют объективные трудности при обработке программы и почему во многих случаях компилятор совершенно обоснованно не может сделать ту или иную оптимизацию, которая кажется очевидной программисту. Ну и заодно я хочу продемонстрировать некоторые возможности помочь компилятору в его работе. Понятно, что иногда существуют и субъективные факторы, в лице разработчиков, которые по како-либо причине не реализовали ту или иную функциональность внутри компилятора.