Crowdsourcing involves releasing tasks on the internet for people with diverse backgrounds and skills to solve. Its adoption has come a long way, from scaling up problem-solving to becoming an environment for running complex experiments. Designing tasks to obtain reliable results is not straightforward as it requires many design choices that grow with the complexity of crowdsourcing projects, often demanding multiple trial-and-error iterations to properly configure. These inherent characteristics of crowdsourcing, the complexity of the design space, and heterogeneity of the crowd, set quality control as a major concern, making it an integral part of task design. Despite all the progress and guidelines for developing effective tasks, crowdsourcing still is addressed as an ``art'' rather than an exact science, in part due to the challenges related to task design but also because crowdsourcing allows more complex use cases nowadays, where the support available has not yet caught up with this progress. This leaves researchers and practitioners at the forefront to often rely on intuitions instead of informed decisions. Running controlled experiments in crowdsourcing platforms is a prominent example. Despite their importance, experiments in these platforms are not yet first-class citizens, making researchers resort to building custom features to compensate for the lack of support, where pitfalls in this process may be detrimental to the experimental outcome. In this thesis, therefore, our goal is to attend to the need of moving crowdsourcing from art to science from two perspectives that interplay with each other: providing guidance on task design through experimentation, and supporting the experimentation process itself. First, we select classification problems as a use case, given their importance and pervasive nature, and aim to bring awareness, empirical evidence, and guidance to previously unexplored task design choices to address performance concerns. And second, we also aim to make crowdsourcing accessible to researchers and practitioners from all backgrounds, reducing the requirement of in-depth knowledge of known biases in crowdsourcing platforms, experimental methods, as well as programming skills to overcome the limitations of crowdsourcing providers while running experiments. We start by proposing task design strategies to address workers' performance, quality and time, in crowdsourced classification tasks. Then we distill the challenges associated with running controlled crowdsourcing experiments, propose coping strategies to address these challenges, and introduce solutions to help researchers report their crowdsourcing experiments, moving crowdsourcing forward to standardized reporting.

No estudo de sistemas complexos interessa capturar a evolução do seu comportamento emergente segundo um conjunto de regras cujas soluções descrevem o seu estado ao longo do tempo. Uma classe particular de modelos matemáticos e computacionais que permite realizar essa investigação são os autômatos celulares. O comportamento global deles é definido apenas por regras locais, o que os tornam um modelo exemplar para estudos de sistemas complexos. Estamos interessados em um tipo especial de autômato celular: os classificadores de densidade unidimensionais. Este tipo de autômato celular está relacionado com o problema da maioria que consiste em fazer convergir uma cadeia de símbolos aleatoriamente distribuídos em um reticulado, para uma cadeia homogênea com um único símbolo final (consenso global), aquele de maioria inicial. Este consenso deve ser obtido exclusivamente a partir de interações locais entre os sítios sem a instância de um controle central. Nesta pesquisa, realizamos alguns experimentos para caracterizar um autômato celular classificador de quatro estados proposto em Gács, Kurdyumov e Levin (1978). Embora seja um classificador imperfeito, este autômato celular é significativamente tolerante a falhas quando o submetemos a níveis de ruídos não nulos. Os resultados corroboram com outros estudos que investigam a robustez deste tipo de autômato celular e lançam luz sobre o entendimento da origem da coordenação global de sistemas que exibem as características aqui descritas / In the study of complex systems we are interested in capturing their evolution of its emergent behavior under a set of rules whose solutions describe the state of the system over time. A particular class of mathematical and computational model to perform this kind of research is the cellular automaton (CA). Its global behavior is defined by local rules, which makes it an exemplary model to study complex systems. Here, we are interested in a particular type of CA: one-dimensional CA that classifies densities. This kind of CA is related to the problem of the majority task that consists of converging an array of symbols, initially randomly distributed, to a single symbol, the more frequent one in the initial configuration of the array (global consensus). This consensus must be obtained solely out of local interactions, without the instance of a central control. In this research, we conducted some experiments to characterize a four-state CA classifier proposed in Gács, Kurdyumov e Levin (1978). While it is an imperfect classifier, this CA is significantly fault tolerant when submitted to the levels of non-zero noise. Our results corroborate other studies that had investigated the robustness of this type of CA, and shed light on the understanding of the origin of global coordinated systems that exhibit the characteristics described here

