Contributions published at Dynamic and Distributed Information Systems (Abraham Bernstein)

In this paper we present the programming language and framework CrowdLang for engineering complex computation systems incorporating large numbers of networked humans and machines agents. We evaluate CrowdLang by developing a text translation program incorporating human and machine agents. The evaluation shows that we are able to simply explore a large design space of possible problem solving programs with the simple variation of the used abstractions. Furthermore, an experiment, involving 1918 different human actors, shows that the developed mixed human-machine translation program significantly outperforms a pure machine translation in terms of adequacy and fluency whilst translating more than 30 pages per hour and that the program approximates the professional translated gold-standard to 75% using the automatic evaluation metric METEOR. Last but not least, our evaluation illustrates that our new human computation pattern staged-contest with pruning outperforms all other refinements in the translation task.

Crowdsourcing markets like Amazon’s Mechanical Turk or Crowdflower are quickly growing in size and popularity. The allocation of workers and compensation approaches in these markets are, however, still very simple. In particular, given a set of tasks that need to be solved within a specific time constraint, no mechanism exists for the requestor to (a) find a suitable set of crowd workers that can solve all of the tasks within the time constraint, and (b) find the “right” price to pay these workers. In this paper, we provide a solution to this problem by introducing CrowdManager – a framework for the combinatorial allocation and pricing of crowdsourcing tasks under budget, completion time, and quality constraints. Our main contribution is a mechanism that allocates tasks to workers such that social welfare is maximized, while obeying the requestor’s time and quality constraints. Workers’ payments are computed using a VCG payment rule. Thus, the resulting mechanism is efficient, truthful, and individually rational. To support our approach we present simulation results that benchmark our mechanism against two baseline approaches employing fixed-priced mechanisms. The simulation results illustrate that our mechanism (i) significantly reduces the requestor’s costs in the majority of settings and (ii) finds solutions in many cases where the baseline approaches either fail or significantly overpay. Furthermore, we show that the allocation as well as VCG payments can be computed in a few seconds, even with hundreds of workers and thousands of tasks.

Recent work on searching the Semantic Web has yielded a wide range of approaches with respect to the style of input, the underlying search mechanisms and the manner in which results are presented. Each approach has an impact upon the quality of the information retrieved and the user’s experience of the search process. This highlights the need for formalised and consistent evaluation to benchmark the coverage, applicability and usability of existing tools and provide indications of future directions for advancement of the state-of-the-art. In this paper, we describe a comprehensive evaluation methodology which addresses both the underlying performance and the subjective usability of a tool. We present the key outcomes of a recently completed international evaluation campaign which adopted this approach and thus identify a number of new requirements for semantic search tools from both the perspective of the underlying technology as well as the user experience.

The Semantic Web defines a way to publish data that is semantically linked to the World Wide Web. The advantages are that computer programs can follow these links and assemble data on their own, without human intervention but with human initiation. In the domain of statistics providing linked data would be a natural step towards open access to information. This thesis uses data from the Federal Statistics Office of Switzerland in a semi-automated process of semantically linking that data. Also four different tools with different methods for automatic matching of data were evaluated. It was found out, that for automated data linking in a manner acceptable for adoption, the raw data is not yet prepared enough, and the matching tools are not sufficiently developed.

Können Videospiele moralische Werte vermitteln? Dieser Gedanke widerspricht einer öffentlichen Debatte, die oft ganz selbstverständlich von einem negativen Einfluss solcher Spiele auf die Moral der Spieler ausgeht. Dieses Buch will die meist verkürzt geführte Diskussion aufbrechen und um neue Themen erweitern. Ausgehend von der Beobachtung, dass moderne Videospiele auch ethische Themen in ihre Spielgestaltung einbauen, untersuchen die Autoren Möglichkeiten und Grenzen der Konstruktion eines «Serious Moral Game» – also eines Videospiels, mit dem man das moralische Handeln des Spielers erfassen und reflektieren kann. Das Buch «Serious Moral Games» zeigt auf, dass in Videospielen ein bislang wenig ausgeschöpftes Potential steckt, das sowohl für die Moralforschung als auch für die Spieler selbst interessant ist: Videospiele als Instrumente, um mehr über sich und das eigene moralische Empfinden und Wertschätzen zu erfahren.

