Все потоки
Поиск
Написать публикацию
Обновить
159.4

Алгоритмы *

Все об алгоритмах

Сначала показывать
Порог рейтинга
Уровень сложности

Минуя бесконечность: t-тест своими руками

Время на прочтение5 мин
Количество просмотров21K

В этом посте речь пойдёт о реализации процедуры вычисления значения функции распределения Стьюдента без использования каких-либо специальных математических библиотек. Только Java (либо C/C++, код вполне универсален).

Читать дальше →

Работа с фреймворком итеративной обработки графов Giraph на примере RBM

Время на прочтение16 мин
Количество просмотров5K

The Indifferent by xetobyte

Всем привет. В предыдущей статье мы рассказали, как создавать свои приложения под фреймворк Giraph (надстройка над системой обработки данных Hadoop), и обещали подробно рассмотреть, как работать с Giraph, на примере алгоритма обучения Restricted Boltzmann Machine. Итак, в какой-то момент группа сегментации аудитории департамента рекламных технологий Mail.Ru Group столкнулась с необходимостью подобрать инструмент для быстрого анализа графов, и по целому ряду причин (читайте ниже) наше внимание привлекла система Apache Giraph.
Читать дальше →

Как на самом деле устроена торговля на бирже, и как ее можно улучшить: Простой алгоритм (часть 4)

Время на прочтение3 мин
Количество просмотров12K
Продолжаем серию статей бывшего HFT-трейдера Марко Стуккио, в которых он на пальцах объясняет, как устроена высокочастотная торговля на бирже (первая часть, вторая часть, третья часть). Пришло время обелить HFT от обвинений в ответственности за краткосрочные сбои в работе финансовых рынков.



В 2012 году много писали о провале трейдерской компании с Уолл-Стрит Knight Capital (KCG). Фирма начала практиковаться в высокочастотной торговле и потерпела сокрушительную неудачу, потеряв $440 млн. и пошатнув веру инвесторов в HFT. Более подробно об этом можно почитать здесь, здесь и здесь. Журналистам обычно некогда вникать в технические детали подобных историй. Но, как утверждает автор блога о HFT, причин для паники не было. Трейдерские системы надежны, если выстроены с умом.
Читать дальше →

Языковая проблема искусственного интеллекта

Время на прочтение18 мин
Количество просмотров29K
imageДоводилось ли вам сталкиваться с системами искусственного интеллекта? Полагаем, ответ большинства хабравчан будет положительным. Ведь ИИ уже перестал быть «чем-то за гранью фантастики». Системы распознавания речи Siri, IBM Watson, ViaVoice, виртуальные игроки Deep Blue, AlphaGo и даже такие ранние системы, как MYCIN, разработанная в 1970-х годах в Стэнфордском университете и предназначенная для диагностирования бактерий, вызывающих тяжелые инфекции, а также для рекомендации необходимого количества антибиотиков — все это вариации на тему ИИ. Но, несмотря на то, что технологии стремительно набирают ход, современные системы все еще весьма «угловаты», и главная проблема, с которой сталкиваются исследователи, — это языковое обучение. Заставить систему говорить не сложно, но объяснить ей «физику» окружающего мира — то, что человек понимает на интуитивном уровне — пока не удавалось никому.

Тема языковой проблемы искусственного интеллекта широко раскрывается в статье Уилла Найта, главного редактора AI MIT Technology Review, которую специалисты PayOnline, системы автоматизации приема онлайн-платежей, старательно перевели для пользователей Хабрахабра. Ниже представляем сам перевод.

Примерно в середине крайне напряженной игры в Го, проходившей в южнокорейском Сеуле, участниками которой были один из лучших игроков всех времен Ли Седоль и созданный Google искусственный интеллект под названием AlphaGo, программа сделала загадочный шаг, продемонстрировавший пугающее преимущество над своим человеческим оппонентом.
Читать дальше →

Процедурная генерация уровней для игр-головоломок

Время на прочтение9 мин
Количество просмотров33K


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

Здорово было бы найти способ заставить компьютер сэкономить вам время и решить проблемы, о которых я сказал выше… И именно тут на помощь приходит процедурная генерация!
Читать дальше →

Как на самом деле устроена торговля на бирже, и как ее можно улучшить: Простой алгоритм (часть 3)

Время на прочтение6 мин
Количество просмотров14K


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

Поиск недействительных паспортов или учимся готовить бинарные файлы

