Loading...

An Extreme Tagging System as a Game With a Purpose

Master's Thesis 2012 86 Pages

Computer Science - Software

Excerpt

Contents

1 Introduction
1.1 Structure of this Work

2 Background and Related Work
2.1 Background
2.1.1 Collaborative Tagging
2.1.2 Extreme Tagging
2.1.3 Games With a Purpose
2.1.4 Mathematical Model For GWAPs
2.2 Related Work
2.2.1 Semantics From User Data
2.2.2 Games With a Purpose

3 Problem
3.1 eXTS
3.1.1 The First Version of eXTS
3.1.2 The Second Version of eXTS
3.2 Theoretical Problems
3.3 Problems derived from eXTS
3.3.1 Setup of the Evaluation Run
3.3.2 Results of the Evaluation Run
3.3.3 Problems Derived From the Results of the Evaluation
3.4 Purpose

4 Proposed Solution
4.1 The Minigames
4.1.1 Racing Game
4.1.2 Falling Words Game
4.1.3 Door Opening Game
4.2 Order of Games
4.3 The Overall Flow of the Game
4.4 Further Incentives

5 Implementation
5.1 General Considerations
5.2 Data Representation
5.3 Frameworks
5.3.1 jMonkeyEngine 3.0
5.3.2 Golden T Game Engine
5.3.3 Game Gardens Framework
5.4 Implementation of the Racing Game
5.4.1 The Distributed Object
5.4.2 The Game Manager
5.4.3 The Game Controller and the View Classes
5.4.4 Computer Controlled Players
5.5 Implementation of the Falling Words Game and the Door Opening Game

6 Mathematical Modelling
6.1 A Formal Model for the Racing Game
6.1.1 The Game Problem Domain
6.1.2 The Game Rules
6.1.3 The Flow of the Game

7 Evaluation
7.1 Setup of the Evaluation Run
7.2 General Conclusions of the Evaluation
7.3 Analysis of the Productivity
7.4 Evaluation of the Questionnaire
7.4.1 General Aspects
7.4.2 Evaluation of the Fun Factor
7.4.3 Evaluation of the Ease of Use
7.4.4 Miscellaneous Results of the Questionnaire

8 Summary and Conclusion
8.1 Summary
8.2 Future Work

Bibliography

List of Figures

A Running the Code
A.1 Server Side
A.2 Client Side
A.3 Playing the Game

B Additional Figures

CHAPTER 1 Introduction

The Semantic Web, as proposed by Tim Berners-Lee as a way of making the Web machine processable[3], is “now starting to come to the public’s attention”[10]. This statement by Jim Hendler is today 4 years old but the great breakthrough of the Semantic Web is yet to come. A reason for the pending success of the Semantic Web may be a chicken-and-egg problem. As Hendler puts it “Web users will not mark up their Web pages unless they perceive value in doing so, and tools to demonstrate this value will not be developed unless Web resources are marked up”[9]. This can be transferred to all areas of the Semantic Web and is not restricted to the mark-up of Web pages: As long as there is no data, there will be no tools and vice versa. Although some effort is invested into this problem, it is still far from being solved.

Most tasks of creating data for the Semantic Web cannot be automated and thus require human work[19]. On the other hand those tasks often are quite monotonous. The upcoming notion of Games With a Purpose (coined by[21] ) may provide a solution to this problem. As a form of Gamification (“the use of video game elements in non-gaming systems”[7] ) Games With a Purpose try to encapsulate tasks into games. By doing so they can bring more fun into monotonous tasks like those required for the creation of semantic data.

This master’s thesis aims at developing a Game With a Purpose, which can be used as a replacement for a tagging system. Tagging in the context of the Semantic Web (and the Web2.0, too) refers to the process of associating keywords with resources, for example in order to provide a better searchability of these resources. This Game With a Purpose shall support the creation of a domain ontology with the help of the data produced by the players of the game. By doing so it is a try to contribute to the solution of the chicken-egg problem of the Semantic Web by offering an alternative way of supporting users in the generation of semantic data.

