Графично обучение и задълбочено геометрично обучение — Част 2

Не забравяйте да прочетете общ преглед на Geometric Deep Learningипредпоставкитеза да се запознаете с тази ниша в машинното обучение.

Следвайте my Twitter и се присъединете към Geometric Deep Learning subreddit за най-новите актуализации в пространството.

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

Тъй като графиката остава най-близо до оригиналната си форма в по-високо измерение, следователно релационното индуктивно отклонение е много по-силно.

Индуктивното отклонение на алгоритъм за обучение е наборът от предположения, които обучаемият използва, за да предвиди изходни данни, дадени входни данни, които не е срещал.

Във всеки алгоритъм за машинно обучение има вид индуктивно отклонение. Във ваниловите CNN например, минималните характеристикииндуктивно отклонение гласи, че освен ако няма убедителни доказателства, че дадена функция е полезна, тя трябва да бъде изтрита. Алгоритмите за избор на характеристики са изградени върху това предположение. В Geometric Deep Learning предположението е релационно:

Чрез структуриране на данните по начин, който дава приоритет на определени модели, можем да подобрим производителността на модела, дори ако данните са едни и същи.

Ванилови навивки

Като цяло традиционната конволюционна мрежа се състои от 3 основни операции:

Ядро/филтър

Мислете за ядрото като за скенер, отколкото за „крачки“ над цялото изображение. Клъстерът от пиксели, които скенерът може да сканира наведнъж, се определя от потребителя, както и броят на пикселите, които той премества, за да извърши следващото сканиране. Ядрото агрегира пикселите в стойности в мрежов формат, за да ги подготви за обединяване.

Обединяване

Отново се извършва операция тип „скенер“, но вместо да агрегира куп пиксели, обединяването отделя само най-важните стойности (максимално обединяване) или осреднява всички стойности (средно обединяване) и използва това за изграждане на мрежа от стойности за сплескване.

Сплескване

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

Графични навивки

Конволюциите върху графиките обаче са много по-предизвикателни. Графиките не се манипулират толкова лесно поради тяхната неправилна структура. Изображенията са представени на двуизмерна евклидова мрежа, където ядрото може да се движи наляво, надясно и т.н. Графиките са неевклидови и понятието за посоки като нагоре, надолу и т.н. няма никакво значение. Графиките са по-абстрактни и променливи като степен на възел, близост и структура на съседство предоставят много повече информация за данните. Така че крайният въпрос е:

Как да обобщим навивки за данни от графики?

Ключът към обобщаването на конволюцията е ядрото/филтъра. Ще видим, че най-голямата разлика между подходите за Graph Learning е в ядрото,или върху какво работи ядрото.

На високо ниво конволюциите събират информация от околните или съседни обекти. Конволюциите в Deep Learning вземат тази обобщена информация, за да изградят карти на функции (стойностите на мрежата), които се използват за правене на прогнози с невронна мрежа. Искаме да направим това на графики.

Видове навивки на графики

Има 2 вида навивки на графиката:

Пространствени методи: не изискват използването на eigen-stuff

и

Спектрални методи: изисква използването на eigen-stuff

И двата метода са изградени на различни математически принципи и е лесно да забележите приликите между подходите във всеки метод. Вероятно обаче не е много интуитивно защо използването на спектрални методи е толкова популярно при изучаването на графики.

Това е анализ на високо ниво на някои от най-популярните архитектури.

Спектрални графични конволюционни мрежи

Изследователската посока на Michaël Defferrard и др. доведе до популяризирането на нова област както в теорията на графите, така и в анализа на сигналите. Това подполе е известно като Обработка на графичен сигнал (GSP).

GSP е ключът към обобщаването на навивки, което ни позволява да изградим функции, които могат да вземат предвид както цялостната структура на графиката, така и отделните свойства на компонентите на графиката.

