Workshop report calls for National Initiative

The Computing Community Consortium has just announced that the workshop report from the Human Computation Roadmap Summit has been published and is available for download as a PDF file here.

This report describes workshop activities and findings, identifies key research areas for further exploration, and calls for a National Human Computation Initiative with policy and funding support at all levels to advance the science of participatory systems.

The report was co-developed by the workshop organizers, including  Pietro Michelucci of the Human Computation Institute, Lea Shanley of the The Woodrow Wilson International Center for Scholars, and Janis Dickinson and Haym Hirsh of  Cornell University.  It also includes important contributions from many of the workshop participants.

MIT Technology Review reports on the workshop here.

Crowdsourcing Alzheimer’s Research

Human Computation Institute is leading an initiative to develop an online Citizen Science platform that will enable the general public to contribute directly to Alzheimer’s Disease research and possibly lead to a new treatment target in just a few years.

It has long been known that reduced blood flow in the brain is associated with Alzheimer’s Disease and other forms of dementia.  However, new imaging techniques have enabled our Cornell-based collaborators to make important discoveries about the mechanisms that underlie this reduced blood flow.

These findings are suggestive of a new treatment approach that could reduce cognitive symptoms and halt disease progression.  However, arriving at a specific treatment target based on these findings requires additional research.  Unfortunately, the data curation required to advance these studies is very labor-intensive, such that one hour’s worth of collected data requires a weeks worth of annotation by laboratory personnel.   Indeed, the curation aspect of the analysis is so time consuming that to complete the studies necessary for identifying a drug target could take decades.

Fortunately, accurate curation of the data, though still impossible for machines, involves perceptual tasks that are very easy for humans.   We aim to address the analytic bottleneck via crowdsourcing using a divide-and-conquer strategy.  The curation tasks in this research map closely to the tasks used in two existing citizen science platforms: stardust@home and EyeWire, both of which have enabled discoveries reported in the journal Science.  In direct collaboration with the creators of these highly successful citizen science platforms, we are developing a new platform for public participation that we expect will reduce the time to a treatment from decades to only a few years.

If you are interested in participating in an online activity that will directly contribute to Alzheimer’s research, please pre-register here.  By participating, you will not only help speed up a treatment, but also understand more about the disease and exactly how your efforts make a difference.

This project includes collaborators from Cornell University, Princeton University, U.C. Berkeley, SciStarter, and WiredDifferently.

Pietro Michelucci

Computational Complexity and Popsicles

Wicked problems“[1][2], such as climate change, poverty, and geopolitical instability, tend to be ill-defined, multifaceted, and complex such that solving one aspect of the problem may create new, worse problems.  Thus, trying to engineer solutions to such problems is exacerbated by our inability to measure overall improvement.  For example, we may observe economic improvements in a locale where we have implemented a poverty mitigation strategy, only to discover later that we have inadvertently introduced health issues that ultimately result in even worse financial burdens related to the consequent healthcare needs.  And there may be other deleterious side-effects that are difficult to measure or that we fail to attribute to our implemented solution.  So what can be done?

Given our interest in applying human-based computational (HC) systems to solving these problems, we might gain insight from computational complexity theory.  This theoretical branch of computer science seeks to classify computational problems based on how difficult they are to solve.  It answers questions like, “How long would it take (at best and worst) to find the shortest path that visits each of these eight U.S. cities exactly once?”  It turns out that problems such as this one, canonically referred to as the “Traveling Salesman Problem“, are considered computationally intractable.   Indeed, for the Traveling Salesman Problem, the processing time for the best known solution increases by a factor of n22n.  In practical terms, a computer that takes one minute to find the shortest path between eight cities would take more than 11 years to find the shortest path between thirty cities.  But here’s the rub: there is no way to verify the solution other than to check it against all other possible paths, which is tantamount to recomputing the solution.

Just as the Traveling Salesman Problem is intractable for machines, wicked problems are intractable for humans.  The problem complexity for wicked problems is very high, but so is evaluating their solutions.  For such problems, assessing improvement broadly can be just as vexing as engineering a solution in the first place.  However, there is another version of the Traveling Salesman Problem for which solution verification is more tractable.  Instead of asking for an optimal path, this version asks a slightly different question: “Is there a path shorter than x that visits each of these cities once?”  This version of the problem does not materially change its difficulty classification, but it does make the solution much easier to evaluate.    Indeed, verifying the solution involves simply adding up the distances along the provided path and comparing the result to the mileage budget (x).  In this case, if my budget of allowed miles is 300, then we just need to verify that the provided itinerary is within-budget – that is, ensure that the generated path that visits each city exactly once is less than 300 miles.  In computational complexity theory, intractable problems for which solution verification can be performed quickly (i.e., in polynomial time) are considered “NP-complete”.  Another example of a problem that is NP-complete is prime factorization.   Today’s computers take a very long time to factor large numbers, the latency of which makes common encryption methods secure.  However, once a number has been decomposed into its prime factors, it is easy to verify the solution by simply multiplying the factors together and comparing the result to the original number.

Perhaps a first and more attainable step to solving wicked problems would be to reframe the problem in a manner analogous to the modified version of the Traveling Salesman Problem described above.  Instead of seeking an optimal solution to a wicked societal problem, perhaps we should seek a solution that simply meets the yes/no criterion of “would this be an improvement over what we have now”.  But how do we broadly measure such improvement?   Could human computation be used to enable tractable solution verification for wicked problems?  Enter the “Popsicle Index”.  Catherine Austin Fitts has proposed a very simple metric for a community’s well-being based on the percent of community members who “believe that a child can leave their home, go to the nearest place to buy a popsicle or other snack, and return home alone safely”[3].

This index is remarkable for several reasons.  First, it cleverly captures a multitude of individual effects, confluent effects, and n-order effects.  For example, the child’s safety could be related to traffic risks, a bad element hanging around the store, or even the perceived risk of chemicals in the purchased snack.  I would go so far as to call it a “wicked metric” because trying to understand the full set of factors and interactions that govern the Popsicle Index might itself constitute a wicked problem.  Second, the Popsicle Index is an HC approach to solution assessment that involves crowdsourcing and aggregating subjective human assessments.  Though such assessments might be of sufficient complexity to be considered intractable for machines, due to differences in computational strategies between humans and machines, such problems are often strong candidates for HC solutions[4]. Third, and perhaps most germane to this discussion the Popsicle Index, as a straight-forward window into community well-being, could facilitate solutions to wicked societal problems by reclassifying those problems from intractable to NP-complete.  Just as with the NP-complete version of the Traveling Salesman Problem, we may not have a quick way to know if we have an optimal solution, but we might at least have a sense of whether we are making things better or worse.  Indeed, the prospect of such comprehensive measures of improvement may bring us one step closer to addressing societal challenges.

What other “wicked metrics” might we explore?

– Pietro Michelucci

Acknowledgments:  I am grateful to Christina Engelbart for bringing the Popsicle Index to my attention and to Jordan Crouser for corrections and feedback that materially improved this article.

REFERENCES

[1] H. Rittel and M. Webber, “Dilemmas in a General Theory of Planning,” Policy Sci., vol. 4, pp. 155–169, 1973.

[2] “Wicked problem,” Wikipedia, the free encyclopedia. 08-Jan-2015

[3] C. A. Fitts, “The Popsicle Index – who makes it go up? who makes it go down?” Solari Blog.

[4] R. J. Crouser, B. Hescott, and R. Chang, “Toward Complexity Measures for Systems Involving Humans,” Human Computation, vol. 1, no. 1, Sep. 2014.