Where “make me very tired” can be under­stood as a euphemism for: “Drive me to a sketchily-​​explained mys­te­ri­ous ‘club meet­ing’ at an undis­closed bunker sup­pos­edly located along the dis­used coun­try road con­nect­ing Despair and Rue, play­ing a really annoy­ing Clas­sic Hits of the 70s cas­sette over and over so loud that I am forced to fling myself from the mov­ing car before we get much far­ther than the edge of Despair—but look! they drove off with my license in the frickin’ car, so I am forced to walk all the god. damned. rest. of. the. way. to. Rue.”

Roughly. That’s been my grad­u­ate school newcomer’s expe­ri­ence of Oper­a­tions Research to date. Your mileage may vary.

Like many crack­pots, I write stuff on 3×5 cards. Here are four cards I found while going through my notes for this other paper I’m sup­posed to write, and all four of them bear sim­ple state­ments of nice lit­tle research projects, any one of which would be suit­able for somebody’s the­sis work. Not mine. Because I’m just a first-​​year stu­dent. A badly-​​trained one, being a half-​​assed biol­o­gist raised by wolves.

Me, I’m in this Advanced Class where we’re learn­ing that Math­e­mat­i­cal Pro­gram­ming is not the be-​​all end-​​all prob­lem solver it’s cracked up to be. Hunh. Go fig. Been learn­ing that all semes­ter. Lucky thing too, because what with my com­plete and utter lack of meet­ing any­body in more than 15 years (until this last year or so) who thought it was worth con­sid­er­ing for a minute, I might’ve slipped and fallen into the kind of unques­tion­ing reliance of Mighty Orac­u­lar CPLEX that my peers in this new dis­ci­pline are prone to exhibit. I picked that up, back in Despair.

Any­way, I need to write a paper on “How Math­e­mat­i­cal Pro­gram­ming Is Some­times Hard, and This May Excuse the Occa­sional Lapse into Heuris­tics. Briefly.” And I need to do it with­out seem­ing for a moment to be… well, uppity. That’s a word. I will use “Made tired”, and “uppity”, and leave it at that.

Raised by wolves. Biol­o­gist. Igno­rance out the wazoo. ‘Nuff said.

So I will not be writ­ing about:

• What is the VC dimen­sion of a search algo­rithm? Think of it as a clas­si­fier that finds the exam­ples in a set of test prob­lems either easy or hard. Con­sider how this clas­si­fier shat­ters the set of pos­si­ble prob­lems of that type. Pick your favorite search algo­rithm and class of prob­lems: con­sider using Trav­el­ing Sales­man Prob­lems (every­body else does), and maybe sim­u­lated anneal­ing? Your call. Heck, try Lin­ear Pro­gram­ming with sim­plex moves, and arbi­trary diet problems.
• What for­mal rep­re­sen­ta­tion of the set of all search and opti­miza­tion prob­lems would be use­ful in build­ing a clas­si­fier that let you auto­mat­i­cally rec­og­nize the canon­i­cal types: knap­sack, assign­ment, trav­el­ing sales­man, bin-​​packing, stock-​​cutting, knee-​​biting? If you could cre­ate an auto­mated clas­si­fier, what would it mean if it told you that a prob­lem was “93% knapsack”?
• Surely—surely—there is a No Free Lunch The­o­rem for branch-​​and-​​bound strate­gies. I mean, oth­er­wise when you pick a vari­able (or some com­bi­na­tion of vari­ables) to branch on, you’re just guess­ing, and that’s so… dumb… well, I don’t even want to think it of you. So tell me you know there is an NFL The­o­rem there.
• Dis­cuss a stan­dard opti­miza­tion prob­lem, with your choice of objec­tive func­tion. Now restate it to find the second-​​best answer. Is that harder? Why? Sure seems harder than find­ing the worst. What do you have to do to the rep­re­sen­ta­tion to make it easy again?

You, who are not in my dis­ci­pline, who are not a first-​​year grad­u­ate stu­dent with a Very Poor Under­stand­ing of the finer details of Lin­ear Pro­gram­ming and the Appalling Frac­tion­al­ity of Lin­ear Relax­ations.… you go have fun. Send me a cite, if you get some­thing done. I can’t stand the thought of doing them, except that they sound quite interesting.

