• Считаем кур, пока их не заклевали

    • Перевод
    Эта история началась с короткой статьи в New York Times о Люке Робитейле, 13-летнем школьнике из Юлесса, штат Техас, который выиграл Raytheon Mathcounts National Competition, правильно ответив на следующий вопрос:
    В амбаре кружком сидят 100 кур. Каждая из кур случайным образом клюёт свою ближайшую соседку слева или справа. Каково ожидаемое количество кур, которых никто не клюнул?
    Судя по статье Times, Робитейлу потребовалось на ответ меньше секунды.

    На следующий день Джордан Элленберг твитнул такую задачу:

    Text of Ellenberg's tweet: 100 chicks in a circle. Each pecks R or L at random. Pecked chicks don't peck. Iterate until no two unpecked chicks adjacent. How many left?

    «100 кур сидят в круге. Каждая клюёт случайным образом R или L. Клюнутые куры никого не клюют. Итерации проводятся до тех пор, пока не останется двух соседних неклюнутых кур. Сколько кур осталось?»

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

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

    • Перевод
    • Tutorial

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

    Читать дальше →
  • Главные достижения в области обработки естественного языка в 2017 году

    • Перевод

    Всем привет. Сразу поделим аудиторию на две части — тех, кто любит смотреть видео, и тех, кто, как я, лучше воспринимает тексты. Чтобы не томить первых, запись моего выступления на Дата-Ёлке:



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

    Читать дальше →
    • +61
    • 10,5k
    • 3
  • Проблемы эгоистов: дорожные пробки и парадокс Браеса

    • Перевод

    Строительство более широких дорог может ухудшить ситуацию с дорожным движением. Обычно этот контринтуитивный и контрпродуктивный результат объясняют следующим образом: чем больше дороги, тем более крупные торговые центры они привлекают, что в свою очередь привлекает больше автомобилей. Но это ещё не вся история. В 1960-х Дитрих Браес обнаружил теоретическую конфигурацию дорог, в которой строительство новой соединительной дороги может замедлить движение каждого, даже если количество машин остаётся постоянным. И наоборот, закрытие одной дороги в сети Браеса позволит всем добираться домой быстрее. Такое явление настолько странно, что заслуживает собственного определения — «Парадокс Браеса».

    Несколько лет назад Джоел Коэн сказал мне, что парадокс Браеса может стать хорошей темой для моей колонки в «Computing Science». Я засомневался. Опубликовано уже немало обсуждений этого парадокса, в том числе потрясающие статьи самого Коэна, а также книга Тима Рафгардена (обзор которой я написал для American Scientist). Я не считал, что смогу добавить что-то новое к дискуссии.

    Однако недавно я начал рассматривать задачу визуализации парадокса Браеса — представлении его таким образом, чтобы мы могли наблюдать отдельные автомобили, едущие через дорожную сеть, а не просто вычислять средние скорости и время в пути. Возможность поэкспериментировать с моделью — понажимать рычаги и кнопки, попробовать разные алгоритмы маршрутизации — может привести к более чёткому пониманию того, почему хорошо информированные и имеющие собственный интерес водители могут выбирать маршрут, который в результате тормозит всех.
    Читать дальше →
  • Как обучть мдль пнмть упртые скрщня

      Недавно я натолкнулся на вопрос на Stackoverflow, как восстанавливать исходные слова из сокращений: например, из wtrbtl получать water bottle, а из bsktballbasketball. В вопросе было дополнительное усложнение: полного словаря всех возможных исходных слов нет, т.е. алгоритм должен быть в состоянии придумывать новые слова.


      Вопрос меня заинтриговал, и я полез разбираться, какие алгоритмы и математика лежат в основе современных опечаточников (spell-checkers). Оказалось, что хороший опечаточник можно собрать из n-граммной языковой модели, модели вероятности искажений слов, и жадного алгоритма поиска по лучу (beam search). Вся конструкция вместе называется модель зашумлённого канала (noisy channel).


      Вооружившись этими знаниями и Питоном, я за вечер создал с нуля модельку, способную, обучившись на тексте "Властелина колец" (!), распознавать сокращения вполне современных спортивных терминов.


      Читать дальше →
    • Параллельная сортировка данных в GPU

      • Перевод


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

      GIF

      Введение


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

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


        Это заключительная часть статей о сверточных сетях. Перед прочтением рекомендую ознакомиться с первой и второй частями, в которых рассматриваются слои сети и принципы их работы, а также формулы, которые отвечают за обучение всей модели. Сегодня мы рассмотрим особенности и трудности, с которыми можно столкнуться при тестировании вручную написанной на python сверточной сети, применим написанную сеть к датасету MNIST и сравним полученные результаты с библиотекой tensorflow.
        Читать дальше →
        • +60
        • 12,1k
        • 8
      • Сверточная сеть на python. Часть 2. Вывод формул для обучения модели


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

          • Перевод

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

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

          Умножение методом русских крестьян


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

          Общее описание метода просто, но не слишком информативно. Тем не менее, давайте начнём с него.
          Читать дальше →
        • Рубрика «Читаем статьи за вас». Октябрь — Ноябрь 2017


            Привет, Хабр! По традиции, представляем вашему вниманию дюжину рецензий на научные статьи от членов сообщества Open Data Science из канала #article_essense. Хотите получать их раньше всех — вступайте в сообщество ODS!


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


            Статьи на сегодня:

            Читать дальше →
            • +61
            • 11,5k
            • 4
          Самое читаемое