No estudo de sistemas complexos interessa capturar a evolução do seu comportamento emergente segundo um conjunto de regras cujas soluções descrevem o seu estado ao longo do tempo. Uma classe particular de modelos matemáticos e computacionais que permite realizar essa investigação são os autômatos celulares. O comportamento global deles é definido apenas por regras locais, o que os tornam um modelo exemplar para estudos de sistemas complexos. Estamos interessados em um tipo especial de autômato celular: os classificadores de densidade unidimensionais. Este tipo de autômato celular está relacionado com o problema da maioria que consiste em fazer convergir uma cadeia de símbolos aleatoriamente distribuídos em um reticulado, para uma cadeia homogênea com um único símbolo final (consenso global), aquele de maioria inicial. Este consenso deve ser obtido exclusivamente a partir de interações locais entre os sítios sem a instância de um controle central. Nesta pesquisa, realizamos alguns experimentos para caracterizar um autômato celular classificador de quatro estados proposto em Gács, Kurdyumov e Levin (1978). Embora seja um classificador imperfeito, este autômato celular é significativamente tolerante a falhas quando o submetemos a níveis de ruídos não nulos. Os resultados corroboram com outros estudos que investigam a robustez deste tipo de autômato celular e lançam luz sobre o entendimento da origem da coordenação global de sistemas que exibem as características aqui descritas / In the study of complex systems we are interested in capturing their evolution of its emergent behavior under a set of rules whose solutions describe the state of the system over time. A particular class of mathematical and computational model to perform this kind of research is the cellular automaton (CA). Its global behavior is defined by local rules, which makes it an exemplary model to study complex systems. Here, we are interested in a particular type of CA: one-dimensional CA that classifies densities. This kind of CA is related to the problem of the majority task that consists of converging an array of symbols, initially randomly distributed, to a single symbol, the more frequent one in the initial configuration of the array (global consensus). This consensus must be obtained solely out of local interactions, without the instance of a central control. In this research, we conducted some experiments to characterize a four-state CA classifier proposed in Gács, Kurdyumov e Levin (1978). While it is an imperfect classifier, this CA is significantly fault tolerant when submitted to the levels of non-zero noise. Our results corroborate other studies that had investigated the robustness of this type of CA, and shed light on the understanding of the origin of global coordinated systems that exhibit the characteristics described here

O advento da TV Digital Interativa no mundo modifica, em definitivo, a experiência do usuário em assistir a TV, tornando-a mais rica principalmente pelo uso do recurso da interatividade. Os usuários passam a ser pró-ativos e começam a interagir das mais diversas formas: construção de comunidades virtuais, discussão sobre um determinado conteúdo, envio de mensagens e recomendações, dentre outras. Neste cenário a participação dos usuários de forma colaborativa assume um papel importante e essencial. Aliado a isso, a recepção na TV Digital Interativa é feita através de dispositivos computacionais que, devido à convergência digital, estão presentes cada vez mais em meios ubíquos. Um outro fator preponderante a considerar, resultante desta mídia, corresponde ao crescimento da quantidade e diversidade de programas e serviços interativos disponíveis, dificultando, assim, a seleção de conteúdo de maior relevância. Diante dos fatos expostos, esta pesquisa tem como principal objetivo propor e implementar uma infra-estrutura de software no cenário da TV Digital Interativa intitulada CollaboraTVware para orientar, de forma transparente, os usuários na escolha de programas e serviços interativos através da participação colaborativa de outros usuários com perfis e contextos similares. No escopo deste trabalho, a participação colaborativa corresponde às avaliações atribuídas por usuários no sentido de expressar opiniões sobre os conteúdos veiculados. As modelagens de usuário, do dispositivo utilizado e do contexto da interação do usuário, essenciais para o desenvolvimento do CollaboraTVware, são representadas por padrões de metadados flexíveis usados no domínio da TV Digital Interativa (MPEG-7, MPEG-21 e TV-Anytime), e suas devidas extensões. A arquitetura do CollaboraTVware é composta por dois subsistemas: dispositivo do usuário e provedor de serviços. A tarefa de classificação, da teoria de mineração de dados, é a abordagem adotada na concepção da infra-estrutura. O conceito de perfil de uso participativo é apresentado e discutido. Para demonstrar e validar as funcionalidades do CollaboraTVware em um cenário de uso, foi desenvolvida uma aplicação (EPG colaborativo) como estudo de caso. / The advent of the Interactive Digital TV around the world transforms, ultimately, the user experience in watching TV, making it richer mainly by enabling user interactivity. The users become pro-active and begin to interact with very different ways: building virtual communities, discussion about contents, sending messages and recommendations etc. In this scenario the user participation in a collaborative assumes an important and essential role. Additionally, the reception in Interactive Digital TV is done by devices that due to digital convergence are increasingly present in ubiquitous environments. Another preponderant issue to consider, resulting from this media, is the growing of the number and diversity of programs and interactive services available, increasing the difficulty of selecting relevant content. Thus, the main objective of this work is to propose and implement a software infrastructure in an Interactive Digital Television environment entitled CollaboraTVware to guide in a transparent way, users in the choice of programs and interactive services through the collaborative participation of other users with similar profiles and contexts. In the scope of this work, the collaborative participation corresponds to the rating given by users in order to express opinions about the content transmitted. The modeling of user, device used and context of user interaction, essential for the development of CollaboraTVware, are represented by granular metadata standards used in the field of Interactive Digital TV (MPEG-7, MPEG-21 and TV-Anytime), and its extensions needed. The CollaboraTVware architecture is composed of two subsystems: user device and service provider. The classification task, from the theory of data mining, is the approach adopted in the infrastructure design. The concept of participative usage profile is presented and discussed. To demonstrate the functionalities in a use scenario, was developed an application (collaborative EPG) as a case study which uses the CollaboraTVware.

