ТЕОРЕМА КОВЕРА ТА ЗАДАЧА ВІДОКРЕМЛЕННЯ МНОЖИН ЗА ДОПОМОГОЮ ПОЛІНОМІАЛЬНИХ ПОРОГОВИХ ФУНКЦІЙ (PTF – POLYNOMIAL THRESHOLD FUNCTIONS)

Анотація

Відокремлення підмножин точок у евклідовому просторі – базова задача аналізу даних і нейрообчислень; її розв’язність істотно залежить від класу допустимих розділювальних поверхонь. Лінійні моделі мають обмеження (для 3 змінних лінійно роздільними є лише 104 із 256 дихотомій), що спонукає перейти до нелінійних підходів. У статті представлений повний комбінаторний перелік усіх 256 можливих розділень вершин, точно кількісно визначено межі роздільності поліномами другого ступеня. Автори показують, що з 22 унікальних класів еквівалентності (орбіт) дихотомій, які існують відносно групи симетрії куба, лише один клас є квадратично нероздільним. Цей аналіз не лише дає вичерпну відповідь на поставлене питання, але й слугує ілюстрацією фундаментальних обмежень, властивих навітьпотужним нелінійним моделям при роботі з високоструктурованими даними.Для досягнення цієї мети автори використовують ізоморфізм між геометричною задачею розділення та алгебраїчною задачею реалізації булевих функцій. Кожна дихотомія вершин куба однозначно відповідає булевій функції трьох змінних, а питання квадратичної роздільності стає еквівалентним питанню про те, чи є така функція поліноміальною пороговою функцією другого ступеня.Результат дає точну межу виражальної здатності квадратичних порогових елементів для задач бінарної класифікації у низьких вимірах і пояснює, чому вже перехід від лінійних до квадратичних моделей кардинально підсилює  класифікаційну потужність.