How to measure model complexity in the context of classification decision trees? Let us have some response variable y which can only get 0 or 1, and some predictor space in $X \in R^n$ (for illustration let's say $n=2$ and that we have $X1, X2$ two explanatory variables, each one between -1 to 1).
I can intuitively say that if the rule of the tree is only y = 1 if X1 > 0 (and 0 otherwise), then the model is not very complex. However, if I say that in order for y to be equal to 1 I need that X1 > 0 & X2 > 0, than this model "feels" to be more "complex". Also, if y = 1 only when observations in $X \in R^2$ are within the radius of 1/2 (i.e. a circle that within it y = 1 and outside of it y = 0), then it is clear I will need infinite number of linear splits in order to create a model that knows when y is 0 and when it is 1. It would also seem to me to be a more "complex" model than the one where y = 1 only when observations in $X \in R^2$ are within the radius of 1/10000 (since then most of the observations would just be 0).
Which type of measure(s) could help here? 
 A: I believe this has been discussed in the literature. In regression context, the measures of model complexity utilize the linear regression relation of the rank of the projection matrix being equal to the number of (non-collinear) regressors. So Ye (1998) generalized this by perturbing the data $\tilde y_i^{(k)} \leftarrow y_i + \delta_i^{(k)}$, running your favorite machine learning model (these were called data mining back then) on these perturbed data, getting predictions $\hat y_i^{(k)}$, and measuring how much the predictions changed in response to perturbations. Repeating this many times, you collect a big data set with such predictions as outcomes, and the magnitude of perturbations as regressors, $\hat y_i^{(k)} \sim \mbox{const} + h_i \delta_i^{(k)}$. Then the sum of regression coefficients $h_i$ gives you the degrees of freedom.
The HTF ESL book repeats this argument in Section 7.6, although without attribution to Ye. They further discuss MDL and VC dimension, which are probably relevant to your case, too.
A: First, it is important to note that you are not talking about the complexity of the model, but the complexity of the relation between X and Y, which has nothing to do with modelling. When we try to figure out such relations, we use models, which typically involve some kind of assumptions, etc. in order to track down that relationship. but there is an inherent difference between the complexity of the underlying relationship and the complexity of a model.
Given that, there is always a tradeoff between model complexity (in some intuitive sense) and model accuracy. when there is underlying complex relationship we try to model, the simpler the model is, the less accurate are its prediction likely to be. So the underlying relationship complexity is in some sense the "sum" of actual model complexity and its lack of fit.
I think that the AIC measure is an attempt to capture such complexity (that takes into account both inaccuracy and the model's "degrees of freedom" so to speak. I use it often to compare models that fall under common "strategies" even if they do not contain the same variables (e.g. two logistic regressions with the same response, but with different set of predictors), but tend to find it less useful/reliable comparing models of different nature.
Second, the example you bring about the circle, emphasize the importance of feature representation and two different sources of "complexity". after all, with a simple polar transformation, the circle with fixed radius become analogous to your first example. so what is worse? another explanatory variable or a transformation on an existing one? and is sin(x) is more complex that x^2 as transformations?
This is to emphasize how "measure of complexity" is totally dependent on the context. you must have some kind of a "loss function" that will quantify/penalize you for any "step" you do in order to get from X to Y. and this function is unlikely to have universal features. it is context specific.
I know this is not the kind of answer that you expected (sorry), But I do think there is no hope for the expectation you expressed in your question.
HTH