But I would have to explain them to my col­leagues. That would be hard. I can tell already. If you need to get in touch about them, just drop me a line.

I’ll be some­where between here and Rue.

As reported in the “Most amus­ing (or aston­ish­ing) text you’ve come across” thread at the Dis­trib­uted Proof­read­ers forum. To find this and more such trea­sure, con­sider vol­un­teer­ing a few min­utes of your time to proof­read a page or two. It’s sim­ple, it’s free, it helps pre­serve the great works of the past, and above all else brings to light the unre­marked gems among the lesser-​​known works.

THE JABBERWOCKY OF AUTHORS

‘Twas gilbert. The kch­ester­ton
  Did locke and ben­nett in the reed.
All mered­ith was the nichol­son,
  And har­ri­son outqueed.

Beware the see-​​enn-​​william, son,
  The lon­don­jack with call that’s wild.
Beware the gertroo dather­ton
 And richardwashburnchild.

He took his brady blade in hand;
  Long time the par­tridge foe he sought.
Then stood a time by the oppen­heim
  In deep mcnaughton thought.

In war­wick deep­ing thought he stood–
  He poised on edith­whar­ton brink;
He cried, “Ohbernard­shaw! I could
  If basilk­ing would kink.”

Rexbeach! rexbeach!–and each on each
  O. Henry’s man­tles fer­ber fell.
It was the same’sif hen­ry­james
  Had wally eaton well.

“And hast thou writ the great­est book?
  Come to thy birm­ing­ham, my boy!
Oh, beres­ford way! Oh, hol­man day!”
  He kiplinged in his joy.

‘Twas gilbert. The kch­ester­ton
  Did locke and ben­nett in the reed.
All mered­ith was the nichol­son,
  And har­ri­son outqueed.

Harry Per­sons Taber.

As seen in The Book of Humor­ous Verse, edited by Car­olyn Wells, 1920. Doran.

The first — and only — sen­tence of the pref­ace from Euro­pean Glimpses and Glances by J. M. Emer­son. 1889.

The ground cov­ered by the con­tents of the fol­low­ing pages hav­ing pro­duced an almost unend­ing series of more or less suc­cess­ful fruitages, the author can hardly expect that the mod­est result which he has brought to mar­ket may be thought wor­thy of atten­tion; and if per­chance it shall be found agree­able to the tastes of some, he will be grat­i­fied to know that they have real­ized some­thing of the enjoy­ment in con­sum­ing that he has expe­ri­enced in pro­duc­ing it.

Dis­trib­uted Proof­read­ers (DP) is an online com­mu­nity of sev­eral hun­dred vol­un­teers who scan books and mag­a­zines that are the pub­lic domain, and then col­lec­tively cor­rect char­ac­ter recog­ni­tion and for­mat­ting errors made by auto­mated OCR soft­ware, pro­duc­ing high-​​quality text and HTML files that are released into the pub­lic domain — for free — at Project Guten­berg.

A “project” at DP is typ­i­cally a sin­gle work: a book, a mag­a­zine num­ber, a small por­tion of an ency­clo­pe­dia, a mono­graph, a song. The com­plex DP work­flow moves these projects through a series of well-​​defined stages, with tasks rang­ing from the scan­ning of the phys­i­cal work by indi­vid­ual content-​​providers, through two sep­a­rate rounds of (text) proof­read­ing of the indi­vid­ual pages of the work, two fur­ther rounds of for­mat­ting to cap­ture details of typo­graphic and mid-​​scale seman­tic struc­ture, and finally a num­ber of rounds of post-​​processing to re-​​integrate the sep­a­rated pages into a sin­gle coher­ent work. Only after they’ve passed through the “hands” of dozens of vol­un­teers are projects con­sid­ered com­plete and sent to the archives for pub­lic distribution.

