• Автоэнкодеры и сильный искусственный интеллект

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

      В статье предложен оригинальный математический аппарат «набор автоэнкодеров с общим латентным пространством», который позволяет выделять абстрактные понятия из входных данных и демонстрирует способность к «one-shot learning». Кроме того, с его помощью можно преодолеть многие фундаментальные проблемы современных алгоритмов машинного обучения, основанных на многослойных сетях и подходе «Deep learning».
      Читать дальше →
    • Как писать программы на стыке мобильной разработки и алгоритмов? Конкурс и истории Яндекса

        С 10 по 22 сентября пройдет конкурс Яндекс.Блиц по мобильной разработке. Регистрация открыта. Блиц — это короткий путь в Яндекс: участникам топ-5 будет достаточно успешно пройти одну секцию собеседования вместо стандартных четырех, чтобы получить предложение по работе.

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



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

        Читать дальше →
        • +27
        • 4,4k
        • 1
      • Бесконечная алгоритмическая мелодия на основе простых чисел

          image

          Привет, Хабр! В прошлой статье «бесконечный узор на основе простых чисел» я рассказал про алгоритм, который позволяет генерировать бесконечные красивые узоры, похожие то ли на инопланетные рисунки, то ли на нечто технологическое, подобно устройству микросхем. Однако, алгоритм для генерирования 2D узоров можно так же использовать и для создания мелодий. Подробнее под катом.
          Читать дальше →
        • Многорукие бандиты в рекомендациях

            Всем привет! Меня зовут Миша Каменщиков, я занимаюсь Data Science и разработкой микросервисов в команде рекомендаций Авито. В этой статье я расскажу про наши рекомендации похожих объявлений и о том, как мы улучшаем их при помощи многоруких бандитов. С докладом на эту тему я выступал на конференции Highload++ Siberia и на мероприятии «Data & Science: Маркетинг».


            image
            Читать дальше →
            • +40
            • 5,2k
            • 4
          • Дротики, кости и монеты: алгоритмы выборки из дискретного распределения

            • Перевод

            Однажды я задал на Stack Overflow вопрос о структуре данных для шулерских игральных костей. В частности, меня интересовал ответ на такой вопрос: «Если у нас есть n-гранная кость, у грани которой i есть вероятность выпадения pi. Какова наиболее эффективная структура данных для симуляции бросков такой кости?»

            Такую структуру данных можно использовать для многих задач. Например, можно применять её для симуляции бросков честной шестигранной кости, присвоив вероятность $\frac{1}{6}$ каждой из сторон кости, или для симуляции честной монетки имитацией двусторонней кости, вероятность выпадения каждой из сторон которой равна $\frac{1}{2}$. Также можно использовать эту структуру данных для непосредственной симуляции суммы двух честных шестигранных костей, создав 11-гранную кость (с гранями 2, 3, 4, ..., 12), каждая грань которой имеет вес вероятности, соответствующий броскам двух честных костей. Однако можно также использовать эту структуру данных и для симуляции шулерских костей. Например, если вы играете в «крэпс» с костью, которая, как вы точно знаете, не идеально честная, то можно использовать эту структуру данных для симуляции множества бросков костей и анализа оптимальной стратегии. Также можно попробовать симулировать аналогичным образом неидеальное колесо рулетки.

            Если выйти за пределы игр, то можно применить эту структуру данных в симуляции роботов, датчики которых имеют известные уровни отказа. Например, если датчик дальности имеет 95-процентную вероятность возврата правильного значения, 4-процентную вероятность слишком маленького значения, и 1-процентную вероятность слишком большого значения, то можно использовать эту структуру данных для симуляции считывания показаний датчика генерацией случайного результата и симуляцией считывания датчиком этого результата.
            Читать дальше →
          • Как мы в «1С: Предприятии» решаем системы алгебраических уравнений

              Работа с числовыми матрицами в целом и решение систем линейных алгебраических уравнений в частности — классическая математическая и алгоритмическая задача, широко используемая при моделировании и расчёте огромного класса бизнес-процессов (например, при расчёте себестоимости). При создании и эксплуатации конфигураций «1С:Предприятия» многие разработчики сталкивались с необходимостью вручную реализовывать алгоритмы расчёта СЛАУ, а после — с проблемой длительного ожидания решения.

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

              Он оптимизирован для использования на данных, имеющих разреженную структуру (то есть содержащие не более 10% ненулевых коэффициентов в уравнениях) и в среднем и в лучшем случаях демонстрирует асимптотику Θ(n⋅log(n)⋅log(n)), где n — количество переменных, а в худшем (при заполненности системы ~100%) его асимптотика сопоставима с классическими алгоритмами ( Θ(n3)). При этом на системах, имеющих ~105 неизвестных, алгоритм показывает ускорение в сотни раз по сравнению с реализованными в специализированных библиотеках линейной алгебры (например, superlu или lapack).

              image
              Важно: статья и описанный алгоритм требуют понимания линейной алгебры и теории графов на уровне первого курса университета.
              Читать дальше →
            • Ой, у вас баннер убежал!

              Ну. И что?
              Реклама
            • Построение орбит небесных тел средствами Python



                Системы отсчёта для определения орбиты


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

                Используя данное предположение, рассмотрим движение одной и той же точки в двух различных системах отсчета К и К', из которых вторая движется относительно первой с произвольной скоростью — радиус-вектор, описывающий положение точки начала системы координат К' относительно системы отсчета К).

                Будем описывать движение точки в системе К' радиус-вектором , направленным из начала координат системы К' в текущее положение точки. Тогда движение рассматриваемой точки относительно системы отсчета К описывается радиус-вектором :

                (1)

                а относительная скорость

                (2)
                Читать дальше →
              • КлассикAI жанра: ML ищет себя в поэзии

                  image Сейчас в прессе часто встречаются новости вида “AI научился писать в стиле автора Х”, или “ML создает искусство”. Посмотрев на это, мы решили – было бы здорово, если эти громкие заявления можно было бы проверить на деле.

                  Можно ли устроить борьбу ботов по написанию стихотворений? Можно ли сделать из этого понятную и воспроизводимую соревновательную историю? Теперь можно точно сказать, что это возможно. А о том, как написать свой первый алгоритм по генерации стихотворений, читайте дальше.
                  Читать дальше →
                • Книга «Алгоритмы и структуры данных. Извлечение информации на языке Java»

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

                    • Научитесь работать со структурами данных, например, со списками и словарями, разберитесь, как они работают.
                    • Напишите приложение, которое читает страницы Википедии, выполняет синтаксический разбор и обеспечивает навигацию по полученному дереву данных.
                    • Анализируйте код и учитесь прогнозировать, как быстро он будет работать и сколько памяти при этом потреблять.
                    • Пишите классы, реализующие интерфейс Map, пользуйтесь при этом хеш-таблицей и двоичным деревом поиска.
                    • Создайте простой веб-поисковик с собственным поисковым роботом: он будет индексировать веб-страницы, сохранять их содержимое и возвращать нужные результаты.
                    Читать дальше →
                  • Поиск объекта на изображении при помощи перцептивного хэша

                      image

                      В те времена, когда я еще верил, что программируя для себя на обеденном перерыве или после работы, можно создать свой стартап, у меня был один проект. И проект требовал такого алгоритма поиска объекта на изображении, чтобы и обучить его было быстро на новый объект, и чтобы он много вычислительных ресурсов не потреблял. Почитав статьи про перцептивный хэш (раз статья и два), я решил, а почему бы не использовать его для ограничения количества исследуемых областей изображения? И начал строить свой велосипед, вместо того чтобы использовать признаки Хаара. использовать перцептивный хэш, как фильтр областей изображения, чтобы после фильтра оставались лишь те участки, где вероятнее всего находится искомый объект. В конце статьи есть ссылка на код на C++ с использованием библиотеки OpenCV.
                      Читать дальше →
                    • Численные методы решения систем нелинейных уравнений

                        Введение


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

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

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

                        (1)

                        Обозначим через вектор неизвестных и определим вектор-функцию Тогда система (1) записывается в виде уравнения:

                        (2)

                        Теперь вернёмся к всеми любимому Python и отметим его первенство среди языков программирования, которые хотят изучать [1].



                        Этот факт является дополнительным стимулом рассмотрения числительных методов именно на Python. Однако, среди любителей Python бытует мнение, что специальные библиотечные функции, такие как scipy.optimize.root, spsolve_trianular, newton_krylov, являются самым лучшим выбором для решения задач численными методами.

                        С этим трудно не согласится хотя бы потому, что в том числе и разнообразие модулей подняло Python на вершину популярности. Однако, существуют случаи, когда даже при поверхностном рассмотрении использование прямых известных методов без применения специальных функций библиотеки SciPy тоже дают неплохие результаты. Иными словами, новое- это хорошо забытое старое.
                        Читать дальше →
                      • Решение цветных японских кроссвордов со скоростью света

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


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


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


                          Читать дальше →
                        • О формировании последовательностей в гипотезе Коллатца ( 3n+1 )

                            Меня привлекают такие задачи, как проблема Коллатца. Они просты в формулировке и отлично тренируют голову, в особенности алгоритмического мышления, что очень полезно программисту.

                            Формулируется задача довольно просто:
                            Берём любое натуральное число n. Если оно чётное, то делим его на 2, а если нечётное, то умножаем на 3 и прибавляем 1 (получаем 3n + 1). Над полученным числом выполняем те же самые действия, и так далее.

                            Гипотеза Коллатца заключается в том, что какое бы начальное число n мы ни взяли, рано или поздно мы получим единицу.

                            Алгоритмически это выглядит так:

                            while (number > 1) {
                            	if (number % 2 === 0) number = number / 2;
                            	else number = 3 * number +1;
                            }
                            
                            Читать дальше →
                          • Численные методы решения уравнений эллиптического типа

                              Введение


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

                              Для решения эллиптических уравнений в случае нескольких измерений используют численные методы, позволяющие преобразовать дифференциальные уравнения или их системы в системы алгебраических уравнений. Точность решения опреде­ляется шагом координатной сетки, количеством итераций и разрядной сеткой компьютера [1]

                              Цель публикации получить решение уравнения Пуассона для граничных условий Дирихле и Неймана, исследовать сходимость релаксационного метода решения на примерах.
                              Читать дальше →
                              • +13
                              • 2,3k
                              • 5
                            • Управляемые токенами реестры 1.0

                              • Перевод


                              Идея управляемых токенами реестров (TCR) зародилась в блокчейн-сообществе не менее года назад. По крайней мере, эта статья была опубликована автором еще в сентябре 2017 года. А недавно я был на конференции DappCon 2018 в Берлине и увидел большой интерес к этой теме, а также несколько ранних набросков на основе TCR. Поэтому предполагаю, что пик интереса еще впереди.


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

                              Читать дальше →
                            • CRDT: Conflict-free Replicated Data Types


                                Как считать хиты страницы google.com? А как хранить счётчик лайков очень популярных пользователей? В этой статье предлагается рассмотреть решение этих задач с помощью CRDT (Conflict-free Replicated Data Types, что по-русски переводится примерно как Бесконфликтные реплицированные типы данных), а в более общем случае — задачи синхронизации реплик в распределённой системе с несколькими ведущими узлами.
                                Читать дальше →
                              • Учим Искусственный Интеллект играть в игру

                                Доброго времени суток, дорогой читатель!

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



                                Примечание: данная статья не объясняет термин "нейронная сеть" и всё, что с ним связано, а также не предоставляет базовую информацию об обучении сети методом трассировки. Рекомендуем кратко ознакомиться с этими понятиями до прочтения статьи
                                Читать дальше →
                                • +17
                                • 6,2k
                                • 6
                              • Динамическое программирование в олимпиадных задачах

                                  Привет!

                                  Недавно решал задачи с архива Timus Online Judge и наткнулся на раздел под названием задачи динамического программирования. Задачи такого типа вызывают у меня особый интерес, потому что зачастую такой подход обеспечивает быстроту и элегантность решения. Что же такое — динамическое программирование?

                                  Динамическое программирование — это подход к решению задач, при котором происходит разбиение на подзадачи, которые «проще» в сравнении с исходной. Слово «динамический» близко по значению к «индуктивный»: предполагается, что известен ответ для какого-то значения $k$, и хочется найти ответ для $k+1$. В математике это называется индуктивным переходом, и составляет основную идею динамического программирования.

                                  Простые примеры


                                  Наиболее яркой и показательной задачей является задача вычисления $n$-ого числа последовательности Фибоначчи.
                                  Читать дальше →
                                  • +11
                                  • 4,6k
                                  • 3
                                • Прореживание таймфреймов (криптовалюты, форекс, биржи)

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

                                  Формулировка задачи: данные поступают на вход с интервалом в 1 секунду в таком формате:

                                  • Название инструмента (код пары USDEUR и пр.),
                                  • Дата и время в формате unix time,
                                  • Open value (цена первой сделки в интервале),
                                  • High value (максимальная цена),
                                  • Low value (минимальная цена),
                                  • Close value (цена последней сделки),
                                  • Volume (громкость, или объём сделки).

                                  Необходимо обеспечить пересчёт и синхронизацию данных в таблицах: 5 сек, 15 сек, 1 мин, 5 мин, 15 мин, и т.д.

                                  Описанный формат хранения данных имеет название OHLC, или OHLCV (Open, High, Low, Close, Volume). Он применяется часто, по нему сразу можно построить график «Японские свечи».

                                  image

                                  Под катом я описал все варианты, какие смог придумать, как можно прореживать (укрупнять) полученные данные, для анализа, например, зимнего скачка цены биткоина, а по полученным данным вы сразу построите график «Японские свечи» (в MS Excel такой график тоже есть). На картинке выше этот график построен для таймфрейма «1 месяц», для инструмента «bitstampUSD». Белое тело свечи означает рост цены в интервале, чёрное — снижение цены, верхний и нижние фитили означают максимальную и минимальную цены, которые достигались в интервале. Фон — объём сделок. Хорошо видно, что в декабре 2017 цена вплотную приблизилась к отметке 20К.

                                  Решение будет приведено для двух движков БД, для Oracle и MS SQL, что, в некотором роде, даст возможность сравнить их на этой конкретной задаче (обобщать сравнение на другие задачи мы не будем).
                                  Читать дальше →
                                • Процедурная генерация уровней


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


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


                                    Внимание! Под катом много текста и "жирных" гифок.

                                    Читать дальше →
                                  Самое читаемое