1.1 Structure of this Work

This master’s thesis is structured as follows: In chapter 2 I present some background knowledge and the basic concepts used in this thesis. This chapter also provides an overview of related work. Chapter 3 contains the problem definition for this master’s thesis and a more detailed description of the purpose of this work. Chapter 4 describes in detail the solution I propose to solve the problems outlined in the previous chapter. In chapter 5 I picture the implementation of the proposed solution. To render the solution more precisely, in chapter 6 I also give a formal model for the developed game with the help of a framework (which is presented in chapter 2).

To assess whether the developed solution provides an advantage over a non-gaming approach to a tagging system, chapter 7 contains an evaluation of the effectiveness and the fun factor of the implemented game compared to a non-gaming implementa- This thesis concludes with a summarisation of this work in chapter 8, where I also point out aspects that are not covered in this work, but are in my opinion worth looking into for future work.

CHAPTER 2 Background and Related Work

This chapter introduces background knowledge that is helpful to understand the remains of this thesis (section 2.1). It also qualifies the research context by giving an overview of related work done in the field of this thesis in section 2.2.

2.1 Background

This section describes the basic concepts this thesis builds on. It introduces the idea of Collaborative Tagging (section 2.1.1) and an extension to it that allows for more flexibility, the concept of Extreme Tagging (section 2.1.2).

Section 2.1.3 gives an introduction into the notion of Games With a Purpose. And section 2.1.4 explains a mathematical model that can be used to describe Games With a Purpose in a formal way.

2.1.1 Collaborative Tagging

Collaborative Tagging Systems (CTS) are a trend that evolved from the Web2.0. In a CTS users are given the possibility to associate content with keywords, also called “tags”, allowing them to later use these keywords for navigating, filtering or searching this content[8]. Examples for CTS are Delicious[1] where users can tag bookmarks, Flickr[2] allowing users to tag pictures and CiteULike[3] for tagging scientific publications.[14] introduce a formal model for such a CTS by representing it through a hypergraph where the set of vertices is partitioned into three disjoint sets:

illustration not visible in this excerpt

Where U is the set of users, R the set of resources and T the set of tags. An annotation then is an element of the set A with:

illustration not visible in this excerpt

The hypergraph representing the CTS then is defined as G with:

illustration not visible in this excerpt

2.1.2 Extreme Tagging

[17] proposed an extension to the hypergraph model for a CTS, treating tags as resources and by this allowing users to tag tags and also tag relations between tags. They call their approach Extreme Tagging System (ETS). The CTS formal model is then extended as follows:

illustration not visible in this excerpt

Similar to CTS this can be represented as a hypergraph:

illustration not visible in this excerpt

A is the set of assignments as in a normal CTS and D is the set of directional annotations occurring when a relation between two entities has been tagged. According to the authors

ETS give an easy way of acquiring knowledge and building comprehensive knowledge bases.

2.1.3 Games With a Purpose

Although computers and computation have been and still are being heavily developed and improved, there are still a lot of tasks computers are unable to solve[19]. Especially when it comes to semantics and meanings of things algorithms are dependent on human input. In the domain of the Semantic Web there are a lot of tasks that computers cannot yet solve on their own. This includes tasks like tagging of resources, particularly nontextual multimedia resources like images, audio and videos, locating objects in videos and the creation or alignment of ontologies [20, 16]. Briefly speaking tasks that require creativity.

The authors of[21] propose to solve such tasks by the “channeling of human brainpower through computer games”. Their suggestion is to wrap tasks that need “human computation” in a computer game. This way users can have fun playing the game while - as a side-effect - they solve tasks computers are unable to perform. The authors coined the term “Games With a Purpose” (GWAPs) for this class of games. GWAPs have evolved into an own area of research and can be seen as a part of the recently becoming more and more important “Gamification” field of study. According to Deterding et al. Gamification “is an informal umbrella term for the use of video game elements in non-gaming systems to improve user experience (UX) and user engagement”[7].

