Вчені винайшли новий спосіб підрахунку речей (так, їх насправді більше, ніж один)

Здається, доволі легко осмислити те, що існують різні способи підрахунку речей. Дещо незрозумілішим видається те, що при всіх досягненнях науки та технологій, ми не знали усіх способів підрахунку й продовжуємо їх відкривати. Ось нещодавно дослідники виявили новий спосіб підрахунку, і його не можна назвати якимось витонченим чи надзвичайно складним, щоб людство не помічало його так довго.

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

Деталі

Група комп'ютерників наткнулася на цей метод, шукаючи відповідь на просте питання: скільки переді мною різних речей? Видається не дуже науковим питанням, так? Але відповідь на нього цікавіша й розумніша, ніж може здатися на перший погляд.

Зі стрімким розвитком штучного інтелекту комп'ютери можуть здаватися нам дуже розумними, у певному розумінні, але насправді це не завжди так. Іноді те, що для нас є найпростішим, для комп'ютера може здаватись чимось надскладним. Серед таких проблем й підрахунок об'єктів. Ми просто дивимось на набір предметів, і наш мозок автоматично сортує їх у групи. У цей момент ШІ шоковано запитує: "як ти це робиш, шкіряний геній?".

Для комп’ютерів підрахунок є фундаментальною проблемою, яка існує десятиліттями (мова не про калькулятори, а про лічбу об'єктів). І це питання, яке справді потребує відповіді, оскільки його застосування в сучасному світі охоплює все: від аналізу мережевого трафіку (наприклад, Facebook або Twitter відстежують, скільки людей увійшли в систему в будь-який момент часу), до виявлення шахрайства, біоінформатики та аналізу тексту.

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

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

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

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

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

У другому раунді все трохи складніше: замість одного орла, щоб зберегти слово в списку, вам знадобляться два підряд – будь-який інший варіант, і воно буде видалено. Так само, у третьому раунді вам потрібно буде отримати три орла поспіль, щоб слово залишилося; у четвертому раунді знадобляться чотири підряд, і так далі, поки не дійдете до кінця "Гамлета".

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

Точність збільшується, якщо у вас достатньо пам'яті, щоб зберігати понад 100 слів. Маючи можливість зберігати 1000 слів, алгоритм оцінює відповідь як 3964, а це лише на 3 менше, ніж правильна відповідь.

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

Раніше ми повідомляли, що NASA планує використовувати Сонце як гігантський телескоп. Це може здатися ідеєю з наукової фантастики, але таке використання нашої зорі пропонував ще Альберт Айнштайн.