Die empirische Erforschung des moralischen Entscheidens und Handelns stützt sich zunehmend auf Patienten, die selten auftretende Hirnläsionen in bestimmten Regionen des Frontallappens aufweisen. Dies stellt sowohl die neuroethische Frage zur Bedeutung solcher Erkenntnisse für unser Verständnis von Moral als auch die medizinethische Frage nach dem Umgang mit solchen Patienten im Kontext von Forschung und Klinik. Basierend auf einer Auswertung der Literatur über den Zusammenhang von Hirnläsionen und Sozialverhalten sowie gut 40 Jahren eigene Erfahrung in der neuropsychologischen Abklärung zeigen wir zwei Wahrnehmungslücken: Zum einen propagieren diese Studien einen Neurodeterminismus des menschlichen Moralverhaltens, der aber wissenschaftlich nicht ausreichend untermauert ist. Zum anderen zeigt sich eine Verschiebung des Forschungsinteresses weg von einem klinischen Fokus hin zur neuropsychologischen Grundlagenforschung über das menschliche Moralvermögen. Letzterer Punkt ist insofern bedeutsam, als dass der klinische und alltägliche Umgang mit solchen Patienten schwierig ist und diese Menschen die Grenzen der Anwendung klassischer medizinethischer Prinzipien wie Autonomie und Fürsorge aufzeigen.

Deep brain stimulation (DBS) is increasingly investigated as a therapy for psychiatric disorders. In the ethical evaluation of this novel approach, incidence and impact of side effects (SE) play a key role. In our contribution, we analyze the discussion on SE of DBS of the subthalamic nucleus (STN)—a standard therapy for movement disorders like Parkinson's disease (PD)—based on 66 case reports, 69 review papers, and 347 outcome studies from 1993 to 2009. We show how the DBS community increasingly acknowledged the complexity of STN-DBS side effects. Then we discuss the issue of study quality and the methods used to assess SE. We note that some side effects are the subject of conflicting evaluations by the different stakeholders involved. This complicates the ethical controversy inherent in any novel treatments for diseases that involve psychiatric aspects. We delineate how the lessons from STN-DBS could guide future DBS applications in the field of psychiatry.

QUESTIONS UNDER STUDY: Deep brain stimulation (DBS) has become a standard therapy for some forms of severe movement disorders and is investigated for other neurological and psychiatric disorders, although many scientific, clinical and ethical issues are still open. We analyse how the Swiss DBS community addresses these problematic issues and future challenges. METHODS: We have performed a survey among Swiss DBS centres and a Delphi study with representatives of all centres and further stakeholders related to the topic. RESULTS: The current DBS infrastructure in Switzerland consists of seven facilities. About 850–1,050 patients have received a DBS system in Switzerland for various indications since its advent in 1976. Critical issues like patient selection and dealing with side effects are in accordance with international standards. There are indications of a conservative referral practice in Switzerland for DBS interventions, but the data available do not allow verifying or refuting this point. CONCLUSIONS: Issues to investigate further are whether or not there is an unmet medical need with respect to DBS, long-term medical and psychosocial sequelae of the intervention, conditions for enhancing the (research) collaboration of Swiss DBS centers, and the effect of the recent decision to reduce the number of DBS centres to 4 (resp. possibly 3) on the potential of this therapeutic approach.

Software quality is an important factor since software systems are playing a key role in today’s world. There are several perspectives within the field on software quality measurement. One such frequently used measurement (or metric) is the number of defects that could result in crashes, catastrophic failures, or security breaches encountered in the software. Testing the software for such defect is essential to enhance the quality. However, due to the rising complexity of software manual testing was becoming extremely time consuming task and consequently, many more automatic supporting tools have been developed. One such supporting tool is defect prediction models. A large number of defect prediction models can be found in the literature and most of them share a common procedure to develop the models. In general, the models’ development procedure indirectly assumes that underlying data distribution of software systems is relatively stable over time. But, this assumption is not necessarily true and consequently, the reliability of those models is doubtful at some points in time. In this thesis, therefore, we presented temporal or time-based reasoning techniques that improve the reliability of prediction models. By exploring four open source software (OSS) projects and one cost estimation dataset, we first disclosed that real-time based data sampling compared to random sampling improves the prediction quality. Also, the temporal features are more appropriate than static features for defect prediction. Furthermore, we found that the non-linear models are better than linear models for defect prediction. This implies, the relationship between project features and the defects is not linear. Further investigations showed that prediction quality varies significantly over time and hence, testing a model in one or few data samples is not sufficient to generalize the model. Specifically, we unveiled that the project features influence the model’s prediction quality and therefore, the model’s prediction quality itself can be predicted. Finally, we turned these insights into a tool that estimates the prediction quality of models in advance. This tool supports the developers to determine when to apply their models and when not.Our presented temporal-reasoning techniques can be easily adapted to most of the existing prediction models for enhancing the reliability of those models. Generality, these techniques are easy-to-use, extensible, and show high degree of flexibility in terms of customization to real applications. More important, we provided a tool that supports the developers to make a decision about their prediction models in advance.

