In a nut shell, machine learning is a class of algorithms that can "train" data-structures. You provide a trainer with partial information, and it will produce some entity which can be queried on information related to, but not necessarily present in the input.
Clearly, the computational power of this model must depend both on the trainer and the trainee: The trainer must be powerful enough to understand the input, and the trainee must be powerful enough to answer questions about it later.
There is a wide array of "trainers" in machine learning- some only work on specific "trainees", and some work on many.
Given that I know the complexity of my input, how do I select a trainer/trainee pair? For each grammar in the Chomsky hierarchy, what would be a canonical pair that can recognize it? How does machine learning relate to automa theory in general?