kvh

What's the best machine learning algorithm?

2012-02-17T10:24:00.000-08:00

People often want to know what "the best" machine learning algorithm is. This kind of question has the same answer in every field: “it depends”. If we could shelve our pedantry for a moment though, and give an answer, that answer would be Random Forests. A Random Forest is a machine learning procedure that trains and aggregates a large number of individual decision trees. It works for any generic classification or regression problem; is robust to different variable input types, missing data, and outliers; has been shown to perform extremely well across large classes of data; and scales reasonably well computationally (it’s also map-reducible). Perhaps best of all, it requires little tuning to get good results. Robustness and ease-of-use are not often appreciated as they should be in machine learning (not to the extent cool-sounding names are, anyways), and it's hard to beat tree ensembles, and Random Forests in particular, on these dimensions.

Random forests work by generating (typically hundreds) of decision trees in a specific random way such that each is de-correlated with the others. Since each decision tree is a low-bias, high-variance estimator, and each is relatively uncorrelated with the others, when we aggregate their predictions we get a final prediction with low bias AND low variance. Magic. The trick is in getting trees trained on the same dataset to be uncorrelated. This is accomplished by using randomly sampled subsets of features for evaluation at each node in each tree and a randomly sampled subset (bootstrap) of data points to train each tree.

Put simply, if you have a machine learning problem and you don’t know what to use, you should use random forests. Here, in table form (courtesy of Hastie, Tibshirani and Friedman), is why:

Random forests inherit most of the good attributes of "Trees" in the above chart, but in addition also have state-of-the-art predictive power. Their main drawbacks are a lack of good interpretability, something that most other highly predictive algorithms do even worse on; and computational performance -- if you need something for real-time production, it could be hard to justify using random forests and spending the time to evaluate hundreds or thousands of trees.

If you are interested in playing around, grab the R package.

I recently heard the president of Kaggle, Jeremy Howard, mention that Random Forests seem to show up in a disproportionate number of winning entries in their data mining competitions. Cross-validation, I call that.

More reading:
A Comparison of Decision Tree Ensemble Creation Techniques

An Empirical Comparison of Supervised Learning Algorithms

Recurrent -- A python library for natural language parsing of recurring events

2012-02-15T15:43:00.000-08:00

For a project I'm working on I needed the ability to turn a natural language phrase like "every other saturday starting next month" into iCalendar-standard RRULEs. I couldn't find a python library that implemented this, so I built it. Check it out on github.

Here are some example input phrases and output recurrence rules:

'on weekdays' => 'RRULE:BYDAY=MO,TU,WE,TH,FR;INTERVAL=1;FREQ=WEEKLY'
'daily starting march 3rd until april 5th' => 'DTSTART:20120303\nRRULE:FREQ=DAILY;INTERVAL=1;UNTIL=20120405'
'the first and third friday of every month' => 'RRULE:BYDAY=1FR,3FR;INTERVAL=1;FREQ=MONTHLY'
'once a year on the fourth thursday in november' => 'RRULE:BYMONTH=11;BYDAY=4TH;INTERVAL=1;FREQ=YEARLY'

It's an alpha release currently, so please submit any issues you find.

Basic Income Guarantee

2012-01-05T13:47:00.000-08:00

Job losses from this recession are staggering. calculated risk has a nice visualization of the magnitude of man hours lost

These losses have not been spread evenly of course -- the less educated have taken the brunt

Even under optimistic scenarios (which we are not currently experiencing), it will take 5 to 10 years to get these jobs back. If they ever come back.

This means a lot of people without work and income. The question then is: what should we do about this? Should we do anything?

One option is to give everyone a basic income. The basic income guarantee is an "unconditional, government-insured guarantee that all citizens will have enough income to meet their basic needs." It differs specifically from a negative income tax, like our current social programs, in that every individual (not household) receives the benefit, regardless of wealth or income, unconditionally.

Why would this work? There are a bunch of reasons, which I'll get into, but more pressing is the one big reason why people think it won't work: people will lose the motivation to work. I think this belief represents a misunderstanding of human motivation. People work harder -- go to college, put in the hours -- because of innate desires for status and social approval, not out of terror of meeting their basic needs. In fact, under pressure of homelessness or starvation, people will often be forced to make sub-optimal long-term decisions, like foregoing investment (schooling) in themselves or their children.

Anyways, here are the pros and cons as I see them, and my rebuttals.

Cons

Reduced incentive to work
I addressed this above, but there is hard evidence on this. Manitoba, Canada, actually tried a basic income program for 5 years, known as Mincome. The results:

On the whole, the research results were encouraging to those who favour a GAI [Guaranteed Annual Income]. The reduction in work effort was modest: about one per cent for men, three per cent for wives, and five per cent for unmarried women. These are small effects in absolute terms.

Smaller and shorter-term studies in the US have found slightly larger effects, around 5% total drop in employment. I think this is a real draw back. It's easy to see how demand for certain low-paying jobs would decrease, raising prices and reducing output for those goods below an optimal level. The good part about basic income is that its distortion of incentives is very simple and fairly predictable, unlike most federal social programs that target specific actions or demographics and create myriad twisted incentives and unintended consequences.

