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

Серия «Белый шум рисует черный квадрат»

История цикла этих публикаций начинается с того, что в книге Г.Секей «Парадоксы в теории вероятностей и математической статистике» (стр.43), было обнаружено следующее утверждение:

Треугольник Паскаля vs цепочек типа «000…-111…» в бинарных рядах и нейронных сетях - 1
Рис. 1.

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

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

Треугольник Паскаля vs цепочек типа «000…-111…» в бинарных рядах и нейронных сетях - 2
Рис. 2.

Для понимания теоремы Эрдёша-Реньи составим аналогичную модель, но узлы будут формироваться из значений, в которых присутствуют наибольшие цепочки, состоящие последовательно из одинаковых значений. Кластеризации будет проводиться по следующему правилу: цепочки 01/10, к кластеру «1»; цепочки 00/11, к кластеру «2»; цепочки 000/111, к кластеру «3» и т.д. При этом разобьём пирамиду на две симметричные составляющие рисунок 3.

Треугольник Паскаля vs цепочек типа «000…-111…» в бинарных рядах и нейронных сетях - 3
Рис. 3.

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

В прошлой статье я описал алгоритм, позволяющий строить более интересные (в противовес более коротким, как делают всякие яндексы-гуглы) пешеходные маршруты между двумя точками. Алгоритм загружал достопримечательности, парки и прочие приятные и интересные для пешеходов объекты из Open Street Map и прокладывал маршрут через них. В итоге путь мог оказаться на 10-20% длиннее, но гораздо живописнее и интереснее.

Гуляем по городу с умом — 2: ходим по городу кругами с помощью генетического алгоритма - 1
Фото города — Alex 'Florstein' Fedorov

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

После некоторого количества экспериментов я сочинил генетический алгоритм, который строит достаточно неплохие (для меня) маршруты в такой ситуации. Под катом описание принципа работы и несколько примеров.Читать полностью »

Привет!

Сейчас вот сидел, делал для товарища прототип генетического алгоритма. Навеяло поделиться оным, да и некоторыми другими мыслями…

Дано (клиент заказал): в некоем царстве складе есть 100 ячеек. В нем товар лежит. Как взять количество Х так, чтобы опустошить все задействованные ячейки до конца? Ну то есть, есть у вас типа ячейки [34, 10, 32, 32, 33, 41, 44, 4, 28, 23, 22, 28, 29, 14, 28, 15, 38, 49, 30, 24, 18, 9, 15, 8, 17, 9, 2, 7, 30, 29, 29, 2, 28, 23, 19, 4, 15, 30, 38, 3, 14, 21, 43, 50, 29, 14, 17, 12, 25, 15, 23, 28, 47, 38, 29, 7, 36, 45, 25, 6, 25, 11, 10, 1, 19, 37, 24, 27, 50, 12, 1, 1, 44, 22, 48, 13, 46, 49, 11, 33, 29, 4, 19, 33, 12, 3, 47, 27, 26, 45, 40, 37, 21, 2, 8, 41, 5, 1, 9, 5] — как набрать, скажем, 40

Ну можно перебором, наверняка есть что-то умное, а можно генетическим алгоритмом это решить…
Читать полностью »

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

Решето Сундарама входит в тройку известнейших методов генерации простых чисел. Сейчас к нему принято относиться как к некоторой экзотике по причине плохой вычислительной сложности: O(N(logN)). Однако асимптотика – асимптотикой, а на практике в 32-битном диапазоне просеивания Аткин, например, перегоняет Сундарама только при тщательной оптимизации.

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

Хеди Ламарр: изобретательница из Голливуда - 1

Хеди Ламарр

Что общего между игрой на пианино в четыре руки, торпедами и «вай-фаем» в вашем гаджете? Ответ вы найдете в этой статье.

9 ноября 2014 года, отмечалось столетие со дня рождения голливудской звезды Хеди Ламарр. Фильмы с ее участием давно стали классикой Голливуда. Но не все знают, что она была не просто актриса. Без нее мы бы сейчас вряд ли говорили по мобильному телефону, ориентировались с помощью GPS и искали, где лучше ловится Wi-Fi. Но обо всем по порядку.
Читать полностью »

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

Статья будет состоять из нескольких разделов ниже:

  • Функции
  • Данные
  • Результаты
  • Выводы

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

Распознавание лиц с помощью сиамских сетей - 1

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

Допустим, нам нужно сделать модель распознавания лиц для организации, в которой работает около 500 человек. Если делать такую модель с нуля на основе свёрточной нейросети (Convolutional Neural Network (CNN)), то для обучения модели и достижения хорошей точности распознавания нам понадобится много изображений каждого из этих 500 человек. Но очевидно, что такой датасет нам не собрать, поэтому не стоит делать модель на основе CNN или иного алгоритма глубокого обучения, если у нас нет достаточного количества данных. В подобных случаях можно воспользоваться сложным алгоритмом однократного обучения, наподобие сиамской сети, которая может обучаться на меньшем количестве данных.
Читать полностью »

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

Как я построила прогнозную модель call-центра, чтобы их звонки не бесили пользователей - 1

Кстати, обо мне. Меня зовут Наташа, я работаю в Skyeng на позиции Data Scientist и вовлечена в разработку различных продуктов компании. Почему я заговорила о внезапных звонках? Общение голосом с клиентам, которые только хотят начать или по какой-то причине резко прервали обучение — часть модели работы в компании. Звонки помогают вовлечь и вернуть людей в процесс изучения языка, либо напрямую узнать, что же пошло не так. Одна из моих последних задач — анализ работы нашего колл-центра. Я помогла им подобрать оптимальное время для выхода на контакт со студентами по всей России и СНГ: потому что звонки в случайное время суток никто не любит, а бесить собственных пользователей — последнее дело.

Настроение людей в ходе таких звонков для нас крайне важно, потому что оно напрямую влияет на конверсию. Так что давайте я расскажу подробнее о том, как Skyeng звонит студентам и какую прогнозную модель я построила для того, чтобы нашим клиентам было хорошо и комфортно, а мы вышли на показатели конверсии в 60-70%.
Читать полностью »

Алгорейв: как программисты устраивают вечеринки - 1
Источник

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

Генеративная музыка — явление не новое. Известно, что даже нейросеть способна создавать музыку, которую сложно отличить от творчества талантливого композитора. Однако алгорейв имеет свои отличительные особенности.

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

Ура! Мы завершили формирование программы конференции UseData Conf 2019! Эта конференция для тех, кто решает практические задачи с помощью методов машинного обучения. Между идеальным алгоритмом в вакууме и его применением на реальных данных часто лежит пропасть. Мы хотим, чтобы те, кто умеет преодолевать эту пропасть, встретились и смогли обменяться опытом.

Что будет на конференции UseData Conf 2019? - 1

Магия машинного обучения для управленцев, истории применения ML для анализа эффективности рекламы в телевизоре, беспилотные игрушечные машинки, нефть и автомобильные номера — это лишь часть докладов на UseData 2019. Об этих и других темах подробнее под катом.
Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js