Натараджанское измерение

В теории вероятно аппроксимально правильного машинного обучения размерность Натараяна характеризует сложность обучения набора функций, обобщая размерность Вапника-Червоненкиса для булевых функций на многоклассовые функции. Первоначально представленное как Обобщенное Измерение , Натараджаном переименовали его в « Натараджанское измерение» . Впоследствии Хаусслер и Лонг

Определение

Позволять $H$ быть набором функций из множества $X$ в набор $Y$. $H$ разрушает набор $C\subset X$ если существуют две функции $f_{0},f_{1}\in H$ такой, что

• Для каждого $x\in C,f_{0}(x)\neq f_{1}(x)$.
• Для каждого $B\subset C$, существует функция $h\in H$ такой, что

для всех $x\in B,h(x)=f_{0}(x)$ и для всех $x\in C-B,h(x)=f_{1}(x)$.

Натараджанская размерность H — это максимальная мощность множества, разбитого $H$.

Легко увидеть, что если $|Y|=2$измерение Натараяна схлопывается до измерения Вапника Червоненкиса .

Шалев-Шварц и Бен-Давид представить всеобъемлющий материал по многоклассному обучению и измерению Натараджана, включая единообразную конвергенцию и обучаемость.