Showing posts with label books. Show all posts
Showing posts with label books. Show all posts

Tuesday, November 10, 2015

Neural Networks in Haskell

Long ago, when I first looked into machine learning, neural networks didn’t stand out of the crowd. They seemed on par with decision trees, genetic algorithms, genetic programming, and a host of other techniques. I wound up dabbling in genetic programming because it seemed coolest.

Neural networks have since distinguished themselves. Lately, they seem responsible for each newsworthy machine learning achievement I hear about. To name a few:

Inspired, I began reading Michael Nielsen’s online book on neural networks. We can whip up a neural network without straying beyond a Haskell base install, though we do have to implement the Box-Muller transform ourselves to avoid pulling in a library to sample from a normal distribution.

The following generates a neural network with 3 inputs, a hidden layer of 4 neurons, and 2 output neurons, and feeds it the inputs [0.1, 0.2, 0.3].

import Control.Monad
import Data.Functor
import Data.List
import System.Random

main = newBrain [3, 4, 2] >>= print . feed [0.1, 0.2, 0.3]

newBrain szs@(_:ts) = zip (flip replicate 1 <$> ts) <$>
  zipWithM (\m n -> replicateM n $ replicateM m $ gauss 0.01) szs ts

feed = foldl' (((max 0 <$>) . ) . zLayer)

zLayer as (bs, wvs) = zipWith (+) bs $ sum . zipWith (*) as <$> wvs

gauss :: Float -> IO Float
gauss stdev = do
  x <- randomIO
  y <- randomIO
  return $ stdev * sqrt (-2 * log x) * cos (2 * pi * y)

The tough part is training the network. The sane choice is to use a library to help with the matrix and vector operations involved in backpropagation by gradient descent, but where’s the fun in that?

It turns out even if we stay within core Haskell, we only need a few more lines, albeit some hairy ones:

relu = max 0
relu' x | x < 0      = 0
        | otherwise  = 1

revaz xs = foldl' (\(avs@(av:_), zs) (bs, wms) -> let
  zs' = zLayer av (bs, wms) in ((relu <$> zs'):avs, zs':zs)) ([xs], [])

dCost a y | y == 1 && a >= y = 0
          | otherwise        = a - y

