How does one even begin to mathematically model an AI algorithm, like alpha-beta pruning or even its thousands of variations, to determine which variation is best?
Begin by learning the mathematical treatments at their foundations.
- Game theory pioneered John von Neumann and Oskar Morgenstern
- Information theory pioneered by Claude Shannon (Bell Labs)
- Incompleteness pioneered by Kurt Gödel (which led to Alonso Church's lambda calculus and Turing's completeness which led to a general criteria that defines what a programming language must do to be called general purpose.
You could take a course in Finite Math and Discrete Math, but there is no better way to understand than to go to the authors of the original ideas, which is why MIT and Cal Tech require it of freshmen. We don't need to be genius to understand genius. We just need to take the time to read. That's the genius of them.
It is good to evaluate the pruning of decision trees mathematically, and modeling the general and specific cases is the right approach. Congratulations for seeing that. The code for pruning is far more developed than the mathematics for modeling it. The literature usually shows speed results just before the conclusions, which is more like sitting in the audience with pop corn and a wager ticket than understanding the anatomy and proper care of a horse.
Once you understand what occurred a century ago that led to all computer science and see what mathematical conventions originated and in what context then you can read work like
Appl. Math. L&t. Vol. 4, No. 6, pp. 77-80, 1991 Printed in Great Britain. 08939659191 Pergamon Press plc Turing Computability with Neural Nets T. SIEGELMANN AND EDUARDO D. SONTAG Department of Computer Science, Rutgers University Department of Mathematics
... and ...
A Survey of Decision Tree Classifier Methodology S. Rasoul Safavian David Landgrebe TR-EE 90-54 September, 1990 School of Electrical Engineering Purdue University West Lafayette, Indiana 47907 (NASA-CR-188208).
WARNING: Don't be surprised if you are disappointed by most recent work after reading von Neuman, Shannon, and Gödel.