O advento da TV Digital Interativa no mundo modifica, em definitivo, a experiência do usuário em assistir a TV, tornando-a mais rica principalmente pelo uso do recurso da interatividade. Os usuários passam a ser pró-ativos e começam a interagir das mais diversas formas: construção de comunidades virtuais, discussão sobre um determinado conteúdo, envio de mensagens e recomendações, dentre outras. Neste cenário a participação dos usuários de forma colaborativa assume um papel importante e essencial. Aliado a isso, a recepção na TV Digital Interativa é feita através de dispositivos computacionais que, devido à convergência digital, estão presentes cada vez mais em meios ubíquos. Um outro fator preponderante a considerar, resultante desta mídia, corresponde ao crescimento da quantidade e diversidade de programas e serviços interativos disponíveis, dificultando, assim, a seleção de conteúdo de maior relevância. Diante dos fatos expostos, esta pesquisa tem como principal objetivo propor e implementar uma infra-estrutura de software no cenário da TV Digital Interativa intitulada CollaboraTVware para orientar, de forma transparente, os usuários na escolha de programas e serviços interativos através da participação colaborativa de outros usuários com perfis e contextos similares. No escopo deste trabalho, a participação colaborativa corresponde às avaliações atribuídas por usuários no sentido de expressar opiniões sobre os conteúdos veiculados. As modelagens de usuário, do dispositivo utilizado e do contexto da interação do usuário, essenciais para o desenvolvimento do CollaboraTVware, são representadas por padrões de metadados flexíveis usados no domínio da TV Digital Interativa (MPEG-7, MPEG-21 e TV-Anytime), e suas devidas extensões. A arquitetura do CollaboraTVware é composta por dois subsistemas: dispositivo do usuário e provedor de serviços. A tarefa de classificação, da teoria de mineração de dados, é a abordagem adotada na concepção da infra-estrutura. O conceito de perfil de uso participativo é apresentado e discutido. Para demonstrar e validar as funcionalidades do CollaboraTVware em um cenário de uso, foi desenvolvida uma aplicação (EPG colaborativo) como estudo de caso. / The advent of the Interactive Digital TV around the world transforms, ultimately, the user experience in watching TV, making it richer mainly by enabling user interactivity. The users become pro-active and begin to interact with very different ways: building virtual communities, discussion about contents, sending messages and recommendations etc. In this scenario the user participation in a collaborative assumes an important and essential role. Additionally, the reception in Interactive Digital TV is done by devices that due to digital convergence are increasingly present in ubiquitous environments. Another preponderant issue to consider, resulting from this media, is the growing of the number and diversity of programs and interactive services available, increasing the difficulty of selecting relevant content. Thus, the main objective of this work is to propose and implement a software infrastructure in an Interactive Digital Television environment entitled CollaboraTVware to guide in a transparent way, users in the choice of programs and interactive services through the collaborative participation of other users with similar profiles and contexts. In the scope of this work, the collaborative participation corresponds to the rating given by users in order to express opinions about the content transmitted. The modeling of user, device used and context of user interaction, essential for the development of CollaboraTVware, are represented by granular metadata standards used in the field of Interactive Digital TV (MPEG-7, MPEG-21 and TV-Anytime), and its extensions needed. The CollaboraTVware architecture is composed of two subsystems: user device and service provider. The classification task, from the theory of data mining, is the approach adopted in the infrastructure design. The concept of participative usage profile is presented and discussed. To demonstrate the functionalities in a use scenario, was developed an application (collaborative EPG) as a case study which uses the CollaboraTVware.

