On the Relations and Differences between Popper Dimension, Exclusion Dimension and VC-Dimension

TY - CHAP

T1 - On the Relations and Differences between Popper Dimension, Exclusion Dimension and VC-Dimension

AU - Seldin, Yevgeny

AU - Schölkopf, Bernhard

PY - 2013/1/1

Y1 - 2013/1/1

N2 - A high-level relation between Karl Popper’s ideas on “falsifiability of scientific theories” and the notion of “overfitting” in statistical learning theory can be easily traced. However, it was pointed out that at the level of technical details the two concepts are significantly different. One possible explanation that we suggest is that the process of falsification is an active process, whereas statistical learning theory is mainly concerned with supervised learning, which is a passive process of learning from examples arriving from a stationary distribution. We show that concepts that are closer (although still distant) to Karl Popper’s definitions of falsifiability can be found in the domain of learning using membership queries, and derive relations between Popper’s dimension, exclusion dimension, and the VCdimension.

AB - A high-level relation between Karl Popper’s ideas on “falsifiability of scientific theories” and the notion of “overfitting” in statistical learning theory can be easily traced. However, it was pointed out that at the level of technical details the two concepts are significantly different. One possible explanation that we suggest is that the process of falsification is an active process, whereas statistical learning theory is mainly concerned with supervised learning, which is a passive process of learning from examples arriving from a stationary distribution. We show that concepts that are closer (although still distant) to Karl Popper’s definitions of falsifiability can be found in the domain of learning using membership queries, and derive relations between Popper’s dimension, exclusion dimension, and the VCdimension.

M3 - Book chapter

BT - Festschrift in Honor of Vladimir N. Vapnik

PB - Springer

ER -