In the proof­read­ing and for­mat­ting stages of the work­flow, there are sev­eral hun­dred works in progress at a given time, each of which may have sev­eral hun­dred pages. Vol­un­teers can choose whichever active project they pre­fer to work on, one page at a time. Thus, at any given moment there is a wide vari­ety of works in process, in many lan­guages, of many styles and in numer­ous domains and cat­e­gories, aimed at many dif­fer­ent audi­ences and age lev­els. Each project poses unique chal­lenges and rewards to the project man­agers, the vol­un­teers, and the even­tual consumers.

In the admin­is­tra­tive sense, the flow dynam­ics of projects in DP is con­trolled by a suite of com­plex par­al­lel and sequen­tial queues gov­erned by numer­ous rules, and projects are pushed and pulled in var­i­ous ways through the dif­fer­ent stages. But at its core, the flow rate of projects through DP is dri­ven by the col­lec­tive pref­er­ences of the vol­un­teers who pick pages — each accord­ing to her own cri­te­ria and abil­ity — to work on. Through the inter­ac­tion of the dri­ving force of col­lec­tive inter­est with the under­ly­ing struc­ture of admin­is­tra­tive rules, some projects lan­guish for months or years with­out pro­gress­ing, while oth­ers race through the stages of DP in a mat­ter of hours.

Not sur­pris­ingly, the rea­sons for these dif­fer­ences are not simple.

Projects in DP dif­fer widely on the basis of many struc­tural fea­tures — the num­ber of pages, the length of the pages, the num­ber of illus­tra­tions and tables. And qual­ity fea­tures — the clar­ity of the scans and the accu­racy of the OCR, the pres­ence of automatically-​​produced HTML markup. And mat­ters of con­tent — lan­guage, fic­tion vs. non­fic­tion, tech­ni­cal vs. nar­ra­tive work, reli­gious con­tent, &c. And there are the ill-​​defined “mar­ket­ing” fac­tors that most affect their rel­a­tive inter­est to the vol­un­teers, that might drive some­body to choose one over another to proof­read. Thus, a novel that moves through the sys­tem quickly could be doing so because the pages are short, or because the OCR is espe­cially clean, or because the story is engag­ing, or because the author is famous. An essay on lin­guis­tics might take weeks to com­plete a stage sim­ply because it con­cerns an uncom­fort­able topic, or the pages are inor­di­nately messy, or there is a sin­gle dif­fi­cult table “block­ing” the vol­un­teers’ progress.

The aver­age speed at which work passes through the DP sys­tem has been remark­ably con­stant over the last year, at least in terms of projects com­pleted. But there is a grow­ing prob­lem with the work­flow: the queue of projects wait­ing to enter the sec­ond stage of proof­read­ing is already dan­ger­ously large, and there is no evi­dence that the com­mu­nity will be able to com­pen­sate with­out a rad­i­cal struc­tural solu­tion or gross change in pol­icy. While a num­ber of dis­cus­sions are under­way about how best the alle­vi­ate the back­log, expe­ri­ence con­spires to under­mine the col­lec­tive con­fi­dence in any one of them: the cur­rent sys­tem was put in place nearly one year ago to address other aspects of unbal­anced work­flow. More impor­tantly the sys­tem of con­trols and queues is so com­plex that it defies under­stand­ing and sim­ple con­trol.

To that end, my wife Bar­bara and I are plan­ning to build a detailed model of the DP work­flow, at a suf­fi­ciently fine scale to cap­ture every impor­tant aspect of the site’s dynam­ics. With those mod­els, we’ll be able to really explore and under­stand “what if” sce­nar­ios: changes in the dynam­ics of queues, changes in the bal­ance and even the qual­ity of work. Over the next few months, Bar­bara and I will report our progress on this over­ar­ch­ing project.

That said, we’re left with an impor­tant job to do before­hand. To com­pare one model or pol­icy with another, we first need to under­stand not just what’s hap­pen­ing but also what’s wanted. We need to estab­lish a set of bench­mark measurements.

“Atten­tion is being paid”

We’re not con­cerned with the rel­a­tive con­tri­bu­tion or per­for­mance of any vol­un­teer or project man­ager, nor should we be. The diver­sity of vol­un­teer inter­ests, abil­i­ties and inten­tions is what makes the Dis­trib­uted Proof­read­ers com­mu­nity so effec­tive and strong.

