depth first search

Another webcomic worth following. Here’s a taste:

• Writing up my thesis proposal. I feel like a real scientist! #

Here’s yet another post about bad papers. I’ve commented on a similar topic before. At the time I thought it was really important to call out bad scholarship publicly. It seems like tenured professors are in a unique position to do this, but standards of decorum often get in the way.  That’s why including “bad” papers in a course might be potentially useful if done correctly.

In the interim I’ve learned quite a bit more about science than I knew before, and I suspect that identifying papers as “bad” is often a subjective judgement based on personal biases and community norms. Papers can include mistakes, such as a faulty proof, that would render them objectively bad. But consider this, are papers before a paradigm shift bad? Certainly, in the context in which the papers were published and read, they were considered “good”, and yet a retroactive evaluations of these papers (post-shift) would probably evaluate them in the context of a changed understanding of the relevant scientific theory. In that sense, pre-shift papers could be then considered “bad.”

[And so, even in the hardest of the hard sciences, the quality of a paper can shift with time even though the paper itself stays the same.]

[As a personal example, a professor in my program brought up the topic of a paper that he thought was terrible. The paper demonstrated a process by which programs can be jointly compiled so that when run together in some form of multitasking environment the programs would use fewer resources. At the time, this did not seem like an important problem. Yet now we live in the era of the iPhone. Last I heard, this professor is now at Microsoft. I wonder if he took his narrow vision of computing with him. ]

Maybe you don’t buy Kuhn’s ideas on science, but you would still need some kind of objective basis for forming conclusions about “good” and “bad” papers. And you’d have to recognize at least the possibility that subjective norms could seep into whatever standard you set.

It’s not that Google is worse on net neutrality than other companies with a stake in the mobile phone game. It’s that they made such a show of being better, of being on the side of the public interest — before they had a big stake in the game.

Echoing my thoughts from the other day.

In a previous post I was a bit inaccurate when trying to make a point about the kinds of complexity issues that arise when dealing with practical problems in AI. I stated that human vision accomplished object recognition using constant depth circuits. Memory plays a role in object recognition, so characterizing the human process of object recognition as constant depth may be wrong. In any event, the function that adults apply in recognizing objects is really quite remarkable both in terms of speed and accuracy. Of course you probably wouldn’t realize this unless you spent any time trying to get computers to do similar feats.

The complexity issue that is normally studied in AI is not the complexity of the object recognition function itself (in the brain or in computers), but the difficulty finding the appropriate function. Treated this way, there are a number of models of complexity (e.g. probably approximately correct) that apply to the problem of finding functions that do things like identify objects.

My understanding is that the best computer vision object detectors (e.g. histograms of oriented gradients) can be learned in polynomial time. That said, there are other problems in vision that are known to be NP-complete, so even in this rather applied problem area, we can’t really escape the fundamental problems and concerns of complexity theory.

One interesting comparison worth making in the context of “net neutrality” is between the positions of Apple and Google. They are now competing in the same mobile space. Among Apple observers, the coverage of Google has been fairly negative recently, but I don’t think this has to do with some kind of fanboi reaction against a new competitor to Apple.

Basically, I think it comes down to tolerance for bullshit.

The problem isn’t that Google and Apple really differ fundamentally in either company’s approach to openness. It’s just that one company has a coherent position that doesn’t pervert language, and the other doesn’t. Apple’s approach is simple, openness depends on the choice of API. If you use Cocoa, you are working within the closed ecosystem of Apple’s app store. If you choose HTML5+Javascript+CSS you are working in the open system. Obviously Apple has a lot of latitude to balance the pros and cons of each API choice to fit whatever corporate strategy they want. In particular, I think mobile Safari innovation will tail off as Apple tries to force more applications into the App Store. But, strategy aside, the distinction makes a certain amount of sense, and at least Apple is treating everyone like adults.

Google was positioning themselves as the “open alternative” to Apple in the mobile space. (Which ironically means running things like Flash.) The only problem is that the handset makers and mobile carriers do not want an open system and so there is no open system. This leaves Google PR in an odd position, one they’ve tried to work their way out of by attempting to broaden the definition of “open.” I can see why this approach drives some people bonkers, even if the end result is two companies with basically similar positions on the issue.