Время на прочтение4 мин
Количество просмотров14K
В комментариях к публикации Почему Go превосходит посредственность, один из хабраюзеров предложил в качестве примера написать алгоритм поиска по списку недействительных паспортов.
Одним из условий задачи было — не использовать для этой цели СУБД. Также решение должно по минимуму использовать память, место на диске и ЦП.

К своему удивлению обнаружил, что большинство комментаторов предлагали всё же использовать СУБД, несмотря на то, что решение, использующее стандартные базы данных будет весьма громоздким (кроме того, что для самих данных нужно использовать минимум 5 байт на запись, так ещё и почти столько же места на индексы).

Имея опыт работы над бинарными базами для Sypex Geo, я решил попробовать набросать формат бинарного файла и алгоритм поиска по нему.
Читать дальше →

Особенности файловых систем, с которыми мы столкнулись при разработке механизма синхронизации Облака Mail.Ru

Время на прочтение8 мин
Количество просмотров22K


Одна из основных функций десктопного клиента Облака Mail.Ru — синхронизация данных. Ее целью является приведение папки на ПК и ее представления в Облаке к одинаковому состоянию. При разработке этого механизма мы встретились с некоторыми, с первого взгляда, достаточно очевидными особенностями различных файловых и операционных систем. Однако если о них не знать, можно столкнуться с довольно неприятными последствиями (не получится загрузить или удалить файл). В этой статье мы собрали особенности, знание которых позволит вам правильно работать с данными на дисках и, возможно, убережет от необходимости срочного хотфикса.
Читать дальше →

Стилизация изображений с помощью нейронных сетей: никакой мистики, просто матан

Время на прочтение14 мин
Количество просмотров93K

Приветствую тебя, Хабр! Наверняка вы заметили, что тема стилизации фотографий под различные художественные стили активно обсуждается в этих ваших интернетах. Читая все эти популярные статьи, вы можете подумать, что под капотом этих приложений творится магия, и нейронная сеть действительно фантазирует и перерисовывает изображение с нуля. Так уж получилось, что наша команда столкнулась с подобной задачей: в рамках внутрикорпоративного хакатона мы сделали стилизацию видео, т.к. приложение для фоточек уже было. В этом посте мы с вами разберемся, как это сеть "перерисовывает" изображения, и разберем статьи, благодаря которым это стало возможно. Рекомендую ознакомиться с прошлым постом перед прочтением этого материала и вообще с основами сверточных нейронных сетей. Вас ждет немного формул, немного кода (примеры я буду приводить на Theano и Lasagne), а также много картинок. Этот пост построен в хронологическом порядке появления статей и, соответственно, самих идей. Иногда я буду его разбавлять нашим недавним опытом. Вот вам мальчик из ада для привлечения внимания.


Читать дальше →

Машинное обучение для прогнозирования тенниса: часть 2

Время на прочтение14 мин
Количество просмотров46K
В первой части обзора я рассмотрел основные термины и понятия в ставках на теннис и сделал обзор статистических моделей для прогнозирования теннисных матчей.
Вторая часть посвящена собственно машинному обучению: алгоритмам, проблемам и кейсам.



Читать дальше →

Как на самом деле устроена торговля на бирже: Простой алгоритм (часть 2)

Время на прочтение8 мин
Количество просмотров23K


Мы продолжаем цикл статей, посвященный тому, как устроен высокочастотный трейдинг простым и понятным языком. В прошлом материале бывший квант Марк Стуккио рассказывал о механике процесса в целом. В этот раз поговорим о понятиях «раскрытия цены» и о ликвидности.
Читать дальше →

Модель взаимодействия судов с водой в видеоиграх

Время на прочтение16 мин
Количество просмотров36K


Давайте поговорим о физике транспортных средств


Физика транспортных средств в видеоиграх не очень сильно обсуждается. Статьи в Интернете о физике транспорта в видеоиграх немногочисленны и поверхностны; обычно они посвящены самым основам. Программист транспорта для видеоигр ощущает себя сегодня в относительном вакууме. Возможно, такая ситуация возникла, потому что эту тему довольно сложно объяснить, а может быть, мы просто стыдимся признаваться в использовании хаков, упрощений и хитростей, которые мы вносим по сравнению с «правильной», реалистичной симуляцией физики. Как бы ни обстояло дело, видеоигры имеют уникальные проблемы в симуляции транспорта, а значит, об этом стоит писать. Это захватывающая тема, относящаяся к физике, работе с камерой, звуку, спецэффектам, а также к восприятию и психологии человека.

