dimensión de Natarajan

En la teoría del aprendizaje automático probablemente aproximado , la dimensión de Natarajan caracteriza la complejidad del aprendizaje de un conjunto de funciones, generalizando desde la dimensión de Vapnik-Chervonenkis para funciones booleanas a funciones multiclase. Introducida originalmente como la Dimensión Generalizada por Natarajan, ^{[ 1 ]} posteriormente fue renombrada como Dimensión de Natarajan por Haussler y Long. ^{[ 2 ]}

Dejar${\displaystyle H}$ser un conjunto de funciones de un conjunto${\displaystyle X}$a un conjunto${\displaystyle Y}$.${\displaystyle H}$rompe un conjunto${\displaystyle C\subset X}$ si existen dos funciones${\displaystyle f_{0},f_{1}\in H}$de tal manera que

• Por cada${\displaystyle x\in C,f_{0}(x)\neq f_{1}(x)}$.
• Por cada${\displaystyle B\subset C}$, existe una función${\displaystyle h\in H}$de tal manera que

a pesar de${\displaystyle x\in B,h(x)=f_{0}(x)}$y para todos${\displaystyle x\in CB,h(x)=f_{1}(x)}$.

La dimensión de Natarajan de H es la cardinalidad máxima de un conjunto fragmentado por${\displaystyle H}$.

Es fácil ver que si${\displaystyle |Y|=2}$, la dimensión de Natarajan colapsa a la dimensión de Vapnik-Chervonenkis .

Shalev-Shwartz y Ben-David ^{[ 3 ]} presentan material exhaustivo sobre el aprendizaje multiclase y la dimensión de Natarajan, incluyendo la convergencia uniforme y la capacidad de aprendizaje. Recientemente, Cohen et al. ^{[ 4 ] [ 5 ]} demostraron que la dimensión de Natarajan es el término dominante que rige la capacidad de aprendizaje PAC multiclase agnóstica.