In[21] von Ahn and Dabbish propose three structural templates for the transformation of a problem into a GWAP, which they deduced from the exploration of many GWAPs they created. They named these templates output-agreement games, input-agreement games and inversion-problem games. I describe these templates in short in the following sections as they are a basis for the remains of this thesis. All three templates have in common that the resulting games are played by two randomly chosen players.

2.1.3.1 Output-agreement Games

In an output-agreement game both players are shown the same input, e.g. a word they have to tag. The instructions for the players are to produce the same output (e.g. tags) as their partner. The players have no way of communication, so the best way for the players of generating the same output is to enter output that is related to the input.

2.1.3.2 Input-agreement Games

In an input-agreement game both players are shown an input. The game knows if these inputs are the same or not, but the players don’t. The task for the players is to determine if they are both shown the same or different inputs. To achieve this goal their best way is to produce output that is related to their input. By doing so they enable their partner to judge correctly.

2.1.3.3 Inversion-problem Games

In an inversion-problem game the two players have different roles. One is the “describer” and the other one is the “guesser”. The describer is shown an input. Her task is to describe the input (by producing outputs) in a way that enables the guesser to correctly determine the input. The guesser only sees the outputs generated by the describer.

2.1.4 Mathematical Model For GWAPs

[5] are to my best knowledge the first and up to now the only ones to propose a formal mathematical framework for modelling social games (or GWAPs). In this section I want to give an overview over this framework as far as it is applicable to the game that is developed in the course of this thesis and in Chapter 6.1 I then apply it to my game.

2.1.4.1 Definitions

The authors make the following definitions:

Definition 1. A data D is an object with a data type T , where T ∈ {text, image, video, sound, U RL}, and a set of attributes A (metadata).

Definition 2. A social game (or GWAP) is a 4-tuple (SGP D, GR, GF, AN S) where

Abbildung in dieser Leseprobe nicht enthalten[1]

The “answer extraction procedure” counts for each answer to a problem e given during all rounds of all games the number of occurrences. If the count is above (or equal) the threshold τ, the answer is considered correct.

The authors give some more definitions (e.g. for “actions” and “roles”), but for my purpose the above cited are sufficient.

2.1.4.2 The Flow of the Game

With the definitions given in the previous section the flow of a game is modelled as follows:

1) Select players and assign roles to them by pSel ().
2) Pick a problem e ∈ E that the players need to solve by eSel ().
3) Collect outputs O from players’ actions.
4) If verification by G () is not passed for the generated outputs, go to step 3.
5) If time passed ≤ tM ax, go to step 2.
6) Increase the reward of the players according to their outputs.

The authors call steps two to three a “segment”, which is what I call a “round” in this thesis. A segment is the period of time in a game in which players work on a specific problem e.

2.1.4.3 Refinement of Game Templates

With the above definitions made, the authors are able to substantiate the definitions of game types given by[21] (and explained in section 2.1.3.1 and following of this thesis). For example an output-agreement game is modelled in the following way:

- There are two players, so pN um = two-player.

- Both players have the same (and only) role and are shown the same input, so [Abbildung in dieser Leseprobe nicht enthalten].

- For a given problem e ∈ E there is a set of correct answers [Abbildung in dieser Leseprobe nicht enthalten] has a set of potential outputs [Abbildung in dieser Leseprobe nicht enthalten] hasasetofpotentialoutputs [Abbildung in dieser Leseprobe nicht enthalten].
- The players need to agree upon the same outputs. The larger the intersection [Abbildung in dieser Leseprobe nicht enthalten] is, the better is the chance of the players to achieve the winning conditions, and the better is the chance that [Abbildung in dieser Leseprobe nicht enthalten] (theplayers agree upon a correct answer).

