11
$\begingroup$

I am an electrical engineer and trying to make a transition into machine learning. I read in multiple articles that I have to learn data structures and algorithms, before this I have to learn about mathematical proofs. I started studying it on my own using the material available on MIT's OCW, while I did grasp the concepts of induction and well ordering etc..

I've been struggling with the exercises for a very long time and it's really frustrating. I can easily deal with any type of proofs that I saw before (e.g. once I saw the proof of a recurrence question I became pretty good at proving them). My problems start when I face an unusual question. I feel like I am memorizing the proofs rather than learn how to prove.

Is there any way (or any resources) that can improve my proving skills in a way that whenever I see an unusual question (like the checkers tiles and chess tiles type of questions) I don't have to stare at them for 2 hours before giving up?

$\endgroup$
  • 33
    $\begingroup$ I don't think you need to understand proofs in order to be successful in applying standard machine learning algorithms. It's more engineering than math. $\endgroup$ – Yuval Filmus Aug 5 at 21:27
  • 14
    $\begingroup$ @YuvalFilmus I'd say “more engineering than maths” is actually optimistic. Many ML people work more like chefs than engineers, nevermind mathematicians: they just follow recipes that may involve some basic calculations, but apart from that it's lots of trial&error rather than following a real rigorous plan. And good luck getting them to prove any guarantees about how the model will behave in the end! $\endgroup$ – leftaroundabout Aug 6 at 16:17
  • 1
    $\begingroup$ ML is Software Engineering, Statistics, Linear Regression. Learning "how to prove things" isn't a requirement unless you're going into academic Computer Science. $\endgroup$ – OrangeDog Aug 7 at 17:11
  • $\begingroup$ I'd recommend taking the coursera course from Sedgewick via Princeton University on data structures and algorithms. Great course, little mathematics needed (just some Java skills) $\endgroup$ – p32094 Aug 10 at 22:33

12 Answers 12

41
$\begingroup$

I feel like i am memorizing the proofs rather than learn how to prove

You can't learn "how to prove". "Proving" is not a mechanical process, but rather a creative one where you have to invent a new technique to solve a given problem. A professional mathematician could spend their entire life attempting to prove a given statement and never succeed.

I can easily deal with any type of proofs that i saw before ( eg. once i saw the proof of a recurrence question i became pretty good at prooving them). My problems start when i face an unusual question.

That is normal. Any mathematics "proofs" course isn't designed to teach you how to take an arbitrary problem you've never seen before and be able to solve it (since nobody, not even the best mathematics professors can do that). Rather, your learning goals are

  1. Learn how to "read" proofs and judge their correctness

  2. Learn how to "write" down a proof in the right mathematical language

  3. Learn about known proof "techniques" and how to apply them

If you are working on a new, unknown problem, it is normal that you might not be able to solve it. However, knowing and having memorized other proof techniques may help you. Often proofs involve combining a new idea with existing known proof techniques. The more, and the more varied the proofs you already know are, the better your chance of being able to solve the given problem.

You are on the right track. You should simply keep studying proof techniques. The exercises you are doing are good. Don't worry if you get stuck. As you get more experienced and your "toolbox" of techniques grows, you will be able to solve exercises that are less "alike" the previous ones you have seen.

