I took Prof. Mohri's class this spring, and we actually used a draft version of this book. I agree with you that it's very theoretical, but Bishop, Mitchell, an

I took Prof. Mohri's class this spring, and we actually used a draft version of this book. I agree with you that it's very theoretical, but Bishop, Mitchell, and the other ML resources don't address learning theory. VC-dimension isn't for everyone, but if you need to know about it, this is the book you want to use. There's also the added bonus of this text coming from Prof. Mohri et al.'s experiences at Google, so there's a lot of discussion about online algorithms and ranking (which you don't see in many other places).