As the example of the model for an output-agreement game shows, this modelling frame- work allows for a more precise definition of different elements in the area of GWAPs. Besides to refining the game templates the framework can be used to map a whole GWAP to a formal model, providing a way of giving a very precise description of this GWAP.

2.2 Related Work

This section gives an overview over a selection of related work done in the contextual surroundings of this thesis. As the foundations for this thesis are twofold, the previous work presented in this section covers two fields. One is the learning of semantics from user data. In section 2.2.1 I highlight some recent development in this field of research.

The second are Games With a Purpose. Section 2.2.2 gives an overview over different kind of GWAPs and briefly describes them.

2.2.1 Semantics From User Data

The scientific core of my work is the learning of semantics from user data - or more specific from tags. The approach I describe in this thesis is a step in this direction. The recent research going on in this field is briefly discussed in this section.

There is a variety of approaches that try to get some semantics into tags by analysing the relations between tags. Many of them do this by clustering related tags according to tag co-occurrence.

[2] use an undirected graph with tags as vertices where an edge between two vertices represents that both tags co-occur and the weight of the edge is the number of co-occurrences.

They then use a spectral clustering algorithm to group related tags. tion.

[23] represent the semantics of a tag as a “multi-dimensional vector where each dimension represents a category of knowledge”. They then use the log-likelihood based on tag co- occurrences to form groups of related tags. Both approaches don’t take into account the type of relation between tags.

As mentioned before[17] introduce a way that lets users explicitly formulate the kind of relation between tags. Another approach proposed in[1] is to derive the relation between tags from their “implicit” relation. They take as input a set of clustered tags (as produced e.g. by the methods discussed before) and then map each tag of a cluster to concepts of online available ontologies. If they discover relations between those ontology concepts they derive relations for their folksonomy. This way they want to generate “explicit semantic relations” between tags by leveraging the “implicit” relations given by a cluster of tags and ontologies.

2.2.2 Games With a Purpose

The practical foundations for my approach are GWAPs. To give a short overview over the state of the art of GWAPs I briefly discuss some of the recent developments in this field.

Up to now there are already a variety of GWAPs for very different problems. I want to give some examples for GWAPs that are used for the purpose of tagging or annotating things, for folding proteins, for collecting geospatial data and for 3D image reconstruction.

On the sector of games used for the tagging and annotation of things there are a lot of approaches for different kind of things.[20] developed the “ESP game” that lets players tag images. Two players are randomly assigned to a game and are shown the same image.

Their task is to guess what their partner is typing for that image. When both players typed the same string they receive points and the next image is shown.

[16] propose the GWAP “OntoTube” for the annotation of videos. Here the players are shown the same YouTube video and have to answer a set of questions regarding the video like “What is the genre of the video?” and “What is the language of the video?” The players receive points for questions they chose the same answer for.

“TagATune”, a game developed by[12], is used to annotate music and sound. Similar to the ESP game two randomly paired players are presented the same sound and have to guess what their partner is typing. As the authors state sounds are more ambiguous than images and to cope with that difficulty the players are shown a category word (e.g. “mood” or “movie genre”) that shall limit their typed description to that category. Players get points for agreed descriptions.

[4] present “Collabio” a GWAP that lets players tag other players to collect descriptive tags for individuals. The game is embedded in Facebook. Players are asked to tag their friends. To motivate the players they see a tag cloud of tags that other players assigned to a person. Tags that other players entered are masked until the player herself guesses that tag. For each entered tag the player gets an amount of points that is proportional to the number of players that entered this tag.

A totally different approach led to the game “Foldit” developed by[6]. Here the problems the players have to solve have a much higher complexity: The task for the players is to fold proteins to find a structure with an optimum of energy. The players are shown a graphical representation of a protein that is not in its energetically optimal state. To make the game playable for players with no scientific background and knowledge of the biochemistry domain the players are trained in some tutorial levels. They can drag and rotate different parts of the protein and use some predefined tools to optimize the protein structure. The less energy the protein has the more points the player gets.

