Привет, меня зовут Михаил Ройзнер. Недавно я выступил перед студентами Малого Шада Яндекса с лекцией о том, что такое рекомендательные системы и какие методы там бывают. На основе лекции я подготовил этот пост.

План лекции:

1. Виды и области применения рекомендательных систем.
2. Простейшие алгоритмы.
3. Введение в линейную алгебру.
4. Алгоритм SVD.
5. Измерение качества рекомендаций.
6. Направление развития.

Добрый день, уважаемые хабровчане. Возможно многие из вас зададутся вопросом: «А где же описание основного алгоритма?».
Так вот, ниже будут указанны ссылки на источники, и переписывать основной алгоритм не буду.
Сразу объяснюсь. Данная статья — это результат моей исследовательской работы, а в дальнейшем и тема моего диплома.
Но хватит вводных слов. Поехали!

1. Искусственные нейронные сети

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

Исторически, искусственные нейронные сети за свою уже более чем полувековую историю испытывали как периоды стремительных взлетов и повышенного внимания общества, так и сменявшие их периоды скепсиса и равнодушия. В хорошие времена ученым и инженерам кажется, что наконец-то найдена универсальная технология, способная заменить человека в любых когнитивных задачах. Как грибы после дождя, появляются различные новые модели нейронных сетей, между их авторами, профессиональными учеными-математиками, идут напряженные споры о большей или меньшей степени биологичности предложенных ими моделей. Профессиональные ученые-биологи наблюдают эти дискуссии со стороны, периодически срываясь и восклицая «Да такого же в реальной природе не бывает!» – и без особого эффекта, поскольку нейросетевики-математики слушают биологов, как правило, только тогда, когда факты биологов согласуются с их собственными теориями. Однако, с течением времени, постепенно накапливается пул задач, на которых нейронные сети работают откровенно плохо и энтузиазм людей остывает.

Специалисты Массачусетского Технологического Института создали автономную модель самолёта, которая может агрессивно маневрировать в стеснённых условиях на скорости до 10 м/сек. Самолёт определяет своё положение в пространстве с помощью гироскопов, акселерометров и лазерного дальномера. Бортовой компьютер работает на процессоре Intel Atom частотой 1,6 ГГц. Ключевой элемент системы — оптимизированный для полёта в реальном времени алгоритм Gaussian particle filter.

В прошлой статье я вкратце рассказал о том, чем же занимается ЦЕРН. Теперь же я хочу немного рассказать об эксперименте ATLAS.



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

И чтобы заинтересовать читателя, я задам один вопрос: почему у вас есть масса?

Эта статья продолжение Модель функционального разделения сознания и бессознательного. Введение. В ней мы лирически описали принципы перцептрона Розенблатта. И подняли проблему обучения от двух и более учителей. В этой статье проблема «двух и более учителей» не рассматривается, её мне достаточно сложно сформулировать технически на простых примерах (на сложных могу). Поэтому с этим будем разбираться возможно в следующей статье — если будет некоторый интерес.

В этой статье мы поговорим о сознании, но если желаете пропустить лирику (а специалистов она несколько напрягает, но хотелось чтобы поняли не только специалисты), то начинайте читать с раздела «Модель «Нулевого сознания» в Интеллектронике». Но лирика все же дает некоторые идеи о связи с такими фиктивными понятиями как сознание.

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

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

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

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

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

Как упоминалось в предыдущей статье, латентно-семантический анализ (ЛСА / LSA) позволяет выявлять латентные связи изучаемых явлений или объектов, что является немаловажным критерием при моделировании процессов понимания и мышления.

Теперь я напишу немного о реализации ЛСА.

Одно из моих любимых удовольствий – productivity porn, порнография эффективности. Или, для тех, кто в теме – pr0n. Это набор техник, тактик и трюков по максимизации личной эффективности. Что называется, «getting things done».

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

Не составляйте себе расписание

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

Линзы

Ваш билет к элегантному коду — это библиотека линз (lens).

Не помню, где первый раз увидел, но был очарован заставкой DropClock, о которой уже упоминалось на Хабре.

=>

Но вот беда: авторы собрали её только для Win и Mac. Несмотря на это, желание было сильнее ограничений, и я решил во что бы то ни стало собрать собственную реализацию.

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

Интерпретация запятых в классической русской литературе – это пример плохого анализа данных, построенного на отсутствии любознательности и понимания математической статистики. Эти факторы + страстное желание развиваться в области информационных технологий – ключевые в понимании специальности «учёного по данным».

Недавно заметил в ленте фейсбука ссылку на статью с кучей примеров «странных корреляций» как на картинке. Первоисточник оказывается здесь, и там таких примеров штук 20. Решил по-практиковаться в статистике и проверить насколько эти корреляции удивительны на самом деле.

Заинтересованных прошу под кат.

Я думаю ни для кого не будет секретом, что у Awesome есть «узкое место», если мы запускаем внешний скрипт, который например должен считать данные из файла, или интернета и вернуть результат в виджет или саму систему, то мы периодически можем наблюдать явлениие «фриза», т.е. когда система перестает реагировать на нажатия клавиш и мыши до получения результата обработки (правда активный клиент при этом продолжает работать). Чаще всего это происходит при использовании io.popen или awful.util.pread

