Here’s the slides from a 2-part lecture I’m giving on ensemble learning at Indiana University. It includes a discussion of the Netflix Prize competition, and the use of ensemble techniques in that competition.
I recently came across a small site running on Mediawiki called MemoryArchive.org. The concept is that each article is a memory written, unlike Wikipedia, by a single author. Subjective content allowed.
There seems to be a legit place for a site with this concept to complement Wikipedia. Wikipedia is derivative knowledge, it is intended that the content be cited, meaning it already had to have been published somewhere. Many valuable (and not so valuable) facts don’t fit that bill. Also, when sources disagree but are merged into a single Wikipedia article, history according to Wikipedia has a rather non-deterministic feel to it.
That said, MemoryArchive.org has a long way to go in terms of concept, technology, and adoption. If anyone involved with MemoryArchive comes across this review…well, I have some ideas:
If you didn’t see our original Wikipedia Activity Visualization, check it out here (there’s a detailed explanation, as well). Also, there is a Google maps style zoomable version here.
This new version uses the same layout and images (well, slightly improved) as the original, but this time we tried to highlight activity in regions of Wikipedia that are predominately math or science or technology.
So we developed a program to classify Wikipedia articles as being one of these three categories (or none), based on the categories the article was assigned to and their positions in the Wikipedia category link network.
We were not surprised to see a tight cluster of math pages, in a region, I would add, which has little ‘hot’ activity. In fact, the only article in that region with lots of activity is the article “Earth”. It was also not surprising that technology articles are fairly spread out among the topics.
What’s striking is the science-related band (green-blue) that runs diagonal through the middle of the topic map. I won’t share my interpretation, but rather let those interested come up with there own. Hope you enjoy, please leave comments!
(CLICK IMAGE TO ENLARGE)
(CLICK IMAGE TO ENLARGE)
Above: The most actively edited science-related articles.
Left: Not much science here…a good indication the algorithms are working pretty well!
I was asked to give a short (1 hr) tutorial on the Scheme language this week for students in the graduate and undergraduate AI courses at Indiana. Thought I would post the slides in case anyone wants to adapt it for their own purposes…
PDF version
PPT (Office 2007) version
ICCBR07 (International Conference on Case Based Reasoning) is held on alternating years with the ECCBR conference. The venue was Belfast, a city with nice blue collar charm to it. Seemed sort of a European version of my hometown of Green Bay. Stayed in a Queens University dorm room, where I was constantly reminded I am too old to be staying in the dorms. Should have paid out for a stay for the Europa Hotel where the conference was held…classy place.
Day 1
Perceptions of CBR by David Aha. Argued that CBR may become irrelevant if there are not more theoretical results published. Showed stats that more recent CBR publications are system-oriented to back up his argument (but may be true of AI in general). Suggested that CBR researchers have theory envy towards machine learning practitioners.
Note: A thought occurring to me is that CBR is more a set of design patterns, ones which are fairly accessible by the general public given the diverse interests of the delegates present.
Credible Case Based Reasoning by Eyke Hullermeier. A formal treatment of the retrieval component of CBR (nicely timed to correspond to Aha’s argument).
Day 2
Databases and CBR by Larry Kerschberg. History of database research. Currently concerned with meta data, reasoning, and data providence, and moving beyond ’just a schema’ (what can happen to data item). Suggested using CBR for web resource discovery (Wikipedia, Amazon, Facebook as parts of casebase) as major direction for CBR. Invitation to submit CBR work to special issue of Journal of Intelligent Information Systems on integrating artificial intelligence and database technologies. Scaling, cross domain issues also brought up. Ran out of time to cover his paper ”Knowledge Sifter”. He was quite interested in CaseML as well.
Empolis by Ralph Traphoner. An Eclipse based tool for CBR systems. Supports a plug-in architecture, a fact alone which makes the tool promising in my mind. Not sure whether it is commercial or what license it carries.
Industry Panel by GE, GM, and Knexus. Discussion of what industry wants. Examples of money making applications was a theme, not surprisingly. Hybrid systems and Internet data were mentioned as well. One researcher suggested that releasing data was not worth his time. Another mentioned he has never heard of a case based recommender in the field. One audience member raised a concern that many outside of the CBR community see CBR as just KNN and a lot of talk. Something that strikes me about this community is that “industry” is non-tech.
Day 3
My talk at the workshop on personalizing similarity measures.
jColibri by Juan Recio-Garcia. CBR system using Lucene.
Day 4
Note: Google Group on context in CBR is now up.
Note: Suggestion that the difference for most people between IR and TCBR is that TCBR systems have some inference step.
CBR in RoboCup Soccer by Hans-Dieter Burkhard. Funny videos! I’ll try to post these.
Note: David Leake’s paper on data providence won best paper. Congrats David!
Additional Comments
Note: A “cooking” contest is being help at next year’s ECCBR where recipes are cases. I like the idea of a contest, and the crossover to the real world (taste of cooking matters), however I wonder if the cooking domain allows for sufficient bragging rights.
Note: Major topics in CBR continue to be similarity measures, context awareness, text processing, and health care support systems. The new topic for next year is to involve web 2.0 technologies.
This is a talk series being given at Google by David Mease based on a Master’s level stats course he is teaching this summer at Stanford. Its easy listening if you already have some data mining or stats background.
The introduction (part 1) is particularly well done, as is the portion on association rule mining (parts 7 and 8). This is the first half of the course which has already occurred…I’ll add links as new sessions are added to Google video.
Part 1: Introduction. Discussion of locations of potentially useful data (grocery checkout, apartment door card, elevator card, laptop login, traffic sensors, cell phone, google badge, etc). Note mild obsession with consent. Overview of predicting future vs describing patterns, and other broad areas of data mining. Intro to R.
Part 2: Data. Reading datasets into excel and R. Observational (data mining) vs Experimental. Qualitative vs quantitative. Nominal vs ordinal. And so on…
Part 3: Data cont. More Excel and R. Sampling.
Part 4: Plots. Histograms, ECDF.
Part 5: More R plots. Overlaying multiple plots. Statistical significance. Labels in plots.
Part 6: More R plots. Box plots. Color in plots. Installing packages. ACCENT principles and Tufte.
Part 7: Association Rules. Measures of location. Measures of spread. Measures of association. Frequent itemsets. Similar to conditional probabilities.
Part 8: More association rule mining. Support and confidence calculations. Personalization using rules. Beyond support and confidence.Part 9: Review
Part 10: Classification. Overview. A negative view of decision trees. DTs in R. Algos for generating DTs.
Part 11: More DTs. Gini index. Entropy. Pruning. Precision, recall, f-measure, and ROC curve.
Part 12: Nearest Neighbor. KNN. Support Vector Machines. Adding ‘slack’ variables, using basis functions to make the space linearly separable. Some comments on Stats vs ML. Intro to ensemble (uncorrelated) classifiers.
Part 13: Last class. Random Forests. AdaBoost. Some discussion of limits of classifiers (nondeterministic observational datasets). Clustering. K-Means.
Definition (from DARPA): The ability of a system to recognize and apply knowledge and skills learned in previous tasks to novel tasks
Current approaches involve either the building of a shared model of a domain or multiple domains, in the form of a case base, hierarchy, or relational schema, that couple the classifiers together, or the creation of mapping between distinct representations. Bayesian and neural approaches dominate the research thus far.
(from Droy 2007-IJCAI07) In spam filtering, a typical data set consists of thousands of labeled emails belonging to a collection of users. In this sense, we have multiple data sets–one for each user. Should we combine the data set and ignore the prior knowledge that different users labeled each email? If we combine the data from a group of users who roughly agree on the definition of spam we will have increased the available training data from which to make predictions. However, if the preferences within a population of users are heterogeneous, then we should expect that simply collapsing the data into an undifferentiated collection will make our predictions worse.
Resources
Caruana dissertation (1997). Part of ALVINN
Berkeley 2005 course. Reading list. Bayesian approaches are focused in on.
Oregon State 2005 course. Probabilistic Relational Models.
DARPA Proposal. Now in its third and final year.
CBR Approach. Strategy game playing.
Wikipedia Entry
Workshops
NIPS 1995
Inductive Transfer : 10 Years Later (2005)
A new visualization Bruce Herr and I recently completed is being featured in this week’s New Scientist Magazine (the article is free online, minus the viz). They did a good job jazzing up the language used to describe the viz–’power struggle’, ‘bubbling mass’, ‘blitzed articles’–but they also dumbed down the technical accomplishments. I guess not everyone gets as excited about algorithms as I do.
Before I talk anymore about the viz, though, let me mention its appearing at the NetSci 2007 Conference this week, and hopefully a varient will appear at Wikimania later this summer as well. The viz is a huge 5 feet by 5 feet when printed, and I only include a low res, smaller version here. At some point high quality art prints of it will appear at SciMaps for sale to fund further visualization research.
Now for the good stuff. Much like my visualization of the netflix prize competition data, we began this piece by representing the data as a network. In this case the nodes in the network are wikipedia articles and the edges are the links between articles. We then (with some help from our friends at Sandia) used an algorithm to lay out all 650,000 nodes (wikipedia articles) that had at least one link in such a way that similar articles are near one another. These are the yellow dots, which when viewed at low res give a yellow tint to the whole picture.
The sizes of the nodes (circles, dots, whatever you want to call them), are based on a model of revision activity. So large circles indicate that an article might be controversial, or the subject of lots of vandalism, or just a topic whose content frequently changes. We labeled only the largest nodes, to keep it readable. There is an interactive version of this in the works based on the google maps platform which will change the labels and pictures used as the user ‘zooms’ in or out. Stay tuned for that.
The image used for each tile was selected automatically, simply by using the first image in the most linked to article among all the articles in that tile. We were pleasantly surprised by the quality of the images that appeared.
Our hope for this visualization approach, which we continue to improve on, is that it could be updated in real time to give a macro sense of what is happening in Wikipedia. I personally hope that some variation of it will end up in high schools as a teaching tool and for generating discussions.
Top 20 Most Hotly Revised Articles
Here’s a recent visualization I did of the dataset used in the Netflix Prize Competition. The dataset is 17,700 movies and 31 gigs of user ratings. This viz shows similar movies close to one another, with the similarities determined by a formula based on ratings.
I found most interesting a cluster of movies (in blue) that I’d say are generally acclaimed. The cluster contains movies of across all genres, such as Schindler’s List, BraveHeart, and Super Size Me. Beyond that, there’s a bunch of clusters which are mostly defined by a genre such as music, sports, documentary, Imax, children’s films, or bonus material. The big blob in the center is mostly what I’d call junk movies.
I’ve labeled some movies just to give some sense of what the clusters contain. There’s an interactive version of the viz as well, so you can explore the movies for yourself…
The visualization activated below (click the button) shows all 17,700 movies that are part of the Netflix Prize Competition. The movies are laid out such that simlar movies are close to one another. Similarity between two movies is computed based on whether users who like one like the other, or (and, really) those who dislike one dislike the other. Alternatively, take a look at a colorful, static version.
Mouse over to get the movie titles…
[swf movie="http://abeautifulwww.com/wp-content/uploads/2007/04/vizview.swf" /]
http://abeautifulwww.com/wp-content/uploads/2007/04/vizview.swf
Just read an article about Google buying a small company called GapMinder which does data visualization. I checked out the talk on the GapMinder homepage, and would recommend watching the first 10 minutes of it. The visualization tool that is used throughout the talk is something special…easy to see Google’s interest.
Setting up WordPress on a GoDaddy hosting account is really not difficult (this blog is an example that it can be done!). Below are my notes on the process. If you glance at these steps, and don’t want to mess around with this, consider using one of the following hosting services which come with WordPress pre-installed (fairly rare): An Hosting, Lunarpages, BlueHost, Yahoo
Steps for installing WordPress on a GoDaddy Hosting Account
1. Get an account. If you haven’t already, purchase a hosting account. I chose the Deluxe plan, which really isn’t very expensive. You’ll be emailed directions after you purchase the account. The email will say it takes 24-48 hrs to activate, but it actually only takes 20 minutes or so.
2. Login to the “my account”. The login is on the GoDaddy homepage. On the my account screen, click “Hosting Account List”. Then click “open” under control panel. You should be at the “Hosting Manager” seen below.
3. Create a MySql Database. WordPress stores its data on MySql.
4. Download WordPress. Unzip the files.
5. Configure the file wp-config.php. Change the following lines using your information.
define(‘DB_NAME’, ‘wordpress’);
define(‘DB_USER’, ‘username’);
define(‘DB_PASSWORD’, ‘password’);
define(‘DB_HOST’, ‘localhost’);
6. Upload the WordPress directory to your GoDaddy account. You’ll need an ftp client to upload files to your account (I use Smart Ftp) and you’ll need the ftp address for your site. Your address is ftp.yourdomain.com. Put the files in you top level directory, that way when you go to www.yourdomain.com it will load WordPress.
7. Test WordPress. There are detailed directions for configuring WordPress here.
Around the Web
Flash remoting is a big improvement over forms/cgi for communication between flash and server. There’s a great little project called amfphp for using php with flash remoting. There’s a whole lot less great (but appreciated!) version called amf::perl for perl and python. There is little documentation, so I thought I’d post an example.
Here’s my remoting notes dealing with amf::perl. For context, I was working on a movie recommendation system.
Steps:
(1) On the Server side, in the cgi-bin, create a perl file, and call it, say “recommendation.pl”. Your version of this file will look the same, except replace “/recommendation” with an appropriate subdirectory where you will put the code in step 2.
#!perl -w use strict; use AMF::Perl; my $gateway = AMF::Perl->new; $gateway->setBaseClassPath("./recommendation/"); $gateway->service();
(2) In a subdirectory, in this case “/recommendation”, create a perl module, in this case called “rec.pm”. This module contains the “methodTable” which will be accessed by the flash code. The example below has both get and set calls.
#!perl -w use AMF::Perl; use lib 'Filesystem\\Active Projects\\'; ## directory where my server side code is use SimMan::TitleLookup; ## my own server side perl modulesuse SimMan::Recommendation; package rec;
## must have this constructorsub new { my ($proto)=@_; my $self={}; bless $self, $proto; return $self; } sub methodTable { return { "getFeatureWeights" => { "description" => "Returns the current feature weights", "access" => "remote", }, "setFeatureWeights" => { "description" => "Sets the current feature weights", "access" => "remote", },
"disambiguateQuery" => { "description" => "Returns possible titles and their ids", "access" => "remote", }, }; } sub getFeatureWeights { my ($self) = @_; my $hash = SimMan::Readers::readFeatureWeights(); my @array; push @array, $hash; return \@array; } sub setFeatureWeights { my ($self, $featureWeights) = @_; SimMan::Readers::setFeatureWeights($featureWeights);} sub disambiguateQuery { my ($self, $usertext) = @_; return $titles = SimMan::TitleLookup::getCandidateTitles($usertext); } 1;
(3) On the client side, first include the necessary files and give the location of the perl files we just created.
Then you can directly call the methods listed in the methodTable. Notice that the results sent back by the perl module will be returned to a function called “method_result”, where method is the name of the method.
import mx.remoting.NetServices; NetDebug.initialize(); NetServices.setDefaultGatewayUrl("http://localhost/cgi-bin/recommendation.pl"); var connection = NetServices.createGatewayConnection(); var recommender = connection.getService("rec", this); function disambiguateQuery_Result(result){ if (result.length == 0){ Results.htmlText = "<b>No movies found</b>"; } else{ Results.htmlText = "<b>Are you looking for...</b><br><br>"; for (i=0; i< result.length; i++) { Results.htmlText += "result[i].id + " " + result[i].title + "<br>"; } } } searchText.enter = function(){ recommender.disambiguateQuery(searchText.text, 10); };
Hope this helps someone!
In my daily work I tend to manipulate fairly large datasets, such as Wikipedia, U.S. Patents, Netflix Ratings, and Imdb. Here’s a few tricks I’ve come across so that you don’t lose time waiting for your programs to finish.
Over the past year and a half I’ve been hooked on the language Processing. I’ve even contributed a early version library for visualizing social network data.
For those unfamiliar with Processing, it’s a variant of Java. Its distinguished by its emphasis on interactive media. The fundamental unit in Processing is a sketch, which is entirely and continuously redrawn at some given rate. Sketches may be compiled into either standalone apps or Java applets.
Many creative types work with Processing–here’s some cool examples: The Dumpster, Thinking Machines 4 (pictured left), and Relations Environment. More can be seen on exhibition. Its not hard to see why I was excited by the language.
I’m still excited by the Processing community and all the cool apps and exhibits they are turning out. However, today I am much less excited by the technology.
Recently I’ve been looking into Flash (e.g., the chart in Google Finance is Flash) and have begun to believe that Flash is a better alternative. It is great at content delivery, has convenient UI components and support, and the fundamental unit of Flash, the “movie”, can be redrawn using separate layers.
I am still learning ActionScript, the object-oriented language used for Flash. My early impressions of it are that recent versions 2.0 and 3.0 are of a pretty high quality, but a far cry from Java.
I’ll post a follow-up to this in a few months after I have more experience with Flash and Actionscript under my belt.
Around the web
This post is a bit off topic for this blog. However, I recently decided I really needed an off-site backup service (er, I lost some files). And, as usual, I spent way too much time looking around the web for such a service. Anyways, I thought I’d share my homework. To give you an idea of my situation, I have about 30GB of data (code, datasets, visualizations) that I need constantly backed up.
Backup Services vs. Online Storage
There are a ton of options. I just wanted an automatic backup service–one that works flawlessly. Many services I looked at emphasize that the files can be accessed anywhere. These services often refer to themselves as online storage rather that online backup. The pure backup services usually offer unlimited space and focus on the software for backing up changes on demand or when your computer is idle, and on the software for restoring files. The tradeoff is usually that files are stored compressed, and are only meant to be accessed for somewhat rare restores. Online storage services, by comparision, limit the storage space, and although they almost always advertise the backup aspect, files usually need to be manually transfered. The advantage is that the files on such services can be accessed over the web.
I’m happy to keep files on my usb flash drive which I need access to wherever I go, and so I just need the automatic backup services.
I’ve ranked the services based on my impressions of their offerings and personal experience…
Best Deals
Runners Up
Maybe others will have a better experience. Foolish
If you just need online storage and remote access, consider a regular hosting account…
Around the Web
All Google Tech Talks are here (Google EngEDU is the actual name of the talk series). Thought I’d compile a top ten list…
I recently posted an efficient algorithm for computing the similarity of two Wikipedia pages (or any two nodes in a network) using cocitation similarity. Another type of similarity which may be worth considering is bibliometric coupling, in which two pages are similar if the pages they link to are similar. What is interesting is that it is only a few minor tweaks to the cocitation algorithm to compute bibliometricc coupling. Here’s the bibliometric coupling psuedocode (Perl style):
%nodes, %links //the wikipedia pages and pagelinks %reverse = reverse(%links) //flipping the pagelinks around %biblioCounts //2d hash for temporarily storing counts %scores //2d hash storing the final similarity scores foreach node (keys %nodes){ foreach linkedNode (keys %links->{node}) //count cocitations for node (wiki page) foreach node2 (keys %reverse->{linkedNode}) $biblioCounts{node}->{node2} ++; citationCount = keys(%linked->{node}) foreach node2 ( keys %biblioCounts{node}) //similarities scores for node citationCount2 = keys(%linked->{node2}) scores{node}->{node2} = 2 * biblioCounts{node}->{node2} / (citationCount + citationCount2) }
I’m working on a visualization, a ‘map’ if you will, of Wikipedia pages. The map will layout pages close to one another if they are similar. So, in order to create such a map I need to compute the similarity of any two Wikipedia pages.
For my first attempt at this, I decided to go with a cocitation measure of similarity. So, two Wikipedia pages will be said to be similar if other Wikipedia pages that link to one usually link to the other.
However, the naive way to compute this, looking at every pair of pages, is far too inefficient given that there are 650,000 pages in the English Wikipedia, and 14.5 million pagelinks. So I’ve worked up a much more efficient algorithm. Here’s the psuedocode…I hope someone, somewhere out in cyberspace will find this useful. (It can, in fact, be used to compute co-citation similarities for any data represented as nodes and links)
%nodes, %links //the wikipedia pages and pagelinks %reverse = reverse(%links) //flipping the pagelinks around %cocitations //2d hash for temporarily storing cocitation counts %scores //2d hash storing the final similarity scores foreach node (keys %nodes){ foreach sourceNode (keys %reverse->{node}) //count cocitations for node (wiki page) foreach cocited (keys %links->{sourceNode}) $cocitations{node}->{cocited} ++; citationCount = keys(%reverse->{node}) foreach node2 ( keys %cocitations{node}) //similarities scores for node citationCount2 = keys(%reverse->{node2}) scores{node}->{node2} = 2 * cocitations{node}->{node2} / (citationCount + citationCount2) }
15 Views of a Node Link Graph: An Information Visualization Portfolio by Tamara Munzner
Scholarly Data, Network Science, and (Google) Maps by Katy Borner
Geographical & Historical
WorldProcessor. Globes overlaid with information. Beautiful…must see!
Wikisky Google maps for the stars.
Flight Patterns Visualizations of FAA data.
TextArc: History of Science Beautiful.
2007 Calender. Brad Paley design.
31 days in Iraq. Visualization of deaths in Iraq. Depressing.
Tracing the Visitor’s Eye Flickr tags on a geospatial basemap.
Schreiner International Cables Map. Old world map of cables.
Napolean’s March. Made famous by Edward Tufte.
Government
The State of the Union in Words. From the NYTimes.
Death and Taxes. Where taxes go to.
U.S. Frequency Allocations Chart. Radio frequency allocations.
2006 Election Results. Interesting maps.
Taxonomy Visualization of Patent Data. Patent viz.
Internet
IRC Arcs IRC viz.
Welkin RDF visualizer.
History Flow Visualization of the Wikipedia. Wikipedia viz.
Who owns the Internet? Map of the net backbones.
Amaznode. Amazon product visualization.
Java Technology Concept Map. Relationships among Java technologies.
The Dumpster. Romance and Blogs.
Pop Culture
Radio Protector Music recommendation visualizer.
Movie and Actors. Visualization of imdb data.
Geneology
rhnav Geneology visualization.
20 Generations Family Tree. One particular family tree viz.
Swarm. Networks of website.
Science
Tree of Life. Species visualization.
Map of Science. From the journal Nature.
Literature
TextArc Visualizations of books, other writings
Visual Poetry. Visualizations of poems.
The Voice. One of the better tag clouds I’ve seen.
Other
Thinking Machine 4. A chess match viz.
Ph.D. Thesis Map. Dissertation outline in the style of a subway map.
Newspaper Map. Very unusual.
Visual Elements Periodic Table.
