Confessions of a Math Idiot

I wasn't always a math idiot. I took the ‘advanced’ math classes in grade school. While I was in high school I took Calculus II over at the community college (the professor was a Harvard grad with a Ph.D. in theoretical physics from Cornell). I took the AP Calc test and my math SAT score was nothing to sneeze at. I went as far as differential equations and linear algebra in college.

But then I found out about computers. On the first day of 6.001 the professor wrote this on the board:

                f(x + dx) - f(x)
f'(x) =  lim  ------------------
        dx->0        dx

(define dx 0.0001)

(define (deriv f)
  (define (f-prime x)
    (/ (- (f (+ x dx)) (f x))
       dx))
  f-prime)

(define (cube x) (* x x x))

(define g (deriv cube))

(g 4)
;Value: 48.00120000993502

It was the beginning of the end.

I started to unlearn math. I began seeing math through the eyes of a computer scientist. Things that I believed in stopped making sense. I used to believe that integration and differentiation were opposites: that one ‘undid’ what the other ‘did’. But look:

(define (deriv f) 
   ...)

(define (integrate f low hi)
   ...)

The arity of deriv is 1 and the arity of integrate is 3. They can't be opposites!

I used to think you couldn't divide by zero. But look:

(/ 2.3 0.0)
;Value: #[+inf]

I started seeing ambiguities in even the simplest math. Is ‘x + 3’ an expression, a function, or a number? Is ‘f(x)’ a function or the value of a function at x? When I see log (f(x)) = dH(u)/du + y, are they stating an identity, do they want a solution for y, or are they defining H?

I started reading weird things like Gosper's Acceleration of Series and Denotational Semantics by Joseph Stoy and Henry Baker's Archive. These look like math, but they seemed to make more sense to me.

But I drifted further away from mathematics. A few years ago a fellow computer scientist explained to me the wedge product. It is a straightforward abstraction of multiplication with the only exception being that you are not permitted to ‘combine like terms’ after you multiply (so you get a lot of irreducable terms). Then he explained the Hodge-* operator as the thing that permits you to combine the like terms and get answers. It's really not very complicated.

But then I looked it up online.

The exterior algebra ∧(V) over a vector space V is defined as the quotient algebra of the tensor algebra by the two-sided ideal I generated by all elements of the form x⊗x such that x ∈ V.

And I discovered that I'm now a math idiot.

I'm probably going to have to live like this the rest of my life. I'm trying to cope by relearning what I used to know but translating it to a style I'm more comfortable with. It will be a long process, but I'm optimistic.

How do you approach a problem?

Douglas Gregor wrote me:

I'm trying to hone my problem solving skills. Do you know any good books written on how to solve complex problems? Did school, i.e., teachers, books, labs, peers, help define the process? How do you approach a problem? How do you break it apart — the fluff from the stuff? How do you formulate a plan?

Wow. These are not easy questions.

Years ago I had a book called How to Solve It by George Pólya. I remember not giving it the attention that I think it deserves. I recall that some of the advice seemed rather obvious. In retrospect, I wish I had payed more attention to it. When someone like Pólya suggests something obvious, it probably isn't as obvious as you think and it is probably worth pondering.

College was a huge influence. The whole focus of the undergraduate curriculum was to “teach you how to think”. The detail of the coursework was almost secondary. It was there in order to be stuff to think about. It had the benefit of being topical. You got to know the jargon of the field and get familiar with the kind of day-to-day problems you would encounter, but that was secondary.

Graduate students would teach the recitations, but the professor was usually a tenured researcher. That made a difference. I found that the professors were amazingly sharp people. They also enjoyed tremendously what they were doing and their enthusiasm showed.

Nearly every course would start with a lecture where the professor would say “we're here to teach you how to think&rdquo. Then they would start in on the “first principles”. For example, in electrical engineering we started with Kirchoff's Laws. Now Kirchoff's Laws are really obvious: all the current flowing into and out of a node has to add up to zero (otherwise it would pile up somewhere or come out of nowhere), and all the voltages around a loop had to add up to zero (or you'd have made power out of thin air). But the professor would always start from “first principles&rdquo.

The next thing the professor would do is introduce a model. Invariably the professor would take a pretty simple and straightforward problem and point out that it is essentially impossible to understand and solve. Again, to use the example from electrical engineering, the action of any electrical circuit whatsoever follows Maxwell's equations (it has no choice), but no one is going to solve those (what's the B field around an irregular lump of solder?) The professor would show us the basic model and how to use it to approximate solutions to real problems.

Finally we'd go over the building blocks. There were a selection of primitive elements and a handful of ways to combine them.

What was interesting is that virtually every course took this approach. It didn't matter whether it was chemistry, electronics, physics, or computer science. It came down to “first principles&rdquo, models, and the basic elements.