| cite | improve this answer | |
$\endgroup$
  • 13
    $\begingroup$ "You can't learn 'how to prove'". What is that statement supposed to mean? Human are able to learn. Even to prove new fact. An answer should start with "You can learn 'how to prove'". (Of course, for many students, it is not necessary to master that art). $\endgroup$ – John L. Aug 6 at 3:57
  • 18
    $\begingroup$ @JohnL. I think the rest of the answer makes it clear what I mean. If people are able to learn "how to prove", how come nobody has managed to prove $P=NP$ (or $P\not= NP$)? Surely if somebody has mastered the art of "proving", they would be able to prove such a statement? I think the OP has a misconception about what level of mastery they're expected to get from the course. Being "able to prove" is not what the OP thinks it is. $\endgroup$ – Tom van der Zanden Aug 6 at 6:19
  • 8
    $\begingroup$ @TomvanderZanden OP asks, "is there any way ( or any resources) that can improve my proving skills ? in a way that whenever i see an unusual question ( like the checkers tiles and chess tiles type of questions) i don't have to stare at them for 2 hours before giving up". It looks like you misunderstood OP. OP just wants to improve his proving skills, not to prove $P=NP$. In fact, the rest of answer shows, as I understand, how a student or just about anyone can to learn to prove. $\endgroup$ – John L. Aug 6 at 7:03
  • 10
    $\begingroup$ @TomvanderZanden "If people are able to learn "how to prove", how come nobody has managed to prove P=NP" - this sounds like a logical fallacy. Like saying "if people can train to increase how fast they can run, how come nobody has managed to run at a speed of 100 miles an hour yet?". $\endgroup$ – Bernhard Barker Aug 6 at 10:14
  • 9
    $\begingroup$ @BernhardBarker I don't think it's a logical fallacy. It's about the semantics of "learning how to prove". One can "learn multiplication" in the sense that you will be able to take any two numbers (written on a piece of paper) and compute the product. You can't "learn proving" in this sense. A mathematics degree doesn't teach you "how to prove" in the same sense that an engineering degree doesn't teach you "how to invent". It only teaches you known (engineering/mathematics) techniques and principles which you might then be able to combine with a new idea to come up with a new proof/invention. $\endgroup$ – Tom van der Zanden Aug 6 at 12:30
13
$\begingroup$

As other authors have mentioned, partly because proofs are inherently hard, but also partly because of the cold fact that proofs are not written for the purpose of teaching, even in most textbooks. Rather, most proofs are written out of a kind of obligation, as a sort of run-away argument; not presenting proofs at all is considered unacceptable, but writing them in exhausting details would burn the author out as well as endanger the reader getting lost in the woods. Hence, most proofs are succinct on purpose, leaving a lot of dots solely for the reader to connect themselves. While some people find this a helpful exercise, many readers like you and me find it making mathematics unnecessarily challenging. This is also why classroom pedagogy in a university setting is indispensable for professional mathematic learning as the tools of dialogue can fill in the blank of textbook proofs.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ While I agree that "proofs are not written for the purpose of teaching", I think "writing them in exhausting details" is exactly what happens. Take "Introduction to algorithms" for example: it's one of the most famous books, and I believe that their way to present proofs is terrible. They prove the simplest things, like DFS and BFS, in very formal, but so much hard to understand way. I remember I couldn't understand dynamic programming for weeks using this book; and I understood it instantly after someone explained Fibonacci example to me. $\endgroup$ – Dmitry Aug 6 at 16:54
  • $\begingroup$ My point is yes, they write proofs as an obligation. And as obligation, their proofs are correct, but hard to understand. So a different approach is needed: something like a tree: you have a main idea at the top level (and explanation why this idea is natural!), which can be split into subproblems (children nodes). At the leaves of this tree we have a hardcore math. This way will allow a reader to predict what happens next (this is what happened to me with my awesome math analysis teacher), not just follow the proof. $\endgroup$ – Dmitry Aug 6 at 16:57
  • 1
    $\begingroup$ @Dmitry That's exactly what happens, right? When a proof is so formal and detailed, you get lost in the woods. Hence, proofs are presented in short, intuitive forms. But the only problem is that my intuition is different from yours, and if that gap exists, it is sometimes insurmountable; I can't get inside your brain. With a formal proof, at least most readers can go through it if they could tolerate the grind, which I suspect is the intention of Intro to Alg. However, I dislike that approach pretty much the same. $\endgroup$ – apen Aug 6 at 17:43
  • 7
    $\begingroup$ I really, really disagree with this answer. I don't see proofs as there just for the sake of "obligation", nor do I think they are not there for learning. I learn a great deal about the subject matter from studying proofs. I learn things that are not in the statement of the theorem nor in the surrounding text. I think authors write proofs so that they will be understood by their intended audience, perhaps with some challenge to a student to work at it a bit. (It's not that I find reading proofs to be easy. That depends, but I have to work hard at it, often.) $\endgroup$ – Mars Aug 6 at 22:21
  • 1
    $\begingroup$ @user28324 You might be running into the fact that your physics "proofs" are closer to "just so stories" than to a solid arguments, while the mathematical "proofs" are closer to an actual solid argument. (Note: formal and provably correct proofs are much longer than even technical proofs in mathematics. See Coq) $\endgroup$ – Yakk Aug 7 at 13:16
11
$\begingroup$

I can certainly recommend the book of G. Polya's, How to Solve It. It is a standard classic, not to be missed. There is a newer book How to Read and Do Proofs: An Introduction to Mathematical Thought Processes by Daniel Solow that may be more accessible.

