Measuring value-adding in Wikipedia

So I've been working on this project on an off.  I've been trying to bring robust measures of edit quality/productivity to Wikipedians.  In this blog post, I'm going to summarize where I am with the project.  

First, the umbrella project:  Measuring value-added

Basically, I see the value of Wikipedia as a simple combination of two hidden variables: quality and importance.  If we focused on making our unimportant content really high quality, that wouldn't be very valuable.  Conversely if we were to focus on increasing the quality of the most important content first, that would increase the value of Wikipedia most quickly.  

Value = Quality × Importance

But I want to look at value-adding activities, so I need to measure progress towards quality.  I think a nice term for that is productivity.  

Value-added = Productivity × Importance

So in order to take measurements of value-adding activity in Wikipedia, I need to bring together good measure of productivity and importance.

Measuring importance

See https://meta.wikimedia.org/wiki/Research:Measuring_article_importance

Density of log(view rate) for articles assessed by Wikipedians

for importance. 

I'm going to side-step a big debate purely because I don't feel like re-hashing it in text.  It's not clear what importance is.  But we have some good ways to measure it.  The two dominant strategies for determining the importance of a Wikipedia article's topic are (1) view rate counts and (2) link structure.  

With view rate counts, the assumption is made that the most important content in Wikipedia is viewed most often.  This works pretty well as far as assumptions go, but it has some notable weaknesses.  For example, the article on Breaking Bad (TV show) has about an order of magnitude more views than the article on Chemistry.  For an encyclopedia of knowledge, it doesn't feel right that we'd consider a TV show to be more important than a core academic discipline.  

Link structure provides another opportunity.  Google's founders famously used the link structure of the internet to build a ranking strategy for the most important websites.  See PageRank.  This also seems to work pretty well, but it's less clear what the relationship is between the link graph properties and the nebulous notion of importance.  At least with page view rates, you can plainly imagine the impact that a highly viewed article has.  

Fun story though: Chemistry has 10 times as many incoming links as Breaking Bad.  It could be that this measurement strategy can help us deal with the icky feeling us academics get when thinking that a TV show is more important than centuries of difficult work building knowledge.  

Measuring productivity 

See: https://meta.wikimedia.org/wiki/Research:Measuring_edit_productivity 

Luckily, there is a vast literature for measuring the quality of contributions in Wikipedia.  Many of which I have published!  There are a lot of strategies, but the most robust (and difficult to compute) is tracking the persistence of content between revisions.  The assumption goes: the more subsequent edits a contribution survives, the high quality it probably was.  We can quite easily weight "words added" by "persistence quality" to get a nice productivity measure.  It's not perfect, but it works.   The trick is figuring out the right way to scale and weight the measures so that they are intuitively meaningful.  

The real trick here was making the computation tractable.  It turns out that tracking changes between revisions is extremely computationally intensive.  It would take me 60 days or so to track content persistence across the entire ~600m revisions of Wikipedia on a single core of the fastest processor on the market.  So the trick is to figure out how to distribute the processing across multiple processors.  We've been using Hadoop streaming.  See my past post about it: Fitting Hadoop streaming into my workflow  It's been surprisingly difficult to work with memory issues in Hadoop streaming that don't happen when just using unix pipes on the command line.  I might make a post about that later, but honestly, it just makes me feel tried to think about those types of problems.  

Bringing it together

I'm almost there.  I've still got to work out some threshholding bits for productivity measures, but I've already finished the hard computational work.  My next update (or paper) will be about who, where and when of value-adding in Wikipedia.  Until then, stay tuned.  

MediaWiki Utilities -- Unix style

Today, I want to talk about a specific type of research output that, I feel, adds a substantial amount of value beyond a single research project.  I'm talking about open sourced research code, but not of the type that you normally see -- the type that's actually intended to be used by other people to serve new purposes.

Before I dig into software libraries I want to talk to you about, I must make a distinction:

• CRAPL quality code -- This is the code that a researcher builds ad-hoc in order to get something done.  There's little thought spent on generalizability or portability.  With this code, it's usually better and faster to fix a problem by adding a step in the workflow rather than fixing the original problem.  So, you end up with quite a mess usually.  While good for documenting the process of data science work, this is not useful to others.  
• Library quality code -- This code has been designed to generalize to new problems.  It's intended to be used as a utility by others who are doing similar work -- but not the exact same work.  It's usually well documented and well tested.  With this code, it is sacreligious to add more code on top of broken code to fix a problem.  This is just one of the many disciplines that must be applied to the practice of writing software to have good, library quality code. 

I've been analyzing Wikipedia data for nearly a decade (!!!) -- and I can tell you that it was never easy.  The English Wikipedia XML dumps that I have done most of my work with are on the order of 10 terrabytes uncompressed.  The database, web API and XML dumps all use different field names to refer to the same thing.  In each one, the absence of a field -- or NULLing of the field can mean different things.  Worse, the MediaWiki software has been changing over time, so in order to do historical analyses, you need to take that into account.  In the process of working out these details and getting my work done, I've produced reams of CRAPL quality code.  See https://github.com/halfak/Activity-sessions-research for an example.  In this case, I have a Makefile that, if executed, would replicate my research project.  But if you look inside that Makefile, you'll see things like this:

# datasets/originals/enwiki_edit_action.tsv: sql/edit_action.sql
#     cat sql/edit_action.sql | \
#     mysql $(dbstore) enwiki > \
#     datasets/originals/enwiki_edit_action.tsv

That's a commented out Makefile rule that calls my local database with my local configuration hardcoded and runs some SQL against it.  This is great if you want to know what SQL produced which datafile, but not very useful if you want to replicate the work.  And why is it commented out!?  Well, the database query takes a long time to run and I didn't want to accidentally overwrite the data file as I was finishing off the research paper.  Gross, right?  This isn't all that useful if you wanted to perform a similar analysis.

But in producing this CRAPL code, there are some nice, generalizable parts that occur to me so I write them up for others' benefit.  I've gone through a few iterations of this and learned from my mistakes.

Back in 2011, I released the first version of wikimedia-utilities, a set of utilities that made the work I was doing at the Wikimedia Foundation easier.  The killer feature of this library was the XML processing strategy.  It changed the work of processing Wikipedia's terrabyte scale XML dumps from a ~2000 line script to a ~100 line script.   But the code wasn't very pythonic, it lacked proper tests and did not integrate well into the python packaging environment.

In 2013, I decided to make a clean break and start working on mediawiki-utilities, a super-set of utilities from wikimedia-utilities that were intentionally generalized to run on any MediaWiki instance.  I had learned some lessons about being pythonic, implementing proper tests and integrating with python's packaging environment.

But as I had been working on new projects and realizing how they could generalize, I ended up expanding mediawiki-utilities to a monolith of loosely related parts.  And it gets worse.  Since I focused on those parts as I needed them, there were certain modules that were ignored.  Since I did most of my work with the databases directly, it was rare that I spent time on the 'database' module of mediawiki-utilities.  I ended up with a monolith that was inconsistently developed!

So, in thinking about monoliths and how to solve problems that they impose, I was inspired by the Unix philosophy of combining "small, sharp tools" to solve larger problems.  I realized that the primary modules of mediawiki-utilities could be split off into their own projects and combined in interesting ways -- and that this would enable a more distributed strategy to management.  So I've been hard at work to bring this vision into the light.

First, the core utilities:

• pip install mwxml • docs • source
• This library contains a collection of utilities for efficiently processing MediaWiki’s XML database dumps. There are two important concerns that this module intends to address: complexity and performance of streaming XML parsing.
• pip install mwapi • docs • source
• This library provides a set of basic utilities for interacting with MediaWiki’s “action” API – usually available at /w/api.php. The most salient feature of this library is the mwapi.Session class that provides a connection session that sustains a logged-in user status and provides convenience functions for calling the MediaWiki API. See get() and post().
• pip install mwdb • source
• This library provides a set of utilities for connecting to and querying a MediaWiki database.
• pip install mwparserfromhell • docs • source
• This library provides an easy-to-use and outrageously powerful parser for MediaWiki wikicode.
• Note that I am primarily a user of this library -- not a major contributor -- but it obviously belongs in this list.