Another thing that I noticed was the almost absurdly naive way that the professors would approach things. They always wanted to mention their research, so we'd hear about some of the cutting edge of science. The problems that the professors were working on could usually be summed up in a sentence or two: “Why do things fall down instead of up?” “How about if I made a computer chip with really tiny mirrors on it and computed with photons?” “If I run my computer backwards, can I get back the energy I put in?”

Of course someone would object and say “That wouldn't work.” or “You can't do that.” and the professor would immediately counter with “Why not?” and start showing that his ideas were actually plausible if you went back to first principles and used some imagination.

I found that the best professors seemed to have what seemed to be the most naive questions. I also found that they usually had a long, long record of posing interesting questions and developing astounding solutions. And they were fun to talk to and hang around with.

I really enjoyed the way that certain professors thought about things and I tried to emulate that. I keep telling myself to start with first principles and make a model. (I have to keep reminding myself of this, too. It's too easy to get wrapped up in the detail.)

There's one more thing these professors did: teach. Some of them taught undergrad courses that weren't their specialty because they wanted to learn the material themselves. If you can teach a non-expert enough to understand what it is you are doing, then you probably have a good grasp of it. Otherwise, you might not even understand what problem you are trying to solve. (That's one reason I want to write more blog entries. It helps me organize my thoughts by trying to describe what I'm doing to other people.)

How do you approach a problem? How do you formulate a plan?

This question gave me a lot to think about. I kept trying to think how I formulate a plan and I realized just this moment that I don't. I think maybe I disagree with Pólya on this point. He gives these steps:

1. First, you have to understand the problem.
2. After understanding, then make a plan.
3. Carry out the plan.
4. Look back on your work. How could it be better?

The interesting problems are the ones where I have no idea at all how to go about solving. Then there is a good opportunity to learn something (and I love learning things).

I usually don't understand the problem, and that's the biggest hurdle. Of course I often think that I do understand it and get off on the wrong path. I have found myself with a ‘solution’ to something I didn't really want to solve, or the answer to a question that wasn't worth asking. I have to keep reminding myself of what question I want the answer to.

I either don't have good plans, or I can't recognize the good plans amongst the bad ones. I look at a lot of different approaches and try one that looks promising. If that doesn't work, I'll try another. I'll keep refining the plan on the way.

When I get really into a problem, I'm constantly explaining it to other people to try to get some insight. Often I find I don't have a clear enough concept to be able to explain it to someone. Usually the person I'm explaining it to gives me some irrelevant suggestions, but it helps me understand how they are perceiving or understanding what I am asking. Sometimes they say words that trigger an idea.

I also like the oddball approaches. For a lot of problems there seem to be one or two people on the ‘fringe’. They eschew the standard approach to something and advocate something that seems to come out of left field. Sometimes, however, a non-standard approach gives you some insight into the problem that you wouldn't have gotten otherwise. A good example is using Clifford Algebras for computer graphics.

That's about all I can think of right now. I hope I answered your questions.

Why I don't like math

You might think it is a contradiction to be a computer scientist and to dislike math. It isn't that I dislike ‘mathematics’. I like the logic, symmetry, and beauty of the ideas. What drives me up the wall is the notation.

Mathematicians like to think they are rigorous. Ha! If you haven't tried to cast your equations into a working computer program I can guarantee you that you left something out. Mathematicians like to omit ‘unnecessary’ detail. I'm a fan of abstraction, but you have to use it in a disciplined manner. If you simply discard the boring parts of the notation, you'll end up with an ambiguous mess. Of course humans can handle ambiguity more gracefully than computers, but it seems to me that if a computer cannot make sense out of what is being expressed, then a poor human like me has very little chance of success.

So here's my current frustration: the distribution I've been studying has an interesting quantile function.And I'm already in trouble. This notation has some extra baggage. Let me recast this as a program.

(define (make-quantile-function alpha beta)
  (lambda (p)
    (* alpha (expt (/ p (- 1 p)) (/ 1 beta)))))

alpha and beta are tuning parameters for this kind of distribution. alpha is essentially the median of the distribution, beta determines whether the curve descends steeply or has a long tail. The quantile function takes an argument p which is a number between 0 and 1. If you give it an argument of .9, it will return the value of the 90th percentile (that value of X where 90 percent of the distribution is below X). If you give it an argument of .5, you'll get the median. If you give it argument of .25, you'll get the first quartile, etc. It's a useful way of describing a distribution.

The reason the fancy equation had a superscript of -1 is because the quantile function is the inverse of the cumulative distribution function. The reason the function was named F^-1 is because they named the cumulative distribution function F. The cumulative distribution function could be defined like this:

(define (make-cumulative-distribution-function alpha beta)
  (lambda (x)
    (/ 1 (+ 1 (expt (/ x alpha) (- beta))))))

We can show that these functions are inverses of each other:

(define q (make-quantile-function .9 1.3))
;Value: q

(define cdf (make-cumulative-distribution-function .9 1.3))
;Value: cdf

(q (cdf 3))
;Value: 3.000000000000001

(q (cdf 1.8736214))
;Value: 1.8736213999999998

(cdf (q .2))
;Value: .19999999999999996

(cdf (q .134))
;Value: .13399999999999995

I mentioned earlier that I thought the quantile function was particularly interesting. If you've read my past posts, you know that I think you should work in log-odds space whenever you are working with probability. The quantile function maps a probability to the point in the distribution that gives that probability. The 90th percentile is where 9 times out of 10, your latency is at least as good, if not better. So what if we convert the quantile function to a `logile' function? In other words, take the log-odds as an argument.

(define (log-odds->probability lo)
  (odds->probability (exp lo)))

(define (odds->probability o)
  (/ o (+ o 1)))

(define (quantile->logile q)
  (lambda (lo)
    (q (log-odds->probability lo))))

(define (make-logile-function alpha beta)
  (quantile->logile 
    (lambda (p)
      (* alpha (expt (/ p (- 1 p)) (/ 1 beta))))))

(define logile (make-logile-function .9 1.3))

(logile 3)
;Value: 9.046082508750782

(logile 1)
;Value: 1.9422949805536014

(logile 0)
;Value: .9

(logile -3)
;Value: .0895415224453726

But let's simplify that computation:

(quantile->logile 
  (lambda (p)
    (* alpha (expt (/ p (- 1 p)) (/ 1 beta)))))

((lambda (p)
   (* alpha (expt (/ p (- 1 p)) (/ 1 beta))))
 (log-odds->probability lo))

(* alpha (expt (/ (log-odds->probability lo) 
           (- 1 (log-odds->probability lo)))
        (/ 1 beta)))

(* alpha (expt (/ (odds->probability (exp lo))
           (- 1 (odds->probability (exp lo))))
        (/ 1 beta)))

(* alpha (expt (/ (/ (exp lo) (+ (exp lo) 1)) 
           (- 1 (/ (exp lo) (+ (exp lo) 1))))
        (/ 1 beta)))

;; after a lot of simplification
(* alpha (exp (/ lo beta)))

(define (make-logile-function alpha beta)
  (* alpha (exp (/ lo beta))))

My ‘logile’ function is even simpler than the ‘quantile’ function. Now if I want to express the answers in log space as well, I simply take the log of the logile function:

(log (* alpha (exp (/ lo beta))))

(+ (log alpha) (/ lo beta))

Which you will recognize is the equation of a line.

Well so what? With sufficient algebra, any function that has two independent parameters can be turned into a line. However, the cumulative distribution function is an integral, so I have an intuition that there is something interesting going on here. I found some work by Steinbrecher and Shaw where they point out that “Quantile functions may also be characterized as solutions of non-linear ordinary differential equations.” Obviously, the logile function can also be characterized this way, too. I'm hoping that looking at the distribution in this way can yield some insight about the distribution.

And this is where I run into the annoying math. Check out these two equations:


By the first equation, Q is obviously some sort of function (the quantile function). H therefore operates on a function. By the second equation, the argument to H, which is called x, is used as the argument to f, which is the probability distribution function. f maps numbers to numbers, so x is a number. The types don't match.

So what am I supposed to make of this? Well, I'll try to follow the process and see if I can make sense of the result.

Did you mean....?

http://www.google.com/search?q=recursion

What's wrong with this code? II

(let loop ((ranges (%char-set-ranges cs))
           (value 0))
      (if (null? ranges)
          value
          (loop (cdr ranges)
                (modulo (+ value (caar ranges) (cdar ranges)) 
                        bound))))

Again, the machinery of iterating down the list is woven into the code. And it is incorrect. Rather than testing for null? and assuming that ranges must otherwise be a list, the code should test if ranges is in fact a pair before taking the car or cdr.

;; Common, but incorrect:

  (if (null? foo)
      ... handle base case ...
      (let ((a (car foo)))
         ... handle recursive case ...
         ))

;; Correct:

    (cond ((pair? foo) (let ((a (car foo)))
                          ... handle recursive case ...
                          ))
          ((null? foo)  ... handle base case ...)
          (else (error "Improper list: " foo)))

The second way might be faster if the compiler is reasonably smart about type propagation. The compiler could note that once (pair? foo) is satisfied, then (car foo) does not need an additional type check. This is not the case with the first sample. Just because foo is not null doesn't mean it is therefore a pair.

But in any case, if we abstract away the iterative list traversal, we don't need to bother ourselves about the minutae of taking car and cdr and checking types:

(fold-left (lambda (value range)
             (modulo (+ value (car range) (cdr range))
                     bound))
           0
           (%char-set-ranges cs))

Here's another example:

(let loop ((syms (make-global-value-list))
           (result '()))
    (if (null? syms)
        result
        (let ((sym-str (symbol->string (caar syms))))
          (if (and (>= (string-length sym-str) (string-length string))
                   (string=? (substring sym-str 0 (string-length string))
                             string))
              (loop (cdr syms)
                    (cons (list (symbol->string (caar syms))) result))
              (loop (cdr syms) result)))))

(fold-left (lambda (result sym)
             (let ((sym-str (symbol->string (car sym))))
               (if (and (>= (string-length sym-str) (string-length string))
                        (string=? (substring sym-str 0 (string-length string))
                                   string))
                   (cons (list sym-str) result)
                   result)))
            '()
            (make-global-value-list))

We don't want to write code that iterates down a list. We want to write code that operates on a single element of a list and then use a higher-order function to make it work across the entire list. map is great example, but fold-left is even more general than map. map always produces a list of the same length as the input list. fold-left can add or remove elements:

;; Double the items in the list.
(fold-left (lambda (result item) 
             (cons item (cons item result)))
           '() foo)

;; Return a list of the lengths
;; of the non-empty strings.
(fold-left (lambda (result item)
             (let ((x (string-length item)))
               (if (zero? x)
                   result
                   (cons x result))))
           '()
            foo)

(Note that the returned list in each of these is in reverse order. That's ok, we can simply call reverse on the result if we want it in forward order. In most cases, a second traversal to reverse the result is about as cheap as trying to construct the list in forward order, and it is far less complicated.)

fold-left doesn't have to return a list, either.

(fold-left + 0 foo) ;; sum the elements of foo

What's wrong with this code?

(define (& . l)
  (let loop ((l l) (s ""))
    (if (null? l)
        s
        (loop (cdr l) (string-append s (->string (car l))))))

The problem is that the code doesn't say what it does. Consider this version:

(apply string-append (map ->string l))

We're going to take a list of items, convert them all to strings, and paste the strings together. That's pretty much what that one-liner says is going to happen. The loop version has a lot of other cruft in it that is the machinery to iterate down a list. We want to abstract that away.

Perhaps we don't want to use apply here, though. Maybe we're worried about the stack space involved. This will do the trick:

(fold-left (lambda (s e)
             (string-append s (->string e)))
           ""
           l)

Variable lookup

After the changes I mentioned in an earlier post I find that about 63% of all variable references are to arguments in the immediately enclosing lambda. In fact, more than half the variable references are to the first argument in the argument list. I'm going to guess that most of the remaining variable references end up referring to global variables, but I could be wrong.

It also turns out that most of the argument references are subproblems of PrimitiveCombination1 and PrimitiveCombination2. Enabling specialization of these forms should be a big win.

Without specialization, these are the steps to evaluating a PrimitiveCombination1:

public override bool EvalStep (out object answer, ref Control expression, ref Environment environment)
{
    Control unev0 = this.arg0;
    Environment env = environment;
    object ev0;
    while (unev0.EvalStep (out ev0, ref unev0, ref env)) { };

    if (ev0 == Interpreter.UnwindStack) {
        ((UnwinderState) env).AddFrame (new PrimitiveCombination1Frame0 (this, environment));
        answer = Interpreter.UnwindStack;
        environment = env;
        return false;
    }

    // It is expensive to bounce down to invoke the procedure
    // we invoke it directly and pass along the ref args.
    if (this.method (out answer, ev0)) {
        TailCallInterpreter tci = answer as TailCallInterpreter;
        if (tci != null) {
            answer = null; // dispose of the evidence
            // set up the interpreter for a tail call
            expression = tci.Expression;
            environment = tci.Environment;
            return true;
        }
        else
            throw new NotImplementedException ();
    }
    else return false;
}

Now if we know that the argument to the primitive is simply going to be an argument bound in the enclosing lambda expression, we can bypass the code that evaluates it and just fetch the value:

public override bool EvalStep (out object answer, ref Control expression, ref Environment environment)
{
    if (this.method (out answer, environment.Argument0Value)) {
        TailCallInterpreter tci = answer as TailCallInterpreter;
        if (tci != null) {
            answer = null; // dispose of the evidence
            // set up the interpreter for a tail call
            expression = tci.Expression;
            environment = tci.Environment;
            return true;
        }
        else
            throw new NotImplementedException ();
    }
    else return false;
}