Это достаточно вольный перевод статьи. Дело в том, что несмотря на конструкции в одну строчку, материал сложен для понимания.
Беря во внимание то, что в комментариях Прелюдия или как полюбить Haskell просили, чтобы код был понятный, я внёс достаточно ремарок, и, надеюсь, код будет понятен и тем, кто далёк от Хаскеля.

Давайте начнём с самого трудного — с самого заголовка: многим непонятны все его слова.
Хаскель — это чистый и ленивый функциональный язык.
Лёб — это немецкий математик, о котором мы поговорим чуть позже.
Ну, и наконец, самое интересное — странные петли.

Странные петли — это запутанные категории, когда двигаясь вверх или вниз в иерархической системе, находишь то же самое, откуда начал движение.
Зачастую такие петли содержат само-референтные ссылки.
Например, подобной странной петлёй обладает рекурсивные акронимы: «PHP — PHP: Hypertext Preprocessor».
Ну, и на сегодняшний день наиболее загадочным словом, содержащим странные петли, является понятие «я».

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

Немецкий математик Лёб мигрировал в 39-м году ХХ-го столетия в Великобританию. Лёб, в частности, развивал математическую логику и миру прежде всего известен Теоремой Лёба. Это теорема развивала труды Гёделя о неполноте математики. Теорема Лёба о взаимосвязи между доказуемостью утверждения и самим утверждением, она гласит, что

во всякой теории, включающей аксиоматику Пеано (аксиоматика о натуральных числах), для любого высказывания P доказуемость высказывания «если доказуемо P, тогда P истинно» возможна только в случае доказуемости самого высказывания P.

Всю эту сложность высказывания можно записать символически:


Можно ли такую функцию написать на Хаскеле?! Можно! И всего в одну строчку!

Добрый день уважаемые читатели. В сегодняшней посте я продолжу свой цикл статей посвященный анализу данных на python c помощью модуля Pandas и расскажу один из вариантов использования данного модуля в связке с модулем для машинного обучения scikit-learn. Работа данной связки будет показана на примере задачи про спасенных с "Титаника". Данное задание имеет большую популярность среди людей, только начинающих заниматься анализом данных и машинным обучением.

Как находить тексты похожие по смыслу? Какие есть алгоритмы для поиска текстов одной тематики? – Вопросы регулярно возникающие на различных программистских форумах. Сегодня я расскажу об одном из подходов, которым активно пользуются поисковые гиганты и который звучит чем-то вроде мантры для SEO aka поисковых оптимизаторов. Этот подход называет латентно-семантический анализ (LSA), он же латентно-семантическое индексирование (LSI)

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

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

Был удивлен, что на хабре нет описания расширения Unite, которое позволяет заменить просто огромное количество плагинов для Vim. Unite сочетает в себе функционал таких расширений как: CtrlP, FuzzyFinder, ack, yankring, LustyJuggler, buffer explorer и т.д.

Мне всегда нравилось, когда заголовок однозначно говорит о том, что будет дальше, например, «Техасская резня бензопилой». Поэтому под катом мы действительно будем добавлять пространственный поиск к СУБД, в которой его изначально не было.

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

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

(Да, пост во многом пересекается с постом Распределенный аудиоплеер на Odroid U2, но чуть проще в настройке)

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

Восстановление формулы ранжирования

Если переводить данную задачу в область математики, то входные данные можно представить набором векторов, где каждый вектор – множество характеристик каждого сайта, а координаты в векторе – параметр, по которым оценивается сайт. В описанном векторном пространстве обязательно должна быть задана функция, определяющая отношение порядка двух объектов между собой. Эта функция позволяет ранжировать объекты между собой по принципу «больше — меньше», однако при этом сказать, насколько именно одно больше или меньше другого – нельзя. Такого вида задачи относятся к задачам оценки порядковой регрессии.
Наши сотрудники разработали алгоритм на основе модели линейной регрессии с регулируемой селективностью, который позволил с определенной долей погрешности восстановить ранги сайтов и спрогнозировать изменение выдачи при соответствующих корректировках параметров сайта. Первым шагом алгоритма является обучение модели. В данном случае обучающая выборка представляет собой результаты ранжирования сайтов в рамках одного поискового запроса. Упорядоченность сайтов в рамках поискового запроса фактически означает, что в признаковом пространстве существует некоторое направление, на которое объекты обучающей выборки должны проектироваться в нужном порядке. Это направление и является искомым в задаче восстановления формулы ранжирования. Однако судя по рис.1, таких направлений может быть много.

Рис. 1. Выбор направляющего вектора

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

Данный подход на различных выборках (100 признаков и 500 признаков на 20 различных множествах поисковых запросов) показал хорошие результаты (см. табл. 1).

Нормальное распределение (распределение Гаусса) всегда играло центральную роль в теории вероятностей, так как возникает очень часто как результат воздействия множества факторов, вклад любого одного из которых ничтожен. Центральная предельная теорема (ЦПТ), находит применение фактически во всех прикладных науках, делая аппарат статистики универсальным. Однако, весьма часты случаи, когда ее применение невозможно, а исследователи пытаются всячески организовать подгонку результатов под гауссиану. Вот про альтернативный подход в случае влияния на распределение множества факторов я сейчас и расскажу.

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

