The probabilistic programming language Church brings together two of my favorite subjects: Scheme and Probability. I highly recommend this tutorial to graduate students interested in machine learning and statistical inference.
The tutorial explains probabilistic inference through programming starting from simple generative models with biased coins and dice leading up to hierarchical, non-parametric, recursive and nested models. Even at the undergraduate level, I have long thought probability and statistics should be taught in an integrated manner instead of their current almost independent treatment. One roadblock is that even the simplest statistical inference (e.g. three tosses of a coin with an unknown (uniformly distributed) weight results in H, H, T; what is the fourth toss?) requires some calculus at the undergraduate level. Using a programming language like Church may allow an instructor to introduce basic concepts without students getting confused about the details of integration.
Full post...
April 09, 2012
April 01, 2012
The wonderful xargs command
I finally found a way I like to run a whole bunch of commands N at a time on an N core machine (well maybe use N-1 to be polite):
1. Say you have a command rprun.pl that takes 4 arguments that you want to run with 1000 different argument combinations.
2. You write a script rprun-args.pl that generates all combinations you need. Say its output looks like:
10 185364 25 0.166
12 92682 25 0.166
18 65536 32 0.166
12 65536 25 0.7071
14 16384 25 0.166
...
3. Now you can use xargs to run these 24 at a time as follows:
rprun-args.pl | xargs -n4 -P24 rprun.pl > rprun.out
-n4 is to feed the arguments 4 at a time. So a typical command line will look like:
rprun.pl 14 16384 25 0.166
-P24 tells xargs to run through the list 24 at a time. If you run ps you will see 24 copies of rprun running together. As soon as the number drops to 23 another child is spawned.
Note that the command above combines the outputs of all runs (in the order they finish) in the same file, so make sure rprun.pl prints out its arguments as well as its result on its output.
Full post...
1. Say you have a command rprun.pl that takes 4 arguments that you want to run with 1000 different argument combinations.
2. You write a script rprun-args.pl that generates all combinations you need. Say its output looks like:
10 185364 25 0.166
12 92682 25 0.166
18 65536 32 0.166
12 65536 25 0.7071
14 16384 25 0.166
...
3. Now you can use xargs to run these 24 at a time as follows:
rprun-args.pl | xargs -n4 -P24 rprun.pl > rprun.out
-n4 is to feed the arguments 4 at a time. So a typical command line will look like:
rprun.pl 14 16384 25 0.166
-P24 tells xargs to run through the list 24 at a time. If you run ps you will see 24 copies of rprun running together. As soon as the number drops to 23 another child is spawned.
Note that the command above combines the outputs of all runs (in the order they finish) in the same file, so make sure rprun.pl prints out its arguments as well as its result on its output.
Full post...
March 10, 2012
On skill acquisition
A couple of months ago, I ran into this video by the Japanese coin magician Ponta the Smith. Its elegance awoke my long dormant interest in close-up sleight-of-hand magic which had started when I was a kid and had peaked in LA taking classes at the Magic Castle. I am especially fond of coin magic because its effects are so simple and direct. I started watching the masters and practicing again. My hands started being able to do things that they were not able to do a few days ago. It surprised me to remember how much fun it was to acquire a new physical skill, and that I had not done so in more than a decade!
Then my friend Alkan showed me a video of Terry Laughlin, a swim coach with a unique training style. He compares dolphins at 80% efficiency with the best olympic athletes at 8% and claims there is a lot to gain from reducing drag compared to adding power to the strokes. Ernest Maglischo's standard reference also has consistent advice on correct body alignment. While scanning Maglischo's book I was shocked to discover that it was not clear whether Newtonian or Bernoulli forces dominate the analysis of the swim stroke! (Hey physicists, when you take a break from looking for the Higgs boson maybe you can help out with this?) I have been swimming all my life and no matter how hard I tried I could not break my efficiency barrier at 17 strokes for a 25m pool. After watching a couple of Laughlin's videos I was able to do it in 13!
Continuing on a chain of skill-acquisition serendipities, I came across Moonwalking with Einstein by Joshua Foer. I should cover it more fully in a separate blog post. In addition to giving an excellent synopsis of our current understanding of memory, it introduced me to the work of Anders Ericsson on skill acquisition. Ericsson has achieved some recent fame thanks to his research showing that experts tend to require about ten thousand hours of training to achieve their word-class status. However what got my attention was the finding that when ordinary skill acquisition hits a plateau and improvement stops, that is rarely the sign of an innate limit, but rather the result of the skill becoming compiled and autonomous. The trick to going past your plateaus and improving further is to bring the activity back to consciousness in sessions of "deliberate practice" where you pay attention to your technique and get constant and immediate feedback on your performance. This is consistent with my swimming experience: Laughlin's videos made me pay attention to every stroke, in effect made me re-learn how to swim, and the 25m stroke count feedback pointed me in the right direction.
I am currently debating whether I should continue my self experimentation in the domain of Go, using techniques championed for chess by my friend Michael de la Maza, or improve my Bridge game by deliberate practice on card memory. This is just too much fun.
On a more serious note, all this shows how little we know about skill acquisition and education in general and how much room there might be for improvement. It seems to me the only way out of this conundrum is to allow experimentation in the educational domain with proper feedback and reward for innovative educators.
(*) Some of my favorite coin masters: David Roth, Michael Rubinstein, Jay Sankey, Gregory Wilson, David Stone, Giacomo Bertini, Kainoa Harbottle, Curtis Kam, Homer Liwag, Apollo Robins, Shoot Ogawa.
Full post...
Then my friend Alkan showed me a video of Terry Laughlin, a swim coach with a unique training style. He compares dolphins at 80% efficiency with the best olympic athletes at 8% and claims there is a lot to gain from reducing drag compared to adding power to the strokes. Ernest Maglischo's standard reference also has consistent advice on correct body alignment. While scanning Maglischo's book I was shocked to discover that it was not clear whether Newtonian or Bernoulli forces dominate the analysis of the swim stroke! (Hey physicists, when you take a break from looking for the Higgs boson maybe you can help out with this?) I have been swimming all my life and no matter how hard I tried I could not break my efficiency barrier at 17 strokes for a 25m pool. After watching a couple of Laughlin's videos I was able to do it in 13!
Continuing on a chain of skill-acquisition serendipities, I came across Moonwalking with Einstein by Joshua Foer. I should cover it more fully in a separate blog post. In addition to giving an excellent synopsis of our current understanding of memory, it introduced me to the work of Anders Ericsson on skill acquisition. Ericsson has achieved some recent fame thanks to his research showing that experts tend to require about ten thousand hours of training to achieve their word-class status. However what got my attention was the finding that when ordinary skill acquisition hits a plateau and improvement stops, that is rarely the sign of an innate limit, but rather the result of the skill becoming compiled and autonomous. The trick to going past your plateaus and improving further is to bring the activity back to consciousness in sessions of "deliberate practice" where you pay attention to your technique and get constant and immediate feedback on your performance. This is consistent with my swimming experience: Laughlin's videos made me pay attention to every stroke, in effect made me re-learn how to swim, and the 25m stroke count feedback pointed me in the right direction.
I am currently debating whether I should continue my self experimentation in the domain of Go, using techniques championed for chess by my friend Michael de la Maza, or improve my Bridge game by deliberate practice on card memory. This is just too much fun.
On a more serious note, all this shows how little we know about skill acquisition and education in general and how much room there might be for improvement. It seems to me the only way out of this conundrum is to allow experimentation in the educational domain with proper feedback and reward for innovative educators.
(*) Some of my favorite coin masters: David Roth, Michael Rubinstein, Jay Sankey, Gregory Wilson, David Stone, Giacomo Bertini, Kainoa Harbottle, Curtis Kam, Homer Liwag, Apollo Robins, Shoot Ogawa.
Full post...
October 29, 2011
Gamma distribution
The Gamma distribution is often used as a prior for positive random variables just like the Gaussian distribution for real valued random variables. The purpose of this post is to build some intuition about how the two parameters, the shape parameter "a" and the scale parameter "b", effect the behavior of a Gamma random variable. In particular we will show that for vague Gamma parameters (a<<1) the distribution almost acts like an upper bound on the random variable.
Full post...
Here is the Gamma PDF:
$f(x) = \frac{1}{\Gamma(a) b} (\frac{x}{b})^{a-1} e^{-x/b} \;\; x\geq 0; a , b>0$
The mean is ab and the variance is ab². When a=1 it is equivalent to the exponential distribution. In fact when a is an integer, it is equivalent to the sum of (a) independent exponentially distributed random variables each of which has a mean of (b). It is shaped like the exponential distribution with a spike at 0 for a<1, but has a mode at (a-1)b for a>1 (see the Wikipedia article).
MacKay suggests representing the positive real variable x in terms of its logarithm z=ln x (ITILA, pp. 314). This will give us a better idea about the order of magnitude of typical x in terms of a and b. The distribution in terms of z is:
$f(z) = \frac{1}{\Gamma(a)} (\frac{x}{b})^a e^{-x/b} \;\; z \in \Re; x=e^z; a, b>0$
We can get an idea about the shape of f(z) by looking at its first two derivatives with respect to z:
$f'(z) = f(z) (a-\frac{x}{b})$
$f''(z) = f(z) (a^2 - (2a+1)\frac{x}{b} + (\frac{x}{b})^2)$
The graph above shows f(z) and its two derivatives for a=1/10 and b=10. The first derivative tells us that f(z) has a single mode at x=ab. Note that x=ab is the mean of f(x) but only the mode (not the mean) of f(z). The curve raises slowly on the left of the mode and falls sharply on the right. The second derivative has two roots that give us the values with the minimum and the maximum slope:
$x = ab + \frac{b}{2} \pm \frac{b}{2} \sqrt{1+4a}$.
Now we are going to look at the limit where a<<1, typically used as a vague prior. The height of the mode at x=ab is aae-a/Γ(a). Γ(a) is well approximated by 1/a for small a, aa and e-a both go to 1, so f(z) ≈ a at the mode.
Next, let's look at the right side (x>ab) where f(z) seems to fall sharply. According to the roots of the second derivative given above, the minimum slope occurs at around x=b (if we ignore the terms with a<<1). The value of f(z) when x=b is 1/(e Γ(a)). Γ(a) is well approximated by 1/a for small a, so this value is approximately a/e. The slope at x=b is approximately -a/e and if we fit a line at that point the line would cross 0 at x=eb. Thus for small a, the probability can be considered negligible for x>eb.
Next, let's look at the left side (x < ab) where f(z) appears more flat. The maximum slope occurs around x=a²b (if we approximate √ 1+4a with 1+2a-2a²). The slope at x=a²b is approximately a² which gives a flat shape for x<ab when a<<1.
In summary, when used with a<<1, f(z) rises slowly for x<ab (with approximate slope a²) and falls sharply for x>ab (with approximate slope -a/e). You are unlikely to see x values larger than eb from such a distribution, but you may see values much smaller than the mean ab. Thus a vague Gamma prior is practically putting an upper bound on your positive value. The figure below shows how the f(z) distribution starts looking like a step function as the shape parameter approaches 0 (b=1/a and the peak heights have been matched for comparison).
I should also note that in the limit where a→0 and ab=1, we get an improper prior where f(z) becomes flat and the Gamma distribution becomes indifferent to the order of magnitude of the random variable. However it flattens a lot faster on the left than on the right.
Full post...
August 16, 2011
Ergun Biçici, Ph.D. 2011
Current position: Senior AI Research Engineer at Huawei. (webpage).
PhD Thesis:The Regression Model of Machine Translation. Koç University, Department of Computer Engineering. August, 2011. (PDF, Presentation).
Publications: bibtex.php, scholar
Abstract:
Machine translation is the task of automatically finding the translation of a source sentence in the target language. Statistical machine translation (SMT) use parallel corpora or bilingual paired corpora that are known to be translations of each other to find a likely translation for a given source sentence based on the observed translations. The task of machine translation can be seen as an instance of estimating the functions that map strings to strings.
Regression based machine translation (RegMT) approach provides a learning framework for machine translation, separating learning models for training, training instance selection, feature representation, and decoding. We use the transductive learning framework for making the RegMT approach computationally more scalable and consider the model building step independently for each test sentence. We develop training instance selection algorithms that not only make RegMT computationally more scalable but also improve the performance of standard SMT systems. We develop better training instance selection techniques than previous work from given parallel training sentences for achieving more accurate RegMT models using less training instances.
We introduce L_1 regularized regression as a better model than L_2 regularized regression for statistical machine translation. Our results demonstrate that sparse regression models are better than L_2 regularized regression for statistical machine translation in predicting target features, estimating word alignments, creating phrase tables, and generating translation outputs. We develop good evaluation techniques for measuring the performance of the RegMT model and the quality of the translations. We use F_1 measure, which performs good when evaluating translations into English according to human judgments. F_1 allows us to evaluate the performance of the RegMT models using the target feature prediction vectors or the coefficients matrices learned or a given SMT model using its phrase table without performing the decoding step, which can be computationally expensive.
Decoding is dependent on the representation of the training set and the features used. We use graph decoding on the prediction vectors represented in n-gram or word sequence counts space found in the training set. We also decode using Moses after transforming the learned weight matrix representing the mappings between the source and target features to a phrase table that can be used by Moses during decoding. We demonstrate that sparse L_1 regularized regression performs better than L_2 regularized regression in the German-English translation task and in the Spanish-English translation task when using small sized training sets. Graph based decoding can provide an alternative to phrase-based decoding in translation domains having low vocabulary.
Full post...
PhD Thesis:The Regression Model of Machine Translation. Koç University, Department of Computer Engineering. August, 2011. (PDF, Presentation).
Publications: bibtex.php, scholar
Abstract:
Machine translation is the task of automatically finding the translation of a source sentence in the target language. Statistical machine translation (SMT) use parallel corpora or bilingual paired corpora that are known to be translations of each other to find a likely translation for a given source sentence based on the observed translations. The task of machine translation can be seen as an instance of estimating the functions that map strings to strings.
Regression based machine translation (RegMT) approach provides a learning framework for machine translation, separating learning models for training, training instance selection, feature representation, and decoding. We use the transductive learning framework for making the RegMT approach computationally more scalable and consider the model building step independently for each test sentence. We develop training instance selection algorithms that not only make RegMT computationally more scalable but also improve the performance of standard SMT systems. We develop better training instance selection techniques than previous work from given parallel training sentences for achieving more accurate RegMT models using less training instances.
We introduce L_1 regularized regression as a better model than L_2 regularized regression for statistical machine translation. Our results demonstrate that sparse regression models are better than L_2 regularized regression for statistical machine translation in predicting target features, estimating word alignments, creating phrase tables, and generating translation outputs. We develop good evaluation techniques for measuring the performance of the RegMT model and the quality of the translations. We use F_1 measure, which performs good when evaluating translations into English according to human judgments. F_1 allows us to evaluate the performance of the RegMT models using the target feature prediction vectors or the coefficients matrices learned or a given SMT model using its phrase table without performing the decoding step, which can be computationally expensive.
Decoding is dependent on the representation of the training set and the features used. We use graph decoding on the prediction vectors represented in n-gram or word sequence counts space found in the training set. We also decode using Moses after transforming the learned weight matrix representing the mappings between the source and target features to a phrase table that can be used by Moses during decoding. We demonstrate that sparse L_1 regularized regression performs better than L_2 regularized regression in the German-English translation task and in the Spanish-English translation task when using small sized training sets. Graph based decoding can provide an alternative to phrase-based decoding in translation domains having low vocabulary.
Full post...
Subscribe to:
Posts (Atom)