The authors of[13] transfer the GWAP paradigm to mobile devices. With their game “CityExplorer” they encourage players to collect geospatial data that can be used for location-based services. The game is based on the board game Carcassonne but the play takes place in the real world, typically in a city. The city is divided into squares by a grid. The players can set markers on locations of defined categories like “church”, “art” or “cafe”. To set a marker a player needs to take a photo of the location, give it a name, approach it as close as possible (for the GPS location) and select a category. At the end of the game players get points for every square they dominate, which means they have the most markers in them, and for placing the most markers of a category on the whole game board.

The game “PhotoCity” ([18] ) aims at collecting photos of real world locations that can be used for building 3D models with an automatic reconstruction. As for this purpose it is not sufficient to only have front-facing views of a location the players need to be directed to take photos of parts of a location, which is not yet modelled detailed enough. The authors encourage the players to do so with the following game mechanics: The players are provided with a virtual map that shows the locations that need to be photographed. The task for the players is to capture virtual flags that are anchored in the real-world locations and by doing so take the ownership of this location. The more new points a photo adds to the model the more points a player gets for submitting this photo. A flag is held by the player with the most points at that flag.

CHAPTER 3 Problem

In the previous chapter I outlined what ETS are and why they can be useful to build knowledge bases. This chapter first describes two implementations of the concept of ETS (section 3.1). In section 3.2 I point out two problems that I found by analysing the theory of ETS. Section 3.3 then shows problems that can be drawn from the results of an evaluation of the latter of the implementations mentioned before. This chapter concludes with the conceptual formulation for this master thesis (in section 3.4) that I conclude from the discussed problems.

3.1 eXTS

This section describes two different implementations of the concept of ETS that were developed as a proof of concept. The first implementation is depicted in section 3.1.1. The second version that is meant as an improvement of the first is pictured in section 3.1.2.

3.1.1 The First Version of eXTS

In order to test the formalism of ETS a simple prototype implementing this formalism was developed by the Corporate Semantic Web working group, called eXTS. This prototype is realised as a web application for the Apache Tomcat application server. The front-end is implemented with JSPs and the design rule for the GUI is to keep it as simple as possible.

The layout of the website is oriented on well-known tagging sites like those mentioned in section 2.1.1 with the required extension of enabling the users to enter relations between entities and tags (see section 2.1.2).

To allow the usage of the back-end from multiple different front-end implementations it is encapsulated in web services. Accordingly the communication between back-end and front-end is done through these web services. The data is stored in an HSQLDB[1] which is integrated in the application, so no external database is used.

illustration not visible in this excerpt

Figure 3.1 gives an overview over the system architecture of the first eXTS version.

The goal of eXTS is to help in the creation of user ontologies that are tailored to the domain (field of expertise) of a user group. To allow this, a user has to register an account in the system before she is allowed to use it. With every user account is stored the domain of the user and every user only sees tags according to her domain. This allows the system to generate domain specific ontologies from the collected data.

For every domain a set of initial words is needed. This set can come from existing sources like the ones mentioned in section 2.1.1. When a user wants to tag, she is presented a randomly chosen word from her domain. After submitting the tag, the user is asked via a pop-up for the kind of relation the word and the tag have. However as said before, the eXTS is only a prototype and is meant for internal uses only. Thus it is not publicly tested with a large user group but only by some members of the developing working group. To make the system ready for a larger public test group, two important enhancements are required:

- The system has no real multi-user capability. There can be different users, but only one can be logged in at the same time. So a real multi-user capability needs to be realised.
- The way the system asks the user for the relation between a word and a tag is sensed too complicated and to hard to understand by the few users that tested it. So an easier way for this task is needed.

Also the initial word sets are hard-coded. For flexibility they should be read dynamically from the database.

illustration not visible in this excerpt

Figure 3.1: This UML component diagram gives an overview over the first version of the eXTS system.

