Міхал Кузьміньскі: Більшість користувачів пошукових систем, мабуть, не знає, що існує теорія пошуку...

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

Пошукові системи - це насправді велетенські бази даних про вміст інтернету - і, крім того, неповні?

Сильно спрощуючи, їх роботу можна описати як використання «грубої сили»: постійне накопичення достатньо великого обсягу інформації, її впорядкування, індексування та організація достатньо швидкого до неї доступу. Останнє є особливо складним - для цього використовують дуже складні алгоритми індексування, запам’ятовування коротких шляхів, пошуку найбільш ймовірних швидких з’єднань і т.д. На задньому плані залишається ще величезна обчислювальна потужність комп’ютерів і їхня велетенська пам’ять. Вони помітно ростуть буквально щомісяця. Ферми серверів, які обслуговують пошукові системи, нині нагадують виробничі цехи.

Павел Парис, цьогорічний лауреат Нагороди згаданого вже Вітольда Ліпського, займається пошуком в XML-документах, рекурсією... Що це означає?

Звичайний - або навіть незвичайний - користувач бачить віконце, у яке вписує слово, і за мить отримує відповідь. Варто усвідомити, що вона з’являється після пошуку у величезній кількості сторінок. Причому це зовсім не відбувається за принципом їх прочісування одна за одною. Шукаючи щось у домашній бібліотеці, іноді ми витягуємо першу книжку, гортаємо, якщо вона нас влаштовує, ми відкладаємо її на купу, а якщо ні, то ставимо її назад на полицю, і беремо іншу...Таке лінійне прочісування інтернету тривало б вічно. І це буквально - йдеться про час, порівнюваний з астрономічним. 

Фокус в тому, як наївний, лінійний алгоритм пошуку замінити набагато складнішим і отримати бажані результати ще до кінця світу. 

Якщо правильно організувати збір даних, лінійний пошук можна замінити логарифмічним, набагато швидшим: коли я знаю, що книжки на полицях розташовані за датами видання, і я знаю рік видання книжки, яку шукаю, то я перевіряю книжки посередині полиці та намагаюся зрозуміти, де її знайду: праворуч чи ліворуч. Потім я переглядаю середину обраної половини... і я власне пояснив вам, що таке рекурсія: до обраної половини я застосував той самий алгоритм, що спочатку до цілого. 

Поняття рекурсії була відоме математикам, і досліджувалося ними задовго до нинішньої «епохи інформатики». Але інформатичні застосування рекурсії підкреслюють значення добрих рекурсивних алгоритмів. Розробка таких нестандартних алгоритмів для важких і важливих проблем - це часто справжнє мистецтво, з великим потенціалом застосування. Павел Парис займався проблемою швидкого знайдення відповідей на запитання, що стосуються даних, які зберігаються в XML-форматі, універсальним нині стандартом творення документів. Він запропонував нетривіальний, ефективний алгоритм, який потенційно може бути застосований у системах, які використовують щодня мільйони користувачів.

Іноді я сам не знаю точно, чого шукаю, а тут Google пропонує правильну відповідь, Facebook пропонує зафрендити колегу, якого я не бачив багато років... Звідки вони це знають?

Я застерігав би від використання слова «знання». Всі ці «знання» спираються на дуже прості насправді асоціації та на аналіз поведінки користувачів у минулому. Система перевіряє, які пошукові запити ви найчастіше робили, і порівнює з цими асоціаціями: якщо «Тарлєцкі», то, ймовірно, це інформатика, а якщо ви ще часто запитуєте про публікації науковців, на перше місце система підсуне перелік публікацій Тарлєцького.Т аким чином, система не стільки «знає», скільки «підозрює». 

А нетверді знання є одним з основних лих інтернету. Хтось сказав, що у мережі можна знайти все... тобто ще й всі дурниці. Нелегкою проблемою є виловлювання цих дурниць та їх оминання на користь інформації, що об’єктивно вартує уваги.

Чи можуть бути корисними алгоритми у визначенні цінності знайденої інформації?

