# sorting functions by amount of conditions for a random dataset to be described using it?

Given a finite dataset like 1, 2, 3, 4 You could find infinite functions, for simplicity I found 2:

1. Add 1 for the next data point, so the sequence continues as 5, 6, etc.

2.Cycle through 1, 2, 3, 4, so the next data point is 1, repeating 1, 2, 3, 4.

Function 2 is more likely to overfit since the conditions for a dataset to be described using function 2 are smaller meaning you could find more datasets possibly described by function 2 than datasets described by function 1.

Since you could describe every single dataset as a cycle consisting of all of the data points in the dataset. Is there a formal method to categorize functions like this for every type of function to reduce overfitting in an ML model?

• There are criteria such as the AIC that penalize a statistical model for having many parameters. In your example, I'd say the first model has 2 parameters while the second has 4. (However, resampling methods such as cross-validation seem to be more popular for model selection in ML.) Commented Jul 2 at 18:42

If you instead are interested in models, which are families of functions (and say the first one is sampled from family of arithmetic progressions, and the second from cycles of length up to $$100$$), then you need VC dimension, which is largest size of dataset s.t. your model can fit any dataset of this size. Then family of arithmetic progressions has VC dimension of 2, and family of cycles has VC dimension of 100.