Стаття Погляд — 01 серпня, 2019

Справжній деформатор

ТЕКСТ:

ІЛЮСТРАЦІЇ: Peter Kok

Біт (скорочення від binary digit) – це мінімальна одиниця кількості інформації. Один біт – це вибір між двома альтернативами, 0 і 1, або «так» чи «ні». Комп’ютери переважно оперують з байтами (1 байт = 8 бітів) – це мінімальна інформація, за якою можна адресно звернутися.

Від мінімальних значень перейдемо до значень великих. Обсяг інформації, з якою має справи людство, невпинно збільшується.  Загальний обсяг даних зростає за експоненційним законом; у 2020 році його оцінюють у 44 зетабайти, а у 2025 році – у 163 зетабайти (зета – це 10 у 21-му степені, 1021).

Великі дані (Big Data) – це такі набори даних,через величину яких із ними не можна працювати традиційними методами. 

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

Та спершу декілька слів про топологію. Це розділ математики, що вивчає інваріанти неперервних перетворень геометричних фігур і загальніших об’єктів – метричних і топологічних просторів. Для унаочнення, припустимо, що фігура зроблена з еластичного матеріалу і її дозволяється як завгодно деформувати, але забороняється розривати, а також склеювати її точки. Тоді з кулі можна зробити куб або циліндр, але не можна зробити бублик (тор). Заважає перетворити кулю на тор те, що в кулі отворів немає, а у тора є («дірка від бублика»). Топологія дає змогу надати точного сенсу цим міркуванням.

Одними з основних понять топології є поняття метричного і топологічного просторів. Метричний простір одержуємо, коли на якійсь множині об’єктів (у математиці для них є універсальний термін – точки) задамо метрику. Останнє означає, що кожній парі x,y точок множини приписуємо значення відстані d(x,y) між ними. Звичайно, при цьому повинні виконуватися деякі природні умови.