Made available in DSpace on 2016-03-15T19:37:38Z (GMT). No. of bitstreams: 1 Mateus Interciso.pdf: 1720671 bytes, checksum: aa67cff2cc9f7abe5fb3b48bead6b38d (MD5) Previous issue date: 2011-08-23 / Fundo Mackenzie de Pesquisa / The search for cellular automata (CAs) rules capable of executing a determined task can be impossible to be achieve manually, given the huge size of the search space usually involved. A method for being able to find rules capable of executing the task at hand has been the usage of genetic algorithms (GAs) to evolve an initially random population, until the desired objective; each individual of those GAs are usually represented by a candidate transition rule. In problems formulated for the resolution by a binary cellular automaton, a recently used modification on the representation of the individuals was the usage of templates with the presence of an extra symbol, capable of representing every other valid symbol. Such schema of ternary representation is used on the present work, aiming for it s net effect on the search process on the GAs. This study is made for two classical tasks of binary unidimensional cellular automata, the density classification task and the parity problem, both traditional in the context of using GAs for searching transition rules with high performance. By comparing the results of the original GAs and their versions implemented with the ternary representation, it s shown that the ternary representation is able to improve the quality of the results. Particularly, it is analized the condition in which the usage of the ternary representation presents to be more effective, as well as some effects of the actual implementation. Possible future works are presented at the end. / A busca por regras de autômatos celulares que efetuem corretamente uma determinada tarefa pode ser impossível de ser efetuada manualmente, dado o enorme tamanho dos espaços de busca usualmente envolvidos. Uma forma para conseguir encontrar boas regras para a execução do problema em questão tem sido a utilização de algoritmos genéticos (AGs) para evoluir uma população inicialmente aleatória, até o objetivo desejado; nesses AGs cada indivíduo é normalmente representado como uma regra de transição candidata. Em problemas formulados para resolução por um autômato celular binário, uma alteração recentemente estudada na literatura para a representação dos indivíduos foi a utilização de templates (moldes) com a presença de um símbolo extra, capaz de representar os demais símbolos. Tal esquema de representação ternária é utilizada no presente trabalho, visando avaliar seu efeito no processo de busca realizado por AGs. O estudo é feito para duas tarefas clássicas de autômatos celulares unidimensionais binários, a tarefa de classificação da densidade e o problema da paridade, ambas tradicionais no contexto da utilização de AGs para encontrar regras de transição com alta performance. Ao comparar os resultados de AGs originais encontrados na literatura com suas versões implementadas com representação ternária, mostra-se que a representação ternária é capaz de melhorar a qualidade dos resultados. Em particular, analisam-se condições em que o uso da representação ternária se mostra mais efetivo, bem como apontam-se efeitos de alguns aspectos de implementação. Possíveis trabalhos futuros pertinentes ao estudo são discutidos ao final.

