Наука – чудовий інструмент для інновацій та покращення нашого життя, але давайте подивимося правді в очі: є речі, які ми знаємо напевно. Наприклад, ви не очікуєте, що ми зможемо вдосконалити щось на кшталт лічби.
Тож не дивно, що група комп’ютерних вчених зробила саме це: вони знайшли новий спосіб вирішити десятиліттями стару проблему, яка, на перший погляд, виглядає дуже просто – скільки різних речей переді мною?
Це складніша проблема – і розумніше рішення, ніж ви можете собі уявити.
Проблема з окремими елементами
Комп’ютери можуть бути дуже розумними, але вони також можуть бути дуже, дуже… нерозумними. Погляньте на нещодавній вибух чат-ботів зі штучним інтелектом, щоб переконатися в цьому: вони чудово виглядають розумними, але перевірте їх на практиці, і ви можете просто опинитися в уроборосі лайна.
А іноді саме ті речі, які здаються людині майже до смішного простими, спричиняють найбільше неприємностей. Візьмемо, наприклад, лічбу – а точніше, лічбу окремих предметів. Для нас це легко: ми дивимося на колекцію предметів, і наш мозок просто автоматично сортує їх по групах за нас. Нам майже не доводиться над цим працювати.
Для комп’ютерів, з іншого боку, це фундаментальна проблема, яка існує десятиліттями. І вона дійсно потребує відповіді, оскільки її застосування в сучасному світі охоплює все: від аналізу мережевого трафіку – згадайте, як Facebook чи Twitter відстежують, скільки людей залогінено в будь-який момент часу – до виявлення шахрайства, біоінформатики, аналізу текстів і багато чого іншого.
Очевидно, що ми вже давно можемо робити ці речі, і це тому, що на це питання підрахунку – відоме як проблема окремих елементів – є відповіді. Вони просто не дуже хороші.
“Раніше відомі алгоритми були “хешуванням”, і якість алгоритму залежала від якості хеш-функцій, які він обирає”, – пояснив Вінодчандран Варіям (Vinodchandran Variyam), професор Школи обчислювальної техніки Університету Небраски-Лінкольна, у своїй минулорічній заяві.
Але разом з колегами Суравом Чакраборті з Індійського статистичного інституту та Кулдіпом Мілом з Університету Торонто він знайшов спосіб значно спростити проблему: “Новий алгоритм використовує лише стратегію вибірки, а аналіз якості можна зробити за допомогою елементарних методів”.
Як це працює?
Новий метод, названий алгоритмом CVM на честь його винахідників, різко зменшує вимоги до пам’яті – важлива перевага в наш час великих даних – і робить це за допомогою хитрого трюку з теорії ймовірностей. Щоб проілюструвати цю концепцію, розглянемо приклад, який вивчали Варіям і його колеги, а також нещодавню статтю в журналі Quanta: уявіть, що ви підраховуєте кількість унікальних слів у шекспірівському “Гамлеті”, але пам’яті у вас вистачає лише на 100 слів за раз.
Спочатку ви робите очевидне: записуєте перші 100 унікальних слів, які вам трапляються. Тепер у вас немає місця – тому ви берете монетку і підкидаєте її для кожного слова. Орел – воно залишається, решка – ви його забуваєте.
Наприкінці цього процесу у вашому списку буде близько 50 унікальних слів. Ви починаєте процес з початку – але цього разу, якщо ви дійшли до слова, яке вже є у списку, ви знову підкидаєте монетку, щоб зрозуміти, видаляти його чи ні. Коли ви досягнете 100 слів, ви знову пробіжитеся по списку, підкидаючи монетку для кожного слова і видаляючи або зберігаючи його відповідно до підказки.
У другому раунді все трохи складніше: замість однієї голови, щоб зберегти слово у списку, вам знадобиться дві поспіль – якщо ви помилитеся, слово буде видалено. Аналогічно, у третьому раунді вам потрібно буде зібрати три голови підряд, щоб воно залишилося; у четвертому раунді – чотири голови підряд, і так далі, поки ви не дійдете до кінця “Гамлета”.
У божевіллі є метод – і він до того ж розумний. Опрацьовуючи текст таким чином, ви переконалися, що кожне слово у вашому списку має однакову ймовірність потрапити туди: 1/2k, де k – кількість разів, яку вам довелося опрацьовувати список. Отже, припустимо, вам знадобилося шість раундів, щоб дійти до кінця “Гамлета”, і у вас залишився список з 61 окремого слова: ви можете помножити 61 на 26, щоб отримати приблизну кількість слів.
Ми позбавимо вас необхідності відкривати калькулятор: відповідь – 3,904, а за словами Варіяма і Ко, фактична відповідь – 3,967 (так, вони порахували). Якщо у вас є пам’ять, яка може зберігати більше 100 слів, точність зростає ще більше: при здатності зберігати 1,000 слів алгоритм оцінює відповідь як 3,964 – вже майже без похибки округлення – і “звичайно, – сказав Варіям в інтерв’ю Quanta, – якщо [пам’ять] настільки велика, що вміщує всі слова, то ми можемо отримати 100-відсоткову точність.”
Простий підхід
Отже, він ефективний – але що робить алгоритм ще більш інтригуючим, так це його простота. “Новий алгоритм напрочуд простий і його легко реалізувати, – розповів Quanta Ендрю МакГрегор, професор Коледжу інформаційних та комп’ютерних наук Массачусетського університету в Амхерсті. “Я не здивуюся, якщо це стане стандартним способом вирішення проблеми [окремих елементів] на практиці”.
Дійсно, з моменту публікації в січні 2023 року – і за винятком кількох незначних зауважень і помилок – алгоритм привернув увагу і захоплення багатьох інших комп’ютерних вчених. Це означає, що, хоча стаття, яка описує алгоритм, не була рецензована в офіційному сенсі, вона, безумовно, була переглянута колегами. Так, Дональд Кнут, автор книги “Мистецтво комп’ютерного програмування” і так званий “батько аналізу алгоритмів”, написав статтю з похвалою алгоритму ще в травні 2023 року: “Відтоді, як я його побачив […], я не можу втриматися від спроб пояснити його ідеї майже кожному, кого я зустрічаю”, – коментував він.
Тим часом, різні команди, включаючи Чакраборті, Варіяма та Міла, провели останній рік, досліджуючи та допрацьовуючи алгоритм. Дехто, за словами Варіяма, вже викладає його на своїх курсах інформатики.
“Ми вважаємо, що це буде основний алгоритм, який вивчатиметься в першому курсі інформатики, присвяченому алгоритмам загалом і ймовірнісному алгоритму зокрема”, – сказав він. Кнут погоджується: “Він чудово підходить для навчання студентів, які вивчають основи інформатики”, – написав він у своїй травневій статті. “Я майже впевнений, що щось подібне з часом стане стандартною темою підручників”.
Як же такий проривний алгоритм так довго залишався непоміченим? На думку Варіяма, це не так малоймовірно, як здається.
“Дивно, що цей простий алгоритм не був відкритий раніше, – каже він. “У науці не рідкість, коли простоту не помічають протягом кількох років”.
