Identifying The Blind Spots

Data Mining + Information Extraction = Knowledge Extraction

Data mining and information extraction have traditionally been separate tasks each with their own communities, conferences, data sets, algorithms, and so forth. In the last few years especially, we've started to see a lot of consolidation and bridges being built between the two communities with people realizing that the two tasks really need to be part of one continous workflow. Most of the interesting data out there (especially text) lives across a diverse, often heterogeneous set of  information delivery sources. While people in information extraction are typically interested in extracting structured records from either unstructured or semi-structured data, e.g. names and addresses from Web pages, which they can use to populate say relational databases, people in data mining generally assume they already have some cleaned up data with attribute/value pairs and want to try and explore the data to find interesting patterns. And in some cases this modularity of roles works quite well. But because of a huge variety of factors, including the emergence of immensely rich and freely available datasets on the Web as well as new sophisticated learning algorithms which people want to use, people have begun to realize the traditional model of of separation and modularity between tasks has largely failed them.

One of the main problems is reference linking. How do I know that the wording "Dr. Johnson" on press release X refers to the same entity as the wording "D. Johnson" on web page Y? If you run your information extraction algorithms on each data source independently and then try and merge them together naively to hand off to some data mining algorithm, you get the whole garbage in/garbage out problem. This is why, for example, the Citeseer computer science research index says that some D. Johnson, is the most highly cited author, when in fact whichever one they're referring to is most likely not.  And the same reason why ZoomInfo says there are 6 different Padhraic Smyths when, in fact, there is only one. Trying to automatically figure out how many entitities there really are and which entity a reference is referring to is still a hard research problem and one that has become a very hot one in just the last few years. I don't have the state-of-the-art accuracies, e.g. F-1 scores, in front of me but I know they're way below human performance. The hardness of this problem is a reason why the vast majority of newbie commercial products/services out there, which are based on fusing information from disparate information sources on the Web, seem to add little value without wasting a huge amount of user time.

Another important reason people are tying the two tasks more closely together is that, in some cases, data mining and information extraction algorithms can help each other during the learning/disovery process. For example, if I want to automatically  identify the communities which individuals in a social network belong to from semi-structured text, say emails, the uncertainty that I may have about who the sender is can help inform my community finding algorithm and also the community memberships I'm thinking about assigning to a person can help decrease my uncertainty that two different senders are in fact the same sender.

Finally, a third reason these two tasks are coming together is that in the last decade there has been a whole new mathematical foundation laid which unifies many of the problems in each task which were once thought to be completely distinct. It's the theory of graphical models. Hidden Markov models, Kalman filters, maximum entropy models, these can all be unified thanks primarily to some pioneering work done in the '80s by Judea Pearl. Unfortunately, industry is slow to catch up on this research and the vast majority of information extraction engines being deployed are still using rule-based engines which are labor-intensive to build and often very brittle when it comes to porting them across domains. As for data mining, most people are building off of relational database technologies which assume the data is cleaned up and can be put into structured records. For cases where that isn't possible, you often have non-standardized data mining implementations which are built in-house.

A great vision paper which elaborates on most of these ideas can be found here.

Finding Communities in Complex Networks

I gave a talk on Friday at the SIAM 2005 Data Mining conference .  The paper can be found here. The abstract summarizes the work:

Clustering nodes in a graph is a useful general technique in data mining of large network data sets. In this context, Newman and Girvan [9] recently proposed an objective function for graph clustering called the Q function which allows automatic selection of the number of clusters. Empirically, higher values of the Q function have been shown to correlate well with good graph clusterings. In this paper we show how optimizing the Q function can be reformulated as a spectral relaxation problem and propose two new spectral clustering algorithms that seek to maximize Q. Experimental results indicate that the new algorithms are efficient and effective at finding both good clusterings and the appropriate number of clusters across a variety of real-world graph data sets. In addition, the spectral algorithms are much faster for large sparse graphs, scaling roughly linearly with the number of nodes n in the graph, compared to O(n^2) for previous clustering algorithms using the Q function.