GSP използва функции за обработка на сигнали като преобразуване на Фурие, което обикновено е инструмент, запазен за сигнали/честоти, и ги прилага към графики. Това е преобразуването на Фурие на графиката, което позволява да се въведе понятието за „честотна лента“ или „гладкост“ на графика. В пространствения смисъл на термина, гладкостта просто означава колко близки са всяка стойност на колекция от неща, спрямо една друга. В спектрален смисъл е малко по-сложно.

Аналогично на плавните времеви сигнали, които имат тясна ширина на честотната лента, графика, която проявява свойства на групиране, ще има тясна ширина на лентата в GFT (сигналите варират по-малко в рамките на клъстери от силно взаимосвързани възли). С други думи, една групирана графика би била рядка в честотната област, което позволява по-ефективно представяне на данните (честота, неевклидова и спектрална област означават едно и също нещо). За малко спектрална интуиция можете да намерите страхотно резюме в тази страхотна статия.

В GCN функциите и атрибутите на възлите са представени от „сигнали“. След това можем да използваме концепции в обработката на сигнали, за да се учим от данните. Обикновено сигналът не е просто функцията на възела или ръба, взета такава, каквато е, а по-скоро това е функция, която се прилага към характеристиката.

Конволюциите могат да бъдат изчислени чрез намиране на собственото разлагане на лапласиана на графиката. Собственото разлагане е начин за факторизиране на матрица в набор от собствени вектори и собствени стойности. Това се нарича още спектрално разлагане, откъдето идва и името Конволюционни мрежи на спектралните графики. Изчисляването на собствените вектори на лапласиана връща базата на Фурие за графиката. Тъй като изчислението се извършва върху лапласиана, ще има толкова собствени вектори, колкото и възлите на графиката. Директното решаване на разлагане е интензивно, поради което много подходи избират вместо това да приближат спектралното разлагане. За по-задълбочено разбиране на спектралното разлагане, Machine Learning Mastery има страхотна публикация за тази операция.

Така че общите стъпки са:

  1. Трансформирайте графиката в спектралната област с помощта на собствено разлагане
  2. Приложете собствено разлагане към посоченото ядро
  3. Умножете спектралната графика и спектралното ядро ​​(като ванилови навивки)
  4. Връща резултати в оригиналния пространствен домейн (аналогично на обратния GFT)

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

ChebNets — Деферард и др.

ChebNets е една от първите и най-важни статии за изучаване на спектрални графи.Спектралните конволюции се дефинират като умножаване на сигнал (характеристики/атрибути на възел) от ядро. Това е подобно на начина, по който конволюциите работят върху изображение, където стойността на пиксела се умножава по стойността на ядрото.

Ядрото, използвано в спектрална конволюция, съставено от полиноми на Чебишев на диагоналната матрица на собствените стойности на Лаплас. Полиномите на Чебишев са вид ортогонални полиноми със свойства, които ги правят много добри при задачи като апроксимиране на функции. Ядрото е представено от уравнението:

Където gθ е ядро ​​(θ представлява вектора на коефициентите на Чебишев), приложено към Λ, диагоналната матрица на Лапласовите собствени стойности ( Λ˜ представлява диагоналната матрица на мащабираните Лапласови собствени стойности). k представлява кварталът на най-малкия ред, а K представлява кварталът на най-големия ред. И накрая, T означава полиномите на Чебишев от k-ти ред.

На обикновен английски:

Ядрото се равнява на сумата от всички ядра на полином на Чебишев, приложени към диагоналната матрица на мащабирани собствени стойности на Лаплас за всеки ред от k до K-1.

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

ChebNet имплицитно избягва изчисляването на собствената позиция, вместо това избира да я приближи. В това отношение ChebNets са много подобни на Graph Convolutional Network от Thomas Kipf et al. GCN са по същество ChebNet от първи ред (първи ред и втори ред+ са обяснени в моята предишна статия), с някои други опростени операции за намаляване на сложността.