Питання - що означає «цінність»? Чи йдеться про щось корисне для мене, чи радше про щось об’єктивно істинне? Для математика чи інформатика свідченням об’єктивної істини є формальне доведення. Вже протягом багатьох років будують бази даних, які накопичують теореми разом з їхніми повними, перевіреними формальними доведеннями. Варто тут згадати польську систему Mizar, яка інтенсивно розвивається. З’являються також системи підтримки формального доведення теорем та властивостей програм, які дедалі краще проявляють себе у практичних застосуваннях. 

Формальне доведення математичної теореми - це, звичайно, ідеал, але хотілося б бути впевненим, що набираючи у пошуковій системі запит про те, у якому році народився Шон Коннері, я отримаю відповідь, що це було... я не пам’ятаю...

Це момент, у який треба звернутися до пошукової системи.

... і я хотів би бути впевненим, що інформація, що це було у - подивимося ... - у 1930 році, є правдивою. Бо зазвичай між джерелами, які пропонує пошукова система, є суттєві відмінності. Ми отримуємо перелік джерел, з якого самі повинні обрати відповідне. Хотілося б, аби алгоритми пошукових систем вміли проводити аналіз зв’язків та суперечностей між різною інформацією. Ми повертаємося тут до теми баз даних з неповною або неточною інформацією. У таких випадках можна застосовувати - і іноді застосовують - статистичний аналіз надійності. 

Однією з найбільших проблем мережі є не те, як знайти інформацію, яка нам потрібна, а те, як перевірити, чи те, що ми знайшли, є надійним. Нині кожна з тисячі сторінок - результатів пошуку за запитом «Шон Коннері» має рівні права з іншими. Алгоритми ранжування сторінок, які зараз використовують, визначають порядок, у якому вони повинні бути показаними, мало чим можуть допомогти у цьому.

Це рейтинг за кількістю посилань на цю сторінку з інших сайтів, тобто рейтинг її популярності. Він ефективний?

Не завжди. В одному з університетів відмовилися від підручників - «адже є інтернет». Жалюгідний ефект цього рішення швидко позначився на рівні робіт студентів. Звідки вони могли знати, що рацію має викладач, що звертається до 50 осіб, а не автор з інтернету, на сторінку якого посилаються кілька тисяч інших?

Останні роки принесли надзвичайний розвиток послуг з пошуку. Розширюється пошук звуків та зображень: можна, наприклад, програти пошуковій системі SoundHound фрагмент пісні, а вона скаже вам, що це за твір, або показати зображення Google, а він знайде подібне. Що ще залишилося вигадати у цій галузі?

Якби я знав, то заробляв би великі гроші. Але у розвитку технологій такого типу немає нічого незвичайного. Не такими далекими є часи, коли інтернет був машиною для надсилання пошти, і лише для посвячених у його таємниці. У якийсь момент настав бум у галузі мережних технологій, наслідком якого було розміщення в мережі усілякої інформації. Причому вся ця інформація існує у цифровому вигляді - вона складається з рядків нулів і одиничок, які можна легко аналізувати, незалежно від того, чи кодують вони текст, зображення чи звуки. Що більше інформації було в мережі, то важливішим був її пошук, який, у свою чергу, став можливий завдяки збільшенню обчислювальної потужності серверів та пропускної здатності каналів. Адже важливим є не тільки те, що можна порахувати, але й те, скільки даних ми можемо передавати. 

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

Недарма ж я запитав раніше: «звідки пошукова система щось знає» - тому що ми схильні приписувати машинам поведінку, наміри, інтелект тощо. Але чи для пошуку використовують методи штучного інтелекту?

Ах, так - але у розумінні набагато точнішому, ніж у популярному уявленні. Я не люблю цього терміну, він позначає для мене розділ інформатики, що займається алгоритмами, які за своєю природою не є точними і не дають абсолютних результатів. Існують такі проблеми - математик чи інформатик скаже: «нерозв’язні проблеми» - для яких не може існувати алгоритму, який цілком їх розв’язує. Це не означає, що не можна робити спроб створити якнайкращий алгоритм, який, можливо, часто зможе дати доволі добру відповідь. 

На жаль, ми примирилися вже, що наші програми недосконалі. Наша улюблена операційна система час від часу висне, і ми навчилися жити з цим, благаючи лише, щоб це не сталося під час писання важливої статті. І для нерозв’язних проблем можна створити «недосконалі» алгоритми, які правильну відповідь даватимуть достатньо часто. Або ж достатньо рідко дадуть неправильну відповідь. Легко можна погодитися на те, щоб алгоритм передбачав правильно «лише» 495 разів з 500, чи завтра котування акцій підуть вгору чи вниз. Аналіз таких алгоритмів не полягає в оцінюванні «погано - добре», а у перевірці, чи будемо ми достатньо часто близькими до достатньо доброї відповіді.