Данный текст является переводом документации Template Haskell, написанной Булатом Зиганшиным. Перевод всего текста разбит на несколько логических частей для облегчения восприятия. Далее курсив в тексте — примечания переводчика. Предыдущие части:

• Часть 1. Необходимый минимум
• Часть 2. Инструменты цитирования кода

Материализация

Материализация (reification) — это средство Template Haskell, позволяющее программисту получить информацию из таблицы символов компилятора. Монадическая функция reify ∷ Name → Q Info возвращает информацию о данном имени: если это глобальный идентификатор (функция, константа, конструктор) – вы получите его тип, если это тип или класс – вы получите его структуру. Определение типа Info можно найти в модуле Language.Haskell.TH.Syntax.
Материализация может быть использована для того, чтобы получить структуру типа, но таким образом нельзя получить тело функции. Если вам нужно материализовать тело функции, то определение функции нужно процитировать и дальше можно будет работать с этим определением с помощью другого шаблона. Например так:

$(optimize [d| fib = … |])

или так

fib = $(optimize [| … |])

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

Облегчённое цитирование имён

Чтобы получить имя (∷ Name), соответствующее интересующему идентификатору, можно использовать функцию mkName, но это не безопасное решение, потому что mkName возвращает не квалифицированное имя, которое может интерпретироваться по-разному в зависимости от контекста. А вот код VarE id ← [| foo |] безопасен в этом смысле, так как цитирование квалифицирует имена (получится что-то типа My.Own.Module.foo), но этот код слишком многословный и требует монадический контекст для использования. К счастью, Template Haskell, имеет другую простую форму цитирования имён: 'foo (одинарная кавычка перед foo) имеет тип Name и содержит квалифицированное имя, соответствующее идентификатору foo, так что код let id = 'foo эквивалентен по смыслу коду VarE id ← [| foo |]. Обратите внимание, что эта конструкция имеет простой тип Name (а не Q Exp или Q Name), так что она может быть использована там, где не возможно использование монад, например:

f ∷ Exp → Exp
f (App (Var m) e) |  m == 'map  =  …

Эта новая форма тем не менее является цитированием и подчиняется тем же правилам, что и цитирующие скобки [| … |]. Например, она не может быть использована внутри этих скобок (так нельзя: [| 'foo |]), но и вклеивание к ней не может быть применено (так тоже нельзя: $( 'foo )), потому что для вклейки нужен тип Q …. Более важно то, что эта форма определяется статически, возвращая полностью квалифицированное имя, с однозначной интерпретацией.
Haskell’евские пространства имён немного всё усложняют. Цитата [| P |] означает конструктор данных P, в то время как [t| P |] означает конструктор типа P. Поэтому для “облегчённого цитирования” необходим такой же способ разделения этих сущностей. Для контекста типов используется просто две одинарные кавычки:

• 'Foo означает “конструктор данных Foo в контексте выражения”
• 'foo означает “имя foo в контексте выражения”
• ''Foo означает “конструктор типа Foo в контексте типов”
• ''foo означает “переменная типа foo в контексте типов”

Облегчённая форма цитирования используется в примере генерации воплощений класса Show, который разбирается в конце.

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

Панель задач — отображает по умолчанию клиенты с активного тега/тегов.

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

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

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

Несмотря на огромную популярность аппарата графических моделей для решения задачи структурной классификации, задача настройки их параметров по обучающей выборке долгое время оставалась открытой. В своем докладе Дмитрий Ветров, рассказал об обобщении метода опорных векторов и некоторых особенностях его применения для настройки параметров графических моделей. Дмитрий – руководитель группы Байесовских методов, доцент ВМК МГУ и преподаватель в ШАДе.

Видеозапись доклада.

План доклада:

• Байесовские методы в машинном обучении.
• Задачи с взаимозависимыми скрытыми переменными.
• Вероятностные графические модели
• Метод опорных векторов и его обобщение для настройки параметров графических моделей.

Сама концепция машинного обучения довольно несложная – это, если говорить образно, поиск взаимосвязей в данных. Данные представляются в классической постановке набором объектов, взятых из одной и той же генеральной совокупности, у каждого объекта есть наблюдаемые переменные, есть скрытые переменные. Наблюдаемые переменные (дальше будем их обозначать X) часто называются признаками, соответственно, скрытые переменные (T) — это те, которые подлежат определению. Для того, чтобы эту взаимосвязь между наблюдаемыми и скрытыми переменными установить, предполагается, что у нас есть обучающая выборка, т.е. набор объектов, для которых известны и наблюдаемые и скрытые компоненты. Глядя на нее, мы пытаемся настроить некоторые решающие правила, которые нам позволят в дальнейшем, когда мы видим набор признаков, оценить скрытые компоненты. Процедура обучения приблизительно выглядит следующим образом: фиксируется множество допустимых решающих правил, которые как правило задаются с помощью весов (W), а дальше каким-то образом в ходе обучения эти веса настраиваются. Тут же с неизбежностью возникает проблема переобучения, если у нас слишком богатое семейство допустимых решающих правил, то в процессе обучения мы легко можем выйти на случай, когда для обучающей выборки мы прекрасно прогнозируем ее скрытую компоненту, а вот для новых объектов прогноз оказывается плохой. Исследователями в области машинного обучения было потрачено немало лет и усилий для того, чтобы эту проблему снять с повестки дня. В настоящее время, кажется, что худо-бедно это удалось.