wymiar Natarajana

W teorii prawdopodobnie poprawnego uczenia maszynowego wymiar Natarajana charakteryzuje złożoność uczenia się zestawu funkcji, uogólniając od wymiaru Vapnika-Chervonenkisa dla funkcji boolowskich do funkcji wieloklasowych. Pierwotnie wprowadzony jako Wymiar Uogólniony przez Natarajana, został później przemianowany na Wymiar Natarajana przez Hausslera i Longa.

Definicja

Niech $będzie$ zbiorem funkcji ze zbioru $displaystyle$ zbioru $Y}$ . ${\ Displaystyle H}$ rozbija zbiór do $\ Displaystyle C \ podzbiór X}$ , jeśli istnieją dwie funkcje ${\ Displaystyle f_ {0}, f_ {1} \ w H}$ takie, że

• Dla każdego ${\ Displaystyle x \ w C, f_ {0} (x) \ neq f_ {1} (x)}$ .
• Dla każdego istnieje taka funkcja, że $displaystyle$$B \ podzbiór C$

dla wszystkich ${\ Displaystyle x \ w b, h (x) = f_ {0} (x)}$ i dla wszystkich ${\ Displaystyle x \ w CB, h (x) = f_ {1} (x)}$ .

Wymiar Natarajana z H to maksymalna liczność zbioru rozbitego przez ${\ displaystyle H}$ .

Łatwo zauważyć, że jeśli ${\ Displaystyle | Y|=2}$ wymiar Natarajan załamuje się do wymiaru Vapnik Chervonenkis .

Shalev-Shwartz i Ben-David przedstawiają obszerny materiał na temat uczenia się wieloklasowego i wymiaru Natarajan, w tym jednolitej konwergencji i zdolności uczenia się.