Я решил сначала поговорить о судах, потому что недавно работал с ними; ещё я обнаружил, что их динамика не совсем понимается даже на уровне исследований (хотя многое и понятно). Модели и теории формулируются таким образом, что их становится сложно применить непосредственно в видеоиграх. Или же они требуют очень ресурсоёмких методов симуляции, которые практически невозможно контролировать и адаптировать под причудливые потребности разработчиков и игроков. Но можно написать упрощённую модель, которая учитывает важные параметры судна. В этом определённо есть доля искусства, «прыжка веры» и небольшая доля «творческой» физики, которая заставит Кельвина и Стокса перевернуться в могилах.
Читать дальше →

Модифицированный алгоритм Geometry Buffer Anti-Aliasing

Время на прочтение12 мин
Количество просмотров11K
Алиасинг представляет одну из фундаментальных проблем компьютерной графики, и для борьбы с ним придумано множество разнообразных алгоритмов антиалиасинга. Появление MLAA привлекло интерес к алгоритмам, работающим на этапе постобработки. Одним из таких алгоритмов (с небольшой оговоркой) является Geometry Buffer Anti-Aliasing (GBAA). В этом материале описана попытка модификации оригинального алгоритма для улучшения качества антиалиасинга в некоторых случаях.

image
Читать дальше →

Ближайшие события

«Машинное обучение»: Потенциал и возможности

Время на прочтение5 мин
Количество просмотров13K


/ фото Jaro Larnos CC

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

Но есть еще одна технология, способная изменить наше представление об обработке информации. Речь идет о машинном обучении, которое в последнее время приобрело особую популярность.
Читать дальше →

Kaggle – наша экскурсия в царство оверфита

Время на прочтение19 мин
Количество просмотров38K
Kaggle — это платформа для проведения конкурсов по машинному обучению. На Хабре частенько пишут про неё: 1, 2, 3, 4, и.т.д. Конкурсы на Kaggle интересные и практичные. Первые места обычно сопровождаются неплохими призовыми (топовые конкурсы — более 100к долларов). В последнее время на Kaggle предлагали распознавать:


И многое-многое другое.

Мне давно хотелось попробовать, но что-то всё время мешало. Я разрабатывал много систем, связанных с обработкой изображений: тематика близка. Навыки более лежат в практической части и классических Computer Vision (CV) алгоритмах, чем в современных Machine Learning техниках, так что было интересно оценить свои знания на мировом уровне плюс подтянуть понимание свёрточных сетей.

И вот внезапно всё сложилось. Выпало пару недель не очень напряжённого графика. На kaggle проходил интересный конкурс по близкой тематике.Я обновил себе комп. А самое главное — подбил vasyutka и Nikkolo на то, чтобы составить компанию.

Сразу скажу, что феерических результатов мы не достигли. Но 18 место из 1.5 тысяч участников я считаю неплохим. А учитывая, что это наш первый опыт участия в kaggle, что из 3х месяц конкурса мы участвовали лишь 2.5 недели, что все результаты получены на одной единственной видеокарте — мне кажется, что мы хорошо выступили.

О чём будет эта статья? Во-первых, про саму задачу и наш метод её решения. Во-вторых, про процесс решения CV задач. Я писал достаточно много статей на хабре о машинном зрении(1,2,3), но писанину и теорию всегда лучше подкреплять примером. А писать статьи по какой-то коммерческой задаче по очевидным причинам нельзя. Теперь наконец расскажу про процесс. Тем более что тут он самый обычный, хорошо иллюстрирующий как задачи решаются. В-третьих, статья про то, что идёт после решения идеализированной задаче в вакууме: что будет когда задача столкнётся с реальностью.


Читать дальше →

Самое главное о нейронных сетях. Лекция в Яндексе

Время на прочтение30 мин
Количество просмотров190K
Кажется, не проходит и дня, чтобы на Хабре не появлялись посты о нейронных сетях. Они сделали машинное обучение доступным не только большим компаниям, но и любому человеку, который умеет программировать. Несмотря на то, что всем кажется, будто о нейросетях уже всем все известно, мы решили поделиться обзорной лекцией, прочитанной в рамках Малого ШАДа, рассчитанного на старшеклассников с сильной математической подготовкой.

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



Константин klakhman Лахман закончил МИФИ, работал исследователем в отделе нейронаук НИЦ «Курчатовский институт». В Яндексе занимается нейросетевыми технологиями, используемыми в компьютерном зрении.

