Ученые изобрели новый способ подсчета вещей (да, их на самом деле больше, чем один)

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

• Чрезвычайно далеко от полюсов: почему северное сияние было заметно в Украине

Детали

Группа компьютерщиков наткнулась на этот метод, ища ответ на простой вопрос: сколько передо мной разных вещей? Кажется не очень научным вопросом, да? Но ответ на него интереснее и умнее, чем может показаться на первый взгляд.

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

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

Теперь, очевидно, компьютеры научились считать вещи, и это потому, что на этот вопрос подсчета, известный как проблема разных элементов, есть ответы. Они просто не очень хорошие. Профессор Школы вычислительной техники Университета Небраски-Линкольна Винодчандран Вариям отмечает, что все ранее известные алгоритмы были "на основе хеширования", и качество этого алгоритма зависело от качества хеш-функций, которые выбирает алгоритм.

Но вместе с коллегами Суравом Чакраборти из Индийского статистического института и Кулдипом Милом из Университета Торонто он нашел способ значительно упростить проблему.

Новый метод, названный алгоритмом CVM в честь его изобретателей, резко уменьшает требования к памяти – важное преимущество в современную эпоху больших данных, и делает это с помощью хитрого приема теории вероятностей. Ученые предлагают пример для иллюстрирования концепции: представьте, что вы подсчитываете количество уникальных слов в шекспировском "Гамлете", но у вас достаточно памяти только для хранения 100 слов одновременно.

Сначала вы, очевидно, запишете первые 100 уникальных слов, которые вам попадаются. У вас закончилось место на жестком диске, поэтому вы берете монету и подбрасываете ее за каждое слово в вашем списке. Орел – запомнили, решка – забыли.

В конце этого процесса в вашем списке будет около 50 уникальных слов. Вы перезапускаете процесс сначала, но на этот раз, если вы находите слово, уже имеющееся в списке, вы снова подбрасываете монету, чтобы увидеть, удалять его или нет. Когда вы достигнете 100 слов, вы снова пересматриваете список, подбрасывая монету за каждое слово, удаляя или сохраняя его.

Во втором раунде все немного сложнее: вместо одного орла, чтобы сохранить слово в списке, вам понадобятся два подряд – любой другой вариант и оно будет удалено. Так же, в третьем раунде вам нужно будет получить три орла подряд, чтобы слово осталось; в четвертом раунде понадобятся четыре подряд, и так далее, пока не дойдете до конца "Гамлета".

Обработав текст таким образом, вы убедились, что каждое слово в вашем списке имело одинаковую вероятность быть там: 1/2 в степени k, где k – это количество раз, которые вам пришлось проработать список. Итак, предположим, что вам понадобилось шесть раундов, чтобы дойти до конца "Гамлета", и у вас остался список из 61 слова: затем вы можете умножить 61 на 2 в шестой степени, чтобы получить примерное количество слов. Вы получите ответ 3904 при том, что фактический ответ 3967 (да, исследователи пересчитали это "ручками", при том, что всего в "Гамлете" более 30 тысяч слов).

Точность увеличивается, если у вас достаточно памяти для сохранения более 100 слов. Имея возможность сохранять 1000 слов, алгоритм оценивает ответ как 3964, а это всего на 3 меньше, чем правильный ответ.

Следовательно, это эффективно, но еще больше интригует его простота. Такой алгоритм подсчета привлек внимание многих экспертов отрасли, которые удивлены, что его не было открыто ранее.

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