I'm looking for a Machine Learning course that would give the maths behind algorithms rather than simply teach how to apply them. I've looked at Udacity Into to Machine Learning and Andrew Ng's course on Coursera, and they both seem too applied to me. Any recommendations of textbooks would also be much appreciated.
To add on to @Digio, I would recommend Abu-Mostafa's Learning From Data, which contains enough statistical learning mathematics to get you excited and wanting more.
Note, Andrew Ng has a more mathematical course in Stanford Online not Coursera.
Recommendations would always be subjective, for me, I personally like
Both books are classical books in machine learning community and freely available.
Related question can be found here.
Try to dig deeper in a specific topic. Ngs course only scratches the surface, but other more specific courses are more theoretical/mathematical.
Bayesian networks/ Markov networks:
Neural Networks for Machine Learning is also a rather theoretical course as it is really profound. Nonetheless it is not as mathematical as the PGM course I mentioned above.
However if you want to understand the theory of Machine Learning itself and not the algorithms you can go for a textbook. In this case go for what @digio proposed.
This (archived) edX machine learning course from Columbia explains a lot of underlying math. For example they show regularized linear regression and probabilistic matrix factorization from Bayesian (Maximum A Posteriori) perspective.
Understanding Machine Learning is a (freely available) textbook that takes computational learning theory approach, and contains derivations and calculations/estimation of VC dimension of classifiers.