Rather, the fam­ily of Project Man­agers and admin­is­tra­tors — and also the even­tual con­sumers — is much more con­cerned with the flow of projects through the sys­tem. Any Project Man­ager prefers to see their work move ahead quickly. Any admin­is­tra­tor prefers to see back­logs emp­tied as much as pos­si­ble. Any inter­ested reader wants to read the book as soon as pos­si­ble, and they can’t until it’s released to the public.

Through­out the DP com­mu­nity there’s clearly already a broad appre­ci­a­tion of this. “Spe­cial Days” have been set up to ease the release of works that would oth­er­wise wait in queues. The first project of any new Project Man­ager is expe­dited. Ad hoc teams of vol­un­teers have arisen that spe­cial­ize in com­plet­ing works that have spent the “longest time” in the sys­tem. More cru­cial, the cur­rent back­log of projects wait­ing for the sec­ond round of proof­read­ing is in itself no prob­lem, except inso­far as it threat­ens to delay ongo­ing projects too long.

In a way, all these are adap­ta­tions to bring extra “atten­tion” to projects that are oth­er­wise being missed. Work only gets done by vol­un­tary atten­tion from the com­mu­nity mem­bers. While every indi­vid­ual wants most to do what’s fun and enter­tain­ing, at the same time there’s a real sense that the emer­gent progress over all projects should be equi­table and in some sense balanced.

That it takes all kinds, in other words.

From an admin­is­tra­tive stand­point, any com­par­i­son between alter­na­tive poli­cies and struc­tural changes should take into account the effects they have on both the indi­vid­ual and over­all progress of projects.

Cur­rent prac­tice for esti­mat­ing the progress of projects tends to focus on the num­ber of projects being released into and out of each stage. But as I men­tioned above, this ignores the diver­sity of work under­way. Is it prefer­able to release many small nov­els at the expense of impor­tant — but dif­fi­cult — larger ref­er­ence works? Anec­do­tally, the “fastest” projects are the small­est and sim­plest ones. Because there are more of them, and they get read faster, they often bypass larger more schol­arly works in the sys­tem… and thus they tend to form a large frac­tion of the end prod­uct released.

In the spirit of pre­serv­ing diver­sity, is this the most desired outcome?

Quan­ti­fy­ing the degree of attention

What I’m propos­ing here is a method of mea­sur­ing the rel­a­tive atten­tion paid to projects. One that takes into con­sid­er­a­tion the many diverse attrib­utes of those projects: the lan­guage, clar­ity, dif­fi­culty, scale, and all the other qual­i­ties that must be bal­anced to com­pare them equi­tably. And equity is the impor­tant point, of course. There is a tacit but strong sense among the vol­un­teers is that every­thing in process should move on, no one at the expense of any other.

The over­all DP work­flow is sur­pris­ingly com­plex. Because there is a press­ing need to address it right now, I’ll focus in this work on projects pass­ing through the sec­ond proof­read­ing (P2) stage. It’s hoped that by devel­op­ing this approach there, we can later derive a more gen­eral approach for bal­anc­ing flow across the entire DP system.

Briefly, I’m propos­ing to apply a math­e­mat­i­cal tech­nique called Data Envel­op­ment Analy­sis (DEA) to com­pare projects that have com­pleted the P2 stage. DEA allows the ana­lyst to under­stand espe­cially com­plex prob­lems with­out over-​​simplifying effects or throw­ing away data that gets lost in regres­sion and many other sta­tis­ti­cal methods.

In fram­ing a DEA model of P2 projects at DP, I’ll col­lect mea­sure­ments that are roughly divided into a set of “inputs” and cat­e­gories, and a set of “out­puts”. “Inputs” and cat­e­gor­i­cal vari­ables for this analy­sis should include traits of the projects (not just the works, but the DP projects) them­selves: the num­ber of pages in the work, the num­ber of char­ac­ters on each page, the lan­guage, the num­ber of dif­fer­ent proof­read­ers work­ing in the two proof­read­ing phases P1 and P2, the amount of poetry or math­e­mat­ics involved, &c. “Out­puts” in this case should reflect our stan­dard­ized mea­sure­ment of “pro­duc­tiv­ity”. I’ll pro­pose we look at the num­ber of days needed per page com­pleted in the P2 stage.