Под катом — подробная расшифровка со слайдами.
Читать дальше →

Сколько нужно нейронов, чтобы узнать, разведён ли мост Александра Невского?

Время на прочтение6 мин
Количество просмотров25K

image


Введение.


На той неделе darkk описал свой подход к проблеме распознавания состояния моста(сведён/разведён).


Алгоритм, описанный в статье, использовал методы компьютерного зрения для извлечения признаков из картинок и скармливал их логистической регрессии для получения оценки вероятности того, что мост сведён.


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


В последние несколько лет сильную популярность обрели нейронные сети, как алгоритм, который умудряется в автоматическом режиме извлекать признаки из данных и обрабатывать их, причём делается это настолько просто с точки зрения того, кто пишет код и достигается такая высокая точность, что во многих задачах (~5% от всех задач в машинном обучении) они рвут конкурентов на британский флаг с таким отрывом, что другие алгоритмы уже даже и не рассматриваются. Одно из этих успешных для нейронных сетей направлений — работа с изображениями. После убедительной победы свёрточных нейронных сетей на соревновании ImageNet в 2012 году публика в академических и не очень кругах возбудилась настолько, что научные результаты, а также програмные продукты в этом направлении появляются чуть ли не каждый день. И, как результат, использовать нейронные сети во многих случаях стало очень просто и они превратились из "модно и молодёжно" в обыкновенный инструмент, которым пользуются специалисты по машинному обучению, да и просто все желающие.


Читать дальше →

&? Trim? Гейзенберг? Не, не слышал

Время на прочтение2 мин
Количество просмотров13K

Введение


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

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

Зачем это нужно? Ну, по мнению Путина В. В., у нас в стране "слишком много бухгалтеров", поэтому вот и сделали еще один ежемесячный отчет.

Мера обсуждается в России уже более десяти лет: считается, что из-за сильных различий в двух видах учета в стране слишком много бухгалтеров (в России насчитывается три миллиона бухгалтеров, что в 2,5 раза больше, чем в США).

Если задаться вопросом, зачем он нужен, этот отчет, то ответ будет достаточно смешным. Это нужно для того, чтобы не индексировать пенсию работающим пенсионерам. Да-да, именно так: в нынешних нефтяных реалиях, а также с учетом того, что бюджет Пенсионного фонда примерно на половину состоит из прямых дотаций, невыгодно это.
Читать дальше →

Перехват функций .NET/CLR

Время на прочтение16 мин
Количество просмотров20K
Иногда при разработке программного обеспечения требуется встроить дополнительную функциональность в уже существующие приложения без модификации исходного текста приложений. Более того, зачастую сами приложения существуют только в скомпилированном бинарном виде без наличия исходного текста. Широко известным способом решения указанной задачи является т.н. “сплайсинг” – метод перехвата функций путем изменения кода целевой функции. Обычно при сплайсинге первые байты целевой функции перемещаются по другим адресам, а на их исходное место записывается команда безусловного перехода (jmp) на замещающую функцию. Поскольку сплайсинг требует низкоуровневых операций с памятью, то он осуществляется с использованием языка ассемблера и С/C++, что также накладывает определенные ограничения на реализацию замещающих функций – они обычно также реализованы на С/C++ (реже на ассемблере).

Метод сплайсинга для перехвата API-функций в Windows широко описан в Интернете и в различных литературных источниках. Простота указанного перехвата определяется следующими факторами:
  1. целевая функция является статической – она сразу присутствует в памяти загруженного модуля;
  2. адрес целевой функции легко определить (через таблицу экспорта модуля или функцию GetProcAddress).

Реализация замещающих функций на C/C++ при перехвате API-функций является оптимальным вариантом, поскольку Windows API реализовано, как известно, на языке C, и замещающие функции могут оперировать теми же понятиями, что и заменяемые.
Читать дальше →

Машинное обучение для прогнозирования тенниса: часть 1

Время на прочтение12 мин
Количество просмотров74K
Математическое моделирование тенниса набирает популярность на наших глазах. Каждый год появляются новые аналитические модели и сервисы, соревнующиеся друг с другом в точности прогнозирования исходов теннисных матчей. Это вызвано желанием заработать на стремительно растущем онлайн рынке спортивных ставок: нередки случаи, когда сумма ставок на отдельный матч в профессиональном теннисе достигает миллионов долларов.

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



Читать дальше →

Вклад авторов