This master thesis expands on previous work concerned with offline Employee fraud de-tection. During the course of this thesis we develop algorithms that are capable of finding the fraudulent pattern identified in the previous work on RDF streams. Our algorithm employs a multi-level filtering and matching scheme capable of coping with a certain amount of memory restriction. We tested a prototypical implementation and found that precision and recall ratios are affected by different parts of our algorithm and that it scales linearly in terms of memory and wall time. We concluded that with further optimization, it should be capable of real-time fraud detection.

Today, human computation systems are mostly used for batch processing large amount of data in a variety of tasks (e.g., image labeling or optical character recognition) and, often, the applications are the result of extensive lengthy trial-and-error refinements. A plethora of tasks, however, cannot be captured in this paradigm and as we move to more sophisticated problem solving, we will need to rethink the way in which we coordinate networked humans and computers involved in a task. What we lack is an approach to engineer solutions based on past successful patterns. In this paper we present the programming language and framework CrowdLang for engineering complex computation systems incorporating large numbers of networked humans and machines agents incorporating a library of known successful interaction patterns. CrowdLang allows to design complex problem solving tasks that combine large numbers of human and machine actors whilst incorporating known successful patterns. We evaluate CrowdLang by programming a text translation task using a variety of different known human-computation patterns. The evaluation shows that CrowdLang is able to simply explore a large design space of possible problem solving programs with the simple variation of the used abstractions. In an experiment involving 1918 different human actors we, furthermore, show that a mixed human-machine translation significantly outperforms a pure machine translation in terms of adequacy and fluency whilst translating more than 30 pages per hour and that the mixed translation approximates the human-translated gold-standard to 75% using the automatic evaluation metric METEOR. Last but not least, our evaluation illustrates that a new human-computation pattern, which we call staged-contest with pruning, outperforms all other refinements in the translation task.

We conduct a laboratory experiment to study whether people intuitively use real-option strategies in a dynamic investment setting. The participants were asked to play as an oil manager and make production decisions in response to a simulated mean-reverting oil price. Using cluster analysis, participants can be classified into four groups, which we label as “mean-reverting,” “Brownian motion real-option,” “Brownian motion myopic real-option,” and “ambiguous.” We find two behavioral biases in the strategies by our participants: ignoring the mean-reverting process, and myopic behavior. Both lead to too frequent switches when compared with the theoretical benchmark. We also find that the last group behaved as if they have learned to incorporate the true underlying process into their decisions, and improved their decisions during the later stage.

