The Power of Integrated Abstraction ofD t
Data‐centrict i Human/MachineH/M hi Computations
Ct tiAtsuyuki
y Morishima,, Norihide Shinagawa
gShoji Mochizuki
University of Tsukuba
VLDS2011 held with VLDB2011, Seattle, Sep. 2011

Outline1. Backgroundg
2. CyLog
3. Prototype Development
4. Related Work and Discussions

1

The Complementary Nature ofHuman/Machine Computations• HighHigh‐speed
speed computation
without errors• Never forget things• Work without a breakComputer Intelligence• Pattern Recognitiong• Common Sense• Gather Information Offline• Create new ideas
Human/SocialIntelligenceBackground• Many “Crowdsourcing Systems (Applications)”
have shown their success [Doan, Ramakrishnan,
Halevyl2011]20 ]– ESP Games– Q&A Services– reCAPCHA– Video Sharing–…

2

Our Challenge: Develop a Systematic Framework toQuickly Build Programs for the Integration of Human/
Machine Computations
Digital Computer Spaces

Human/Social
Intelligence Spaces

Traditional Abstraction forComputing(Executed by Computers)

Programming/Analysis

Our Abstraction of Computing(Executed in Cybernetic Information Spaces)

A Natural (and Important) Question
What is a good abstraction to describe (andprogram) such applications of human/machinecomputation?
• ESP Games• Q&A Services• reCAPCHA• Video Sharing•…

A possibility: Since they are data‐centric,
database languages can be a starting point todevelop such an abstraction

3

Our idea: Extend the DB Abstraction todeal with Cybernetic Dataspaces (1/2)
Application Program

Codes in Data‐
Data‐centric Declarative
Language

Codes in OtherLanguages

Traditional dataspace

Query
Data Generation
And Input

Our Idea: Extend the DB Abstraction todeal with Cybernetic Dataspaces (2/2)
Application Program

Codes in Data‐
Data‐centric Declarative
Language

Codes in OtherLanguages

Traditional dataspace

QueryData Generation
And Input

Cybernetic dataspace4

Integrated Abstraction of Data‐centric
Human/Machine Computations:
An Example of CyLog Rule

metadata(x, y) :‐ img(x), keyword(x, y), inDict(y)Evaluated bydata

Evaluated byhumans

Evaluated by
d t
data

Many Ongoing Projects• We saw exciting ongoing projects in publicationsi 2011in– Qurk [MIT]– sCOOP/hQuery [StanfordԜ&ԜSanta‐Cruz]– CrowdDB [UC Berkeley, ETH Zurich]…

• They try to achieve database functions in thepresence of human data‐sources5How is CyLog Different?
• Introduces the concept of rational data source, asa new typetoff WWebbddatat source• Open Predicates/Attributes to model theinteraction with people• Data games for obtaining appropriate values• Our first international presentation was in 2010!**Atsuyuki Morishima. A Database Abstraction for Social Applications, KJDB2010, May 2010.

Outline1. Backgroundg
2. CyLog
3. Prototype Development
4. Related Work and Discussions

6

Point 1: Datalog‐like Declarative
Language

metadata(x, y) :‐ img(x), keyword(x, y), inDict(y)Evaluated bymachine

Evaluated byhumans

Evaluated bymachine

Point 2: Open Predicates (1/3) ‐ CWA
Parent(pam, bob)
Parent(bob, pat)kate
Parent(kate, pat)
Parent(kate, ann)
ann
Ancestor(X,Y) <‐ Parent(X,Y),
Ancestor(X,Z) <‐ Parent(X, Y), Ancestor(Y, Z)

pam

bob

pat

?‐ Ancestor(pam,Ancestor(pam pat)yes?‐ Ancestor(pam, ann)
No7

Point 2: Open Predicates (2/3)
pamParent(pam, bob)
Parent(bob, pat)katebob
Parent(kate, pat)
Parent(kate, ann)annpatAncestor(X,Y) <‐ Parent(X,Y),
Ancestor(X,Z) <‐ Parent(X, Y), Ancestor(Y, Z)
Parent(X,W)/open <‐ Parent(X,Y), Parent(Z, Y), Parent(Z, W)

Yes!

?‐ Ancestor(pam, pat)yes?‐ Ancestor(pam, ann)
Yes!

Point 2: Open Predicates (3/3) ‐ Details• Can have open attributes
keyword(x y)/open<‐ img(x)keyword(x,y)/open<• Possible to actively ask people
keyword(x,y)/open{group}:active• Can be an open “fact”
img(x)/open• Open for a specified set of humans
keyword(x,y)/open{group}8

Point 3: Data Games (1/2)
Challenge: Obtaining appropriate values in thepresence of human data sources.
Approaches :• Majority Voting• Probabilistic Approach*• Approach Using Item
Item‐ResponseResponse TheoryTheory*• Data Games*Mentioned in [Parameswaran et al. 2011]

Point 3: Data Games (2/2)• A concept to connect data flows with reward systems• Models each human as a rational data source who behaves
rationally according to the rewards given in the games.
Rational
Ril
Data Sources

Data

Data GameRewards• This framework gives a possibility to use the game theory as ananalysis tool.
• We provide some built‐in data games to define the reward andaggregation to produce values.

9Games
A game can be described with players, theiroptions, and payoffsEx1)) ppayoff
y matrix of a simple
p ESP Game
Player A＼B
Term A