In any event doing proofs is entirely Unnatural for humans. It is a discipline that requires careful thought we do not normally use. We are used to making many assumptions to get through our days and our lives. If we had to justify the first of them we could not get out of bed. A mathematical proof strips away the assumptions and lives on only what you can show clearly and unambiguously.

I had the similar trouble with problems over trigonometric identities. Trying to get from the start to the finish is easy when there is a known, learned method. Identities may require multiple steps in unknown directions without much sense of direction. Proofs are a bit easier since the logical methods are fairly limited and known (if you read the books). Keep at it.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ what's weird is i was pretty good with trig and complex numbers identity problems. xD $\endgroup$ – user28324 Aug 6 at 18:37
  • $\begingroup$ i found the book you mentioned used by a course in stanford, i also found online lectures given by the author, i guess i will try it. It looks more focused on mathematical proofs than polya's book $\endgroup$ – user28324 Aug 6 at 18:45
  • $\begingroup$ I thought of this book too, then saw your answer. It's a good read. I mean, Polya's. Not sure about Solow's book, but will look for it. $\endgroup$ – auspicious99 Aug 7 at 11:54
  • $\begingroup$ @User28324 I only just noticed myself that Polya's is How to Solve It while the other is How to Prove it. $\endgroup$ – Elliot Aug 7 at 14:53
4
$\begingroup$

I like Tom's answer: there's no magic bullet but you just need to continue doing exercises and gradually you will develop a better intuition and know how to attack a problem.

As for resources, you might like G. Polya's book How to Solve It. Looks like the Wikipedia article gives a nice and somewhat detailed overview. Basically, the book will offer you a strategy or methods for dealing with mathematical statements and their proofs.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ any idea if machine learning researchers use mathematical proofs as often as statistics and linear algebra ? $\endgroup$ – user28324 Aug 6 at 0:25
  • $\begingroup$ @user28324 That's not so easy to say - ML is a large field and perhaps some subfields don't need proofs at all. But this is a bit like a student saying "I have never needed matrices for anything" - is it because you didn't know matrices so well you were unable to realize you could have applied them? I mean, a piece work could be much better if you could additionally prove something. Especially in ML, theorems tend to be highly valued as they can explain why things work in practice. $\endgroup$ – Juho Aug 6 at 6:54
  • $\begingroup$ @user28324, there are plenty of proofs when your objective can be represented as a convex function: for multiple algorithms, it's shown that they converge, and converge fast. For non-convex settings, the situation is worse since even finding a local minimum is NP-hard in general. I believe the best results are something like convergence to second-order stationary points. For specific algorithms, there are specific guarantees: e.g. it was shown that k-manes++ gives a $O(\log k)$ approximation. $\endgroup$ – Dmitry Aug 6 at 15:33
  • 1
    $\begingroup$ That is a very good book, not just for mathematicians but also programmers & computer scientists. My copy's almost fallen apart. In fact, I think I'll re-read it. $\endgroup$ – J.G. Aug 6 at 15:51
  • 4
    $\begingroup$ @Dmitry No comment within this character limit can do justice to how little justice Wikipedia does to the content in their abbreviation of it. But the book's example problems are definitely not standard in high school. To be honest, some aren't standard anywhere. It's a book about how to attack arbitrary problems you encounter. $\endgroup$ – J.G. Aug 6 at 16:22
4
$\begingroup$

Why are mathematical proofs so hard?... I have to learn data structures and algorithms,

