За проклятието на измерението

Ако има един съвет, който бих дал на всеки в областта на машинното обучение, това би бил той: никога не забравяйте проклятието на размерността. Традиционното обяснение е нещо подобно: „Е, ако имате много входни измерения, тогава вашият проблем става изчислително скъп и труден за решаване“. Да, това е вярно, но защо е вярно? Нека поговорим за това по-подробно.

Едно от най-интуитивните обяснения, на които попаднах за проклятието на размерността, е разглеждането на единична хиперсфера и нейния обем. Какво имам предвид с това? Е, точка от данни най-вече се представя като d-измерен вектор. Нека си представим, че всички точки от данни в конкретен проблем са разположени в единична хиперсфера. Всички знаем какъв е обемът на хиперсфера в 3D, а именно:

За да разширим това до размери d, можем да пренебрегнем константите в уравнението за обем и да ги поставим в променлива c, след което уравнението за обем отнема следната форма:

Нека да разгледаме следния кръг за минута, геометрично изглежда, че повечето от точките падат от черупката (пространство между синята линия и червената линия). С други думи, обвивката на тази единична окръжност до радиус 0,95 заема много малка част от площта на окръжностите:

Сега, какво бихте си представили как изглежда тази ситуация, когато погледнем d-измерна хиперсфера? Подозирам, че повечето хора биха казали, че би било подобно, по-голямата част от обема ще лежи извън обвивката на хиперсферите. Както бихте подозирали, повечето хора биха грешали. Истината е, че хората всъщност не са способни да мислят в пространства с високи измерения. Не е интуитивно, просто не можем да ги визуализираме. Нека да разгледаме какво всъщност се случва. Можем да напишем частта от обема, която обвивката заема от d-измерната хиперсфера, както следва:

Гледайки как се развива фракцията, ако вземем 5% от радиуса на хиперсферите за черупката, става ясно къде се крие проблемът. С увеличаването на входния размер d има значително увеличение на обема, който се намира в черупката, както показва следната фигура:

Можем да видим, че делът на черупката от обема нараства експоненциално по отношение на размерността към 1, като 1 е неговата граница. Дори при малки количества отrфракцията на черупката нараства бързо до 1.

Какво означава това, кога това може да създаде проблеми? За да видим това, нека вземем най-често използваното разпределение в машинното обучение, разпределението на Гаус. Ако разгледаме гаусовата плътност за триизмерно входно пространство, това би било нещо като хиперсфера, където вероятностите намаляват с радиуса от средната стойност, това важи като цяло за повече от 3 измерения, можете да видите какво имам предвид под гледайки следната фигура:

В пространствата с големи измерения се случва плътността на Гаус да се концентрира във външната обвивка на нейната хиперсфера, в резултат на частта на обвивката от обема на хиперсферата, което става значително в пространствата с големи измерения. Това означава, че в случай, че вземете проба от този Гаус, резултатите ще бъдат точки от данни от външната обвивка на хиперсферата с най-висока вероятност.

Можем да мислим за проклятието на размерността по отношение на емпиричното минимизиране на риска, което подробно обясних в статията „Теория на обучението: Емпирично минимизиране на риска“. Накратко, искаме да получим представителна извадка за обучение от нашите данни, за да можем да обобщим към невиждани данни. Сега, в примера с хиперсферата, проверихме, че външната обвивка на сферите съдържа над 90% от обема, когато има дебелина 5% от радиуса на сферите и ако размерността на данните е приблизително 400 измерения. Представете си, че имаме проби от данни между центъра на сферата (0% радиус) и 95% радиус. В този случай покрихме 95% от обхвата на радиуса, но покрихме само по-малко от 10% от обема. Ясно е, че е трудно да се получи представителна извадка в този случай, когато наблюдаваме само данни от диапазона, който покрива 10% от обема.

За щастие проклятието на размерността не трябва да означава, че не можем да изградим ефективни модели. Често имаме някои гаранции за гладкост на данните, пространството на данните не е населено толкова плътно или размерността може да бъде намалена (голяма част от изследванията на машинното обучение). Може би най-добрият пример за това е пространството на всички възможни 64x64 RGB изображения. Размерността на данните е 64x64x3=12288. Ако помислим за примера с хиперсферата, това очевидно може да е проблем. Но в действителност повечето от различните комбинации от пиксели нямат абсолютно никакъв смисъл за каквато и да е класификация, а са обикновен шум. Също така, подходите за компютърно зрение са пълни с полезни предишни неща, които правят проблема много по-лесен за решаване.

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