Now the peripheral libraries that make use of these core utilities:

• pip install mwoauth • docs • source
• This library provide a simple means to performing an OAuth handshake with a MediaWiki installation with the OAuth Extension installed.
• pip install mwreverts • docs • source
• This library provides a set of utilities for detecting reverts (see mwreverts.Detector and mwreverts.detect()) and identifying the reverted status of edits to a MediaWiki wiki.
• pip install mwsessions • docs • source
• This library provides a set of utilities for group MediaWiki user actions into sessions. mwsessions.Sessionizer and mwsessions.sessionize() can be used by python scripts to group activities into sessions or the command line utilities can be used to operate directly on data files. Such methods have been used to measure editor labor hours.
• pip install mwpersistence • source
• This library provides a set of utilities for measuring content persistence and tracking authorship in MediaWiki revisions.

And I have a bunch more that are just on the horizon.  They represent a sampling of my active research projects.

• mwmetrics -- User behavioral statistics extraction for MediaWiki editors
• mwrefs -- Extract citations, references and scholarly identifiers from MediaWiki
• mwevents -- Generalized event extraction and processing framework for MediaWiki
• mwtalkpage -- A talk page discussion parser for MediaWiki

It's my goal that researchers who haven't been working with wiki datasets will have a much easier time building off of my work to do their own.  I think that a good set of libraries can make a huge difference in this regard.  That's my goal.

I'll be making a more substantial announcement soon.  In the meantime, I'm cleaning up and extending documentation and working together some examples that demonstrate how a researcher can compose these small, sharp libraries together to perform powerful analyses of Wikipedia and users in other MediaWiki wikis.  Until then, please use these utilities, let me know about bugs and send my your pull requests!

Fitting hadoop streaming into my python workflow

I got something working in Hadoop (by reading the documentation[1]) that is going to change the way I work with Wikipedia text data.  In order to give you a sense for how excited I am, I'm going to need to talk to you about the way that I approach my work with large datasets. 

My python workflow

So, I try to do as much work as I can with input/output streams.  I'm a bit of a unix geek, so that means I'm thinking about standard-in and standard-out and writing my analytics code as though I were supplementing UNIX core utils.  This has nice computational practicalities and it allows you to stream operations together.

Computational practicalities

The worst bottleneck you're likely to encounter in the course of doing data analysis on large files is memory.  Most statistical environments specifically support in-memory analysis of datasets to the exclusion of streaming.  This means that, in order to get any work done, you need to first copy all of your data from disk to memory.  If your dataset is larger than the available memory, you'll likely end up crashing the machine you are working with -- or at least render it unusable until your process finally crashes.

On the other hand, python, perl and unix utilities (like cut, shuf, sort, sed, etc.) afford some powerful capability for working with datasets as streams, and therefore, dramatically reducing the memory footprint of a dataset.  As the diagram above makes apparent, if you can fit your data operation into a streaming job, then it doesn't matter how big your dataset is and you'll end up needing very little memory. 

Streaming operations together

I like Doug McIlroy's summary of the unix philosophy:

Write programs that do one thing and do it well. Write programs to work together. Write programs to handle text streams, because that is a universal interface.

By following these principles, you can build "operators" rather than stand-alone programs.  This allows you to write less code (which is a Good Thing™) and get more done.  Recently, I wrote a paper that required me to wrangle 12 different datasets from 7 different websites -- and being able to integrate my code with unix core utilities was a godsend.  Here's a line from my projects Makefile that I think captures the amazingness. 