Сайти соціальних мереж, а віднедавна також пошукові системи залучають тим часом до пошуку людський інтелект. Позначення користувачем на світлинах своїх друзів вони використовують для навчання алгоритмів, що розпізнають обличчя. Або навіть ставлять користувачу запитання: «чи ця відповідь була правильною?».

По-перше - це теж класика. Взаємодія з людиною, яка знає щось краще, ніж щойно збудована система - це нормальний метод здобування знань. 

По-друге, тут працюють дуже цікаві класи алгоритмів, що навчаються, які змінюють свою структуру - йдеться, наприклад, про так звані генетичні алгоритми, нейронні мережі або «мурашкові» алгоритми, що спираються на поведінку людей у натовпі. Тому остаточну структуру надання відповіді вони будують у певному сенсі у випадковий спосіб. Навіть у випадку генетичних алгоритмів, для того, щоб знайти найкраще рішення, обирається випадковим чином множина об’єктів, яка може ним бути, і перевіряється, чи так є насправді. Якщо ні, то ці об’єкти трохи змінюються, також випадковим чином, і перевіряється знову, чи після змін ми стали ближчими до рішення.

Як в еволюції?

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

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

А зразки дають власне користувачі?

Залежно від галузі та застосування. Розпізнавання обличчя на Facebook - це щось зовсім тривіальне у порівнянні зі системами підтримки діагностування для лікарів. Тут функції оцінки перевіряють на реальних базах людських захворювань. А це вже набагато серйозніша справа, ніж те, чи Facebook або Picasa навчаться правильно розпізнавати обличчя чийогось друга. Багато технологій, які починають нині служити користувачам щодня, виводяться із серйозних наукових робіт, над якими працювали, даю слово честі, не думаючи про Facebook.

Наша праця, взаємовідносини і повсякденні дії залежать від роботи машин, принципи функціонування яких ми не може собі уявити. Пояснення того, як працює паровий двигун, було, ймовірно, легшим від пояснення того, як працює процесор. Чи хвилює вас дефіцит розуміння користувачем технологій?

Хоча для нас нині у розумінні принципу роботи парового двигуна немає нічого особливого, ми пам’ятаємо, що колись таких машин не було, і треба було ще їх винайти. А локомотив - це не лише головна ідея дії на поршень пари під тиском, але й також тисячі високоточних деталей, зроблених так, а не інакше - і тут ми вже не знаємо, чому. Крім того, ровер теж начебто є простою машиною, але пропорції і розміри його елементів є продуктом праці фахівців з фізіології, медицини, механіки. Загалом, ми знаємо, як працює передача, але поняття не маємо, чи у вальниці [підшипнику] має бути чи 13, чи 17 кульок. Проте, я не відчуваю себе цим стривоженим - я вірю, що над кожним процесором, і над кожним гвинтом, яким я користуюся, працювали люди, які знаються на цьому. А те, що знання, необхідні для створення машин, які супроводжують нас нині, стають дедалі складнішими, випливає просто з їх величезного розвитку.

Ми живемо також у час, коли точна математика - фундамент наших технологій - породила гуманітарні чи соціологічні явища: вона вплинула не тільки на якість заняття наукою, але й на соціальні комунікації, міжособистісні стосунки...

Але у цьому немає нічого дивного! Нові інструменти відкривають нові можливості. У 1983 році я вів тривалу дискусію з подружжям митців - про те, чи на екрані комп’ютера можна створювати реалістичні зображення. Я тоді обстоював погляд, що так, який тепер є очевидним і для тодішніх моїх опонентів. І пензлем на полотні, і мишею на комп’ютері можна створювати як великі твори, так і кітч.

Але інструменти також впливають на нас. Нещодавно Science опублікував статтю про так званий ефект Google: ми нині менше - і точно інакше - запам’ятовуємо, делегуючи пошуковій системі завдання, якими, зазвичай, займалася наша пам’ять. Ми не повинні пам’ятати, тому що в нас під рукою є Google.