Redistribution
You may or may not see this as a con, but in the end a basic income is a redistribution of wealth from the rich to the poor. (Yes the "rich" get the income too but they are paying for their own in taxes as well as the poor's.) You can make a moral argument against redistribution, but I think it is a weak one. Luck plays an enormous role in any one person's outcome. To the extent we can smooth out luck, I think we should. A basic income guarantee seems like a reasonable step in the right direction.

Inflation
Some people argue a basic income would simply raise prices. Again, this money is not just printed, it comes from a (presumably progressive) tax, so any affect on the money supply would come from marginal consumption differences at high and low income levels, which do exist empirically, but the effect would be small and predictable (i.e. preventable).

Political hazard
It would be hard politically to ever reduce the basic income, and very politically profitable to increase it. This would quickly result in another runaway social program (we have enough of those already). I think this is very easily solved by tying the basic income amount to hard economic and government indicators (inflation, gdp, debt ratio) in a way that guarantees both the solvency of the state and utility of the income. The rate setting could never be something that was easily changed by politicians.

Pros

Simplification
I am a HUGE proponent of simplified (not smaller) government. Currently we have

medicaid
medicare
CHIP
social security
foodstamps
unemployment benefits
Section 8 housing
TANF
and more...

All of these could be replaced by a dead simple basic income program: cut everyone over 18 with a social security number a check. The opportunities for the government to screw it up are minimal; the bureaucracy would be tiny.

Increased education

Research on the Mincome program found significant increases in education.

Reduced poverty, homelessness
This is of course the big benefit. The negative externalities of poverty are large (cite, cite). Reducing it benefits everyone. Even if you are rich, have no feelings of empathy for the poor, and only want the best for yourself (in short you are an asshole), I still think it is in your best interest, economically and politically, to keep poverty low.

I was prompted to write about this by my growing belief that human labor, as a factor of production, will eventually and inevitably be priced out of most of the economy. Machines have been and will continue to produce more and more of our goods without our input. This is an awesome thing, and it doesn't mean humans won't find other productive work to fill their time, it just means as a proportion of our total output, our contribution will be continually less significant. This means a lot of surplus value, value that could be productively put towards a basic income instead of, say, capitalists' (bulging) pockets.

Now I sound like a Marxist.

How to save Hacker News

2011-12-16T15:28:00.000-08:00

There seems to be increasing agreement that HN is slowly descending into another reddit (no offense reddit, you're great). I'm sure someone has suggested this before, but I think the fix is simple: split upvoting into two distinct actions:

I agree with this comment/post
This comment/post was informative and high-quality

Here is a poorly conceived implementation:

(this comment "informs" me, this comment "conforms" with my beliefs/values)

The ranking (on the front page and for comments, or just for comments) could then be some mix of the two votes with options for sorting by different mixes: "most informative", "most conforming". The popularity of the single binary voting dimension on aggregation sites is no doubt due to simplicity and the maximum mental effort a community member is willing to expend on evaluating any given link/comment. But, I don't think this is too much to ask. Especially for a community like HN. I think this would have a tremendous impact on the quality of comments (and links).

Introducing Scientifiqa, the science-based Q&A site

2011-11-20T17:44:00.000-08:00

I just launched Scientifiqa, yet another general Q&A site (and stackexchange clone). What makes this one different? Every answer must be a citation (and summary) of a peer-reviewed academic article or survey. The hope is that this requirement will ensure high quality discussions and give people an easy and quick way to come up to speed on current scientific understanding in a particular area.

Some questions already posted:

Or ask your own question.

Please share any suggestions or feedback!

A better arXiv

2011-10-03T13:38:00.000-07:00

Imagine if arXiv was a fully functional online community.

Here’s one vision:

Member profiles
The community would be open to anyone (possibly contingent upon approval by existing members.) Profiles would hook into Linkedin, Mendeley, Researchgate, etc to pull in your education, institutions and publications.

Reputation
Every member of the community would have a (private) reputation score based on their “impact” in their field. All actions on the site would be weighted by a member’s reputation, it’s calculation based on:

published papers (traditional impact scores)
education, employment and institutions (verified by community)
actions within the arXiv community (peer reviews, upvoted comments, well-rated submissions)

This would obviously be controversial, and would have to be handled openly and with care, but I think it is necessary in order to keep quality high and to entice well-respected academics to engage in an online forum.

Peer review

Members could write and request (public or private) reviews of submissions. This would include “rating” the submission across various dimensions. Possible dimensions:

methodology
novelty
expected impact

Comments

There would also be an outlet for less formal discussion, with upvoting and threading.

Article discovery

There would be support for sorting and filtering submissions by ratings and reviews. There could be a published “journal” of best articles every month, possibly selected by weighted vote, if people felt the need for a formal publication.

In addition there would be a personalized feed of submissions, based on topic filters and a recommender system.

Open access

Most importantly, ANYONE could read the output of this community. Even the taxpayer/college student who funded it all...

In addition to these community features, there could be added capabilities for submitting papers. This could be simple things like support for attaching code, data or arbitrary media; or a more significant overhaul of a “paper”, turning it into what is essentially a web page, with inline links for references, expandable sections, embedded media, etc. Unfortunately, there is no standardized typesetting solution for the web yet, so some work might be required to make this happen.

If this got built and people adopted it, I think it could deliver a swift, fatal blow to the academic publishing industry -- something it desperately needs. (When I say swift, I mean swift in academic terms)

I built science.io with this end vision in mind. If you are involved with arXiv or are interested in making this or something like it happen, I’d love to chat. Get in touch kvh@science.io