As the implementation of the prototype is not developed for being easy to maintain or extent, in order to integrate the new features a re-implementation seems the easiest way. The functionality of the web services was never used and is not intended to be used in the future, so with the re-implementation the architecture is no longer based on web services. This simplifies the implementation and reduces the complexity of the server-side architecture.

3.1.2 The Second Version of eXTS

With the issues discussed in the previous section it becomes obvious that a new version of the eXTS is required in order to let a greater group of users test the ETS concept. This section describes the implementation of this new version and compares it to the first version.

The second version of the eXTS is (like the first version, too) implemented as a web application. The front-end is realised with JSPs, keeping the same layout as the first version. The back-end is composed of plain java classes and some servlets. The front-end directly accesses methods of the back-end classes. The back-end comprises a real multi-user capability. The user permission handling is done with the Java EE security services and is provided by the application server[1]. This gives an easy way of user management. In a configuration file the server is told, which sites of the application need authorization. If a user visits a site, that needs specific rights, the user is asked to log in. Only if the user logs in with an account that has the required rights to see the site, it is accessible for her. In another configuration file the server is given a database table that contains the registered users and their rights. That is all that needs to be done; the application server handles the rest.

To give the users a more comprehensive way of specifying the relation between a word and a tag they are presented with two input fields instead of one. One is for the tag and one for the relation (labelled accordingly). This supersedes the need for a pop-up to ask for a relation after a tag has been submitted. Figure 3.2 gives an impression of the resulting tagging site.

Like in the first version the data is stored in a database. But as opposed to the first version, the database is not integrated in the application, but is an external MySQL database. The

illustration not visible in this excerpt

Figure 3.2: This is a screenshot of the second version of the eXTS implementation, showing the user interface for tagging entities.

back-end communicates with the database with the help of an object-relational mapper. I use Hibernate[1] and JPA[2] with annotations for this purpose. This allows me to let all the database handling be done automatically by the object-relational mapper and minimizes the need for native SQL queries in the code. For example there is a class (a bean to be precisely) Assignment that represents an assignment a user can create. With the JPA annotation @javax.persistence.Entity this class is marked as an entity class. This gives an easy way of persisting instances of this class to the database and loading instances of this class from the database. To store an instance in the database JPA provides the method persist(). To load an instance from the database the method find() can be used, which is given the class and the primary key of the instance to be loaded and returns a new Java object representing it.

As said in the previous section the initial set of words is dynamically loaded from the database and no longer hard-coded. This allows a simple way of adding new domains with their own set of initial words.

Figure 3.3 gives an overview over the system architecture of the second version of the eXTS.

In the following whenever is talked about the eXTS it refers to the second version of the eXTS as it is the basis for the remains of this thesis.

[...]


1 http://www.delicious.com/

2 http://www.flickr.com/

3 http://www.citeulike.org/

1 The authors let GF be a set rather then a 6-tuple, but there seems to be no explicit reason for that decision. And as all other definitions are tuples I think it is just a typing error and decide to let GF be a tuple.

1 http://hsqldb.org

1 I use Apache Tomcat, but any other application server should be suitable.

1 http://www.hibernate.org/

2 http://www.oracle.com/technetwork/java/javaee/tech/persistence-jsp-140049.html

Details

Pages
86
Year
2012
ISBN (eBook)
9783656280149
ISBN (Book)
9783656281047
File size
20 MB
Language
English
Catalog Number
v200644
Institution / College
Free University of Berlin – Institut für Informatik
Grade
2,3
Tags
Semantic Web Tagging Extreme Tagging Extreme Tagging System Collaborative Tagging Collaborative Tagging System Games With a Purpose Serious Games Game With a Purpose Serious Game Computer Science Tag Tags Taxonomy Folksonomie Crowd Computing Social Annotation Annotation

Author

Share

Previous

Title: An Extreme Tagging System as a Game With a Purpose