Насамперед відстань між точками має бути невід’ємним числом. Також ця відстань симетрична, тобто (d(x,y)=d(y,x). Нарешті вимагаємо, щоби виконувалася нерівність трикутника (тобто, (d(x,y)не перевищує суми d(x,z)+d(z,y), хоч яке є z). Для заданого додатного числа r всі точки, що на відстані

Поняття метрики є математичною абстракцією звичного поняття відстані на площині і в тривимірному просторі. Так, будь-яку пласку чи просторову фігуру можна вважати метричним простором. У математиці важливим узагальненням площини і тривимірного простору є поняття n-вимірного простору для довільного n. Точкою такого n-вимірного простору є послідовність довжини  n дійсних чисел, x=(x1,x2,…,xn).

Є різні способи запровадження метрики у n-вимірному просторі. Один із найпростіших, коли для  x=(x1,x2,…,xn) та y=(y1,y2,…,yn) приймаємо d(x,y) як найбільше з чисел |x1-y1|,  |x2-y2|, … ,  |xn-yn|. Можна також за значення d(x,y) взяти суму |x1-y1|+|x2-y2| +… +|xn-yn|. А ще можна вважати, що d(x,y) є коренем квадратним з суми квадратів |x1-y1|2+|x2-y2|2+… +|xn-yn|2 – при такому означенні відстані у n-вимірному просторі буде виконуватися теорема Піфагора.

Повернімося до колекцій даних. Кожен елемент такої колекції описується певним скінченним набором числових характеристик. Для прикладу, піксель на світлині характеризується своїм положенням (це дві координати), а також кольором (скажімо, три координати у колірній моделі RGB) насиченістю й інтенсивністю. У загальному випадку таких характеристик буде n, тобто кожен елемент з набору даних однозначно описується точкою n-вимірного простору, а вся колекція даних стає таким чином підмножиною у n-вимірному просторі. До дослідження таких множин застосовують різноманітні топологічні методи.

Однією з найпростіших технік аналізу великих даних є кластеризація. Нехай X – масив даних. Розглянемо довільне число r > 0. З’єднаємо відрізком кожні дві точки з X, якщо відстань між ними не перевищує r. Утвориться об’єкт, що в математиці називається графом. При цьому точки називають вершинами графа, а відрізки, що їх з’єднують, — ребрами.

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

Цю ситуацію можна зобразити як дерево. При цьому на рівні r (вертикальна вісь) перетин прямої з цим деревом має число точок, що дорівнює числу компонент зв’язності відповідного графа. Дерево показує, на яких рівнях відбувається злиття кластерів. Перевага такого зображення даних у вигляді дерева полягає, зокрема, у тому, що, незалежно від числа вимірів сукупності даних, дерево кластерів розміщується на площині. 

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

Та спершу опишемо будівельний матеріал для цих узагальнень, а саме, фігури, які називаємо  із заданими вершинами. Нульвимірним симплексом називаємо довільну точку у n-вимірному просторі. Одновимірним симплексом називаємо відрізок, що з’єднує дві різні точки (вершини). Двовимірний симплекс – це трикутник із заданими вершинами, тривимірний симплекс – тетраедр. Можна означити поняття k-вимірного симплекса для довільного k.

Із симплексів, як і з деталей конструктора Lego, можна складати складніші об’єкти. Симпліціальним комплексом називають таке скінченне об’єднання симплексів, у якому кожні два симплекси або не перетинаються, або їх перетин є підсимплексом кожного з них. Зауважимо, що граф є прикладом симпліціального комплекса, він складається з точок і одновимірних симплексів (відрізків).

Одним з важливих інструментів якісного дослідження великих даних є так звані «стійкі гомології» (persistent homology). Звичайно, пояснювати, що таке стійкі гомології варто вже коли вивчена теорія гомологій, та все ж спробую принаймні створити враження.

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

Топологічними характеристиками симпліціальних комплексів є «отвори» в них. Одновимірні отвори бачимо у комплексах з попереднього рисунку. 

Для кожного такого отвору можна вказати значення параметра r, при якому він виникає, і значення, при якому він зникає (заклеюється). Скажімо, два отвори в симпліціальному комплексі зліва зникли у симпліціальному комплексі справа, натомість з’явився новий отвір.

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

Тепер побудуємо так звану «штрих-код діаграму» (barcode diagram). Для цього на вертикальній осі відзначимо точки, якими позначаємо всеможливі отвори у побудованих симпліціальних комплексах. Горизонтальна вісь служитиме для параметра r.

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

Один зі способів порівняти між собою дві бази великих даних полягає у тому, щоби порівняти їх штрих-кодові діаграми. Для цього спочатку перетворимо кожну штрих-кодову діаграму у так звану «стійку діаграму». Це відбувається за допомогою такої процедури: кожному відрізкові зі штрих-кодової діаграми поставимо у відповідність точку (x,y) на координатній площині, де x – значення параметра, при якому цей цикл народжується, а y – значення параметра, при якому цей цикл вмирає.

На рисунку показано як шукати відстань між двома діаграмами стійкості. Одна діаграма складається зелених точок, а інша – з синіх. Насамперед потрібно розбити точки цих діаграм на пари – у кожній парі повинна бути синя і зелена точка; оскільки число точок у діаграмах може бути різним, то дозволяється за потреби будь-яку точку рожевої діагоналі (тобто, там, де x=y) приписувати до кожної з діаграм.

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

Опишемо одне цікаве застосування топологічних методів до аналізу великих даних. Ґуннар Карлссон зі Стенфордського університету провів дослідження мільйонів піксельних зразків розміром 3×3, взятих із реальних чорно-білих світлин.

Кожен такий зразок моделюється точкою у дев’ятивимірному просторі – досить відкласти на відповідній координаті значення інтенсивності сірого кольору. Відніманням медіани і нормуванням можна помістити всі ці зразки на одиничну 7-вимірну сферу у 8-вимірному просторі. Дивовижним результатом Карлссена і його групи було те, що такі піксельні зразки не розподілені рівномірно на 7-вимірній сфері, а концентруються навколо поверхні, що носить назву пляшки Кляйна. Ця поверхня утворюється, коли в квадраті зробити утотожнення протилежних сторін, зображені на рисунку (вздовж стрілок). Після склеювання вертикальних сторін одержуємо циліндр. 

Подальше склеювання горизонтальних  сторін (вони вже стали верхнім і нижнім колом на циліндрі) не можна здійснити в реальності, а лише в нашій уяві. Можна також і у n-вимірному просторі при n>3, який для математиків є цілком реальним об’єктом.

Цей вельми несподіваний теоретичний результат отримав практичне застосування – на його основі було запропоновано алгоритм стискання зображень, кращий від відповідного JPEG.

У зв’язку з використанням топології для дослідження великих даних американський математик Айседор Зінгер (співавтор знаменитої теореми Атії-Зінґера) ще 15 років тому передбачав створення нової математичної дисципліни – статистичної топології. Вона повинна би займатися статистичними розподілами чисел циклів і т. п., коли розглядаємо необмежені простори й коли параметри прямують до нескінченності. Численні результати останніх років показують, що це передбачення стало реальністю.

 

Михайло Зарічний – доктор фізико-математичних наук, професор кафедри геометрії і топології, декан механіко-математичного факультету (2004-2016) Львівського національного університету імені Івана Франка. 

Популярні статті

Стаття Суспільство — 27 березня

Як Росія завойовувала вплив у країнах Африки

Стаття Космос - 29 лютого

Куншткамера з Девідом Сперґелом про реліктове випромінювання, НАЯ (НЛО) та співпрацю з українськими науковцями

Стаття Пост правди - 25 березня

Пост правди, епізод 7: Анонімність в телеграмі