Формальна постановка задачі машинного навчання

Нехай задана множина об'єктів $X$, множина допустимих відповідей $Y$, і існує цільова функція (target function) $y^*: X \to Y,$ значення якої $y_i = y^*(x_i)$ відомі тільки на скінченній підмножині із $l$ об'єктів $\{x_1, \ldots, x_l \} \subset X$. Пари об'єкт-відповідь $(x_i, y_i)$ називаються прецедентами. Множина із $l$ пар $X^l = \{(x_i, y_i)\}_{i=0}^{l}$ називається навчальною вибіркою (training sample).

Задача машинного навчання (навчання за прецедентами) полягає в тому, щоб за вибіркою $X^l$ відновити залежність $y^*$, тобто побудувати вирішальну функцію (decision function) $a: X \to Y$, яка наближала (апроксимувала) б цільову функцію $y^*(x)$, причому не тільки на об'єктах навчальної вибірки, а й на всій множині $X.$ Вирішальна функція $a$ повинна допускати ефективну комп'ютерну реалізацію; з цієї причини будемо називати її алгоритмом.

З точки зору математики, ситуація виглядає так -- нехай є деяка невідома функція $f:X \to Y$, і нам дано лише обмеження $\bar f: \bar X \to Y$ цієї функції на підмножину $\bar X \subset X.$ В задачі машинного навчання потрібно відновити функцію $f$ по її обмеженню $\bar f$. В такій загальній постановці не існує єдиного розв'язку, тому для обмеження можливих варіантів будемо виходити з припущення, що $f$ визначає деякий закон природи і множина $\bar X$ достатньо велика щоб цей закон відновити.

Машинне навчання, по суті, займається розглядом наступних питань:

• Яким чином задаються об'єкти?
• Якими можуть бути відповіді?
• Як будувати функцію яка апроксимує нашу невідому залежність $a$?
• В якому сенсі $a$ наближає $y$?