Щоразу, коли ми включаємо телефон і дивимося в камеру, йому доводиться вирішувати складну задачу: зрозуміти, чи його господар зараз намагається його включити. По суті, це один з найближчих нам зараз прикладів завдання розпізнавання образів. Її можна сформулювати так: нехай у нас є велика бібліотека фотографій осіб різних людей в різних ракурсах. Як за новою фотографією обличчя визначити, чи належить вона комусь із людей у бібліотеці, і якщо так, то кому саме? Математик Денис Федосєєв з мехмату МДУ і його колеги спробували з'ясувати, якою розмірністю має бути простір ознак, які дозволять відрізнити Вупі Голдберг від Шона Коннері.
Щоб вирішувати завдання розпізнавання облич за допомогою комп'ютера, потрібно спершу закодувати фотознімки якимось зрозумілим комп'ютеру методом. Звичайно, кожна картинка в пам'яті комп'ютера вже представлена деяким кодом - наприклад, багатовимірним вектором, де кожній його компоненті відповідає піксель на картинці, а значення компоненти - це, наприклад, представлення кольору цього пікселя. Але у такого кодування є проблема: коди фотографій однієї і тієї ж людини, взагалі кажучи, не будуть мати між собою нічого спільного. Тому що людина-то одна, але самі картинки виглядають дуже по-різному.
Вирішення цієї проблеми прийшло з розвитком нейромереж. Не вдаючись у подробиці можна сказати, що нейромережу можна представляти як якусь чорну скриньку, яка кодує фотографії «розумним чином»: так, що фотографії однієї і тієї ж людини отримують хоч і різні, але в якомусь сенсі схожі коди. Говорячи більш точно, нейромережа зіставляє кожній фотографії точку в просторі деякої великої розмірності, причому відстані між точками, що відповідають одній людині, досить малі в порівнянні з розмірами отриманої хмари точок, а точки, що відповідають різним людям, навпаки, більш далекі один від одного.
Обличчя у векторах
Отже, незрозумілі фотографії перетворені на точки з урахуванням їх приналежності людям. Але тепер потрібно розібратися, в якому сенсі вони «близькі» або «далекі». Справді, розгляньмо простий приклад. Нехай простір, в якому живуть отримані точки, почесний - це площина. І нехай точки виявилися розміщені на спіралі.
Відстань на площині між червоною і жовтою точками - довжина з'єднуючого їх відрізка - менша, ніж відстань між жовтою і синьою. Але якщо йти вздовж спіралі, жовта точка виявиться набагато ближчою до синьої, ніж до червоної.
Значить, щоб вирішити завдання розпізнавання образів, потрібно зрозуміти, яку геометрію має безліч точок, побудоване нейромережею. Питання ускладнюється ще й тим, що об'ємний простір, в якому живуть точки, як правило має величезну розмірність. Наприклад, деякі зі стандартних в індустрії нейромереж (скажімо, ResNet50 і ResNet100) працюють з простором розмірності 512. Щоб зрозуміти, наскільки це безглуздо, наведу приклад: візьмемо крапку в 512-мірному просторі і для кожної її координати скажемо тільки, позитивна вона або негативна. Отримаємо 2512 варіантів, що більше числа атомів у спостережуваній частині Всесвіту. Тобто для такої розмірності навіть найпростіша спроба класифікувати точки по знаку координат приречена на провал.
На щастя, фахівцями в цій науці давно сформульована - і хоча й не доведена, але багаторазово експериментально підтверджена, - так звана «Гіпотеза про різноманіття». Вона говорить, що точки, отримані з реального світу (наприклад, як говорилося вище, з фотографій людей), зосереджені в об'ємному просторі поблизу деякого різноманіття істотно меншої розмірності. І геометрію цього-то різноманіття і потрібно визначити, щоб ефективно вирішувати завдання розпізнавання.
Клаптикова ковдра
Різноманіття - це, кажучи, неформально, багатовимірний «розумний» аналог кривої або поверхні. Нехай, наприклад, у нас є площина, акціонерний об'єкт. Якщо ми виріжемо з неї маленький шматочок, отримаємо так званий акціонерний диск. Дозволимо собі згинати цей диск - головне його не розривати і не склеювати його точки. Тепер будемо склеювати з таких вигнутих дисків «клаптикову ковдру». Отриманий об'єкт вже може бути влаштований «хитріше» диска. Наприклад, з двох вигнутих аркушів можна склеїти сферу, яка на диск зовсім не схожа. Це і є неформальний опис пристрою різноманіття. У загальному випадку замість ^ єрного диска - шматочка площини - потрібно брати диски багатовимірні, шматочки багатовимірного простору фіксованої розмірності.
Чим дивовижна гіпотеза про різноманіття? Припустимо, точки виявилися зосереджені поблизу різноманіття розмірності 20 в 512-мірному просторі. Це означає, що в будь-якій області цього різноманіття можна вибрати 20 параметрів, і точки в цій області будуть описуватися тільки цими параметрами - а не всіма 512.
Нехай, наприклад, ми працюємо з фотографіями голлівудських зірок. У нас є кілька фотографій Шона Коннері - вони розташовані близько один до одного і описуються 20 параметрами. Це вже не цілком очевидно (точки в 512-мірному просторі можуть бути дуже близькі, але відрізнятися всіма координатами), але все-таки не контринтуїтивно: фотографії однієї людини схожі, тому можна в принципі очікувати, що вони будуть відрізнятися якимось невеликим числом параметрів.
Але нехай тепер у нас ще є фотографії Вупі Голдберг. Вони теж описуються двадцятьма параметрами. І, що найдивовижніше, відмінність - або схожість - фотографій Вупі Голдберг від фотографій Шона Коннері теж описується всього-на-всього 20 параметрами.
Насправді, звичайно, це різноманіття може бути влаштоване складніше, воно може складатися з багатьох шматків, які якось хитро розташовані в об'ємному просторі, але ключова ідея зберігається: суттєвих параметрів, які насправді описують взаєморозташування точок, небагато.
Подорож різноманітними
Щоб дослідити геометрію різноманіття, поруч з яким лежать наші точки, важливо зробити перший крок: знайти його розмірність, те саме число істотних параметрів. Після цього можна, наприклад, спробувати побудувати різноманіття цієї розмірності, добре апроксимуюче відоме («тренувальне») безліч точок, щоб надалі (коли на вхід будуть подані нові, тестові фотографії) працювати з побудованим різноманіттям.
З цим завданням ми з колегами зіткнулися, коли нам було потрібно розробити геометричні методи для поліпшення розпізнавання образів. Ми запропонували два методи оцінки розмірності, і вони дали цікаві результати.
Перший метод має суто геометричну природу і використовує так звану розмірність Мінківського. Ідея його в наступному. Нехай у просторі є різноманіття, розмірність якого ми хочемо оцінити. Розіб'ємо об'ємний простір на кубики з фіксованою довжиною сторони і порахуємо, скільки кубиків перетнулося з різноманіттям, що вивчається. Позначимо це число через ().
Будемо тепер зменшувати розмір кубика, а кількість кубиків, відповідно, збільшувати. Уявімо собі граничну ситуацію: кубики стиснулися в точки. Тоді безліч кубиків, що перетинаються з нашим різноманіттям, в точності з ним збігається, а решта кубиків заповнять іншу частину простору. Звідси можна припустити, що відношення () до загальної кількості кубиків якось описує «розмір» різноманіття.
Насправді приблизно так все і йде. Виявляється, що якщо спрямувати до нуля, відношення логарифма () і логарифма 1/прагне до деякого числа. Воно і називається розмірністю Мінківського:
Тепер подивимося на зв'язок числа кубиків з різноманіттям з іншого боку. Нехай розмір кубика малий. Тоді кубики, що перетинаються з різноманіттям, покривають все і трохи вилазять за його межі. Причому чим менше розмір кубика, тим точніше вони апроксимують різноманіття. Відомо, що число () при маленьких веде себе приблизно як, де - -мірний обсяг нашого різноманіття (розмірності, яку ми хочемо оцінити). Цей факт можна розуміти так, що пропорційно (): тут () - кількість розглянутих кубиків, а - обсяг підкубика розмірності, що збігається з розмірністю різноманіття: ця величина близька до обсягу перетину кубика з різноманіттям. Наприклад, розглянемо простий випадок: коли різноманіття - справжня горизонтальна площина в тривимірному просторі. Коли ми покриваємо кубиками тривимірний простір, перетин кубика зі стороною r з цим різноманіттям - це в точності квадратик зі стороною (і площею - тобто почесним об'ємом - 2). Якщо різноманіття влаштовано складніше, точної рівності не вийде, але при малих значеннях відмінність теж буде мало (як кажуть, є асимптотична формула).
Логарифмуючи це співвідношення, отримуємо, що при маленьких логарифм () влаштований приблизно як (loglog). Логарифм об'єму - це деяка константа, значить log () є деяка лінійна функція від логарифма довжини сторони кубика, похідної якої буде в точності розмірність n. Оскільки () можна порахувати експериментально, цей метод дає можливість оцінити розмірність: достатньо отримати () з експерименту, і вирахувати тангенс кута нахилу дотичної до графіка цієї функції. Це і буде оцінка на розмірність.
Правда, в разі кінцевої безлічі точок, з яким ми працюємо в реальному житті, виникає маленький нюанс. Раз точок кінцевий безліч, між ними є кінцеві відстані. Якщо ми візьмемо сторону кубика дуже маленькою, вийде, що в кожен кубик увійде не більше однієї точки хмари: кожна крапка отримає «свій» кубик, в якому інших точок немає, тому що вони занадто далеко, а у всіх інших кубиках буде порожньо. Але тоді число () - число кубиків, в які потрапили точки хмари, - перестане змінюватися зі зменшенням: воно буде просто дорівнює числу точок у хмарі. Тому потрібно грамотно вибрати шматок функції до цього критичного значення, який дасть вірну оцінку на розмірність.
Друга особливість, що виникає при застосуванні методу до реальних даних, пов'язана з розмірністю об'ємного простору і обчислювальними можливостями комп'ютера. Як обчислити ()? Саме природне - взяти кожен кубик з усіх, на які розбито простір (точніше, його обмежений шматок, в якому ми живемо), і перевірити, чи перетинається він с. На практиці такий метод виявляється непримінним. Справді, нехай все наше різноманіття помістилося в кубі зі стороною 1. Якщо ми розглянемо навіть порожні, то ми отримаємо 2512 кубиків. Це число ми вже згадували вище: воно все ще перевищує число атомів у спостережуваній частині всесвіту, а тому абсолютно неозорому.
З іншого боку, в реальності наше різноманіття не безперервно, а складається з кінцевої безлічі точок, яких відносно небагато. І правильною тактикою виявляється розглядати не кубики на предмет перетину з, а, навпаки, точки - і відзначати, в які кубики вони потрапили. Таке звернення підходу робить цей метод обчислювально ефективним і застосовним.
Другий запропонований метод носить вже не тільки геометричний, але і ймовірнісний характер. Справа в тому, що коли ми беремо випадкові фотографії людей і за допомогою нейромережі перетворюємо їх на точки, ми отримуємо не просто точки на різноманітті, але випадково розподілені точки на різноманітті. Отже, для їх дослідження можна використовувати ймовірнісні методи. Виявляється корисно розглянути наступну випадкову величину, що характеризує це безліч точок: для кожної точки береться відстань до її найближчого сусіда, тобто найменша з попарних відстаней між цією точкою і всіма іншими точками хмари.
Виявляється, якщо ці випадкові величини відповідають ряду умов, значення обсягу мінімальної кульки з центром в такій точці хмари, в якому є хоча б ще одна точка хмари, розподілені експоненціально. При цьому параметри цього розподілу залежать від розмірності різноманіття, що вивчається. Ці умови потрібно, звичайно, перевіряти при використанні цього методу, але у вивченому нами випадку вони виявилися виконаними, якщо говорити більш точно, має місце рівність:
Тут () -мірний об'єм кулі радіуса (а - все ще шукана розмірність).
Цей розподіл можна обчислити емпірично за наявною хмарами точок, а значить, щоб оцінити розмірність, достатньо підібрати таке, що емпірично підраховане максимально схоже на експоненціальне, зазначене вище, для цього. Для пошуку підходящого використовується наступний метод. По-перше, добре відомо, що у експоненціального розподілу квадрат першого моменту дорівнює другому. По-друге, для порівняння двох розподілів можна використовувати так звану статистику Колмогорова-Смирнова, яку можна розглядати як деяку відстань між розподілами. Відповідно, алгоритм оцінки розмірності виглядає так.
Для безлічі «підозрілих» (кандидатів на роль розмірності) обчислюються моменти розподілу і статистика Колмогорова-Смирнова. З претендентів вибирається таке, для якого одночасно досягається мінімум статистики Колмогорова-Смирнова і виконується рівність 12 = 2 для моментів. Якщо серед кандидатів відповідного не знайшлося, максимальне допустиме значення збільшується і алгоритм повторюється.
Для поліпшення цього методу можна додатково підготувати проведену хмару точок. Так, у цій статті був запропонований алгоритм «втілення» хмари (після якого воно стає схоже на свого роду багатовимірний багатогранник), що збільшує точність методу.
Як ужити 512 в 25
Експерименти, проведені на реальних базах даних фотографій людей показали, що обидва методи дають близькі результати, що побічно підтверджує правильність цих результатів (оскільки методи абсолютно різні за своєю природою, близькі результати свідчать про достовірність). Виявилося, що розмірність знаходиться десь в діапазоні від 22 до 26. Це цікаво саме по собі - це означає, що хоча розмірність простору величезна, 512, самі точки істотно описуються тільки приблизно 25 параметрами.
Крім того, цей результат підтверджує і гіпотезу про різноманіття, оскільки якби безліч точок було влаштовано хаотично, слід було очікувати, що методи оцінки розмірності «побачать» весь простір і дадуть 512 або близько до того. А приємно маленька відповідь підказує, що структура різноманіття дійсно є. Отже, її можна дослідити і завдяки цьому вчити комп'ютер все краще і краще відрізняти Шона Коннері від Вупі Голдберг.