In fact, the nuts and bolts of A.I. research can often be more usefully interpreted without the concept of A.I. at all. For example, I.B.M. scientists recently unveiled a “question answering” machine that is designed to play the TV quiz show “Jeopardy.” Suppose I.B.M. had dispensed with the theatrics, declared it had done Google one better and come up with a new phrase-based search engine. This framing of exactly the same technology would have gained I.B.M.’s team as much (deserved) recognition as the claim of an artificial intelligence, but would also have educated the public about how such a technology might actually be used most effectively.

More on this later…

… or how important is that problem really?

There’s an interesting attempt to prove floating around. The best set of initial reactions seems to be here. Beyond the absolute basics, I can’t evaluate what’s going on with the proof, and anyway it seems like most of AI is predicated on the assumption that so we really only have to worry about our basic assumptions regarding complexity if a serious paper comes along proving the opposite.

[Aside: I'm being a bit glib about this important problem. For one thing, their are some interesting implications for various lower bounds on the class NP that might be of immediate practical concern in AI. But on the other hand there's also something of a category distinction between worrying about problem difficulty in strictly computational terms and fighting with the finicky nature of a robot arm that won't grasp a damn block. Another way to think of the distinction is that object recognition in humans is very nearly instantaneous and probably computed using some kind of constant depth circuit. But we're not even close to finding even a much slower algorithm that can do the same thing at nearly the level of an average adult.]

There are a couple of interesting issues with exactly how this paper came to be so public. First, it seems like the author sent it to a small number of people looking for some feedback. With a result of this kind, you’d probably want to be cautious with your handling of the draft before even uploading a copy to arXiv. That caution didn’t really pan out in this era of social networking. Now the researcher is stuck defending a non-publication that he just wanted a second opinion on as if it were a final manuscript. I bet that’s sort of awkward. Then again, it already looks like this probably incorrect proof brings some new ideas to the table, so reputation-wise this may be a net positive for the researcher involved.

Also, it seems like there was some hesitation on the part of complexity theorists to even begin to evaluate the proof. This is not really odd considering the number of “proofs” that arise for all kinds of famous open problems. That said, one aspect of the hesitance seems to be that nobody really works on proving anymore. The demands of research (and research funding) push people in research positions at research universities away from anything that can’t yield some form of paper every six months. The general attitude is that proposals that focus on proving do not get funded and so nobody works on the problem (or pays students to do so) with anything like their full attention. Supposing this particular paper is the real deal, it serves as something of an indictment of the university establishment that eschews working on big picture problems and instead focuses on what can be published in the next six page double column conference paper. In any event, the fact a dedicated researcher with the necessary background can put forward a compelling effort in his spare time must say something about the way full time complexity theorists allocate their resources.

Just saying.

UPDATE: Actually, this isn’t even really an indictment. I’m not even sure the fact that so much focus is placed on rapid fire results in conferences is a bad thing. I guess the point I’m trying to make is that when evaluated sociologically, is not actually an important problem at all. That is to say it is far less important in practical terms than the latest and greatest ad auction theory proposal that actually does get funded and gets the care and attention of many seasoned researchers.

Network neutrality is back in the news. Google and Verizon have put together some kind of “policy framework.” I don’t really have any problem with the framework. In fact, I think it captures the current status quo and later versions of these kinds of frameworks will look much worse for the average consumer.

[Aside: I recall how the DMCA looked like the devils work when it was being drafted, but in retrospect that law looks like a smart compromise compared to what certain content producers are clamoring for now. Better to pass some kind of network neutrality compromise soon because in ten years deals that pass muster with special interests will look much worse for you and I. It's sort of sad that the key to dealing with special interests is for forward thinking politicians and policy experts to get legislation out the door before special interests can even figure out what they want.]

More generally, I feel like we are all just sort of tiredly waiting for the inevitable. The established rhythms of 21st century capitalism may objectively advance the state of the art, but I think we all know how oligopolies leave behind frustrated consumers as they pursue various kinds of short sighted strategies in the absence of any real competition amid conditions of regulatory capture.

We are transitioning from a virtuous cycle where engineering innovation drives profits to depressing spiral where profits are derived from business school tricks like market segmentation and cost cutting. It was fun while it lasted.

Jonathan Mugan (occasional commenter on this blog, newly minted doctor, all around great guy) won for best educational video at this years AAAI video competition. Enjoy!