Първи ред просто означава, че показателят, използван за определяне на приликата между 2 възела, се основава на непосредственото съседство на възела. Втори ред (и след това) означава, че показателят, използван за определяне на сходството, взема предвид непосредственото съседство на възела, но също така и сходствата между структурите на съседство (с всеки нарастващ ред, дълбочината на считаните възли се увеличава). Редът, който се разглежда в рамките на една намотка, се обозначава с K (k за най-малкия ред), в повечето документи.

ChebNets не ограничава K до каквато и да е стойност и така моделът е в състояние да научи квартала на даден възел от всякакъв ред. GCN обаче ограничават своите K стойности до 1, като по този начин ограничават обхвата на конволюцията до сходство от първи ред.

Графични конволюционни мрежи (GCN) — Кипф и Уелинg

Сред най-цитираните трудове в графичното обучение е статия на Kipf и Welling. Статията въвежда спектрални навивки в графичното обучение и е наречена просто „графични конволюционни мрежи“, което е малко подвеждащо, тъй като е класифицирано като спектрален метод и в никакъв случай не е източникът на всички последващи работи в графичното обучение.

В GCN на Kipf и Welling конволюцията се определя от:

Където gθ е ядро ​​(θ представлява параметрите), което се прилага (представено със звездата) към x,сигнал на графиката. K означава броя на възлите далеч от целевия възел, който трябва да се вземе предвид (Kта област на реда, с k е най-близкият съсед по ред). T обозначава полиномите на Чебишев, приложени към L̃, което представлява уравнението:

Където λ maxозначава най-голямата собствена стойност на L, нормализираният лапласиан на графиката. Могат да се извършат множество навивки на графика и изходът се обобщава в Z.

Където Z е матрица от свити сигнали (от съседни възли), Ã е матрицата на съседство на графиката ( плюс идентификационната матрица), D̃ е степента на диагоналния възел от Ã, Θе матрица от параметри на ядро/филтър (може да се споделя в цялата графика), а Xе матрица от вектори на характеристики на възли . Dна степен -1/2 са части от трик за пренормиране, за да се избегне експлозия или изчезване градиенти.

Уравнения 1 и 3 са компонентите, които са обвити във функция за активиране (Relu, Sigmoid и т.н.). Комбинираният резултат е правилото за разпространение по слоеве, което съставлява един слой на GCN. Ключовата иновация е използването на преобразуването на Фурие, популярна операция в квантовата механика (при изучаването на Q-битове) и обработката на сигнали (при изследването на вълните).

ChebNets и GCN са много сходни, но най-голямата им разлика е в избора им за стойност K в eqn. 1. В GCN мъдрото навиване на слоевете е ограничено до K = 1. Това има за цел да облекчи риска от пренастройване на локален квартал на графика. Оригиналната статия от Kipf et al. допълнително обяснете как това прави архитектурата линейна по отношение на Laplacian, опростявайки цялостната сложност на модела.

На високо ниво GCN използва преобразуването на Фурие на графиката, за да агрегира характеристики и атрибути на съседни възли. Тези характеристики и атрибути са представени като сигнали, които са компонентни декомпозиции на латентната графика. Това е аналогично на начина, по който честотите на компонентите са разлагане на звукова вълна; честотите на компонентите са характеристики на възли (като сигнали), а сигналът на звуковата вълна е латентна графика.

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

Бързи/опростени навивки на графики (FastGCNs/SGCs)

Най-големите недостатъци на Spectral Convolutions е тенденцията им да бъдат много скъпи от изчислителна гледна точка. Ядрото е дефинирано в пространството на Фурие и графичните трансформации на Фурие са известни като скъпи за изчисляване. Изисква умножение на характеристиките на възлите с матрицата на собствения вектор на лапласиана на графиката, което е O(N²) операция за графика с N възли.