«Іліаду» спочатку могли повторювати усно, лише потім її записали, а ще пізніше відтворювали у друкованому вигляді. Технологія її поширення змінювалася. Те, що ми вважаємо знаннями, необхідними для збереження у голові, теж змінювалося протягом століть. 

Я хотів би зараз могти сказати, що оскільки зараз для нас є легкодоступними рутинні знання, проста інформація, то більше місця ми залишаємо собі для креативного інтелекту. Але це не завжди правда. Зі мною трапилося - на щастя, не у Польщі - що, коли я мав заплатити 10,25 фунта, то дав банкноту у 20 фунтів та 25 пенсів, а касирка ніяк не могла перестати дивуватися тому, що комп’ютер наказав їй видати таку рівну решту. 

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

Бо якщо ми всі захочемо користуватися Вікіпедією, її не буде кому писати?

Вікіпедією ми користовуємося у галузях, в яких ми не можемо до неї писати, натомість, ми пишемо до неї у тих галузях, в яких нашими знаннями можуть скористатися інші. Ми дедалі більше спеціалізуємося не тому, що стаємо дедалі дурнішими та в нас звужується світогляд, а лише тому, що так сильно множиться обсяг знань. 

На переломі 1970-х і 1980-х, коли я починав свої пригоди з інформатикою, в мене складалося враження, що я розумію практично кожну лекцію, і можу орієнтуватися у будь-якій темі. Нині вже не можна бути настільки зарозумілим. Інформатика розрослася неймовірно, а дистанція від початку навчання до проблем, які розв’язує, наприклад, Павел Парис, є величезною - але це не означає, що її не можна швидко подолати. Приклад лауреатів Нагороди ім. Ліпського найкраще про це свідчить.

У Польщі є чудові молоді інформатики. Чого нам бракує, щоб над Віслою виросла друга Кремнієва долина?

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

Більше того, у світі також не завжди перемагають найкращі ідеї, і вони не завжди створюють стандарти, якими нам всім доводиться користуватися... 

Безперечно, в нас є чудові студенти, хоча дистанція, про яку я щойно казав, збільшується в обох напрямках. Середній рівень математичних та інформатичних знань, які молоді люди виносять зі школи, є, м’яко кажучи, поганим. При цьому я не кажу тут про так звану «інформатику», яку розуміють як вміння користуватися комп’ютером і з якою сучасна молодь майже народжується, а про точні математичні знання, навички абстрактного мислення та розв’язання проблем. Хоча середній рівень і змінюється, на щастя, залишаються лідери: щороку на нашому факультеті математики, інформатики та механіки Варшавського університету починає навчання група з декількох десятків молодих людей, які зможуть завоювати світ. Це не випадковість - ми завдячуємо цим цілій системі, яка функціонує завдяки групі ентузіастів: це олімпіади з предметів, перш за все з інформатики та математики, такі ініціативи, як «Алгоритмічні бої», конкурси для молодих студентів чи стипендії Національного фонду допомоги дітям. Це дозволяє заразити молодих людей інформатикою, а потім успішно займатися ними. 

Чудово, що багато з них потім присвячує свій талант, ентузіазм і працю дослідженням у галузі інформатики. Найкращі з них, як-от лауреати Нагороди ім. Ліпського попередніх років, можуть похвалитися помітним у світі науковим доробком, проводять дослідження і досягають результатів на найвищому світовому рівні - беруть участь у великому розвитку інформатики у всіх, зокрема й дуже практичних її аспектах.

Професор Анджей Тарлєцкі є інформатиком, працює у Варшавському університеті та Інституті основ інформатики Польської академії наук. Займається математичними основами інформатики та їх застосування для створення програмного забезпечення найвищої якості.Автор понад 70 наукових робіт, член Academia Europea. Голова комітету Нагороди ім. Вітольда Ліпського для молодих науковців у галузі інформатики.

Розмовляв Міхал Кузьміньскі

Автор: Анджей Тарлєцкі [Andrzej Tarlecki]

Назва оригіналу: Algorytm wyrabia sobie opinię

Джерело: Tygodnik Powszechny, 06.12.2011

Зреферував Омелян Радимський, Zaхідна аналітична група

Фото - ladymaksima.com