Readings in Machine Learning

Brains, Minds and Machines

2011-05-04T08:43:00.007-07:00

Former UofA student, Alborz, shared a link to a video recording of a recent MIT150 symposium on Brains, Minds and Machines on facebook. I watched the video yesterday (guess what, I need to mark 40 something finals, hehe:)).
I wrote a comment back to Alborz on facebook and then I thought, why not make this a blog post? So, here it goes, edited, expanded. Warning: Spoilers ahead and the summary will be biased. Anyhow..

The title of the panel was: "The Golden Age — A Look at the Original Roots of Artificial Intelligence, Cognitive Science, and Neuroscience " and the panelist were Emilio Bizzi, Sydney Brenner, Noam Chomsky, Marvin Minsky, Barbara H. Partee and Patrick H. Winston. The panel was moderated by Steven Pinker who started with a 20-30 minute introduction. Once done with this each of the panelist delivered a little speech and at the end there were like two questions asked by Pinker.

My heroes in the panel were Minsky and Winston. They rocked! Minsky almost fell asleep during his talk, but he was well aware of this and I loved him. He told a story about Asimov not wanting to come to his lab to see the real robots (he did not want to get disappointed) and about von Neumann who said that he does not know if Minsky's thesis could qualify as a thesis on mathematics (they were both at Princeton in the math department), but soon it will be. I really enjoyed this part. Winston acted a bit like a comedian. I did not mind this either. One thing that Minsky and Winston both said is that the mistakes happened when AI became successful and everyone from that on seemed to forget the science part of AI. But they did not say much about how we can get back on the track (except that we should try). Winston blamed the short-sightedness of funding agencies and who would disagree.

Chomsky made some interesting claims. He claimed that language is designed for thoughts and not for communication. This was a pretty interesting claim. He claimed other things supporting his idea about innate, universal grammars, but I did not know how much credit to give to those as I have many linguist friends who strongly disagree. Things became interesting when answering a question at the end, he dumped the whole of machine learning. He talked about "a novel scientific criterion" that was never heard of before referring to being able to predict "on unanalyzed data". He said that "of course" with enough data you will do better, but it seemed that he thinks that the evaluation criterion is already ridiculous. He also said that a little statistics does not hurt, but he still seems that the big deal is the engineering part. (He did not say with these words, but this is what I got from what he said).

Sydney Brenner (pioneer in genetics and molecular biology) was puzzled about why he was invited, though he had some good stories. I liked when he said that in 50 years people will not understand why everyone talked about consciousness 50 years ago.

Emilio Bizzi (a big shot in neuroscience, in particular in motor control) talked about modularity, "dimension reduction" and generalization, and he looked like a fine Italian gentleman, but I have to confess that I don't remember anything else, though this could have been because it was late.

Barbara H. Partee read a script. In the first 5 minutes or so she was mostly praising Chomsky. Then she started to talk about her own work, which was foundational in semantics. She talked about how semantics is the real thing. By semantics she means formal semantics (like in logics). While in general I am fond of this work, I am not sure if anything like this is going on in our brain and if sentences really do have a meaning in a formal sense. It seems to me that the fact that sentences can have a formal meaning is more likely an illusion, a post-hoc thought than the real thing. Ad it is unclear if bringing in formal logics is going to bring us anywhere. Unfortunately, there was no discussion of this at all. At one point she made the remark that "search engines do not use semantics", but then left us in vain about how we could do any better. Oh, well..

In summary, an impressive set of people, some nice stories, but little cutting edge science. Loads of romanticism about the 50s and 60s and no advice for the young generation. The title tells it all. It was still nice to see these people.

Useful latex/svn tools (merge, clean, svn, diff)

2011-04-13T20:09:00.006-07:00

This blog is about some tools that I have developed (and yet another one that I have downloaded) which help me to streamline my latex work cycle. I make the tools available, hoping that other people will find them useful. However, they are admittedly limited (more about this) and as usual for free stuff they come with zero guarantee. Use them at your own risk.

The first little tool is for creating a cleaned up file before submitting it to a publisher who asks for source files. I call it ltxclean.pl, it is developed in Perl. It can be downloaded from here.
The functionality is
(1) to remove latex comments
(2) to remove \todo{} commands
(3) to merge files included from a main file into the main file
(4) to merge the bbl file into the same main file

If you make the tool executable (chmod a+x ltxclean.pl), you can use it like this:

$ ltxclean.pl main.tex > cleaned.tex

How does this work?

The tool reads in the source tex file, processes it line by line and produces some output to the standard output stream, which you can redirect (as shown above) to a file.
Thus, whatever the tool does is limited to the individual lines. This is a limitation, but this made it possible for me to write this tool in probably less time than I spend on writing about it now.
There are other limitations, see below. Now, how do we know that this worked? The advice is to run latex+dvips and then diff original.ps new.ps to see if there is any significant change. On the files I have tried, the only difference was the filename and the date.

Why this functionality and the glory details

As it happens, removing the comments before you submit a source file is crucial. Not long ago, it happened to me that I have submitted a source to a publisher and I did not care about removing the comments. At the publisher, they loaded the file into a program, which wrapped the long lines, including the ones with comments! This created a lot of garbage in the middle of the text. We were pressed against time, though I could not check the text in details. The result: The text was printed with a lot of garbage! Too bad!! A painful experience for me.. I will never again submit source files with the comments kept in the file! Now, the above utility is meant to handle comments correctly. It pays attention to not to create empty lines (and thus new lines) inadvertently, not to remove end-of-line comments etc.

The \todo{} commands belong to the same category: They are better removed before submitting the file. For my todos, I use the todonotes package, which puts todo notes on the margin (or within the text). This package supplies the \todo[XX]{ZZZ} command, where [XX] is optional. The above little script removes such todo commands, but only if they span a single line only. For now, you would need to remove multi-line todos by hand.

Another service of this little tool is to merge multiple files into a single one. Oftentimes, we use the latex command \input to break a large source file into multiple files. However, publishers typically want just one file. So this tool reads in the main file and the recursively, whenever it sees \input{FILE} in the source, it reads in the corresponding file and processes it before it continues with the current file (just like latex would work).

Finally, if the tool finds a \bibliography{...} command, it will take that out and open the .bbl file sharing the same base name as the input to the tool. Thus, if the tool was called on the file main.tex, when seeing a bibliography command, the tool will attempt to open main.bbl and include it in place of the \bibliography command. (If you use hyperref, turn off pagebackref, otherwise this functionality will not work.)