As I said in the talk, there are already a huge number of clustering algorithms out there in the literature. Our goal was to produce algorithms that satisfy all of the following properties:

1. No assumption of a fixed # of clusters ahead of time, i.e. the number of communities should be found automatically.
2. Run in sub-quadratic time, preferably close to linear in the number of nodes, i.e. can scale to large graphs
3. No limiting assumptions which make it less than ideal for complex networks that exhibit community structure (e.g. social networks)
4. Produces high quality clusters, preferably a global optimum of appropriate cost function

Our algorithms are at least another step in this direction but more work needs to be done before we satisfy all of these properties especially to the extent that they are scalable to truly massive networks and which consistently find very high quality clusters without getting stuck in local minima. Actually it's interesting how fast the field is evolving. After I submitted the paper, two new algorithms came out which are competitive with our own, one which seems to be faster, at least for certain kinds of networks, but which can easily get stuck in local minima, and the second being much slower and which doesn't seem to perform as well on complex networks.

Event Calendaring & Feedback Networks

Great post  on event calendaring over at Anarchogeek. What I found equally interesting as the review/critique of Upcoming.org, EVDB, and Trumba and ideas for what event calendaring done right should be was the fact that 2 of the 3 comments were by the project creators whose work was being evaluated (at the time of this writing).  We take the power of TrackBack for granted sometimes but it really is amazing that you can create social feedback loops so easily and effortlessly and then expose the loops for others to see through Comments, something you can't really do with email. No doubt that feature is hugely responsible for blogging's success. Hyperlinks, by themselves, are good at helping people discover new information when they are already in the right neighborhood of the network, as well as giving cues to search engines, but it's really Trackback that is the main engine in helping to stimulate dialogue between bloggers by creating links between them (and not just their blogs).  As this percolates up to the macro-level, communities are more easily formed. Of course, it's well known in complex systems, that feedback loops are crucial for self-organizing systems to evolve but it's nice to see this directly manifested in software. Perhaps one suggestion Anarchogeek (real name?) left out, when talking about things event calendaring software producers needs to get right before their products are widely adopted, is that they need to make it easier to create feedback loops. Not only between people but also between events and between people and events. I won't say any more on this topic as they're already getting enough free advice.

Shake-up at Yahoo! Research And Markov Defection Processes

I just got this email from my ex-uber boss at Yahoo! Research:

As of April 15, 2005, I no longer work at Yahoo!.  Starting June 27th, I
will be working at MSN.
 
See http://slashdot.org/article.pl?sid=05/04/15/1118245 for details.
 
Should you need to contact me:
...
Thanks,
Gary Flake
 
(Soon to be Distinguished Engineer of MSN, and Darth Vader of the Internets)

I probably shouldn't say anything about my suspicions of why he was motivated to leave other than I'm sure Microsoft's extremely generous offer wasn't the entire reason. Interestingly, Usama Fayyad, who has a great reputation in the data mining community and who's only been working there for a half year or so, is going to take his place as head of R&D.

I've heard of many high-profile defections where people have left Microsoft to go to Google. I can't remember hearing about any high-profile defections from Google to Yahoo! nor the other way around.  Does this mean we're beginning to see a Markov process where the most probable sequence of defections among the search companies is that of people going from Yahoo! to Microsof t and then to Google? Given my few data points to go by, probably not, but it's fun to think about.

The Peer Review Turing Test

Have you ever thought the peer review process at a computer science conference was of such low quality that you wanted to try and see if you could get a bogus paper in? A couple of MIT students have recently made doing this a whole lot easier. Apparently they have even got a randomly generated paper accepted into an actual conference and are planning on giving a randomly generated talk. Hilarious! Actually as it turns out the chair of the conference who accepted the paper recently sent me an email that read:

Dear Dr. Scott White:

On behalf of the WMSCI 2005 Organizing Committee, I would like to invite you to participate in the 9th World Multi-Conference on Systemics, Cybernetics and Informatics (http://www.iiisci.org/sci2005), which will take place in Orlando, Florida, USA, from July 10-13, 2005.

...

Also, we would like to invite you to organize an invited session related to a topic of your research interest. If you are interested in organizing an invited session, please, fill the respective form provided in the conference web page, and we will send you a password, so you can include and modify papers in your invited session.

Given the akward and anachronistic sounding conference title and the fact that I didn't recognize anyone on the program committee, I had to pass. 

Actually I would love to see someone take this a step further and set up a server which crawls Computer Science conferences on the Web and automatically submits a few different papers to each conference from randomly generated authors. I seriously think this would be a great way to keep peer reviewers on their toes. Can you imagine the embarassment of some professor, postdoc, or grad student who didn't have the time to peer review a paper and so quickly skimmed over it thinking " it looks presentable, I'll just mark it 'Neutral' so others can decide."  That person would not only never be asked to peer review a paper again but if word got out it could do some serious reputational damage.  Of course, we wouldn't want too many bogus papers to be submitted causing people to throw their arms up in despair. 

Update: This article has since come out from Reuters describing the hoax mentioned above in more detail as well as the infamous WMSCI conference.

How To Hedge Against Soaring Gas Prices?

I just paid close to $60 to fill up a tank of gas, the most ever. Rather than go out and buy a hybrid, I'm wondering what the best derivatives trading strategy might be to help hedge against the rising cost of gas prices. I'm fairly confident that prices are not going to stay where they are. Newspaper articles like this one seem to be arguing that prices will continue to go up in the long term although perhaps come down a bit in the short term. What does the main reason seem to be for the long term increase? India and China and other fast growing countries, where many  millions of people are finally able to afford cars and thus needing to tap into the world's oil supply, combined with the increasingly limited supply of oil. If everyone believes it's not a matter of if but when prices surge even higher then buying calls in the futures market will be expensive. Of course, if one took  a contrarian position one could make a ton of money if gas prices go down, as someone like Nassim Taleb  is probably doing, but the problem is I don't think they will. Maybe there is some hedge I could put on to offset the expensive price of calls on oil. Possibly something like an iron condor spread, which is a neutral trading strategy which allow me to make money if the market moves either up or down, but I would want something which is more biased towards the upside. I wish there was some visual tool I could use to literally draw the exact risk profile I want to have and then it would tell me what trades to put on. Hmm...

Transforming The Web Into A Commercial-Free Zone

John Udell  seems to be trying to subvert corporate power with his latest screencast (now a few days old). He shows how one can go to an Amazon book page and customize the page on the fly so that one can see whether said book is available at the local library. Presumably, this is very useful since now you don't need to actually buy the book on Amazon since you know it's available for free just a few miles down the road. This is all done by using a Mozilla web browser extension called GreaseMonkey and writing some Javascript code to  perform queries on the local library's search page and then display the result on Amazon's page.  While other examples I've seen using GreaseMonkey to dynamically customize a page were interesting, this is downright devious. If you think of any business on the web that has content, that content is there for a reason:  to get you to open your wallet. While many people already go to corporate web sites not to buy something but to take advantage of all the free content, myself included, this is the first time I've seen someone demonstrate how you can not only enjoy the free content but you can then use that content as an indexing platform to find where you can get the product they are selling for free somewhere else. GreaseMonkey can do a lot more than that (as I mention below), but that idea in and of itself is extremely powerful. Of course, it is not universally applicable since there are many companies which sell stuff you can't find for free elsewhere. 

And there are other ways you can use GreaseMonkey to subvert corporate control over your viewing experience. You can use GreaseMonkey to strip away all of the ads and even any sign that something is being sold. With a little bit of intelligence, you can turn the entire web into a commercial-free zone.  I'm sure Richard Stallman would love that. Think not only a world with no ads or shopping carts but a world where every instance of the word 'customer' is replaced by the word 'fellow human being' and every instance of the word 'buy' is replaced by the word 'enjoy.' Just run the text through a simple filter that reflects the way you want the world to be.  And all it takes is a little Javascript.

Information Overload

I know I am not alone in feeling like I'm drowning in information. And I'm not talking about spam. I'm talking about information after it's passed through all my filters, stuff I'm eager to know about.  There is just too much of it. Notwithstanding the normal channels through which I've grown accustomed to such as email, friends to stay in touch with, meetings to attend to, research papers that I need to stay on top of, books I want to read, Tivo recordings I want to watch, and so forth. Now that RSS feeds have become ubiquitous, I could have literally hundreds of posts each day from highly selective sources coming through my aggregator, the majority of which, much to my dismay, are actually worth reading. To make matters worse, people are now finding ways to take non-textual informational sources such as audio files (e.g. podcasting) and even video files and tying that to RSS. In the near foreseeable future, it will be possible to tie together something like RSS and BitTorrent and have Hollywood blockbusters, independent films, and quarterly conference calls all streamed to me right when they are released (notwithstanding the legal implications).  It's so bad that when I walk in the bookstore, I sometimes have the urge to stop by the self-help section to skim through books on time management to pick up any bones of advice one of these authors might throw my way. And it's clear it's not just me. A large fraction of the people I interact with are walking around with their eyes glazed, seemingly on auto-pilot, speaking a mile a minute about this blog they read, this documentary they Tivo'd, this video they saw on the Net, this new startup company that's hot. And every year it just seems to get worse and worse.

All of this information seems to be having strange psychological effects in the way we perceive time.  Generally speaking, most people tend to experience time relative to the number of events that occurr in their life, larger events getting more weight.  So what happens when we start to experience more, when more opportunities for interaction become available and more and more events interrupt our nourmal course of awareness , thereby disrupting our ability to settle into long moments of concentration, sometimes called flow? Well, I think what happens is that the event horizon beyond which we perceive as the distant past gets closer and closer to the present. The present becomes more muddled and fuzzy. And the future begins to feel more like the present.  Five years ago, for example, the distant past might have seemed like anything that happened more than three months ago. This year, it could be that, on average, the distant past feels like anything more than two weeks ago. Who knows? Maybe ten years from now, we won't even remember what we had for breakfast. Actually, I'm almost starting to feel like that now. It's a bit scary because while all of these new sources for information are capable of making us more informed and educated about what is going on in the world, the overabundance of high signal/low noise information channels is having a deep impact on our sense of time. People no longer have time to read books. Instead they read magazines.  One can only already see signs of the trend spiraling downards with people replacing magazines for summaries of magazine articles, then summaries for summaries of summaries, leading ultimately to the famous image in the Matrix of green rivers of information literally flowing down the screen as fast as the eye can track them. Of course, I hope things don't turn out that way. I think, as a technologist, it's my duty and those of my peers to think carefully about the consequences of this new technological ecosystem we are building and how we can build better interfaces not only for filtering and summarizing information, but also to prioritize information and ideally tell us when enough is enough and it's time to go to bed.

Bagging the Wisdom of Quantum Computers

A fascinating idea about how to use multiple unreliable 1st generation quantum computers to produce a full-scale quantum computer appears in this issue of Nature.  The NIST press release nicely sums up its significance:

Use of Knill's architecture could lead to reliable computing even if individual logic operations made errors as often as 3 percent of the time—performance levels already achieved in NIST laboratories with qubits based on ions (charged atoms). The proposed architecture could tolerate several hundred times more errors than scientists had generally thought acceptable.

Unfortunately at this stage it's just that: a concept: No experimental evidence or theoretical proof has been given to demonstrate this can actually work in practice. But the thought of using a collective of independent solutions to produce a more exact estimate of the unknown solution would certainly bring a surge of delight to any statistician.   In fact, I would guess this paper could very well get a whole army of statistically-trained scientists working in the area of statistical estimation and related areas excited enough to take the core ideas (e.g. bagging) from some of their previously published papers and port them over to quantum computing.