Рубрика «Алгоритмы»

image Привет, Хаброжители! Недавно у нас вышла первая русская книга о глубоком обучении от Сергея Николенко, Артура Кадурина и Екатерины Архангельской. Максимум объяснений, минимум кода, серьезный материал о машинном обучении и увлекательное изложение. Сейчас мы рассмотрим раздел «Граф вычислений и дифференцирование на нем» в котором вводятся основополагающее понятие для реализации алгоритмов обучения нейронных сетей.

Если у нас получится представить сложную функцию как композицию более простых, то мы сможем и эффективно вычислить ее производную по любой переменной, что и требуется для градиентного спуска. Самое удобное представление в виде композиции — это представление в виде графа вычислений. Граф вычислений — это граф, узлами которого являются функции (обычно достаточно простые, взятые из заранее фиксированного набора), а ребра связывают функции со своими аргументами.
Читать полностью »

Параллельная сортировка данных в GPU - 1

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

GIF

Параллельная сортировка данных в GPU - 2

Введение

Если вы изучали теорию вычислительных машин в 80-х или 90-х, есть вероятность, что вы упорно пытались понять, что же некоторые разработчики находят восхитительного в алгоритмах сортировки. То, что поначалу кажется незначительной задачей, оказывается краеугольным камнем Computer Science.

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

Сверточная сеть на python. Часть 3. Применение модели - 1

Это заключительная часть статей о сверточных сетях. Перед прочтением рекомендую ознакомиться с первой и второй частями, в которых рассматриваются слои сети и принципы их работы, а также формулы, которые отвечают за обучение всей модели. Сегодня мы рассмотрим особенности и трудности, с которыми можно столкнуться при тестировании вручную написанной на python сверточной сети, применим написанную сеть к датасету MNIST и сравним полученные результаты с библиотекой tensorflow.
Читать полностью »

Проблематика вопроса сформулирована в предыдущей статье.

А именно: как оценить влияние определенного допущения модели Блэка-Шоулза на расчетную величину премии по европейскому опциону? Допущения о том, что цена торгуемого актива имеет логнормальное распределение. Как альтернативу расчета по формуле Блэка-Шоулза я использовал подход — прогнозирование выплат покупателю опциона методом Монте-Карло. На вход программе я подавал:

  • “эталонные данные” (моделирование логнормального распределения”),
  • случайный ряд, характеризующийся распределением с “толстыми хвостами”,
  • и, наконец, цены нескольких биржевых активов — валютных пар и криптовалют.

В каждом случае я рассчитал премию опциона по формуле Б-Ш и методом Монте-Карло. Сравнил результаты и сделал(?) выводы:
Расчет премии по опциону методом Монте-Карло vs формула Блэка-Шоулза - 1

Читать полностью »

Кривые Безье и Пикассо - 1

Пабло Пикассо в своей студии на фоне картины «Кухня», фотография Херберта Листа.

Художник и простота

Одни из самых любимых мной работ Пабло Пикассо — это его линейные рисунки. Он изобразил на некоторых из них животных: сову, верблюда, бабочку и т.д. Эта работа под названием «Собака» висит на моей стене:

Кривые Безье и Пикассо - 2

(Можете перейти к интерактивному демо, в которой мы воссоздали «Собаку» с помощью представленных в статье математических расчётов)

Эти рисунки чрезвычайно просты, но каким-то образом им удаётся глубоко тронуть зрителя. Они создают впечатление простоты композиции и реализации. Одно движение руки и подпись создают настоящий шедевр! Рисунок одновременно кажется и небрежной импровизацией, и точно подобранной увертюрой в симфонии изящества.Читать полностью »

От переводчика:

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

Нахождение 3-го элемента от конца в односвязном списке или n-го узла от хвоста является одним из каверзных и часто задаваемых вопросов по проблемам односвязных списков на собеседованиях. Задача, в данном случае, в том, чтобы решить проблему всего в один проход цикла, т.е., нельзя снова пройтись по связному списку и нельзя идти в обратном направлении, т.к. список односвязный. Если вы когда-нибудь решали проблемы связных списков, например, нахождение длины, вставки или удаления элементов, вы должны уже быть знакомы с вопросом обхода списков. В данной статье мы используем тот же самый алгоритм, который мы использовали для нахождения срединного элемента связного списка в один проход цикла. Этот алгоритм также известен как «алгоритм черепахи и зайца» из-за скорости двух указателей, используемых алгоритмом для обхода односвязного списка.
Читать полностью »

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

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

Код в статье будет на Scala.

Всех заинтересовавшихся прошу под кат.
Читать полностью »

Из блога Netflix Technology

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

Один из вариантов решения проблемы — принять в учёт картинки или обложки для фильмов. Если картинка выглядит убедительно, то она служит толчком и неким визуальным «доказательством», что фильм достоин просмотра. На ней может быть изображён известный вам актёр, захватывающий момент вроде автомобильной погони или драматическая сцена, передающая суть фильма или сериала. Если мы покажем идеальную обложку фильма на вашей домашней странице (как говорится, картинка стоит тысячи слов), то возможно, только возможно, вы решитесь выбрать этот фильм. Это просто ещё одна вещь, в которой Netflix отличается от традиционных медиа: у нас не один продукт, а более 100 млн разных продуктов, а каждый из пользователей получает персональные рекомендации и персональные обложки.

Netflix подбирает оптимальные обложки фильмов для каждого зрителя - 1
Главная страница Netflix без обложек. Так исторически наши алгоритмы рекомендаций видели страницу
Читать полностью »

Введение

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

Находясь под впечатлением прочитанных не так давно историй взлетов и метаморфоз рынков деривативов — прежде всего, фьючерсных и опционных контрактов, я заинтересовался нетривиальным ценообразованием опционов. Мне открылось, что, хотя интернет полон рерайтов статей, толкующих знаменитую формулу Блэка-Шоулза, практических инструментов — web-сайтов, технологических программ или банальных руководств для программиста — не математика, по данному вопросу в интернете недостает. Пришлось вспомнить азы тервера и адаптировать строгие математические описания в популярном, понятном, прежде всего, мне самому, формате.
Читать полностью »