The vast product variety and product variation offered by online retailers provide an amazing amount of choice options to individuals, thus posing a big challenge to them finding and choosing interesting products which provide them the most utility. Consequently, consumers have to be satisfied with finding a product that provides them sufficient utility. Beyond that, individuals tend to even defer product choice. Recommender systems have emerged in the past years as an effective method to help individuals with finding interesting products. As a result, the consumer welfare enhanced by $731 million to $1.03 billion in the year 2000 due to the increased product variety of online bookstores. Consumer welfare refers to consumers’ total satisfaction. This enhancement in consumer welfare is 7 to 10 times larger than the consumer welfare gain from increased competition and lower prices in the book market. In other words, recommender systems are essential for increasing consumer welfare, which ultimately leads to an increase of economic and social welfare. Typically, recommender systems use the collective wisdom of individuals for exposing individuals to products which best fits their preferences, thus maximizing their utility. More precisely, the product ratings of like-minded individuals are considered by the recommender system to provide individuals recommendations. Commonly, like-minded individuals are retrieved by comparing their ratings for common rated products. This filtering technology is commonly referred to as collaborative filtering. However, retrieving like-minded individuals based on their ratings for common rated products may be inappropriate because common rated products may not necessarily be a representative sample of two individuals’ preferences being compared. There are four reasons. Firstly, the set of common rated products is too sparse to draw a significant conclusion about the preference similarity of both individuals. Secondly, ratings for common rated products correspond to the intersection of two individuals’ rated products and thus may represent only partially both individuals’ preferences. Consequently, overall preference similarity is, in fact, deduced from partial preference similarity. Thirdly, the preference similarity between two individuals is not assessable in the case when both individuals do not share ratings for the same products. Consequently, like-minded individuals are missed due to lack of ratings. Lastly, retailers collect only a fraction of individuals’ ratings on their store, because individuals purchase products from different stores. Hence, individuals’ ratings are distributed across multiple retailers, which limits the set of common rated products per retailer. In this dissertation, we propose hypothesis-based collaborative filtering (HCF) to expose individuals to products that best fits their preferences. In HCF, like-minded individuals are retrieved based on the similarity of their respective hypothesized preferences by means of machine learning algorithms hypothesizing individuals’ preferences. Machine learning is a method to extract patterns to generalize from observations, thus being adequate to hypothesize individuals’ preferences from their product ratings. Generally, the similarity of two individuals’ hypothesized preferences can be computed in two different ways. One way is to compare the hypothesized utilities that products provide to both individuals. To this goal, we use both individuals’ hypothesized preferences to predict the utilities of some products. To compute the preference similarity, we propose three similarity metrics to compare product utilities. The other way is to analyze the composition of both individuals’ hypothesized preferences. For this purpose, we introduce the notion of hypothesized partial preferences (HPPs), which are self-contained and form the components which constitute hypothesized preferences. We propose several methods to compare HPPs to compute the similarity of two individuals’ preferences. We conduct a large empirical study on a quasi benchmark dataset and diverse variation of this dataset, which vary by means of sparsity degree, to evaluate the cold-start behavior of HCF. Based on this empirical study, we provide empirical evidence for the robustness of HCF against data sparsity and the superiority to state-of-the-art collaborative filtering methods. We use the research methodology of grounded theory to scrutinize the empirical results to explain the cold-start behavior of HCF for retrieving like-minded individuals relative to other collaborative filtering methods. Based on this theory, we show that HCF is more efficient in retrieving like-minded individuals from large sets of individuals and is more appropriate for individuals who provide few provide ratings. We verify the validity of the grounded theory by means of an empirical study. In conclusion, HCF provides individuals better recommendations, particularly for those who provide few ratings and for frequently rated products, which complicates the retrieval of like-minded individuals. Hence, HCF increases consumers welfare, which ultimately leads to an increase of economic and social welfare. Die überwältigende Produktvielfalt und Produktvariation, welche von Online-Händlern angeboten werden, bietet Individuen eine unglaubliche Menge an Wahlmöglichkeiten. Dies stellt jedoch eine grosse Herausforderung für Individuen dar, die aus dieser Auswahl diejenigen Produkte finden möchten, welche ihnen den höchsten Nutzen bringen. Angesichts eines solchen überdimensionalen Sortiments sind Individuen kaum in der Lage diese Produkte zu finden. Folglich müssen sich Individuen in der Regel mit Produkten zu frieden geben, welche ihnen genügend hohen Nutzen bringen. Nicht zu letzt tendieren Individuen gar dazu kein Produkt auszuwählen und setzen ihre Entscheidung aus. Empfehlungssysteme haben sich in den vergangenen Jahren entwickelt und als effektive Methode erwiesen, um Individuen bei der Suche nach interessanten Produkten zu helfen. Damit konnte sich die Konsumentenwohlfahrt um $731 Millionen auf $1.03 Milliarden im Jahr 2000 erhöhen. Dies alleine aufgrund der höheren Produktvielfalt in Online-Buchhandlungen. Die Konsumentenwohlfahrt bezieht sich auf die totale Konsumentenzufriedenheit. Diese Wohlfahrtserhöhung ist sieben bis zehnmal grösser als die erhöhte Wohlfahrt, welche durch verstärkten Wettbewerb und tieferen Preisen resultiert. Mit anderen Worten, Empfehlungssysteme sind wesentlich für die Steigerung der Konsumentenwohlfahrt, welches letztlich zu einer Steigerung des wirtschaftlichen und öffentlichen Wohlstandes führt. Empfehlungssysteme verwenden typischerweise die kollektive Weisheit der Massen, um Individuen diejenigen Produkte zu zeigen, welche am Besten ihren Präferenzen entsprechen und damit ihren Nutzen erhöhen. Dazu werden nur die Produktbewertungen von Individuen berücksichtigt, welche ähnliche Präferenzen haben. Allgemein werden Individuen mit ähnlichen Präferenzen durch einen Vergleich ihrer Bewertungen für die selben Produkte festgestellt. Diese Filter-Technologie wird gemeinhin als kollaboratives Filtern bezeichnet. Jedoch ist das finden von Individuen mit ähnlichen Präferenzen basie- rend auf ihren Bewertungen für die selben Produkte nicht immer geeignet, da diese Produktbewertungen nicht notwendigerweise repräsentativ für ihre Präferenzen sind. Dafür gibt es vier Gründe. Erstens, die Menge der gemeinsam bewerteten Produkte ist zu klein, um einen signifikanten Rückschluss der Präferenzähnlichkeit zweier Individuen festzustellen. Zweitens, die Bewertungen für gemeinsam bewertete Produkte entsprechen der Produktschnittmenge zweier Individuen. Somit ist es möglich, dass diese gemeinsam bewerteten Produkte nur teilweise beide Präferenzen repräsentieren. Drittens, die Präferenzähnlichkeit kann nicht festgestellt werden, wenn zwei Individuen keine gleichen Produkte bewertet haben. Daraus folgt, dass Individuen mit ähnlichen Präferenzen nicht erkannt werden aufgrund fehlender Bewertungen für gleiche Produkte. Viertens, Händler können nur einen Teil der Bewertungen von Individuen auf ihren Online-Shops sammeln, da Individuen üblicherweise Produkte von verschiedenen Händlern kaufen. Somit sind die Bewertungen von Individuen über verschiedene Händler verteilt, welche die mögliche Menge von gemeinsam bewerteten Produkten pro Händler limitiert. In dieser Dissertation schlagen wir deshalb Hypothesen-basiertes kollaboratives Filtern (HCF) vor, um Individuen an Produkte heranzuführen, welche am Besten ihren Präferenzen entsprechen. Bei HCF werden Individuen mit ähnlichen Präferenzen aufgrund der Ähnlichkeit ihrer hypothetischer Präferenzen, welche mittels Algorithmen für maschinelles Lernen erzeugt werden, erkannt. Maschinelles Lernen ist ein Verfahren, um Muster aus Beobachtungen zu erkennen. Dadurch eignet es sich, um die Präferenzen von Individuen basierend auf ihren Produktbewertungen zu hypothetisieren. Es gibt zwei verschiedene Möglichkeiten, um die Ähnlichkeit von hypothetischen Präferenzen zu berechnen. Eine Möglichkeit ist der Vergleich des hypothetischen Nutzens, welche Produkte zweien Individuen bringt. Zu diesem Zweck verwenden wir die hypothetischen Präferenzen, um den Nutzen von Produkten für beide Individuen vorherzusagen. Wir stellen drei verschiedene Ähnlichkeitsmetriken vor, um diese Produktnutzen zu vergleichen und die Ähnlichkeit zu berechnen. Die andere Möglichkeit ist die Analyse der Komposition der hypothetischen Präferenzen beider Individuen. Zu diesem Zwecken führen wir den Begriff der partiellen Präferenzen ein, welche die Komponenten von hypothetischen Präferenzen bilden. Wir stellen mehrere Verfahren vor, um hypothetische partielle Präferenzen zu Vergleichen und damit die Ähnlichkeit zweier hypothetischen Präferenzen zu berechnen. Wir führen eine grosse empirische Studie durch basierend auf einem Quasi-Benchmark Datensatz und verschiedener darauf basierenden Variationen, welche bezüglich der Menge an Produktbewertungen variieren. Damit evaluieren wir die Empfehlungsqualität des HCF bezüglich der Spärlichkeit an Produktbewertungen, was auch als Kalt-Start Problem bezeichnet wird. Basierend auf dieser Studie können wir empirische Evidenz zeigen, dass HCF robust gegenüber der Spärlichkeit von Produktbewertung ist und State-of-the-Art Methoden des kollaborativen Filterns überlegen ist. Wir verwenden die Forschungsmethodik Grounded Theory, um diese empirischen Resulte zu untersuchen und dadurch das Verhalten von HCF im Vergleich zu anderen kollaborativen Filter-Methoden zu verstehen und zu erklären. Wir zeigen basierend auf dieser Theorie, dass HCF im Vergleich zu anderen Methoden effizienter Individuen mit ähnlichem Geschmack aus einer grossen Menge potentieller Kandidaten filtert. Zudem zeigen wir, dass HCF insbesondere für Individuen, welche wenige Produkte bewertet haben, geeigneter ist als andere Methoden. Wir verifzieren die Gültigkeit dieser Theorie mittels einer weiteren empirischen Studie. Zusammenfassend bietet HCF Individuen bessere Empfehlungen, insbesondere für Individuen, welche wenige Produkte bewertet haben. Dadurch kann die Konsumentenwohlfahrt weiter erhöht werden und führt somit zu einer Erhöhung der ökonomischen Wohlfahrt.

This thesis describes the concept, implementation and evaluation of a temporal extension to the triple store RDFBox. The most important goal was to compare two new temporal index structures and integrate them into RDFBox. Foremost attention has been paid on evaluating the concepts of those two indices and the performance compared with each other and not with the existing sys- tem. In the first section an overview of the existing system is given, followed by an introduction to the changes the temporal extension brings with it. The third and most important part of the thesis shows the evaluation of the indices and possible enhancements.