deltas xv yv layers = let
  (avs@(av:_), zv:zvs) = revaz xv layers
  delta0 = zipWith (*) (zipWith dCost av yv) (relu' <$> zv)
  in (reverse avs, f (transpose . snd <$> reverse layers) zvs [delta0])
  where
    f _ [] dvs = dvs
    f (wm:wms) (zv:zvs) dvs@(dv:_) = f wms zvs $ (:dvs) $
      zipWith (*) [sum $ zipWith (*) row dv | row <- wm] (relu' <$> zv)

descend av dv = zipWith (-) av ((0.002 *) <$> dv)

learn xv yv layers = let (avs, dvs) = deltas xv yv layers
  in zip (zipWith descend (fst <$> layers) dvs) $
    zipWith3 (\wvs av dv -> zipWith (\wv d -> descend wv ((d*) <$> av))
      wvs dv) (snd <$> layers) avs dvs

See my Haskell notes for details. In short: ReLU activation function; online learning with a rate of 0.002; an ad hoc cost function that felt right at the time.

Despite cutting many corners, after a few runs, I obtained a neural network that correctly classifies 9202 of 10000 handwritten digits in the MNIST test set in just one pass over the training set.

I found this result surprisingly good. Yet there is much more to explore: top on my must-see list are deep learning (also described in Nielsen’s book) and long short-term memory.

I turned the neural net into an online digit recognition demo: you can draw on the canvas and see how it affects the outputs.

Sunday, May 25, 2014

Straw Men in Black

There’s a phrase used to praise a book: “you can’t put it down”. Unfortunately, I felt the opposite while reading The Black Swan by Nassim N. Taleb.

I’ll admit some prejudice. We’re told not to judge a book by its cover, but review quotes in the blurb ought to be exempt. One such quote originated from Peter L. Bernstein, the author of Against the Gods. While I enjoyed reading it, his book contained a litany of elementary mathematical mistakes. Did this mean The Black Swan was similarly full of errors?

All the same, the book began well. Ideas were clear and well-expressed. The writing was confident: perhaps overly so, but who wants to read text that lacks conviction? It promised wonders: we would learn how statisticians have been fooling us, and then learn the right way to deal with uncertainty, with potentially enormous life-changing payoffs.

I failed to reach this part because several chapters in, I was exhausted by a multitude of issues. I had to put the book down. I intend to read further once I’ve recovered, and hopefully the book will redeem itself. Until then, here are a few observations.


One Weird Trick

What’s on the other end of those "one weird trick" online ads? You won’t find out easily. If clicked, one is forced to sit through a video that:

  • makes impressive claims about a product

  • takes pains to keep the product a secret

  • urges the viewer to wait until the end, when they will finally learn the secret

This recipe must be effective, because I couldn’t help feeling the book was similar. It took me on a long path, meandering from anecdote to anecdote, spiced with poorly constructed arguments and sprinkled with assurances that the best was yet to come.

Perhaps this sales tactic has become a necessary evil. With so much competition, how can a book distinguish itself? Additionally, I’m guessing fattening the book for any reason has a positive effect on sales.

Even so, the main idea of the book could be worth reading. I’ll post an update if I find out.


Lay Off Laplace

Chapter 4 features a story about a turkey. As days pass, a turkey’s belief in the proposition such as "I will be cared for tomorrow" grows ever stronger, right until the day of its execution, when its belief turns out to be false. This retelling of a parable about a chicken due to Bertrand Russell is supposed to warn us about inferring knowledge from observations, a repeated theme in the book.

But what about Laplace’s sunrise problem? By the Rule of Succession, if the sun rose every day for 5000 years, that is, for 5000 × 365.2426 days, the odds it will rise tomorrow are only 1826214 to 1. Ever since Laplace wrote about this, he has been mercilessly mocked because of this ludicrously small probability.

So which is it? Do repeated observations make our degrees of belief too strong (chicken) or too weak (sunrise)?

Live long and prosper

Much of this material is discussed in Chapter 18 of Probability Theory: The Logic of Science by Edwin T. Jaynes, which also contains the following story.

A boy turns 10 years old. The Rule of Succession implies the probability he lives one more year is (10 + 1) / (10 + 2), which is 11/12. A similar computation shows his 70-year old grandfather will live one more year with probability 71/72.

I like this example, because it contains both the chicken and the sunrise problem. Two for the price of one. Shouldn’t the old man’s number be lower than the young boy’s? One number seems too big and the other too small. How can the same rule be wrong in two different ways?

Ignorance is strength?

What should we do to avoid these ridiculous results?

Well, if the sun rose for every day for 5000 years and that is all you know, then 1826214 to 1 is correct. The only reason we think this is too low is because we know a lot more than the number of consecutive sunrises: we know about stars, planets, orbits, gravity, and so on. If we take all this into account, our degree of belief that the sun rises tomorrow grows much stronger.

The same goes for the other examples. In each one, we:

  1. Ignored what we know about real world.

  2. Calculated based on what little data was left.

  3. Un-ignored the real world so we could laugh at the results.

In other words, we have merely shown that ignoring data leads to bad results. It’s as obvious as noting that if you shut your eyes while driving a car, you’ll end up crashing.

Sadly, despite pointing this out, Laplace became a victim of this folly. Immediately after describing the sunrise problem, Laplace explains that the unacceptable answer arises because of wilfully neglected data. For some reason, his critics take his sunrise problem, ignore his explanation for the hilarious result, then savage his ideas.

The Black Swan joins the peanut gallery in condemning Laplace. However, its conclusion differs from those of most detractors. The true problem is that most of the data is ignored when computing probabilities. Taleb considers addressing this by ignoring even more data! But then why not toss out more? Why not throw away most of mathematics and assign arbitrary probabilities to arbitrary assertions?

Orthodox statistics is indeed broken, but not because more data should be ignored. It’s broken for the opposite reason: too much data is being ignored.

Poor Laplace. Give the guy a break.


Hempel’s Joke

Stop me if you’ve heard this one: 2 + 2 = 5 for sufficiently large values of 2. This is obviously a joke (though sometimes told so convincingly that the audience is unsure).

Hempel’s Paradox is a similar but less obvious joke that proceeds as follows. Consider the hypothesis: all ravens are black. This is logically equivalent to saying all non-black things are non-ravens. Therefore seeing a white shoe is evidence supporting the hypothesis.

The following Go program makes the attempted humour abundantly clear:

package main

import "fmt"

func main() {
state := true
for {
var colour, thing string
if _, e := fmt.Scan(&colour, &thing); e != nil {
break
}
if thing == "raven" && colour != "black" {
state = false
}
fmt.Println(" hypothesis:", state)
}
}

A sample run:

black raven
hypothesis: true
white shoe
hypothesis: true
red raven
hypothesis: false
black raven
hypothesis: false
white shoe
hypothesis: false

The state of the hypothesis is represented by a boolean variable. Initially the boolean is true, and it remains true until we encounter a non-black raven. This is the only way to change the state of the program: neither "black raven" nor "white shoe" has any effect.

Saying we have "evidence supporting the hypothesis" is saying there are truer values of true. It’s like saying there are larger values of 2.

The original joke exploits the mathematical concept “sufficiently large” which has applications, but is absurd when applied to constants.

Similarly, Hempel’s joke exploits the concept "supporting evidence", which has applications, but is absurd when applied to a lone hypothesis.

Off by one

If we want to talk about evidence supporting or undermining a hypothesis mathematically, we’ll need to advance beyond boolean logic. Conventionally we represent degrees of belief with numbers between 0 and 1. The higher the number, the stronger the belief. We call these probabilities.

Next, we propose some mutually exclusive hypotheses and assign probabilities between 0 and 1 to each one. The sum of the probabilities must be 1.

If we take a single proposition by itself, such as "all ravens are black", then we’re forced to give it a probability of 1. We’re reduced to the situation above, where the only interesting thing that can happen is that we see a non-black raven and we realize we must restart with a different hypothesis. (In general, probability theory taken to extremes devolves into plain logic.)

We need at least two propositions with nonzero probabilties for the phrase "supporting evidence" to make sense. For example, we might have two propositions A and B, with probabilities of 0.2 and 0.8 respectively. If we find evidence supporting A, then its probability increases and the probability of B decreases accordingly, for their sum must always be 1. Naturally, as before, we may encounter evidence that implies all our propositions are wrong, in which case we must restart with a fresh set of hypotheses.

To avoid nonsense, we require at least two mutually exclusive propositions, such as A: "all ravens are black", and B: "there exists a non-black raven", and each must have a nonzero probability. Now it makes sense to ask if a white shoe is supporting evidence. Does it support A at B’s expense? Or B at A’s expense? Or neither?

The propositions as stated are too vague to answer one way or another. We can make the propositions more specific, but there are infinitely many ways to do so, and the choices we make change the answer. See Chapter 5 of Jaynes.

One Card Trick

Instead of trying to flesh out hypotheses involving ravens, let us content ourselves with a simpler scenario. Suppose a manufacturer of playing cards has a faulty process that sometimes uses black ink instead of red ink to print the entire suit of hearts. We estimate one in ten packs of cards have black hearts instead of red hearts and is otherwise normal, while the other nine decks are perfectly fine.

We’re given a pack of cards from this manufacturer. Thus we believe the hypothesis A: "all hearts are red" with probability 0.9, and B: "there exists a non-red heart" with probability 0.1. We draw a card. It’s the four of clubs. What does this do to our beliefs?

Nothing. Neither hypothesis is affected by this irrelevant evidence. I believe this is at least intuitively clear to most people, and furthermore, had Hempel spoke of hearts and clubs instead of ravens and shoes, his joke would have been more obvious.

Great Idea, Poor Execution

The Black Swan attacks orthodox statistics using Hempel’s paradox, alleging that it shows we should beware of evidence supporting a hypothesis.

It turns out orthodox statistics can be attacked with Hempel’s paradox, but not by claiming "supporting evidence" is meaningless. That would be like claiming "sufficiently large" is meaningless.

Instead, Hempel’s joke reminds us we must consider more than one hypothesis if we want to talk about supporting evidence. This may seem obvious; assigning a degree of belief in a lone proposition is like awarding points in a competition with only one contestant.

However, apparently it is not obvious enough. The Black Swan misses the point, and so did my university professors. My probability and statistics textbook instructs us to consider only one hypothesis. (Actually, it’s worse: one of the steps is to devise an alternate hypothesis, but this second hypothesis is never used in the procedure!)


Mathematics Versus Society

In an off-hand comment, Taleb begins a sentence with “Mathematicians will try to convince you that their science is useful to society by…”

By this point, I already found faults. First and foremost: how often do mathematicians talk about their usefulness to society? There are many jokes about mathematicians and real life, such as:

Engineers believe their equations approximate reality. Physicists believe reality approximates their equations. Mathematicians don’t care.

The truth is being exaggerated for humour, but asserting their work is useful in the real world is evidently a low priority for mathematicians. It is almost a point of pride. In fact, Taleb himself later quotes Hardy:

The “real” mathematics of the “real” mathematicians…is almost wholly “useless”.

This outlook is not new. Gauss called number theory “the queen of mathematics”, because it was pure and beautiful and had no applications in real life. (He had no way of foreseeing that number theory would one day be widely used in real life for secure communication!)

But sure, whatever, let’s suppose mathematicians go around trying to convince others that their field is useful to society. [Presumably Hardy would call such a mathematician “imaginary” or “complex”.] They are trivially right. If you try to talk about how useful things are to society, then you’ll want to measure and compare usefulness of things, all the while justifying your statements with sound logical arguments. Measuring and comparing and logic all lie squarely in the domain of mathematics.


Jumping to Conclusions

So far, I feel the author’s heart is in the right place but his reasoning is flawed. Confirmation bias is indeed pernicious, and orthodox statistics is indeed erroneous. However, The Black Swan knocks down straw men instead of hitting these juicy targets.

The above are but a few examples of the difficulties I ran into while reading the book. I had meant to pick apart more specious arguments but I’ve already written more than I had intended.

Again, I stress I have not read the whole work, and it may improve in the second half.

Tuesday, November 12, 2013

Lies, damned lies, and frequentist statistics

Earlier this year I rekindled an interest in probability theory. In my classes, Bayes' theorem was little more than a footnote, and we drilled frequentist techniques. Browsing a few books led me to question this. In particular, though parts of Jaynes' "Probability Theory: The Logic of Science" sounded like a conspiracy theory at first, I was soon convinced that the author’s militant condemnation of frequentism was justified.

Today, I had the pleasure of reading a Nature article about a paper by Valen E. Johnson directly comparing Bayesian and frequentist methods in scientific publications, who suggests the latter is responsible for a plague of irreproducible findings. I felt vindicated; or rather, I felt I had several more decibels of evidence for the hypothesis that Bayesian methods produce far better results than frequentist methods when compared against the hypothesis that the two methods produce equivalent results!

This post explains it well. In short, frequentist methods have led to bad science.

An apologist might retort that it’s actually the fault of bad scientists, who are misusing the methods due to insufficient understanding of the theory. There may be some truth here, but I still argue that Bayesian probability should be taught instead. I need only look at my undergraduate probability and statistics textbook. On page 78, I see the 0.05 P-value convention castigated by Johnson, right after recipe-like instructions for computing a P-value. If other textbooks are similar, no wonder scientists are robotically misapplying frequentist procedures and generating garbage.

Johnson’s recommended fix of using 0.005 instead 0.05 is curious. I doubt it has firm theoretical grounding, but perhaps the nature of data that most scientists collect mean that this rule of thumb will usually work well enough. Though perhaps striving for the arbitrary 0.005 standard may require excessive data: a Bayesian method might yield similar results with less input. I guess it’s an expedient compromise. Those with poor understanding of statistical inference can still obtain decent results, at the cost of gathering more data than necessary.

The above post also mentions a paper describing how even a correctly applied frequentist technique leads to radically different inferences from a Bayesian one. The intriguing discussion within is beyond me, but I’m betting Bayesian is better; or rather, the prior I’d assign to the probability that Bayesian inference will one day shown to be better is extremly close to one!

Monday, February 18, 2013

Probability Made Less Uneasy

I’ve been leafing through a few books on probability, a subject which I’ve mostly avoided since undergrad. Originally thinking I’d just refresh what I already learned, to my surprise I was led to reconsider fundamental beliefs. What follows is my journey told via book reviews.


Hexaflexagons and Other Mathematical Diversions by Martin Gardner

As a kid, I devoured this book and the others in the series, which I later learned were collections of Mathematical Games columns from Scientific American magazine. I didn’t always understand the material, and the puzzles were often too difficult, but Gardner’s writing skill kept me reading on.

Among the many fascinating chapters was “Probability Paradoxes”. Gardner’s ability to communicate was so strong that after many years I still remember much of the content. In particular, he asked:

Mr. Smith says, "I have two children and at least one of them is a boy." What is the probability that the other child is a boy?

and his explanation of 1/3 being the correct answer not only stuck in my mind, but shaped my early views on probability. For the details, see this New Scientist article on a Martin Gardner convention.

Only a few years ago, after a debate with a friend, did I reconsider the reasoning. It turns out Gardner’s statement of the problem is ambiguous. This revelation sparked a desire to hit the books and brush up on probability one day.


A Primer of Statistics by M.C. Phipps and M.P. Quine

The second edition of this slim volume was the textbook for my first course on probability. I used it to cram for exams. For this purpose, it was good: I got decent grades.

Sadly, it wasn’t as good in other respects. I acquired a distaste for the subject. Why did Probability and Statistics seem like a bag of ad hoc tricks, with few explanations given? Do I have poor intuition for it? Or is it glorified guesswork that seems to work well enough with real-life data? Whatever the reason, I decided that for the rest of my degree I’d steer towards the Pure Mathematics offerings.


The Signal and the Noise: Why So Many Predicitons Fail — but Some Don’t by Nate Silver

My renewed interest in probability was also sparked by the United States presidential election of 2012, or rather, its aftermath. Many had predicted its outcome but few were accurate.

It was only then I read about Nate Silver, who turned out to have been famous for his prowess with predictions for quite some time. Eager to learn more, I thumbed through his bestseller.

Though necessarily light on theory, the equations that do appear are correct and lucidly explained. Also, the pages are packed with interesting data sets and anecdotes. General pronouncements are often backed up with concrete tables and graphs, though, as Silver readily admits, some qualities are difficult to quantify, resulting in potentially dubious but novel yardsticks (such as measuring scientific progress by average research and development expenditure per patent).

But most of all, I was intrigued by the tale of an ongoing conflict that I never knew existed, with frequentists on one side and Bayesians on the other. They never told me this in school!

I soon found out why: Silver states that Fisher may almost be single-handedly to blame for the dominance of frequentism, the ideology foisted upon me when I was just out of high school. Sure enough, I went back and confirmed Phipps and Quine listed Fisher in the bibliography.


Against the Gods: The Remarkable Story of Risk by Peter L. Bernstein

My dad told me about this book. Technical details are scant as it is also aimed at the general public. But in contrast to Silver’s work, what little that appears is laughably erroneous. In some sections, I felt the author was trying to trick himself into believing fallacies.

The misinformation might be mostly harmless. Those with weak mathematical ability are going to skip the equations out of fear, and those with strong mathematical ability are probably also going to skip them because they already know them.

But conceivably this book could be a gifted reader’s first introduction to probability, and it’d be a shame to start off on the wrong foot. As a sort of public service, I’ll explain some of the gaffes.

Exercises

Chapter 6 contains an example expected value calculation involving a coin flip.

We multiply 50% by one for heads and do the same for the tails, take the sum---100%---and divide by two. The expected value of betting on a coin toss is 50%. You can expect either heads or tails, with equal likelihood.

Why is this wrong? How can we fix it?

The next example involves rolling two dice.

If we add the 11 numbers that might come up…the total works out to 77. The expected value of rolling two dice is 77/11, or exactly 7.

Why is this wrong? How can we fix it?

What’s the difference?

Bernstein and Silver offer competing reasons why modern civilization differs from the past. Bernstein singles out our relatively newfound ability to quantify risk, and also suggests that key intermediate steps could only have occurred at certain points in history due to the overall mood of the era.

In contrast, Silver seems to place most importance on the printing press. In an early chapter, Silver suggests that after some teething trouble (lasting 330 years), the printing press paved the way for modern society. Apart from distribution of knowledge, perhaps more importantly the printing press helped with the preservation of knowledge; previously, writing would often be lost before it could be copied.

I’m inclined to side with Silver, partly because of Bernstein’s basic technical mistakes. After observing how fast and loose Bernstein was playing with mathematics, I’m tempted to believe some of his statements are gut feelings.

There is another glaring difference. Bernstein’s book lacks any mention of the frequentist-Bayesian war. Fisher’s name is conspicuously absent.

For or Against?

Against the Gods is riveting. My favourite feature is the backstories of famous scholars. For some of them, before reading the book, the only thing I knew about them were their names, and I would have known even less if their names weren’t attached to their most famous discoveries (or at least, discoveries vaguely connected with them). Learning about their life, motivations, temperament, beliefs, and so on was illuminating. An intellectually superior form of gossip, I suppose.

However, the elementary mathematical mistakes ultimately cast a cloud of suspicion over the book. How reliable are the author’s assertions in general? Although I heartily recommend Against the Gods, I also recommend thorough fact-checking before using it as a reference.

So a tip for bestseller authors: if a section is technical, then ask an expert, be an expert, or cut it out. Too many howlers make readers like me wary of the whole, no matter how well-written and accurate the non-technical parts are.

Answers to exercises

As Bernstein himself implies, an expected value is a weighted average. We need weights, and we need numbers to sum. It takes two to tango; the expected value dance can only proceed if probabilities are accompanied by values.

One example neglects the values, and the other neglects the probabilities. The author only computes the sum of the weights for the coin flip, and the sum of the values for the dice roll. In both cases the author divides by the number of outcomes, which might be considered another error: we already divided by the number of outcomes to compute the weights (probabilities) in the first place.

Why are these blunders amusing? For the coin example, let’s ignore that the expected value is confused with a probability. Instead of a coin, consider winning the lottery. The probability of winning the lottery plus the probability of not winning the lottery sums to 100%. Dividing this by the number of outcomes, i.e. 2, yields 50%, so apparently we win or lose the lottery with equal likelihood! It’s almost like saying “either it happens or it doesn’t happen, so the chances it happens is 50%”.

For the dice example, imagine rolling 2 loaded dice, both of which almost always show 6. The expected value should be close to 12, but because the probabilities are completely ignored, the author’s procedure leads to the same expected value of 7. Surely your calculation should change if the dice are loaded?

How do we fix these problems? For the dice example, the author supplies the correct method in the very next paragraph. At last, both the probabilities and values are taken into account. Unfortunately, the author then concludes:

The expected value…is exactly 7, confirming our calculation of 77/11. Now we can see why a roll of 7 plays such a critical role in the game of craps.

This should have never been written. The first sentence suggests both methods for computing the expected value are valid, when of course it just so happens the wrong method leads to the right answer.

The second sentence is difficult to interpret. Perhaps uncharitably, I’m guessing the sentence is an upgraded version of: “Look! Here’s a 7! Didn’t we see a 7 earlier?” What would have been written if we rolled a single die? The expected value is 3.5, but a roll of 3.5 obviously has no role in any game we play with one die.

As for fixing the coin example: computing an expected value requires us to attach a numerical value to each outcome. One does not simply plow ahead with “heads” versus “tails”. We need numbers; any numbers. We could assign 42 to heads, and 1001 to tails; here, the expected value of a fair coin toss would be 50% of 42 plus 50% of 1001, which is 521.5. Typically we pick values relevant to the problem at hand: for instance, in a game where we earn a dollar for flipping heads, and lose a dollar for tails, we’d assign the values 1 and -1 (here, our expected winnings would be 0).

[It may be possible to reinterpret the coin example as assigning the value 1 to both heads and tails. But if this were done, the expected value should also be 1, not “50%”. Furthermore, we learn nothing if the outcomes are indistinguishable.]


Probability Theory: The Logic of Science by E. T. Jaynes

If only Jaynes' book had been my introduction to probability. Like a twist ending in a movie, reading it was a thought-provoking eye-opening earth-shattering experience that compelled me to re-evaluate what I thought I knew.

Whereas Silver presents whimsical examples that demonstrate the Bayesian approach, Jaynes forcefully argues for its theoretical soundness. From a few simple intuitive “desiderata” (too ill-defined to be axioms), Jaynes shows step-by-step how they imply more familiar probability axioms, and why the Bayesian approach is the natural choice. And all this happens within the first 3 chapters, which are free online.

I had been uneasy about probability because I thought it was a collection of mysterious hacks, perhaps because it had to deal with the real world. I was flabbergasted to learn probability could be put on the same footing as formal logic. All those hacks can be justified after all. Probability is not just intuition and duct tape: it can be as solid as any branch of mathematics.

Since there still exist competing philosophies of probability, presumably others find fault with Jaynes' arguments. I’m still working through it, but I’m convinced for now. If there’s another twist in this story, I’ll need another great book to show it to me.

Washington University in St. Louis maintains a page dedicated to Jaynes. It’s a shame he died before he finished writing. The remaining holes have been papered over with exercises, which explains their depth and difficulty.

It’s also a shame Jaynes left Stanford University many years ago. Had he stayed, with luck I would have discovered his work earlier, or even have met him. A backward look to the future describes his reasons for departure.

In short, Jaynes felt the “publish or perish” culture of academia was harmful and was taking over Stanford. I can’t tell if Jaynes was right because by the time I got into the game, this culture seemed universally well-established. I had no idea an alternative ever existed.

Saturday, April 10, 2010

Self-publishing with CreateSpace

From time to time, somebody sends me a kind email saying that they only truly appreciated Git after encountering my Git guide. One such reader had already bought a few Git books, and he suggested I should therefore turn my website into a book.

I had idly thought about doing this, but why bother? Was: FREE, Now: $9.95!? However, the email made me realize that some seek information by buying books first, then look around online if they want more. Making a book out of my guide might be a good idea after all: I’m not trying to sell it to people who already know they can read it for free; rather, I’m aiming for those who might not otherwise find it until much later because they visit bookshops before search engines.

CreateSpace

Because the most renowned technical publishers already offered books on Git, I chose to self-publish on CreateSpace. Their tools are free, and they list your work on Amazon (who owns CreateSpace). I’d love to have bricks-and-mortar bookshops carry copies of the book too, but an Amazon listing should be enough for now.

In a brief search, I found controversy over CreateSpace ISBNs, but Richard Sutton’s post reassured me: firstly, for my book, the issues stemming from CreateSpace being the registered owner of the ISBN are irrelevant, and secondly, if you really want you can have an ISBN registered in your name (but you’ll have to buy it yourself).

The whole process is not quite free. After submitting your PDF file, you must order a proof copy. If you find errors, you submit a corrected PDF, and repeat. I made a stupid mistake the first time, so I went through this cycle twice and finished down about 16 bucks.

It’s not all bad though. I was surprisingly pleased to hold my book in my hand, as it felt like I had accomplished something. Also, in print form, the same old sentences become more authoritative and strangely convincing. Online, they look like stuff that some guy posted on some random website.

Preparing the book took much longer than expected. I had mentioned to a reader that I was considering making a book. I tried follow advice he gave me so it would look less amateurish. I cut a chapter and an appendix. I added an index. I renamed headings so they were more descriptive. I replaced all variables (e.g. "SHA1_HASH") in the command-line examples with values (e.g. "1b6d"). I selected a 6 inch by 9 inch form factor, which meant I had to shorten some lines to get them to fit. While doing all this, I found poorly spelled words, poorly worded paragraphs and poorly organized sections. I doubt I caught them all.

To avoid further delays, I used their Easy Cover Creator. Perhaps I’ll revisit this eventually, as I want a more spartan look: something like Kernighan and Ritchie’s "The C programming language". Or perhaps a sort of cheat sheet so the book would be useful even while shut.

I set the price to $9.95 USD, which means I get 2 bucks or so per sale. I considered a lower price, but I’ll be lucky to make my $16 back as it is! Still, it ought to be low enough that a buyer won’t be too annoyed when they find out the material is freely available on my homepage. (I would have linked to the free version from the book description, but this is forbidden.)

AsciiDoc, xsltproc, fop

I had some trouble with my tool chain that produces PDFs from text files. AsciiDoc produces a DocBook XML file out of the source text, which xsltproc turns into an XSL-FO file, which fop renders into a PDF. The design of the various formats probably have technical merit, but I found it difficult to figure out how to get what I wanted.

For example, I replaced variables with values because I could not italicize them easily with AsciiDoc. The only methods I discovered destroyed the natural beauty of the source text.

It seems the smaller the detail, the larger the effort required to tune it. Changing page sizes, font sizes and chapter heading styles was easy enough to figure out, but I still don’t know the right way to insert a blank page after the front matter so the first chapter starts on an odd page. I gave up editing some XSL file or other. Instead, I scripted a fragile search-and-replace on the XSL-FO output.

Nonetheless, I stand by my choices. There’s something appealing about source files which resemble old-school text files. Also, once the configuration nightmare is over, editing is simple: I can use any text editor, and the tool chain will automatically produce several HTML versions as well as a reasonable PDF for a book.

Shameless plug

I couldn’t possibly end this post without a link to my book: "Git Magic". It’s the most important book you’ll ever have, or my name is not Winston! Buy it now!

Monday, November 2, 2009

I'm right, you're wrong

I enjoy ranting about programming languages, whatever the medium: blog posts, emails to friends, colleagues and strangers, verbally to anyone within earshot. Mostly I rail against the evils of object-oriented languages, and why C is still the one true language.

Over the years, I’ve amassed enough material to fill several pages, which I’m now launching. Hopefully if I concentrate all these tirades in one place I’ll expend less energy overall on arguing!

Sunday, May 24, 2009

A really fundamental data structure

There are many things I wish my textbooks had taught me. It's often not the fault of the authors: in any field, even the best ideas suffer a lag between discovery and dissemination. However, even accounting for this, it seems I'm always behind the times. Some glaring omissions I belatedly redressed:
But most of all, I bemoan my ignorance of binary decision diagrams (BDDs). In his Computer Musings lecture, Don Knuth states "it's one of the only really fundamental data structures that came out in the last 25 years". He felt it was so important that he devoted the following lecture to ZDDs, a close relative of BDDs.

Take a map of the USA, and consider the following problems:
  1. Suppose you want to visit every state capitol exactly once, traveling on highways. Which route is shortest? Which route is longest? What is the mean and standard deviation of all the routes?
  2. Weight the states by any means, for example, by reading their two-letter code as a number in base 36. Then find a set of states such that no two members of the set are adjacent, and the total weight is maximized.
  3. There are several ways to colour the map with four colours such that no two adjacent states have the same colour. How do we pick one of these colourings at random (uniformly)?
Or consider these:
  1. How many ways can you tile a chessboard using 1x1, 2x1 and 3x1 rectangles? What if we also have pieces that look like 2x2 boxes with one tile missing?
  2. List all 5-letter words that remain words after replacing a 'b' with 'o'.
Do you know how to solve these efficiently? If not, you might want to read up on BDDs, particularly Knuth's treatment, which has just hit the presses, and watch his lectures. Using these sources, I took some notes on ZDDs.

Learning about BDDs reminded me of learning about Pólya theory, another simple yet powerful technique which transforms the seemingly impossible into child's play.

Wednesday, February 14, 2007

Chase the Pig

I was surprised to find that Wikipedia currently lacks an entry for the card game 拱豬 (Gong Zhu). This four-player trick-taking Hearts-like game is often played by my relatives on my mother's side, and I assume it's relatively well-known amongst the Chinese.

John McLeod maintains a page describing various rulesets for Gong Zhu (in particular the variants involving exposing cards sound highly intriguing to me), but none of them exactly match the one I was taught. For posterity I'll record my family's rules here.

For the first deal, the player with the seven of spades leads the first trick. The lead can be any card, not necessarily the seven of spades. In subsequent deals, the player that took the Queen of Spades in the previous deal leads the first trick. This player is sometimes nicknamed "The Pig". As in Hearts, there are no trumps, and the winner of the trick leads the next trick.

Why the seven of spades and not the two? Because another card game popular amongst my aunts and uncles involved building sequences starting with seven, and the first card played in that game had to be a seven. They adopted this rule for consistency.

My family always played a predetermined number of hands (e.g. 4) and the winner was the player(s) with the highest total score, but the more standard convention seems to be that one keeps playing until someone has a total score of -1000 or lower, and then the player(s) with the highest score is the winner. (I'm guessing they did this because when playing for stakes, payoffs occur more frequently with this scheme.)

The values of the cards are as follows:

  • Jack of Diamonds, or goat (羊): +100
  • Queen of Spades, or pig (豬): -200
  • Ten of Clubs: doubles your score, unless you have won no other cards in which case it is worth +50
  • Hearts: two to ten are worth minus their pip value, except for four which is worth -10. The Jack is -20, Queen -30, King -40 and Ace -50. The other cards are worth nothing.

I was taught a couple of mnemonics for the Four of Hearts being -10. Firstly, 4 is an unlucky number amongst the Chinese (I was told this is because the word for 4 sounds similar to the verb "to die" in Mandarin, and also in other variants of Chinese), so that's why its penalty value is worse than it should be.

Secondly, the word for 4 and the word for 10 in Mandarin sound similar. If you know a Mandarin speaker, get them to say "44 is 44" to hear for yourself!

If a player wins all the hearts, then the values of the hearts are reversed in sign, that is, they are positive instead of negative, and it can be checked that they are worth 200 points in total. Furthermore, if that same player also wins the pig, the pig is now worth +200 points.

If you win every card with a value, then you receive 100 points for the goat, 200 for the sheep, 200 for all the hearts, and finally your score gets doubled by the Ten of Clubs, giving a total of 1000 points. This is is the best possible score. The worst possible score is -796, when all but the Jack of Diamonds and Two of Hearts is taken.

Naturally, the name of the game refers to the practice of leading low spades in an attempt to flush out the pig: eventually the holder of the Queen of Spades may be forced to play it and take the trick.

Comparison with Hearts

I prefer this game to Hearts. There is something special about every suit in this game, whereas in Hearts, the clubs and diamonds tricks feel like filler. Winning the Jack of Diamonds is always good, and winning the Ten of Clubs sometimes helps, so even if you're not going for all the hearts there is something to do.

I never liked the Hearts rule preventing players from "breaking into" hearts, and I'm glad that Gong Zhu is free from this restriction.

Scoring is more complicated as each heart has a different penalty value. However I found after several hands I enjoyed the less trivial mental arithmetic, even missing it when playing Hearts.

Generally, I feel the game experience is richer because there are more important cards than Hearts, yet the additional complexity is not overly random nor overwhelming. In contrast, while playing Hearts if I'm not trying to shoot the moon, my play feels almost forced, as my only goal is to avoid the Queen of Spades and as many hearts a possible. Sometimes I can choose who to penalize more by playing in a certain way, but this aspect of the game is limited and unrewarding.

Even when shooting the moon, the strategy is often clear, a drawback that I feel is exacerbated by the prohibition on breaking into penalty cards.

I'm ambivalent about the Hearts convention of passing three cards before the game starts. Sometimes it's extremely helpful since some people I've played with are rather predictable, allowing me to mold hands which I can easily shoot the moon with. On the other hand, this does reduce the challenge, and in general getting extra information about opponent's hands detracts from the game experience.

The internal conflicts are more intense and exciting. I can feel my greed fight my fear. Do I save high cards to win the goat? What if this causes me to wind up with the pig and/or a bunch of high hearts as well? Do I go for the double? It's 50 points on its own, but how sure am I that I won't pick up any hearts later on?

Other Fun Card Games

I recall being enthralled when introduced to playing cards as a child. Nothing but fifty-two bits of pasteboard, yet the possibilities are legion. Games of pure skill. Games of pure chance. Games that fell in between, and it seemed that a game existed for any given skill/luck ratio. And they can be played almost anywhere, with any number of people, even alone. Such power, and I could hold it in one hand. Merely shuffling and performing sleights at once soothed and inspired me. To this day I often carry a pack of cards on my person.

One of my well-loved books from my childhood was "The Book of Games" by Richard Sharp and John Piggott (ISBN 0883653893). I read it cover to cover countless times, though not necessarily in order, marvelling at the illustrations and fascinated by the history. I tried out many of the games within, goading whoever was around me to learn their obscure rules so I could play.

(I took offence to one sentence however: in the entry on Mah Jong it describes the Chinese as "devious". I don't think they're inherently better at games than other races!)

If only the internet and Wikipedia existed back then! I was frustrated by rules they omitted, not to mention the games they left out. Sometimes the descriptions were too concise due to space limitations. Today the rules of just about any game with some following are at one's fingertips, and one can sometimes even find free programs for an instant opponent, instructor and umpire. Unfortunately, this came after my heaviest gaming days (at least, games that don't involve computers!), so the games below are mostly from the above book.

Though I'll mention card games of many species, some bias will be noticeable since I'm fond of lightweight teamless trick-taking games. Player ability varies wildly in some circles, making partner selection problematic in games such as bridge and canasta.

If there are four players, I almost always enjoy playing Hearts and Chase the Pig. Big Two is another favourite.

When there are three players, Knaves is a good choice if I'm in the mood for something like Hearts. It is also a no-trump trick-taking game with penalty cards, but also gives one an incentive to win as many tricks as possible. Sergeant Major is an entertaining diversion for three, especially for those newer to trick-taking games. My friends and family found David Parlett's Ninety-nine refreshingly unique and challenging. (We played the original rules, as described in The Book of Games.)

I never found two-player card games appealing, though I feel like I could if I dedicated more time to them. In particular, I feel like I should like Cribbage, Bezique and Piquet. I've tried some novel two-player games described in "The Pan Book of Card Games" by Hubert Philips, but never grew attached to them.

For five players or above, I'd play poker, or in a less serious crowd, Bartog.

Also, Napoleon is a five-player trick-taking game whose gimmick is the existence of a secret partnership: the identity of highest bidder, Napoleon, is known, but his secretary is determined by the holder of a particular card that is not revealed until played during a trick. Thus it is a two-versus-three game where initially no one knows the composition of the teams.

I had forgotten the details of this game. But thanks to Google, I rediscovered this old friend, and learned a lot more. Apparently, my parents left out at least half the rules when they taught it to me. Also, it seems Napoleon is a popular Japanese card game.

As for patience/solitaire for one, I'd recommend downloading a program like PySol and exploring.

Monday, July 17, 2006

Mnemonic Major Systems

I discovered two things when I tried using the net to brush up on mnemonic major systems (aka phonetic number systems). (If you have no idea what they are read the article before continuing!) Firstly, the only encoding from digits to sounds I've seen online so far is the one published by Harry Lorayne. Secondly, it turned out I didn't need any brushing up at all. The mapping I learnt many years ago was so easy to remember that, not only can I still recall it, but the memory is so strong I cannot use Lorayne's system without confusion.

I came across the major system I use in a book by Jean Hugard. I argue that it is more natural and easier to learn. There were only a few rules to remember:

1,2,3 correspond to the consonants l,n,m respectively. This is easy to remember since the letters require 1,2, and 3 strokes to write. If you happen to know the British sign language alphabet, observe that you place 1, 2 or 3 fingers on the other hand's palm when signing l, n and m respectively.

Some mappings are based on the way you pronounce digits in English. 4 is r (think “fourrr”), 5 is f or v (think “five”). 0 is s or z (think “zero”).

Then there are the digits that look like letters. 6 is b or p, 7 is t, th or d. 9 is k or g. With sufficiently bad handwriting (or fonts), 6 and b are indistinguishable, as are 9 and g (or q, which in English is always pronounced starting with a k or g sound, and always as a k sound in several European languages). 7 and T are also similar.

The only rule I never liked much was the one for 8 (which is not a problem since being the odd one out makes it easy to remember!): “Eight” sounds like “aitch”, which hopefully helps you remember that the sh, ch (and j) sounds correspond to 8.

Digit Consonant(s) Reason
1 l strokes
2 n strokes
3 m strokes
4 r sound
5 f, v sound
6 b, p shape
7 d, t, th shape
8 ch, j, sh special
9 k, g, q shape
0 s, z sound

I also mostly prefer the mapping from playing cards to words as presented by Hugard. Although I dislike the aces been treated specially and agree with Lorayne assigning the names of the suits to the jacks, I believe thinking KH as a groom and QH as a bride for example is easier to learn.

However, there is at least one practical benefit to Lorayne's system. By Benford's law, it is more likely that a number one wishes to memorize begins with a 1, and it is easier to think of a word starting with d, t or th than to think of one starting with l.

Friday, February 17, 2006

Calculus Using Infinitesimals

I only recently became aware that it is possible to formalize the methods that Newton and Leibniz first used when developing calculus. In fact, not only is it possible, but it is quite easy to understand, and the notation is more elegant than those of limits.

I had always looked down on the pseudo-proofs I was shown in physics lectures, handwavy sloppy arguments that defied the rigour and precision that centuries of mathematics fought for. I tolerated them because I needed the results. But it seems with a few definitions, you can have your cake and eat it.

One introduction to this subject is a free online book: “Elementary Calculus: An Approach Using Infinitesimals” by H. Jerome Keisler.

Tuesday, November 1, 2005

Elements of Style

I had heard of William Strunk's Elements of Style long ago. I finally saw what all the fuss is about when I found this online HTML version of the book [alternate link].

Much of this 1918 work is still relevant today. I was surprised to find that many misused and/or hackneyed words and phrases have been around for many years.

When I write English, I borrow techniques I use to write code. I start with a syntactically correct body of text that gets the job done. I then revise and optimize: I reword, rephrase, replace and remove lines, aiming for clean, concise, efficient and effective writing.

The analogy isn't perfect. With prose, I'll throw in extra words if I like the way it sounds, but for code, I'll sacrifice style for performance.

Some of the rules in Elements of Style seem to achieve the same goals, though they are explained from a nonprogrammer's viewpoint!