И така проблемът, който изследователите на IBM се заеха да разрешат, беше как да подобрят изчислителната ефективност, като същевременно запазят възможно най-добрите резултати. По този начин FastGCN е роден от необходимостта от мащабируеми навивки на спектрални графики. Проектът по същество модифицира оригиналната GCN архитектура, за да може да използва подходи на Монте Карло (метод на предубедена произволна извадка) за последователно оценяване на интегралите, което позволява пакетно обучение, намалявайки общо време за обучение.

От друга страна, опростените графични навивки (SGC) подходиха към проблема по различен начин; вместо подобряване на изчислителната ефективност, може би намаляването на изчислителната сложност е естественото решение. Резултатите от техния експеримент са показани на диаграмата вляво. Предпоставката зад тяхната хипотеза:

„Предполагаме, че нелинейността между слоевете на GCN не е критична – но че по-голямата част от ползата произтича от локалното осредняване.“

Проектът премахна нелинейните преходни функции между всеки конволюционен слой. Окончателното активиране на softmax позволи вероятностни изходи, които могат да бъдат оптимизирани със стохастичен градиентен низход.

CayleyNets

CayleyNets подобрява проблема с високите изчислителни разходи на ChebNet, използвайки тайна съставка. Както е посочено от името, този подход използва преобразуването на Cayley(представено от единица полукръг), за да коригира проблема.

На високо ниво трансформацията помага за „увеличаване“ на изкривени точки от данни, както е показано в този шантав GIF.

Полиномите на Кейли споделят сходни свойства с полиномите на Чебшев в ChebNets, включително полезното понятие за локализация(имайте предвид, че и в двата подхода „полиномите“ се отнасят до функцията, която действа като ядро/филтър).

Cayley доказа, че се представя по-добре при широк набор от задачи за Graph Learning благодарение на способността им да откриват важни честотни ленти по време на обучение и да се специализират в тях, докато са добре локализирани в графиката.

Благодарение на параметър (h) в ядрото/филтъра на Cayley, по-малките собствени стойности на спектъра могат да бъдат разпръснати, което позволява наядрата да се специализират в различни честоти. Това се визуализира в 3-те диаграми от оригиналния документ, демонстриращи нормализиращата сила на параметъра (h), където знаците показват собствените стойности (червеното е това, което съдържа важна информация).

Рамо до рамо, CayleyNets (оранжев) най-вече превъзхождаше ChebNets (син), като същевременно изискваше по-малко параметри.

MotifNets

MotifNets беше различен подход, който се основава на оригиналния GCN модел чрез въвеждане на понятието „мотиви“. По същество режимът разделя входните графики на мотиви, които са уникални подструктури с x дължина, така че всяка графика в набора от данни може да бъде изградена чрез някаква комбинация от мотивите.

Тези мотиви са с размер x = 3. Забележете, че мотивите вземат под внимание посоката на ръбовете, подробност в теорията на графите, която е била пропуснати в предишните подходи за обучение на графики. Това е особено полезно за приложения, които имат присъща представа за посока, като социални мрежи, транспортни мрежи и енергийни мрежи.

ChebNet е екземпляр на MotifNet с един лапласиан на неориентирана графика, в която се използва матрица от полиноми на Чебишев. Всеки конволюционен слой на MotifNet има многовариантен матричен полином (фантастично ядро, където всеки елемент е полином с множество променливи), който се прилага и се учи от матриците на Лаплас на мотива.

Въпреки ефективността на ChebNet и GCN, и двата метода се борят, когато работят с графики, съдържащи групирани собствени стойности, явление, което обикновено се среща в графите на общността. В това отношение MotifNet се стреми да поправи същата слабост като CayleyNet.

Спектралните методи като цяло

Здрави, надеждни и проучени спектрални навивки дадоха тласък на интереса към Graph Learning и Geometric Deep Learning като цяло. Дори Ян Лекун и други изследователи в челните редици на тази ниша са направили принос.