My guess is you'll also want to learn about algorithms' space and time complexity, as quantified in big O notation. Time complexity, in particular, hints at why proofs are hard. If I promised you there is a proof of at most length $n$ of a given statement, how would you find it? In theory, you could go through all proofs of length $\le n$ until you find one, which would take exponential time, say $O(ne^{cn})$ (I've included a factor of $n$ for reading time). That's far too inefficient for our purposes, unless $n$ is very small. There might be a much better algorithm, but no-one's found a particularly efficient general one. That's why proving things remains a "creative" exercise, by which we mean "we don't know in pseudocode terms how such thinking works".

Is there any way (or any resources) that can improve my proving skills in a way that whenever I see an unusual question (like the checkers tiles and chess tiles type of questions) I don't have to stare at them for 2 hours before giving up?

You call such questions unusual, yet you know what examples to give. That's the crux of the issue right there. It's only "unusual" in your experience if you've not seen it (much). As other answers note, just keep learning more tools. Hopefully, you should then be able to tell which ones help with a problem. Judging by your choice of examples, the use of invariants in proofs is something you could work on. I don't know how good your big/small O notation is, but I'll mention that topic again because it's often useful to prove results, such as inequalities or anything dependent on them, e.g. limits (at least if you're meant to give an $\varepsilon$-$\delta$ proof).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Automated proof writers do exist, and proof writing aids as well. Tools that let you write out an informal "human" proof and help fill in gaps between your statements with fully formal provable steps. If I remember right, much of it involves pattern matching (basically, "books" of techniques). $\endgroup$ – Yakk Aug 7 at 13:18
  • $\begingroup$ @Yakk Laudable efforts I hope continue to yield fruit. They work well for proving certain kinds of theorem, as dictated by the "book" you give them. But new results, even if they have reasonably short proofs (as they sometimes do), are beyond such software for now. That's why mathematicians still have to think so much. Unfortunately, making the book big enough to prove every known result is a double-edged sword, as it forces the computer to consider far more options. $\endgroup$ – J.G. Aug 7 at 13:27
  • $\begingroup$ I don't see why it would be harder than Go. ;) (that is a bit of a joke, but only a bit of one) $\endgroup$ – Yakk Aug 7 at 13:31
  • $\begingroup$ @Yakk Then I'll respond to the non-joke part: you can't prove theorems just through satisficing. $\endgroup$ – J.G. Aug 7 at 14:32
3
$\begingroup$

Some proofs have to be cumbersome, others just are cumbersome even when they could be easier but the author didn't came up with a more elegant way to write it down. Coming up with a simple proof is even harder than understanding a proof and so are many proofs more complicated than they should be.

There is no general advice how to understand proofs (elegant or not). Some technique that you can try is to disprove the statement. Why does the proof work? What would happen when you leave out one of the preconditions for the proof?

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

If you're already pretty handy with programming, you might enjoy learning to use an interactive proof assistant like Coq or Lean. A proof assistant is a programming language with a very rich type system in which it's possible to express constructive logic. These kinds of languages largely operate on the notion that there's a direct analogy between programs and their types on the programming side, and between propositions and proofs on the math side. (This is called the Curry-Howard isomorphism.)

A really interesting project on these lines is the Natural Number Game. The game is part of a larger program by several professors at Imperial College of London to formalize all of undergraduate mathematics using the proof assistant Lean. At the start of the game, you're given just the Peano axioms of arithmetic: 0 is a natural number, the successor of a natural number is a natural number, and the successor of any natural number is not equal to itself. You're allowed to use the usual rules of predicate logic and induction. The object of the game is to come up with rigorous, formal proofs of the properties of addition, multiplication, and some basic number theory.

Proof assistants effectively gamify doing pure mathematics -- they remember the rules for you and they give you feedback practically in real time. If you're looking for a way to improve your skills at doing proofs through self-study, I think proof assistants are great tools. On top of that, they're also used in formal verification of computer programs, which is an interesting and employable specialization in its own right.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

I've been struggling with the exercises for a very long time and it's really frustrating. I can easily deal with any type of proofs that I saw before (e.g. once I saw the proof of a recurrence question I became pretty good at proving them). My problems start when I face an unusual question. I feel like I am memorizing the proofs rather than learn how to prove.

So you do know how to read proofs, but you're finding these ones to be difficult. I think there are probably a few things that are relevant.

One is that differences between ability required by different mathematical textbooks is exponential, not linear. I have seen books titled "Introduction to X" that are much harder than books titled "Advanced Y". Authors have in mind different audiences, and the levels of difficulty are correspondingly different.

Second, it might just be that once you get more familiar with concepts and proofs in a particular area, they will become easier. As some of the other answers indicate, proofs often leave out steps that the author thinks would be obvious for their intended audience. None of us would expect a proof to point out that two plus two equals four. Some things that one reader finds completely mysterious are like $2+2=4$ for other readers. That doesn't mean that the book or article isn't for you, though. If you can work through the missing steps, you will get a deeper understanding of the subject, and after you do that a few times, what was difficult will become easier. (A proof in a book that's a little bit too hard is like an exercise.)

Third, I understand if you don't want to stare at a proof for two hours, but I think that during that period, you may be learning a lot. What you are doing during that time is thinking through different interpretations of the concepts and steps and possible ways to get from one step to another, and thinking about what assumptions the author had in mind. That is a learning process, and I think that doing that helps one understand other things more easily, later.

I do a lot of self-study in subjects that are unfamiliar to me. Sometimes I use two or three books for one subject, because what's left out in one book will be explained more clearly in the other. Sometimes I find that I have to go and read books on other subjects, because the author assumed that their readers would all have a certain background--and I don't have it. That doesn't necessarily mean I read the entire book on the other subject. Sometimes I just read enough so that I can understand the book I really want to understand. This is not a bad practice. I end up learning things that I wasn't interested in learning, but that turn out to be useful later.

(Maybe all of this seems obvious, but hopefully some comment here is helpful to someone.)

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

I am an electrical engineer as well as a mathematician by training. After completing my undergraduate in EE, I switched to maths and finally obtained a hard-earned doctorate in it. I won't say that I am a particularly bright kid. However I have always found mathematics easy and consequently boring. However, thanks to my dad, even at a very early age (about eight or nine) I knew that there is far more to maths than my school. So I endured it.

I also derived my self-esteem from being good at maths (yes, wrecks like me do exist). I probably still do.

Since I progressively did less and less maths, by the time I completed my high school, I was somewhat scared of it. My situation would be very much that same as yours in my first or second year of undergraduate, which was very bad for my self esteem. Then I begun my reeducation in maths - largely by self-study and also by way of audit courses, which I attended at the expense of my regular EE curriculum. EE, anyway, was a cake-walk for me. But mathematics proved a very hard nut to crack.

I continued my mathematics studies after college, enrolled into maths program and after a long, hard and frustrating struggle did complete my doctorate.

I don't know which area of maths you are looking at. But I will not suggest any online resources or guest lectures to get entry into maths. Such things only give you an illusion of understanding. You will have to pick up a book. You will have to pick up a pen. And you will have to start writing. And you too will learn the hard way, only the hard way. If you have someone to discuss things with, great! Else toil in obscurity.

To begin with, talk to someone to get the first couple of books suitable for you. Rest you can figure out yourself.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

I can't believe no one else is mentioning this but you are probably overdoing it if you want to learn applied machine learning. You'd be better off brushing up on linear algebra, and basic computer science. There are some great specializations on coursera - specifically the Machine Learning and Mathematics for Machine Learning tracks (it says there is a cost but you can audit each of the courses individually for free - there are about 8 of them total between the two specializations); Andrew Ng's Deep Learning specialization (5 courses) is also fantastic. Then sign up for Kaggle and apply what you're learning. I understand personally wanting to know how to derive mathematical proofs with rigor but no one is paying you to do that in production. You're better off actually studying machine learning.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

It sounds like your issue is that you lack experience with logical reasoning in general. The fact that you can prove similar theorems easily by adapting a proof that you have seen before, shows that you do not have a problem with understanding proofs. But I suspect you have never learnt first-order logic proper, which is a necessary ingredient in real mathematical reasoning. Once you learn a deductive system for FOL (for which I recommend Fitch-style), it actually becomes easy to deal with arbitrary areas of mathematics even if they are completely new. However, there is an upfront cost, which is roughly half the effort you need to put in to learn a new programming language. So I leave you to decide whether to try or not.

Independent of learning FOL, you also need a source for practice, and for that I recommend How to Prove It by Daniel Velleman. It does teach you a bit of logical reasoning, and it gives you plenty of neat and interesting things to prove.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ By the way, finding a proof of a mathematical problem you have never seen before is very much like solving a new chess puzzle. To solve a mate-in-n puzzle, you need to find a winning strategy. Guess what? FOL can be understood using game semantics. $\endgroup$ – user21820 Aug 7 at 14:15
0
$\begingroup$

Theoretically Proof Search is a rather high-complexity computational task.

For the case of Boolean propositions, it is coNP-complete, and therefore conjectured to not have algorithms that are faster than exponential in the size of the formula you want to prove.

For proof in Peano Arithmetic (and many stronger systems like standard set theory ZFC), it is undecidable. So there is no "algorithm" that one can learn and follow to find proofs.

Godel, in his famous letter to von Neumann, speculates about the possibility of an efficient algorithm that can be used to find proofs. Turns out he was kind of touching on the subject of P vs. NP.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.