В общем виде словарь — множество записей вида {строка, данные ассоциированные с этой строкой}.

Например, для морфологического анализа словарь состоит из троек {словоформа, нормальная форма, морфологические характеристики}. При анализе слова «мыла» из предложения «мама мыла раму» надо уметь получать следующие варианты анализа:

Нормальная форма	Характеристики
МЫЛО	S (существительное), РОД (родительный падеж), ЕД (единственное число), СРЕД (средний род), НЕОД (неодушевленность)
МЫЛО	S (существительное), ИМ (именительный падеж), МН (множественное число), СРЕД (средний род), НЕОД (неодушевленность)
МЫЛО	S (существительное), ВИН (винительный падеж), МН (множественное число), СРЕД (средний род), НЕОД (неодушевленность)
МЫТЬ	V (глагол), ПРОШ (прошедшее время), ЕД (единственное число), ИЗЪЯВ (изъявительное наклонение), ЖЕН (женский род), НЕСОВ (несовершенный вид)

Люди могут различать примерно 10 000 визуальных категорий высокого уровня, но мы можем различать гораздо больший спектр визуальных импульсов, называемых особыми признаками. Эти признаки могут соответствовать частям объекта, конечностям животного, архитектурным деталям, объектам на местности и другим зрительным образам, названия которых мы не знаем, но именно этот гораздо больший набор признаков мы используем в качестве основы для реконструкции и объяснения нашего ежедневного визуального опыта.

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

Сегодня мы хотим рассказать о технологии Real Time MapReduce, благодаря которой всё это стало возможно. Она обеспечивает передачу и обработку огромных объёмов данных, необходимых для этой задачи, и чтобы сделать это, нам даже не пришлось переписывать код для MapReduce, который у нас уже использовался.



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

Недавно я наткнулся на такую удивительную штуку как число Данбара.
История такова. 20 с лишним лет назад, когда выражение «британские учёные» ещё не было мемом, антрополог Робин Данбар, изучая данные по человекообразным обезьянам, обнаружил, что численность их стаи подчиняется определённому закону. Есть максимальное количество членов стаи. Если стая разрастается и её численность превышает порог, она разделяется на две. Причём для разных видов этот предельный размер получается разным.

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

Скрытые модели/цепи Маркова одни из подходов к представлению данных. Мне очень понравилось как обобщается множество таких подходов в этой статье.

В продолжение же моей предыдущей статьи описания скрытых моделей Маркова, задамся вопросом: откуда взять хорошую модель? Ответ достаточно стандартен, взять неплохую модель и сделать из нее хорошую.

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

Эта статья рассказывает о времени выполнения и о расходе памяти большинства алгоритмов используемых в информатике. В прошлом, когда я готовился к прохождению собеседования я потратил много времени исследуя интернет для поиска информации о лучшем, среднем и худшем случае работы алгоритмов поиска и сортировки, чтобы заданный вопрос на собеседовании не поставил меня в тупик. За последние несколько лет я проходил интервью в нескольких стартапах из Силиконовой долины, а также в некоторых крупных компаниях таких как Yahoo, eBay, LinkedIn и Google и каждый раз, когда я готовился к интервью, я подумал: «Почему никто не создал хорошую шпаргалку по асимптотической сложности алгоритмов? ». Чтобы сохранить ваше время я создал такую шпаргалку. Наслаждайтесь!

Предисловие

Когда я начал изучать Хаскель, я был почти сразу поражён. Для начала, нырнув с головой в актуальные рабочие проекты, открыл, что большинство настоящих библиотек используют языковые расширения, присутствующие только в GHC (Glasgow Haskell Compiler). Это меня покоробило слегка, прежде всего потому, кто захочет использовать язык настолько немощный, что будет необходимо использовать расширения, присутствующие лишь у одного поставщика. Ведь так?
Хорошо, я решился снова это осилить и узнать всё об этих расширениях, и я вывел три горячих топика для общества Хаскеля, которые решали похожие проблемы: Обобщённые Алгебраические Типы Данных, Семьи Типов и Функциональные Зависимости. Пытаясь найти ресурсы, которые обучают о них, я смог найти только статьи, описывающие, что это такое, и как их использовать. Но никто, на самом деле, не объяснял зачем они нужны!.. Поэтому я решил написать эту статью, используя дружественный пример, пытаясь объяснить зачем всё-таки нужны Семьи Типов.



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

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

Введение

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

На провокации вида «при помощи такой системы можно слить гостайну врагу» я отвечаю сразу: при помощи ядерных ракет можно не только устроить конец света, но и отогнать или расколоть угрожающий нашей планете астероид.

Потребность в пространственном поиске возникает довольно часто. Равно как и в пространственном JOIN’е — нахождении пересечения двух наборов пространственных объектов. Далеко не всегда хочется привлекать тяжелую артиллерию. Что ж, попробуем придумать способ решить проблему “малой кровью, могучим ударом”.