Спектралните методи обаче нямат недостиг на слабости и недостатъци, но това е тема за друга публикация.

Пространствени графични конволюционни мрежи

GraphSage — Хамилтън и др.

Красотата на GraphSage е неговата простота. Моделът е от най-високо ниво и остава конкурентен по отношение на производителност, дори и с по-нови или по-мощни модели. Той е особено мощен, защото се мащабира добре с големи, плътни, хомогенни, динамични мрежи. Създаден отчасти от приноса на Юре Лесковец, който също е допринесъл за различни други алгоритми в тази статия (включително node2vec), GraphSage е един от многото алгоритми за обучение на графики, които са излезли от SNAP, проекта за мрежов анализ на Станфорд.

На високо ниво GraphSage има 3 стъпки:

Извадка от квартала:

Започнете с намиране на непосредственото съседство на целевия възел в графика. Дълбочината k се определя от потребителя и определя колко „съседи на съседи“ ще бъдат взети за извадка. Тази операция се извършва рекурсивно за определен брой стъпки.

Агрегиране:

След като всеки възел в графиката е извадил съответния си квартал, трябва да съберем заедно всички характеристики на възлите на квартала към целевия възел. Оригиналната статия предлага 3 функции за агрегиране

  • Средно агрегиране— Осредняване на всички характеристики на съседния възел (може да бъде средно претеглено)
  • LSTM агрегиране — Използване на LSTM клетка за селективно агрегиране на характеристиките на кварталния възел (подредени на случаен принцип)
  • Агрегиране на обединяване — Максималното обединяване взема под внимание само „най-високата“ характеристика (с най-добри резултати в експериментите)

Прогноза:

Целевият възел използва агрегираните характеристики на съседния възел, за да направи прогноза чрез невронна мрежа, която може да бъде задача като класификация на възел или определяне на структура/контекст. Това е мястото, където се случва обучението. Този процес от 3 стъпки се повтаря за всеки възел в графиката по контролиран начин. Визуално представяне на подхода е показано по-долу:

Експериментите показаха, че агрегирането на обединяване се представя най-добре, както и че е най-ефективно за изчисляване. Ефективността на GraphSage е причината той да е един от малкото модели за Graph Learning, които понастоящем се прилагат в приложение от реалния свят. Pintrest, уебсайтът за споделяне на снимки, в момента използва GraphSage (макар и модифициран и преименуван на PinSage), за да предвиди подходящи снимки въз основа на интересите на потребителя и заявките за търсене.

„Мрежи от смесен модел (MoNet) – Монти и др.“

MoNet постигна голям успех в по-нататъшните изследвания и разработки, като оригиналната статия се превърна във вдъхновение и точка за създаване на множество подходи и архитектури, включително геодезични CNN (GCNN), анизотропни CNN (ACNN), сплайнови CNN и дифузионни CNN.

Оригиналната книга на MoNet имаше 3-кратен принос

  1. Обобщение на различни подходи за графично обучение, обединяване на пространствени и спектрални подходи
  2. Нов подход, използващ параметрични ядра, псевдо-координати, интегрирани със съществуващи модели (Anistropic CNN, Geodesic CNN,)
  3. Серия от експерименти, извършени върху различни еталонни колектори, графики и мрежи

Обобщението на MoNet първо разглежда променливата x като точка в колектора или възел в графика в зависимост от приложението, задачата и входа. Променливите y се считат за съседните възли или точки, които са свързани с вектор от псевдокоординати в d-измерното пространство, така че u(x, y) са псевдокоординатите, от които има уникален набор за всеки съсед на x .

Всяка псевдокоордината се прекарва чрез претегляща функция, която възпроизвежда ефекта на традиционното ядро ​​за навиване на изображение, при което всяка стойност на ядрото се умножава по стойността, която в момента се разглежда. В случая на MoNet, функцията за претегляне е ядро ​​с параметри, които могат да се научават, което работи с псевдо-координати:

където Σj е ковариационна матрица на d по d и μj е d на 1 среден вектор на ядрото. d е размерите на псевдокоординатните вектори (u(x, y)). Тези векторни/псевдокоординатни конволюционни ядра картографират някои много интересни визуализации:

На 3D моделите са локални полярни координати, центрирани в точка на техните колектори. Кръговите диаграми (които представляват многоцветните части на моделите) са функции за претегляне на пач оператор (фантастичен начин да се каже ядро), използвани в различни конволюционни операции върху колектора.

Това ядро се научава само в MoNet, в сравнение с твърдо кодирано в GCNN и ACNN. Първото нещо, което може да забележите, е колко „по-гладки“ са теглата (червените криви) в MoNet, в сравнение с по-различните (GCNN) и по-интегрирани (ACNN) тегла на другите подходи.

Тези визуализации на ядрото ще се променят с всяка уникална конфигурация на GCNN и ACNN. Но MoNet, подобно на GraphSage, може да научи параметри. Тази гъвкавост е част от причината, поради която и двете позволяват споделяне на параметри между набори от данни. Това отваря капацитета за идеи като Прехвърляне на обучение, които да бъдат приложени към геометричната област . Бъдещето на Graph Learning изглежда доста страхотно!

Пространствените методи като цяло

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

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

По същество

През 2010-те до 2012-те години, благодарение на съвместните усилия на най-добрите изследователи в Deep Learning, включително хора като Yann Lecun (Image convolutions) и Джеф Хинтън (Back-propagation), конволюционните невронни мрежи предизвикаха завръщане на Deep Learning, което само те виждаха да идва . Ефективните и ефикасни навивки на графики имат потенциала да имат този ефект, изкарвайки полето на Geometric Deep Learning в светлината на прожекторите.

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

Спектралните навивки са математически, както и теоретично подобни на техните двойници на ванилови навивки, докато пространствените навивки са концептуално, както и подчертано подобни на ванилови навивки.

Когато единият метод следва дефинициите от учебниците и математиката, за да обобщи конволюция, другият заема позиция от гледна точка на теорията на графите.

Определено съм пропуснал куп алгоритми и модели, особено след като неотдавнашната експлозия на интерес към Geometric Deep Learning и Graph Learning доведе до нови приноси, изскачащи в публикации почти ежедневно. Някои интересни подходи включват проекти като Graph U-Net и Graph Markov Neural Networks. Има и съществуващи модели, които все още не съм разбрал напълно; но когато го направя, ще актуализирам тази статия.

Ключови изводи

  • Целта на навивките на графики е да обобщи операцията по навиване на изображения към графики, така че да можем да постигнем сходни нива на производителност и точност.
  • Конволюциите на графики са различни от конволюциите на изображения, защото графиките като структура от данни с неевклидови свойства са много различни от зададената структура на евклидово изображение.
  • Подходите за графично обучение са разделени на 2 фракции; sспектрални методи и пространствени методи. Класификациите се определят чрез изследване на използването на собствено разлагане и свързани операции.
  • Спектралните методи се опитват да използват концепции като сигнали за представяне на характеристики на възел и операции като преобразуването на Фурие за агрегиране на информация за възел и извършване на прогноза.
  • Пространствените методи използват операции като предаване на съобщения и методи за представяне като псевдокоординати за агрегиране на информация между възли и извършване на прогноза.

Следва гмуркане в повтаряща се графика и методи, базирани на вниманието🔥

Нуждаете се от повече съдържание като това?

Следвайте ме в LinkedIn, Facebook, Instagram и, разбира се, Medium за повече съдържание.

Цялото ми съдържание е на моя уебсайт и всичките ми проекти са на GitHub

Винаги се стремя да се срещна с нови хора, да си сътруднича или да науча нещо ново, така че можете да се свържете с [email protected]

Нагоре и напред, винаги и само 🚀