Term A(1, 1)

Solution

Term B(0,0)

Term B(0,0)(1,1)

Solution

E 2) payoff
Ex2)
ff matrix
t i off a Q&A Service
S i Game
G
Player A＼B
Best Answer

Best Answer Worst Answer(15, 15)(30, 0)
Solution

Second Best Answer(0,30)(0,30)

Human‐as‐a‐data‐sourceCyLog

QL
DB view

Human‐as‐a‐data‐source• Accept every input “as is”• Implicit human‐id attributekeywords(hid, img, keyword)• Key attributes are important

Crowd‐as‐a‐data‐source
The DB view has the values
computed by combining
the inputs from thecrowd

10Game Aggregations
Duplicate Game

Player A＼B

Term A

Term B

Term A(1, 1)
Term A
(0,0)

(0,0)

Term B

PathTable p(1,1)
Term B

Duplicate(p)*Duplicate_v(p)Built‐in Game Aggregations
The following game aggregations are different to eachother in what are chosen for the output values and in how
payoff points are given to players.
• Duplicates (Values given by more than one player)• Majority (Values given by the largest number of people)• Unique (Values given by only one person)• Intersection (Values given by everyone)• Union (All values given by any player)• First （The value given first）

11

Discussions on Data Games• The data game concept is widely applicablebeyond the real “games,” since there are many
applications in which connecting dataflow withfeedback to people is the key.
• How to deal with payoff points depends on
applications• We believe that the data game is a general
concept– The games can be used to obtain the “correct” values,– They can be used to obtain values chosen based onother criteria– The data games can handle wider situations beyond
the AMT‐style crowdsourcing setting.

Example: Little Known Hot Spots• Show (possibly a part of) the list of restaurant• LabelL b l eachh restauranttt as– L1: Good– L2: Not good– L3: I have never been there• Give more points to people who labeled as“Good” those restaurants that are good on
average but labeled as “I have never been
there” by many people

12

Example: The ESP game in CyLog
Data:
M t d t I
MetadataInput(file,t(fil kkeyword)/opend)/<‐ File(file)Fil (fil )Metadata(file, g(file):keyword)/game:g(file) <‐ File(File)
Game AggregationGame Guard
Game:g(file)@time(10): Duplicate, {MetadataInput}
Game Skolem Function

Game AggregationGame Termination

Relations for the PathTable

An Attempt to Define the Semantics ofCylog Programs
Consequences
Strategies S1Consequences
Program P

Strategies S2

FactsRules
Best Strategies S3Best Strategies S4

Rational Consequences
The Semanticsof P
Rational Consequences13

Outline
1. Backgroundg
2. CyLog
3. Prototype System
4. Related Work and Discussions

Prototype System
PeoplePrograms

Results
PayoffQueries

Mail
Server/Twitter

CyLog
Interpreter

Web
ServerQueries• External functions are allowed toimplement complex algorithms andcustomized user interface• Modules to work with AMT isunder development

ServerRelations

Data• The current working version of our
prototype system provides adefault function to generate HTMLforms for open predicates

GeneratedWeb Pages

14

Outline
1. Backgroundg
2. CyLog
3. Prototype System
4. Related Work and Discussions

Related Work(1/3)
Recent Work: Qurk, sCOOP/hQuery, CrowdDB• Common or Similar Points– Declarative approach– Concepts similar to open predicates/attributes(hPred, CNULL,…)• Points Unique to CyLog– Introduce rational data sources– Data games as a means to obtain appropriate values– Takes the human‐as‐a‐data‐sources approach toincorporate data games in the language.

15Related Work(2/3)
Collective Knowledge base [Richardson, Domingos 2003]• Common or Similar Points– Rules and facts can be added by humans– Feedback to contributors• Points Unique to CyLog– Designed for data‐centric applications in the presence ofhuman data resources– Open predicates/attributes, data games

Related Work(3/3)
Turkalytics [Heymann, Garcia‐Molina, 2011]– An analytics tool for Human Computation

Can be used to tune and optimize CyLog
programs when executed with the Amazon
M h i l Turk.
Mechanical
T k16

Open Problems• Optimization issues• AdvancedAdd mechanisms
h iforf playerlselectionl ti• Development of various types of data‐games• Design theory• Definitive rationality
Some of the above are addressed in the related
work

The Current Status• Updating and extending the syntax of CyLog– The basic idea is the same
– Nest Structure for the concise description– Support of Status values for complex games• Developing a software platform open to public17

Summary• CyLog: Datalog‐like declarative language• Introduces the concept of rational data
source as a new typetoff WWebbddatat source• Open predicates/attributes to interact withpeople• Data games for obtaining appropriate values

The FusionCOMP Project:
http://www.kc.tsukuba.ac.jp/~mori/isbuilder/18