Made available in DSpace on 2016-03-15T19:37:41Z (GMT). No. of bitstreams: 1 Mateus Interciso.pdf: 1732926 bytes, checksum: f29787f421b0b5f1d6dedd2c1eb4e0fc (MD5) Previous issue date: 2011-09-23 / Fundo Mackenzie de Pesquisa / The search for cellular automata (CAs) rules capable of executing a determined task can be impossible to be achieve manually, given the huge size of the search space usually involved. A method for being able to find rules capable of executing the task at hand has been the usage of genetic algorithms (GAs) to evolve an initially random population, until the desired objective; each individual of those GAs are usually represented by a candidate transition rule. In problems formulated for the resolution by a binary cellular automaton, a recently used modification on the representation of the individuals was the usage of templates with the presence of an extra symbol, capable of representing every other valid symbol. Such schema of ternary representation is used on the present work, aiming for it s net effect on the search process on the GAs. This study is made for two classical tasks of binary unidimensional cellular automata, the density classification task and the parity problem, both traditional in the context of using GAs for searching transition rules with high performance. By comparing the results of the original GAs and their versions implemented with the ternary representation, it s shown that the ternary representation is able to improve the quality of the results. Particularly, it is analized the condition in which the usage of the ternary representation presents to be more effective, as well as some effects of the actual implementation. Possible future works are presented at the end. / A busca por regras de autômatos celulares que efetuem corretamente uma determinada tarefa pode ser impossível de ser efetuada manualmente, dado o enorme tamanho dos espaços de busca usualmente envolvidos. Uma forma para conseguir encontrar boas regras para a execução do problema em questão tem sido a utilização de algoritmos genéticos(AGs) para evoluir uma população inicialmente aleatória, até o objetivo desejado; nesses AGs cada indivíduo é normalmente representado como uma regra de transição candidata. Em problemas formulados para resolução por um autômato celular binário, uma alteração recentemente estudada na literatura para a representação dos indivíduos foi a utilização de templates (moldes) com a presença de um símbolo extra, capaz de representar os demais símbolos. Tal esquema de representação ternária é utilizada no presente trabalho, visando avaliar seu efeito no processo de busca realizado por AGs. O estudo é feito para duas tarefas clássicas de autômatos celulares unidimensionais binários, a tarefa de classificação da densidade e o problema da paridade, ambas tradicionais no contexto da utilização de AGs para encontrar regras de transição com alta performance. Ao comparar os resultados de AGs originais encontrados na literatura com suas versões implementadas com representação ternária, mostra-se que a representação ternária é capaz de melhorar a qualidade dos resultados. Em particular, analisam-se condições em que o uso da representação ternária se mostra mais efetivo, bem como apontam-se efeitos de alguns aspectos de implementação. Possíveis trabalhos futuros pertinentes ao estudo são discutidos ao final.

Made available in DSpace on 2016-03-15T19:38:09Z (GMT). No. of bitstreams: 1 Fernando Faria.pdf: 516281 bytes, checksum: fc784946b9c2438b3c18c34593a182cb (MD5) Previous issue date: 2008-03-11 / Wolfram Research, Inc. / Cellular automata are discrete dynamical systems composed of simple, locally connected structures (the cells), general in terms of their computational power, and that display complex patterns of behaviour. The purpose of this work was to expand previous studies by Zanon (2006), on non-uniform, one-dimensional cellular automata with nonlocal neighbourhood, in order to verify the existence of rules of these kinds of automata to solve the density classification task, that is, the determination of the predominant bit in a binary string. Our concern here was to look for solutions of the problem mainly by evolutionary computation means, to solve it in a non-trivial fashion, i.e., without including in the solution the majority rule over the entire lattice, and, at the same time, with the target of inferring common features for the solutions that would be found. The results achieved led to an expansion in the quantity of perfect solutions available in the literature, but it became clear that all of them have at least one of the rules involved able to account for the entire lattice at once, an evidence that solutions without rules with global action may not exist. Furthermore, the following observations have been made for the type of automata we considered: even distinct automata may have the same temporal evolution; a certain degree of flexibility is allowed in the total balancing of the rules present in a solution of the density classification task; and, in principle, no common patterns seem to exist between solutions for lattices with 3 and 5 cells, thereby suggesting the impossibility of constructing a solution to the problem from another of a smaller lattice. / Autômatos celulares são sistemas dinâmicos discretos, formados por estruturas simples (as células) conectadas localmente entre si, gerais em termos de seu poder computacional, e que apresentam padrões de comportamento bastante complexos. O intuito deste trabalho foi expandir estudos anteriores de Zanon (2006), sobre autômatos celulares unidimensionais não-uniformes, com vizinhança não-local, visando verificar a existência de autômatos desse tipo na resolução da tarefa da classificação de densidade, isto é, a determinação do bit predominante em uma cadeia binária. Interessou-nos aqui descobrir soluções do problema principalmente por meio de buscas evolutivas, resolvê-lo de forma não trivial, isto é, sem a necessidade da regra da maioria sobre todo o reticulado, e objetivando inferir características necessárias para as soluções que viessem a resolver o problema. Os resultados obtidos levaram a uma expansão da quantidade de soluções perfeitas reportadas na literatura, mas observou-se que todas elas contém pelo menos uma das regras envolvidas tomando todo o reticulado como base de ação, uma evidência da impossibilidade de existir soluções sem regras individuais de ação global. Adicionalmente, as seguintes constatações foram feitas para os autômatos celulares do tipo considerado: mesmo autômatos distintos entre si podem ter a mesma evolução temporal; uma flexibilização do balanceamento total das regras na solução do problema da classificação de densidade é conseguida; e, em princípio, não há padrões nas soluções perfeitas para reticulados de 3 e 5 células, sugerindo a impossibilidade de se construir uma solução a partir de outra de menor tamanho de reticulado.