DEA in this con­text is an exploratory, not a pre­scrip­tive tech­nique. While the tech­ni­cal details aren’t impor­tant here, the gist is this: DEA is first used to iden­tify the sub­set of projects that are processed fastest com­pared to oth­ers that “use” the same amount of the “inputs”; we’ll call these the ones receiv­ing “max­i­mum atten­tion” from the vol­un­teers, but in DEA par­lance they’re often referred to as “effi­cient”. More­over, DEA pro­vides a mea­sure of how “inef­fi­cient” the other projects are; here we can think of this as a mea­sure of how much less atten­tion they’re get­ting, com­pared with other projects with com­pa­ra­ble characteristics.

I’m being care­ful not to talk about “effi­ciency” as such, mainly because it’s a term of art in this con­text. This isn’t some sort of hare-​​brained pro­posal to “improve effi­ciency at DP”. Rather, it’s a way of mea­sur­ing what’s actu­ally get­ting done. My hope is that by mea­sur­ing it, we (as ana­lysts, admin­is­tra­tors and vol­un­teers) can look at the process and learn more about what actu­ally hap­pens in DP. While the biggest ben­e­fit of dis­trib­ut­ing work among many indi­vid­u­als is the “wis­dom of crowds” effect we read about in the sci­en­tific press these days, the neg­a­tive side is that crowds as such aren’t that good at com­mu­ni­cat­ing the finer details of self-​​knowledge.

Use­ful outcomes

This project offers at least four ben­e­fits I can see.

First, it can be the ratio­nal frame­work we use to com­pare alter­na­tive poli­cies. This will be espe­cially use­ful in a few weeks a mod­el­ing frame­work comes along that allows simul­ta­ne­ous explo­ration of numer­ous alter­na­tives. DP is extra­or­di­nar­ily com­plex, and under­stand­ing the shifts and flows and their effects on pro­duc­tiv­ity and qual­ity is dif­fi­cult even for small seg­ments, let alone the whole system.

Sec­ond, label­ing each active project with a num­ber called “atten­tion being paid to this project” could pro­vide impor­tant infor­ma­tion for project man­agers and admin­is­tra­tors, even within the cur­rent sys­tem. My analy­sis may high­light ways indi­vid­ual PMs can man­age and fine-​​tune the progress of their own projects (even at the expense of oth­ers’), or it could spark the inven­tion of mar­ket­ing and incen­tive sys­tems to help drive vol­un­teer atten­tion one way or another.

Third, this might focus the col­lec­tive atten­tion of the vol­un­teer com­mu­nity as a whole. We’ve all heard to old saw: “What gets mea­sured gets done.” As I’ve pointed out above, I think there’s a con­sen­sus that equity is good. If only the col­lec­tive knew what progress was being made, they might be able to bet­ter col­lec­tively bal­ance it.

Finally, say it works. If a robust auto­mated sys­tem can be built that helps with this sort of “bal­ance”, it might save DP. There are going to be more vol­un­teers all the time, and more con­tent and more projects wait­ing to move ahead. The present setup strains the col­lec­tive man­age­ment skills of the cur­rent com­mu­nity; wit­ness the back­log of P2 projects. If we incor­po­rate this sort of self-​​awareness into the auto­mated infra­struc­ture to bet­ter steer projects more trans­par­ently and effi­ciently, we’ll surely ben­e­fit over the sit­u­a­tion with the cur­rent suite of ad hoc rules that are fre­quently over­rid­den or “gamed”.

I’m send­ing requests for the nec­es­sary data (and a dupli­cate of this post) to the DP web­site itself, but will be happy to dis­cuss the progress of the analy­sis here or there.

There aren’t a lot of col­lec­tive col­lab­o­ra­tive production-​​oriented com­mu­ni­ties yet. I’d be inter­ested in hear­ing any­thing you might know about other examples.