(echo -e "user_id\tintertime\ttype";
bzcat datasets/originals/aol_search.tsv.bz2 |
tail -n+2 |

sort -k1,2 |
./intertimes |

sed -r "s/(.*)/\1\tapp view/" | things
shuf -n 100000) >
datasets/aol_search_intertime.sample.tsv

These lines achieve the following steps of a streaming job:

1. Print out new headers: user_id, intertime, type
2. Decompress the app_view.tsv.bz2 dataset
3. Trim off the original header line
4. Sort the dataset by the first two columns (user_id, timestamp)
5. Compute the time between events per user (this is my python)
6. Add a column of "app view" corresponding to the "type" header
7. Randomly sample 100000 observations
8. Write it all out to a new data file.  

In order to perform this complex operation over 28 million rows, I wrote ~30 lines of python code and put it in the middle of a few unix utilities that do most of the heavy lifting for me.  The processes took about 2 minutes and used a couple hundred MB of memory.  The random sample that we finally arrive at contains only 100k rows and will happily load into memory in about a second.  

Bringing it together with Hadoop streaming

If you've been living under a rock for the last 5 years or so, Hadoop is a framework for performing map/reduce operations that has become the industry standard.  Through Hadoop's streaming interface, I can make use of UNIXy streaming utilities to get my python work done faster.  Since I'm already thinking about my work as processing data one-row-at-a-time, map/reduce is not that much of a leap. '

However, there's one part of my streaming scripts that is very important to me, but I hadn't told you about it yet.  When I do behavioral analysis in Wikipedia, I often need to choose a dimension and process user actions in order over time.  A good example of actions in Wikipedia is an "edit".  There are two really interesting dimensions to process edits: page and user. 

The diagram above visualizes these two dimensions.  If we look at my edits over time, we are looking at the "user" dimension.  If we look at the article Anarchism's edits of time, we are looking at the "page" dimension.  In order to processed data based on these dimensions, I'll usually sort and partition the data.  Notabily, the designers of Wikipedia's XML dumps had this in mind when they put together their format.  They partition based on page and sort based on timestamp.  Yet, hadoop's native map/reduce strategy doesn't afford the ability to insist that I'll see a page's revisions or a user's edits together and in order.

Enter secondary sort.  Using  org.apache.hadoop.mapred.lib.KeyFieldBasedComparator and org.apache.hadoop.mapred.lib.KeyFieldBasedPartitioner, I can tell hadoop to sort and partition data before the "reduce" phase of the process.  The best part is, these guys are parameterized in the exact same way as UNIX sort! 

So, let's say you want to process a users activities over time.  Set the partitioner divide the data based on the user_id column and tell hadoop to sort based on the revision timestamp.  Here's what the call looks like for a dataset I'm working with right now.  (first column == user_id, second column == timestamp)

hadoop jar /usr/lib/hadoop-mapreduce/hadoop-streaming.jar \
    -D  mapreduce.output.fileoutputformat.compress=false \
    -D  mapreduce.input.fileinputformat.split.minsize=300000000 \
    -D  mapreduce.task.timeout=6000000 \
    -D  stream.num.map.output.key.fields=2 \
    -D  mapreduce.partition.keypartitioner.options='-k1,1n' \
    -D  mapred.output.key.comparator.class="org.apache.hadoop.mapred.lib.KeyFieldBasedComparator" \
    -D  mapreduce.partition.keycomparator.options='-k1,1n -k2,2n' \
    -files       intertime.py \
    -archives    'hdfs:///user/halfak/hadoopin/virtualenv.zip#virtualenv' \
    -input       /user/halfak/enwiki_20141025.*.tsv \
    -output      "/user/halfak/hadoopin/enwiki_intertime/$(date +%Y%m%d%H%M%S)" \
    -mapper      cat \
    -reducer     intertime.py \

    -partitioner org.apache.hadoop.mapred.lib.KeyFieldBasedPartitioner

So, I'm stoked.  This will change the way I do my work.

1. Which leaves a bit to be desired[2]

2. Finding which error code to google is worse