Managing revisions with svn

Two other small utilities that I make available are svnprevdiff and svnreviewchanges.
The purpose of these scripts is to help one review changes to files which are under svn control.
There is a third script, diffmerge, called by the above two scripts. This script takes two file arguments and loads these into the program DiffMerge which allows you to visually inspect the differences between the two files and make changes to the second one loaded. On a different platform/installation, or if you want to use a different tool for comparing/merging files.

The utility svnreviewchanges takes a file as an argument, compares it to its base version stored on your disk and opens up the two versions for comparison using diffmerge. The purpose is to allow one to quickly review how a file was changed before submitting a file to the svn server (so that you can write meaningful comments in the commit message).

The utility svnprevdiff takes a filename as an argument, compares it to its previous version stored on the svn server and then opens up the two versions using diffmerge. The purpose of this is to check the changes implemented by your pals after an update. A future version will take an optional argument which when present will be interpreted as a revision number. Maybe.

Advice on using latex when working in a team: Break long lines

A small, but useful thing is to put every sentence on its own line and generally avoiding long lines (even when writing equations). The reason is that this will make the job of diff much easier. And believe me, diffing is something people will end up doing for good or bad (mostly good) when they are on a team.

Some of my friends, like Antoska would recommend breaking up the individual sentences into multiple lines. You can do this, but if you overdo it, you will find yourself fiddling way too much with what goes into which line.

Finally, a tool which does this, written by Andrew Stacey, is fmtlatex.pl.
This is also in Perl and its documentation will be written on the screen if you use perldoc fmtlatex. I still have to try this.

I can run Matlab on my Mac again!

2011-04-13T19:22:00.005-07:00

After much struggling today I managed to make Matlab run again my Mac.
The major problem was that Matlab complained about that I have the wrong version of X11 installed on my system and it won't start. As I have finished teaching today for the semester, I thought that I am going to celebrate this by resolving this issue which I was struggling with for a year or so by now. On the internet you will see a lot of advice on what to do, and as they say, the truth is indeed out there, however, it is not so easy to find. In a nutshell what seems to happen is this:

Why Matlab does not start when other applications do start (say, Gimp, Gnuplot using X11, etc.).
Matlab seems to make the assumption that the X11 libraries are located at /usr/X11/lib and it sticks to this assumption no matter how your system is configured. I use XQuartz and macports' X11 and they put stuff elsewhere. I had some legacy code sitting in /usr/X11/, which I did not use. It was a remainder of some version of X11 that I used probably 2 or 3 laptops ago. Matlab reported that the lib was found, but the "architecture was wrong". The error message had something like:

.. Did find: /usr/X11R6/lib/libXext.6.dylib: mach-o, but wrong architecture..

Anyhow, here is one solution.
You have to arrange that /usr/X11 points to a directory that has a working X11 copy.
It is probably a good idea to first clean up the old X11 installation. You can do this by following the advice on the XQuartz FAQ page by issuing the following commands in the terminal:

sudo rm -rf /usr/X11* /System/Library/Launch*/org.x.* /Applications/Utilities/X11.app /etc/*paths.d/X11 sudo pkgutil --forget com.apple.pkg.X11DocumentationLeo sudo pkgutil --forget com.apple.pkg.X11User sudo pkgutil --forget com.apple.pkg.X11SDKLeo sudo pkgutil --forget org.x.X11.pkg

Then I have reinstalled the latest XQuartz copy (not all these steps might be necessary, but in order to stay on the safe side, I will describe everything I did).
I also have macports and xorg-libX11, xorg-libXp, xorg-server seems necessary for the following steps to succeed (but possibly other xorg-* ports are also needed). I am guessing that XQuartz does not install all the libraries, but after installing enough xorg-* ports through macports, all the libraries will be installed which are used by Matlab.

Now, my X11 is located at /opt/X11 and some additional libs are found at /opt/local/lib.

So I created a bunch of symbolic links:

sudo ln -s /opt/X11 /usr/X11
for i in /opt/local/lib/libX* ; do sudo ln -s $i /usr/X11/lib; done

The first line creates a symbolic link to /opt/X11, while the second is necessary because of the additional libX* libraries which, for some reason, macports puts into /opt/local/lib instead of puttting it into /opt/X11/lib. Initially I did not know that I need these libs, and then Matlab complained that it did not find the image for some lib (it was /usr/X11/lib/libXp.6.dylib).

Anyhow, I am really happy that this worked!
I hope people who will have the same trouble will find my post useful.

Djvu vs. Pdf

2009-11-17T08:55:00.008-07:00

Long blog again, so here is the executive summary: Djvu files are typically smaller than Pdf files. Why? Can we further compress pdf files? Yes, we can, but the current best solution has limitations. And you can forget all "advanced" commercial solutions. They are not as good as a free solution.

Introduction

DJVU is a proprietary file format by LizardTech. Incidentally, it was invented by some machine learning researchers, Yann LeCun, Léon Bottou, Patrick Haffner and the image compression researcher Paul G. Howard at AT&T back in 1996. The DJVULibre library provides a free implementation, but is GPLd and hence is not suitable for certain commercial softwares, like Papers, which I am using to organize my electronic paper collection. Hence, Papers, might not support djvu in the near future (the authors of Papers do not want to make it free, and, well, this is their software, their call).
Djvu files can converted to Pdf files using ddjvu, a command line tool which is part of DJVULibre (djvu2pdf is a script that calls this tool). Djvu can also be converted into PS files using djvups (then use ps2pdf). However, all these leave us with pretty big files compared to the originals and, on the top of it, if there was an OCR layer in the Djvu file, it gets lost, but this is another story. How much bigger? Here is an illustration:

Original djvu file: 9.9MB
djvu2pdf file: 427.6MB(!)
djvu2ps file: 1.0GB
djvu2ps, ps2pdf file: 162.6MB

Note that I have turned on compression in the conversion process (-quality=50). (The quality degradation was not really noticeable at this level.) So, at best, I got more than 16 times the original file size. Going mad about it, I started to search the internet for better solutions. I have spent almost a day on this (don't do this, especially if you are a student!)..

JBig2 and the tale of commercial solutions

First, I figured, the difference is that these use general image compression techniques (like jpeg), while djvu is specialized to text and black&white images. Thus, for example, it can recognize if the same character appears multiple times on the page, store a template and a reference to the template. This is clever. I then figured that PDF files support the so-called jbig2 encoding standard, which is built around this idea. Hence, the quest for software that would support encoding a document using a jbig2 encoder and put the result into a pdf format. The easiest would be, if such a software just existed out there. A few commercial packages indeed mention jbig2. I felt lucky (especially, seeing that there are a few cheap ones). So, I started to download trial versions. Here are the results:

PDFJB2: 34.1MB
CVision PdfCompressor: 48MB
CVision PdfCompressor with OCR: 49MB
A-PDF: 106.8MB
A-PDF + PDFCompress: 106.8MB
djvu2pdf + PDFCompress: conversion failed

Hmm, interesting. 34MB is much better than 160MB, but it is still a long way from 9.9MB. (After a superficial look at the resulting files I concluded that only the A-PDF compressed file lost quality. What happened with this file is that on some page in some line containing a mathematical formula, the top of the letters got chopped.)

Free, open source solutions

Becoming desperate, I continued hunting for better solutions. Searching around, I have found iText, which is an open source, free Java library supporting all kinds of manipulations of Pdf files. I have figured that it "uses" Jbig2, but it was not clear if it uses it for compression or just knows how to handle the encoding. So, here I go, I wrote a java program opening a pdf file and then writing it out in "compressed" mode. Hmm, this few lines of coding allowed me to create a file of size 26MB, smaller than what I could ever get previously. Exciting! Unfortunately, opening the file revealed the `secret': Quality was gone. The file looked to be seriously downsampled (i.e., the resolution was decreased). Not good.

Then I have found pdfsizeopt on google code, which aims exactly at compressing the size of pdf files! The Holy Grail? Well, installing pdfsizeopt on my mac was far from easy (I use a Mac, which also runs Windows; quite handy as some of the above software runs only under Windows..). However, finally, I was able to run pdfsizeopt. Unfortunately, it seems to crash, without even looking at my pdf file (I hope the bug will be corrected soon and then I can report results using it). Along the way, I had to install jbig2enc. For this, I just had to install leptonica (version 1.62, not the latest one), which is really the part that is doing the image processing part of the process. JBig2Enc expects a tif file and produces "pdf" ready output (every page is put in a separate file), which can be concatenated into a single pdf file by a python script provided. Having jbig2enc on my system, I gave it a shot. I first used ddjvu to transform the input to a tif file (using the command line option, "-quality=75", resulting in a file of size 1GB). Then I used the jbig2 encoded with the command line arguments "-p -s". The result is this:

jbig2enc: 3.8MB

Wow!! Opening the file revealed a dirty little secret: Color images are gone, as well as the quality of some halftoned gray-scale images got degraded. However, line drawings were kept nicely and, in general, the quality was good (comparable to the original djvu file). Conversion to tif took 5 minutes, conversion from tif to jbig2 took ca. 4 minutes, altogether making the whole process take close to 10 minutes. (Other solutions were not faster at all either. And the tests were run on a resourceful MacBook Pro.)

Conclusions

jbig2enc seems to work, but you will lose colors. If you are happy with this, jbig2enc is the solution, though the process should be streamlined a bit (a small script good do this). Oh yes, I did not mention that these processes are not fast. I did not attempt to measure the speed, but conversion takes a lot of time. Jbig2Enc is maybe on the faster end of the spectrum.

Future work

pdfsizeopt is a good idea. It should be made work.
It would be nice to create a jbig2enc wrapper
ddjvu is open source: Maybe it can be rewritten to support jbig2 directly. The added benefit could be that one could also keep the OCR layer in the original djvu file if one existed
Along the way, I have found a cool google code project, Tesseract, which is an open source OCR engine. How cool would it be if we had an OCR engine that helps the compression algorithm and eventually also puts an OCR layer on the top of documents which lack text information (think of scanned documents, or documents converted from an old postscript file). Currently, I am using Nuance's Pdf Converter Professional (yes, I paid for it..), which I am generally very satisfied with apart from its speed. However, this could be the subject of another post.

PS: I have tested the capabilities of Nuance's Pdf Converter Professional and Abbyy's in terms of their compression capabilities:
Nuance: 132MB
Abbyy: 129MB
Yes, I tried their advance "MRC" compression, in Nuance I have explicitly selected jbig2. No luck.

Keynote vs. Powerpoint vs. Beamer

2009-11-14T12:47:00.006-07:00

A few days ago I decided to give Keynote, Apple's presentation software, a try (part of iWork '09). Beforehand I used MS Powerpoint 2003, Impress from NeoOffice 3.0 (OpenOffice's native Mac version) and LaTeX with beamer. Here is a comparison of the ups and downs of these software, mainly to remind myself when I will reconsider my choice in half a year and also to help people decide what to use for their presentation. Comments, suggestions, critics are absolutely welcome, as usual. Btw, while preparing this note I have learned that go-oo.org has a native Mac Aqua version of OpenOffice. Maybe I will try it some day and update the post. It would also be good to include a recent version of Powerpoint in the comparison.

Stability

Keynote: Excellent
After a few days of usage, so take this statement with a grain of salt..
MS Powerpoint 2003: Excellent
Impress: Poor
Save your work very often
Beamer: Excellent

Creating visually appealing slides, graphics on slides

Keynote: Excellent
Positioning rulers help a lot. The process is really smooth. Keynote forces you to use less text. Built in templates are professional looking. Adding presentation graphics (tables, basic charts) is very easy. Cooler (technical drawing) better done with OmniGraffle. You can also easily animate the graphics, tables. Overall, very impressive.
MS Powerpoint 2003: Good
Aligning to other objects is more cumbersome than in Keynote. The quality of fonts, color palettes, templates is not as good in Keynote.
Impress: Good
Same as MS Powerpoint, maybe somewhat below (but the difference is not big).
Beamer: Poor
The fonts and styles (templates) are great. However, creating slides with lively graphic is a nightmare (due to the lack of a GUI): You will end up with a few standard layouts, you will in general not use graphics, let alone animated graphics (or you will spend days on creating your slides). Also, departing from the styles is difficult and I am just bored of some of these styles that everyone seems to use.

LaTeX (math) support

Keynote: Poor
Supported through LatexIt (free), but overall a cumbersome process. Details below.
MS Powerpoint 2003: Medium
Supported through TexPoint (commercial, USD30) process is roughly same as with LatexIt and Keynote, slightly better integration.
Impress: Medium
Supported through OOoLatex (free), same as MSPowerPoint + TexPoint, the integration is slightly better.
Beamer: Excellent
Beamer is built for this!

Animations

Keynote: Near perfect
Magic slide transition helps a lot with continuity across slides. What does this do? If you have the same object on two consecutive slides, Keynote will create an animation, keeping the object on screen and flying it to its new position. Works with multiple objects, too. I have found this very helpful for presenting a multi-slide argument. In general, Keynote animations are slick, polished, the flexibility is great. I lack some features of Beamer, such as animated highlighting, in-place replacement of some text (these can all be simulated with the existing tools, but with difficulty only).
MS Powerpoint 2003: Basic
I miss Keynote's magic transitions. In general, Keynote is richer in animations. Again, some features of Beamer would be nice to have.
Impress: Weak
Impress is inferior in terms of its animation caps to MS Powerpoint
Beamer: Good
If only someone added support for magic transitions between slides. Some other cool effects would also come handy.

Dual screen presentation support

The idea is to show notes, time left in addition to the current and next slide on your screen, while showing the current slide on the big screen.

Keynote: Excellent
Keynote supports double screen presentations natively. If you need to swap displays, go on the notes screen in the options menu. This will be on the big screen, obviously, if you need to swap the the screens.
MS Powerpoint 2003: Not available
I have no experience with this feature of MS Powerpoint. Maybe you can use and add-on or something, but the basic software does not support it. I am pretty sure newer versions of Powerpoint must support this.
Impress: Excellent(?)
The "Sun Presenter Console" extension supposedly supports dual screen presentations just like Keynote, but I have never had the chance to test it. Hence, the question mark. Some posts on the internet indicate that the extension might leak memory.
Beamer: Basic support
Use Splitshow for this purpose. However, as far as I know, you cannot show the current time or the time remaining on the notes screen.

Interoparability

I want to put my presentations on the web so that people can look at them no matter what (major) operating system they use, without loosing animations or any other features. Another desired feature is the ability to create a compact, printable version of the slides: That is, if you have animations spanning multiple slides, somehow they should get handled intelligently. There is a tradeoff here: The more animation rich your slides are, the more bloated/complicated your printout will be.

Keynote: OK
Proprietary file format. This is my biggest complaint. A keynote presentation is a keynote presentation. Apple likes to lock you in. Export to PDF and PPT works relatively well, but will lose some features of the presentation, like the cool animations. Exporting to PDF without animations to create printable versions seems to work well.
MS Powerpoint 2003: Good
Free powerpoint viewers exist that can play any PPT file. Export to PDF will again lose some features.
Impress: Good
Same as powerpoint.
Beamer: Excellent
Produces PDF outputs: The presentations can be viewed on any computer! Also, the source is later, beamer is available on all systems. Add [handout] to the style and beamer will create an animation free version of your slides that works almost all the cases.

More about using formulae in Keynote (and why it sucks)

I used LatexIt which produces a PDF that can be embedded into the presentation. Style is not matched automatically. The PDF contains the latex source for the formulae, copy paste it back to LatexIt to edit it. When done with the edit, you need to drag and drop the formula back into Keynote. This sucks, since you need to delete the original that you have edited, reposition the new formula and reapply animations if you had any. Horrible.

Another issue is that the source saved with the formula by default does not have the preamble, thus using a command set specific to a presentation is difficult to achieve (you have to set this up manually). Another major headache is that you will not be able to use inline formula (a text is either in LaTeX, or in Keynote, the fonts in general do not match and mix well, alignment is a nightmare), nor will you be able to animate easily formulae (e.g., displaying a multiline formula line by line requires you to split the formula into multiple PDFs and use Keynote animations to show them one by one; this is problematic because formula alignment by hand is time consuming).

Optogenetics

2009-10-31T11:01:00.002-07:00

This is a little deviation from the usual topic.
Scientist are able to genetically modify neurons that respond to light. They are in fact able to do this in a targeted manner. A patient would then have some LEDs inside his skull, emitting some light. In response the selected neurons start to fire. They demonstrated the technology by making mice run counterclockwise when they turn on the light. This is input to the brain. Earlier, it was demonstrated that neurons can be genetically modified to emit light when they are firing. Are we heading towards rewiring the brain and turning it into a light computer?
The motivation for the research is to cure diseases like Parkinson's disease, when the patient has all the circuity and muscles but is just unable to make the movements. In fact, the researchers are already testing this technology on primates. Source: Wired Nov. 2009, "Powered by Photons" pp. 109--113. The wikipedia entry for optogenetics is here.

Pitfalls of optimality in statistics

2009-10-25T19:28:00.006-07:00

I was reading a little bit about robust statistics, as we are in the process of putting together a paper about entropy estimation where robustness comes up as an issue. While searching on the net for the best material to understand this topic (I am thinking about posting another article about what I have found), I have bumped into a nice paper (downloadable from here) by Peter J. Huber, one of the main figures in robust statistics, where he talks about a bunch of pitfalls around pursuing optimality in statistics. Huber writes eloquently -- he gives plenty of examples, motivates definitions. He is just great. I can only recommend this paper or his book. Now, what are the pitfalls he writes about? He distinguishes 4 types with the following syndromes:

The fuzzy concepts syndrome: sloppy translation of concepts into mathematics. Think about uniform vs. non-uniform convergence (sloppy asymptotics). In statistics a concrete example is the concept of efficiency which is defined in a non-uniform manner with respect to the estimable parameters, which allows for (weird) "super-efficient" estimators that pay special attention to some distinguished element of the parameter-space.
The straitjacket syndrome: the use of overly restrictive side conditions, such as requiring that an estimator is unbiased or equivariant (equivariant estimates in high dimensions are inadmissible in very simple situations). In Bayesian statistics another example might be the convenient but potentially inappropriate conjugate priors.
The scapegoat syndrome: confusing the model with reality (offering the model for the gods of statistics instead of the real thing, hoping that they will accept it). The classic example is the Eddington-Fisher argument. Eddington advocated the mean-absolute-deviation (MAD) instead of the root-mean-square (RMS) deviation as a measure of scale. Fisher argued that MAD estimates are highly inefficient (converge slowly) relative to the RMS deviation estimates if the sample comes from a normal distribution. Tukey has shown that the situation gets reversed even under small deviations from a normal model. The argument that under narrow conditions one estimator is better than some other should not be even made. Another example is perhaps classical optimal design and the fundamentalist approach in Bayesian statistics. Of course, there is nothing wrong with assumptions, but the results should be robust.
The souped-up car syndrome: by optimizing for speed we can end up with an elaborate gas-guzzler. Optimizing for one quantity (efficiency) may degrade another one (robustness). Practical solutions must find a balance between such contradicting requirements.

These syndromes are not to hard identify in machine learning research. Wear protective gear as needed!

How to make Thunderbird delete temporary file

2009-09-07T10:06:00.004-07:00

If you are using Thunderbird (TB) on Mac OSX, you might be annoyed by that when TB opens an attachment (like a pdf file) it creates the file on the Desktop and then leaves just it there! I have finally found a solution, which seems to work at least for me and assuming that you also have Firefox. The solution is here, but I duplicate it here to make sure the idea spreads:

Simply open Firefox, in the address bar type in about:config, then add a boolean variable browser.helperApps.deleteTempFileOnExit and set its value to true.

Now, this works to the extent that when you exit Firefox(!!) (after quitting Thunderbird), it will remove the cluttering files.

Enjoy!

Ninja Carburglars

2008-04-05T14:01:00.001-07:00

see more crazy cat pics

Statistical Modeling: The Two Cultures

2008-03-29T16:55:00.004-07:00

Sometimes people ask what is the difference between what statisticians and machine learning researchers do. The best answer that I have found so far can be found in
"Statistical Modeling: The Two Cultures" by Leo Breiman (Statistical Science, 16:199-231, 2001).
According to this, statisticians like to start by making modeling assumptions about how the data is generated (e.g., the response is a noise added to the linear combination of the predictor variables), while in machine learning people use algorithm models and treat the data mechanism as unknown. He estimates that (back in 2001) less than 2% of statisticians work in the realm when the data mechanism is considered as unknown.
It seems that there are two problem with the data model approach.
One is that the this approach does not address the ultimate question which is making good predictions: if the data does not fit the model, this approach has nothing to offer (it does not make sense to apply a statistical test if the assumptions are not valid).
The other problem is that as data become more complex, data models become more cumbersome. Then why bother? With complex models we lose the advantage of easy interpretability, not talking about the computational complexity of fitting such models.
The increased interest in Bayesian modeling with Markov Chain Monte Carlo is viewed as the response of the statistical community to this problem. True enough, this approach might be able to scale to complex data, but does this address the first issue? Are not there computationally cheaper alternatives that can achieve the same prediction power?
He characterizes the machine learning approach, as the pragmatic approach: You have to solve a prediction problem, hence take it seriously: Estimate the prediction error and choose the algorithm that gives a predictor with the better accuracy (but let's not forget about data snooping!).
But the paper offers more. Amongst other things it identifies three important recent lessons:

The multiplicity of good models: If you have many variables, there can be many models of similar prediction accuracy. Use them all by combining their predictions instead of just picking one. This should increase accuracy, reduce instability (sensitivity to perturbations of the data). Boosting, bagging, aggregation using exponential weights are relevant recent popular buzzwords.
The Occam dilemma: Occam's razor tells you to choose the simplest predictor. Aggregated predictors don't look particularly simple. But aggregation seems to be the right choice otherwise. I would think that Occam's razor tells you only that you should have a prior preference to simple functions. I think this is rather well understood by now.
Bellman: dimensionality -- curse or blessing: Many features are not bad per se. If your algorithm is prepared to deal with the high-dimensional inputs (SVMs, regularization, random forests are mentioned) then extracting many features can boost accuracy considerably.

In summary, I like the characterization of the difference between (classical) statistical approaches and machine learning. However, I wonder if these differences are still as significant as they were (must have been) in 2001 when the article was written and if the differences will become smaller over time. Then it will be really difficult to answer the question on the difference between the statistical and the machine learning approaches.

Bayesian Statistics in Medical Clinical Trials

2008-03-21T19:48:00.004-07:00

I came across a very interesting document.
The document is titled "Guidance for the Use of Bayesian Statistics in Medical Device Clinical Trials". It is a draft guidelines poster by the Center for Devices and Radiological Health of FDA, dated May 23, 2006.
Why is this interesting? The job of FDA (the US Food and Drug Administration) is to make sure that the decisions in any clinical trial are made in a scientifically sound manner. Clearly, when following the Bayesian approach the choice of the prior and the model can influence the decisions. What does FDA do in this situation?
The establish a process where they require a pre-specification (and agreement on) both the prior and the model, including an analysis of the operating characteristics of the design. This latter includes estimating the probability of erroneously approving an ineffective or unsafe device (the Type I error). This will typically be done by conducting Monte-Carlo simulations, where the Type I error is measured for the borderline cases when the device should not be approved. In the case of a large estimated Type I error, the trial will be rejected.
Is this a good procedure? If the simulations use a biased model then the estimated Type I error might be biased. Their response is that both the prior and the model should be backed up with scientific arguments and existing statistics. Yet another problem is that the calculations often use MCMC. How do you determine if your samples converged to the posterior? The samples of the posterior are not iid. How do you know that you took enough samples of the posterior? (Think of a mixture of Gaussian, with a narrow Gaussian proposal. If you sample from the mixture and then sample just a few points with Metropolis-Hastings, you will likely miss the second mode if the two modes are sufficiently far away.)
On the other hand, there are a number of potential advantages to a Bayesian design. If we accept that the model and the prior is good, then often the Bayesian analysis will require smaller sample sizes to reach a decision (if they are not, the conclusion might be wrong). It can also provide flexible methods for handling interim analyses (stopping when enough evidence is available for either approval or rejection) and sometimes good priors are available such as earlier studies on previous generations of a device or from overseas studies. Such approaches can be used with a fequentist approach, too, but the frequentist analysis of deriving a procedure is often non-trivial, while the Bayesian "only" needs to be concerned about computational issues.
The document cites two trials that used Bayesian analysis. It appears that in both studies Bayesian analysis was used only as a supplementary information, i.e., the critical decisions (if a device is safe and minimally effective) were made using traditional, frequentist methods.
Common to both the frequentist and the Bayesian approaches is the use of a number of unverified assumptions. In the frequentist case, if the design is simple then the typical assumption is only that there is a common underlying distribution to the outcome-patient pairs and that patients are selected uniformly at random from the population. This looks fairly minimal, but can be questioned nevertheless (drifts, environmental effects, sample biases, etc.). In a more complicated scenario there will be more assumptions. If the set of assumptions for the methods satisfy some containment relation then one naturally trusts the method that relies on less information. In the lack of containment the decision of which method to prefer is not so simple. In any case, it is very interesting to see how a regularity body (like FDA) wrestles with these fundamental issues. They look to act in a pretty reasonable manner. The existence of this document predicts that we should expect to see more decisions that used Bayesian analysis in the future. Is this good or bad? One could be concerned by the use of more unverified assumptions in the Bayesian analysis and that the probability of making an error can also increase because the calculations are non-trivial. Life is dangerous, is not it? But how dangerous will it be if Bayesian analysis is used routinely in assessing success in clinical trials? Time will tell for sure. Well, assuming some form of stationarity.

Curse of dimensionality

2008-03-15T20:41:00.005-07:00

I came across two papers today that discuss the curse of dimensionality. I thought this is just enough to write a short blog about the topic that definitely deserves attention. So, here we go:

The first paper is by Flip Korn, Bernd-Uwe Pagel and Christos Faloutsos, the title is On the "Dimensionality Curse" and the "Self-Similarity Blessing". This is a 2001 paper that won The paper is about nearest neighbor retrieval: You have $n$ datapoints that you can store and the task is to find the nearest neighbor among these datapoints of a query point. If the data lies in a $D$-dimensional space Euclidean space, it was a common wisdom to believe that the time required to find the nearest neighbor scales exponentially with $D$. The essence of the paper is that if the data lies on a low dimensional manifold then the complexity of search will depend only on the intrinsic dimensionality of the manifold. (The cover tree package due to Alina Beygelzimer, Sham Kakade, and John Langford should be mentioned here. This software is able to deal with data that does not necessarily lies in a vector space. The algorithms comes with guarantees similar to the above mentioned one. For details and further references see the accompanying paper. I guess there were quite a few precursors to this paper since around 1998, where a lot of excitement was generated when people started to realize this phenomenon.) This paper has some relation to our recent work that I will write about at the end of this blog.

So the good news here is that although with a little bit of a luck, a clever algorithm might run significantly faster than what is predicted by the worst case bounds. Note that a not so clever algorithm will not run faster. So you need luck for your data to display some regularities, but you need a clever design to take advantage of those regularities.

The other paper is by David Donoho from 2000, High-dimensional data analysis: The curses and blessings of dimensionality, an Aide-Memoire lecture delivered at the conference "Math Challenges of the 21st Century". Donoho mentions three curses (in optimization, Bellman's original use; in function approximation and in numerical integration). When talking about the blessings, he first talks about the concentration of measure (CoM) phenomenon, which roughly states that any Lipschitz function defined over the $D$-dimensional sphere is "nearly constant": If we place a uniform measure on the sphere then the the probability that it deviates from its expectation by more than $t$ is bounded by $C_1 exp(- C_2 t)$, where $C_i$ are universal constants (i.e., they neither depend on $D$, nor $f$)! This is important since often we are interested in an expected value of a Lipschitz function and we hope to estimate the expected value by the observed (random) value of the function. This phenomenon is important in model selection, as explained to some extent in the paper. The second blessing, related to the CoM phenomenon is "dimension asymptotics". The observation is that when the CoM applies, often as $D$ goes to infinity, the distributions converge to some limiting distribution. Sometimes then it becomes possible to obtain predictions that work for moderate dimensions but which are derived by using the limiting distributions (the example mentioned is the prediction of the top eigenvalue of a data covariance matrix). The third blessing is when the data is a sampled version of a continuous phenomenon (he calls this "approach to continuum"). Since what is measured is continuous, the space of observed data will show signs of compactness that can be exploited. Here the example is that a basis derived from some sampled data with some procedure tends to resemble wavelets, an object from the continuous world. For larger $D$ the resemblance becomes stronger and so the interpretation becomes easier. The is the bless of dimensionality in action.

Back in 2001 he mentioned 3 areas of potential interest: The first is high-dimensional approximate linear algebra (use randomization, the concentration of measure phenomenon to speed up calculations). Here he mentions rank $k$ approximation to data matrices. The second area is when the data are curves or images and the problem is to select a good basis. He mentions an interesting example here: We have a single data point and $D$ is very large. Then if the data is the realization of a stationary Gaussian stochastic process (i.e., coordinates are correlated) then we can in fact learn the full probability distribution. The third example is coming from approximation theory. Here, he cites a well-known result of Barron, that imposes a constraint on the derivative of the function: The derivative must be such that its Fourier transform is integrable. Since assuming $s$ times differentiabily typically yields that the function can be approximated only at a rate of $n^{-s/D}$, we expect to see a slow approximation rate of $n^{-1/D}$. However, Barron has shown that this type of functions can be approximated at the rate $n^{-1/2}$. What this and similar results point to that there are non-classical spaces of functions where things might work differently from what one expects. Again, the need arises for algorithms that are clever enough to take advantage if the situation is such that the curse of dimensionality can be avoided.

On another note, recently with Amir massoud Farahmand and Jean-Yves Audibert we published a paper related to these topics at ICML. The subject is dimensionality estimation of manifolds based on random samples supported by the manifold. Here again, the good news is that the embedding dimension does not play a direct role in the quality of the estimates (only through the properties of the embedding). One motivation for coming up with this method was that we wanted to modify existing regression procedures so that when the data lies on a low dimensional manifold, the methods should converge faster. We figured that many algorithms tune their parameters to the dimensionality of the data points and if we replace that dimensionality by the manifold dimensionality, we get a "manifold adaptive" method, which is clever enough to converge faster when the input lies on a manifold. Interestingly, these results can be obtained without ever estimating the manifold itself. However, this should be the subject of another post!

On a last note, quite a few references to works dealing with the curse of dimensionality can be found in the annotated bibliography of Damien Francois. Enjoy!

Discriminative vs. generative learning: which one is more efficient?

2007-08-12T06:12:00.000-07:00

I just came across a paper by Philip M. Long, Rocco Servedio and Hans Ulrich Simon. (Here is a link to the paper titled "Discriminative Learning can Succeed where Generative Learning Fails".) The question investigated in the paper is the following:
We are in a classification setting and the learning problem is defined by a pair of jointly distributed random variables, (X,Y), where Y can take on the values +1 and -1. Question: How many iid copies of this pair does an algorithm need to (i) find a classifier that yields close to optimal performance with high probability (ii) find two score functions, one trained with the positive examples only, the other with the negative examples only such that the sign of the difference of the two score functions gives a classifier that is almost optimal with high probability?
The result in the paper is that there exists a class of distributions, parameterized by d (determining the dimension of samples) such that there is a discriminative algorithm (tuned to this class) that can learn the correct classifier with only $2log(2/\delta)$ samples, while the number of samples required for any generative classifier is at least d.
Since it is clear that the requirements of generative learning are stronger than those of discriminative learning, it follows that in the above framework discriminative learning is strictly "easier" than generative learning.
The distribution concentrates on O(d) samples and the main idea is that the joint knowledge of positive and negative samples suffices for the easy identification of the target distribution (hence, classifier), while knowing only either the positive or negative examples alone is insufficient. Two special inputs, both marked for easy of recognition, determine the full distribution jointly but one of the inputs is in the positive set, the other is in the negative set and the knowledge of only one of them is insufficient to learning the otherwise "difficult" to learn distribution.
Although the construction given in the paper is simple and works as intended, it is arguably "artificial and contrived", as it was also noted by the authors. In particular, does a similar result hold when we consider a continuous domain of a fixed dimension, and/or we restrict the class of algorithms to consistent ones? Further, the example shows more the limitation of algorithms that learn from positive and negative samples independently of each other than the limitation of generative algorithms (generative algorithms traditionally refer to learners that estimate the joint distribution of the inputs and outputs).
The question of whether generative or discriminative algorithms are more efficient are particularly interesting in light of an earlier paper by Andrew Y. Ng and Michael Jordan ("On Discriminative vs. Generative classifiers: A comparison of logistic regression and naive Bayes", NIPS-14, 2002). In this paper the authors compare one particular discriminative algorithm with another particular algorithm that is "generative". The two algorithms are logistic regression and naive Bayes and together they form what is called a "Generative-Discriminative" pair. The meaning of this is that while naive Bayes maximizes the total joint log-likelihood, $\sum_{i=1}^n \log p_\theta(x_i,y_i)$ over the samples, logistic regression maximizes the total conditional likelihood, $\sum_{i=1}^n \log p_\theta(y_i|x_i)$ over the same parametric model. In the case of these two particular algorithms the parametric model is written in terms of $p(x|y)$ and asserts independence of the individual components of the feature-vector $x$. (For continuous spaces the individual feature distributions, $p(x_k|y)$, are modeled as Gaussians with unknown mean and variance.) The agnostic setting is considered (the input distribution is not restricted). Since both learners pick a classifier from the very same class of classifiers and the discriminative learner in the limit of an infinite number of samples converges to the best classifier from this class, it follows that the ultimate loss suffered by the discriminative learner is never higher than that suffered by the generative learner. Hence, it seems that if the naive Bayes assumption made by the generative method is not met, the discriminative method can have an edge -- at least ultimately (open issue: give an example that shows positive separation!). However, this is just half of the story: the generative model may converge faster! In particular, the authors state an upper bound on the convergence of loss for the generative model that scales with $\sqrt{1/n \log(d)}$ ($d$ is the number of components of $x$), while as follows from standard uniform convergence results, the same convergence rate for the discriminative method is $\sqrt{d/n \log(d/n)}$. They argue that this result follows since the hypothesis class has a VC-dimension of $d$. Note the difference in the way the two bounds scale with $d$, the dimension of the input space: In the case of the discriminative algorithm the scaling is (log-)linear with $d$, while in the case of the generative algorithm it is logarithmic in $d$. (Strictly speaking, the upper bound would call for a proof since logistic regression is not a risk-minimization algorithm for the 0/1 loss and the cited theory has been worked out for risk-minimization algorithms.) Since comparing upper bounds is not really appropriate, they point to existing lower bounds that show that the worst-case sample complexity is lower bounded by $O(d)$. (My favorite paper on this is by Antos and Lugosi: "Strong minimax lower bounds for learning": link.) Hence, the conclusion of Ng and Jordan is that, contrary to the widely held belief, generative learning can sometimes be more efficient than discriminative learning; at least when the number of features is large compared to the number of samples and the ultimate loss of the generative learner is not much higher than that of the discriminative learner. They also performed experiments on UCI datasets to validate this claim. The experiments show that the performance of naive Bayes is indeed often better when the number of examples is smaller. Unfortunately, the figures show the loss as a function of the number of samples only and hence validate the theory only half-way since for a full validation we should know how the dimension of the dataset influences the performance.
A similar conclusion to that of Ng and Jordan was shown to hold in an earlier KDD-97 paper titled "Discriminative vs. Informative Learning" by Y. Dan Rubinstein and Trevor Hastie (link) who did a case study with simulated and real examples.
The convergence rate comparison looks quite intriguing at the first sight. However, some more thinking reveals that the story is far from being finished. To see this consider the "rate" function $r(n,d) = L_{gen}$ if $n\le D-1$, $r(n,d) =\min(L_{gen},\sqrt{d/n})$ if $n\ge D$. Imagine that $r(n,d)$ is an upper bound on the loss of some learner, where $L_{gen}$ is the loss of the generative learner. The rate of convergence then is $\sqrt{d/n}$, not contradicting with the lower bounds, but clearly, this discriminative learner will be competitive with the generative learner.
So is discriminative learning more (sample) efficient than generative learning? It seems that sometimes having both the positive and negative samples at hand can be useful. However, generative learning might be advantageous when the model considered fits well the data. Hence, the case is not yet settled. Many interesting open questions!

Learning Symbolic Models

2007-07-30T04:20:00.001-07:00

It is quite a common sense that successful generalization is the key to efficient learning in difficult environment. It appears to me that this must be especially true for reinforcement learning.
One potentially very powerful idea to achieve successful generalization is to learn symbolic models. Why? It is because a symbolic model (almost by definition) allows for very powerful generalizations (e.g. actions with parameters, state representation of environments with a variable number of objects with different object types, etc.).
JAIR just published the paper on this topic by H. M. Pasula, L. S. Zettlemoyer and L. P. Kaelbling, with the title "Learning Symbolic Models of Stochastic Domains". A brief glance reveals that the authors propose a greedy learning method, assuming a particular representation. The learning problem itself was shown earlier to be NP-hard, hence this sounds like a valid approach.
However, one thing is badly missing from this approach: learning the representation itself. It appears that the authors' assumption is that the state representation of the environment is given in an appropriate symbolic form. This is in my opinion a very strong assumption -- at least when it comes to deal with certain real-world problems when only noisy sensory information of the environment is available (think of robotics).
However, I must realize that I am disappointed only because I wrongly assumed (given the title) that the paper will be about the problem of learning representations. Will we ever be able to learn (symbolic) representation in an efficient manner? What are the conditions that allow efficient learning? Do we need the flexibility of symbolic representations to scale up reinforcement learning at all? Here, at UofA several people are interested in these questions (well, who is not??). More work needs to be done, but hopefully, some day you will here more about our efforts..

Minimize!

2007-05-21T14:26:00.000-07:00

A matlab code for minimizing a multivariate function whose partial derivatives are available by Carl Rasmussen is downloadable from here. The routine looks pretty efficient, at least on the classical Rosenbrock function.

A notion of function compression

2007-05-20T10:07:00.000-07:00

The following compressibility concept is introduced by Harnik and Naor in their recent paper: Given a function $f$ over some domain, a compression algorithm for $f$ should efficiently compress an input $x$ in a way that will preserve the information needed to compute $f(x)$. Note that if $f$ is available (and efficiently computable) then compression is trivial as then $y=f(x)$ will serve the purpose of the compact representation of $x$. Actually, the concept was originally studied in the framework of NP decision problems where unless $P=NP$ $f$ is not efficiently computable, hence the trivial solution is not available.

I am wondering if this compressibility notion could be used in learning theory or function approximation? Consider e.g. classification problems so that the output of $f$ is $\{0,1\}$. In order to prevent the trivial solution we may require that $x$ be compressed to some $y$ such that for some fixed (efficiently computable) function $g$, $f(g(y))=f(x)$. We do not require that $g(y)=x$, though if $g$ satisfies this then we certainly get a solution: if a compact representation of $\{ x| f(x)=1\}$ is available then $f$ can be well-compressed. We might allow of course for some error and study approximation rates. Of course, the notation applies to real-valued or more general functions, too. What is the class of functions that can be efficiently compressed? How is this class related to classical smoothness spaces (in the case of real-valued functions)? One obvious thought is that the smoother the target function is, the better the obvious discretization approach would be. It would be interesting to find out whether this new approch could lead to new regularity descriptions by varying the restrictions on the compression.

Another related thought is to compress the training samples in a learning problem such that the solution is kept (roughly) the same.

LaTeX support

2007-04-17T00:38:00.000-07:00

I added the following two lines to the header section of the template of this page:

  <script type="text/javascript"
src="http://www.maths.nottingham.ac.uk/personal/drw/LaTeXMathML.js">
</script>

Suddenly, I can type (almost) anything in latex, e.g. \$a_n\$ becomes $a_n$. Fancy!
(If you do not see anything fancy then either Javascript is disabled in your browser or you are using Internet Explorer without MathML support. In the latter case you may want to download MathPlayer by DesignScience.)

Many thanks for Peter Jipsen the folks who developed ASCIIMathML, which serves as the basis of LaTeXMathML by Douglas R. Woodall. Examples showing what is possible with LatexMathML can be found here. This is an indispensable tool!

The nice thing is that MathML is scaleable:

$E=m c^2$

The Fastest Mixing Markov Chain on a Graph

2007-04-16T18:05:00.000-07:00

The paper can be found here. The authors are Stephen Boyd, Persi Diaconis and Lin Xiao. I have found the paper while looking at the papers by Perso Diaconis, a notable mathematician and magician.

The paper talks about exactly what the title suggests: You are given a finite graph and you can set up a random walk on this graph by determining the transition probabilities between vertices that are connected by an edge. The walk must be symmetric so that the uniform distribution is a stationary distribution of this walk. Assuming that the associated Markov chain is irreducible and symmetric, the state distribution will converge to the uniform. The task is to maximize the rate of convergence of this. The solution is the Fastest Mixing Markov Chain on the graph (FMMC).

The authors show that this is a convex optimization problem and give a polynomial algorithm (based on semidefinite programming) to find the solution. A subgradient method is given that can be more effective for larger graphs. The solution is generalized to the non-symmetric case by considering reversible Markov chains.

Why I find this paper interesting? Well, it is always nice to find out that a problem is convex hence can be solved in an "efficient" manner. But the main reason is that if an agent wanted to find out the most about the states of its environment, it would need to find exactly the FMMC (assuming a finite state environment). Questions: What if the transitions probabilities cannot be changed in an arbitrary manner. The case I have in mind is when you have an Markovian Decision Problem and you want to find the fastest mixing policy, where the goal is to converge say e.g. to a distribution which is close to uniform (the uniform distribution might not be a solution). Is there a well-defined solution to this problem? Do the ideas generalize to this problem? To what extent? Can such a solution be found while interacting with the environment?

The Loss Rank Principle by Marcus Hutter

2007-04-15T19:43:00.000-07:00

I found the paper posted by Marcus Hutter on arxiv quite interesting. The paper is about model (or rather predictor) selection. The idea is a familiar one, but the details appear to be novel: You want to find a model which yields small loss on the dataset available, while yielding a larger loss on most other datasets.

Classification: The simplest case is when we consider supervised learning and the target set is finite. Then you can count the number of target label variations such that the predictor's loss is smaller than its loss when the true targets are used. This idea sounds very similar to the way Rademacher complexity works, see e.g. the paper of Lugosi and Wegkamp, where a localized version of Rademacher complexity is investigated.

Regression: For continuous targets you can use a grid with an increasing resolution (assume that the range of targets is bounded) and count the number of gridpoints such that the predictor's loss is less than its loss on the true dataset.
With an appropriate normalization this converges to the volume of such target values (hopefully this set is measurable:)).

The paper does not go very far: Some examples are given that demonstrate that the criterion gives a computable procedure and that this procedure is reasonable. A quick comparison to alternatives is given. It will be interesting to see the further developments!

Why this Blog??

2007-04-14T19:48:00.000-07:00

I am struggling with organizing the notes I make after lectures or after reading a paper. Hence I will experiment with this fancy way of keeping track of my thoughts. Of course, I will be happy to receive feedback from the occasional readers.

We will see how well it goes!