Source-linked AI summary
Information and Computation
Carlos Gershenson
TL;DR
Human-computation systems need useful ways to represent people, information, computation, and their interactions. This chapter reviews information theory and computation, models systems as computing networks, and illustrates the approach with social networks and Wikipedia. It concludes that these formalisms support comparison and measurement of human-computation systems, including monitoring information overload and poverty.
Problem
Human-computation systems require appropriate descriptions and measures for understanding their structures, functions, algorithms, and information dynamics.
Method
The chapter reviews information theory and computation, then represents neural, distributed-machine, and human systems as computing networks.
Results
Computing networks describe and compare human-computation systems, including online social networks and Wikipedia, while information theory measures their information dynamics.
Takeaways & Limitations
These formalisms can support the design and self-monitoring of human-computation systems, including efforts to avoid information overload and information poverty.
Abstract
from arXiv · showhide
In this chapter, concepts related to information and computation are reviewed in the context of human computation. A brief introduction to information theory and different types of computation is given. Two examples of human computation systems, online social networks and Wikipedia, are used to illustrate how these can be described and compared in terms of information and computation.
1 Introduction
Human computation is introduced as computation performed by humans, requiring practical working notions of both “human” and “computation.”
- Human computation is defined at its most general level as computation performed by humans.
2 Information
Information theory provides a way to describe information and uncertainty, extending beyond engineering to human computation. Its measures can characterize transmission, novelty, dependence, and complexity.
- Information theory was developed mathematically by Claude Shannon to study reliable message transmission across noisy channels.
- Information theory can describe anything in terms of information, making it useful beyond engineering.
- Shannon information is based on how much messages reduce uncertainty.Regular, predictable data has low H, whereas irregular or nearly random data has high H.
- Information theory generally assumes that meaning or decoding is fixed, while semiotics studies meaning.
- In human computation, information theory can measure transmission between people, novelty, dependence, and complexity.
3 Computation
Computation is framed as information transformation governed by algorithms or programs, with dynamics ranging from static and periodic to chaotic and complex. The chapter also notes an unresolved conjecture about universal and regular computation.
- 3 Computation: A broad view treats computation as information transformation, but that definition is too broad to be useful.
- 3 Computation: Turing’s formal machine-based definition may be too narrow, while Wolfram’s two-type conjecture remains an open question.Wolfram conjectured that computation is either universal or regular.
- 3 Computation: A practical definition of computation is transforming information through an algorithm or program.This notion is tractable and is not limited to abstract machines.
- 3 Computation: Changing inputs or programs can reveal static, periodic, chaotic, and complex information dynamics.
- 3 Computation: Complex computation preserves information while allowing change, balancing robustness and adaptability; living systems are classified this way.
4 Computing Networks
Computing networks represent computational structures as nodes and information-sharing edges, enabling comparisons across neural, distributed-machine, and human computation. Their models capture states, algorithms, functions, and multiple dynamical scales.
- 4 Computing Networks: Computing networks are a formalism for comparing neural, distributed-machine, and human computation.
- 4 Computing Networks: A computing network consists of nodes linked by edges and governed by an algorithm that computes a function.Nodes and edges may be stochastic or deterministic, synchronous or asynchronous, and discrete or continuous.
- 4 Computing Networks: Neural-network CNs model neurons as nodes, synapses as directed edges, neuron outputs as functions of inputs, and learning as weight adjustment.The network operates on fast functional and slower learning scales.
- 4 Computing Networks: Distributed-computation CNs model computers as nodes, network connections as edges, and programs as transformations of stored information.A slower algorithm can determine and modify network topology.
- 4 Computing Networks: Human-computation CNs model people as nodes and interactions as edges, with people transforming and sharing information through computers or environments.The system function combines people’s computations, while social links can change according to an algorithm.
- 4 Computing Networks: In distributed computation algorithms are centrally determined, whereas in most human-computation systems people determine and execute them themselves.
5 Examples
Online social networks and Wikipedia illustrate human computation as information-processing systems whose structures, algorithms, and outputs are shaped by people. Modeling them as computing networks makes human-information relationships and system dynamics explicit.
- 5.1 Social Networks: Online social networks represent people and organizations as nodes that receive, share, and produce information through social links.Facebook uses bidirectional links, whereas Twitter uses unidirectional links; individuals decide how links are created or removed.
- 5.1 Social Networks: Simple social-network information dynamics can spread both non-official news and false rumors rapidly, while verifiable and false information follow different spreading dynamics.These dynamics can be described as functions f of the network computation.
- 5.1 Social Networks: Information theory applied to social networks can detect novelty, imitation, unusual patterns, correlations, and communities across local, meso, global, fast, and slow scales.High H values in edges indicate novelty, while low H values indicate imitation; mutual information can identify correlations.
- 5.2 Wikipedia: Wikipedia is a human-built encyclopedia modeled as a hypernetwork because editable topic pages can link more than two people.People choose which pages to edit, so the system’s algorithm is also decided by individuals.
- 5.2 Wikipedia: Modeling Wikipedia as a computing network makes relationships between humans and collaboratively produced information explicit, unlike a conventional page-link network.The computing-network description better represents the collective phenomenon of human computation.
6 Conclusions
Information and computation provide general formalisms for describing, comparing, designing, and monitoring human-computation systems. Their use is motivated by the need to make sense of overflowing data while recognizing that important challenges remain.
- 6 Conclusions: Information and computation concepts can be applied to any system, allowing human computation to benefit from their formalisms and descriptions.The chapter treats systems as describable in terms of information.
- 6 Conclusions: Computing networks can describe and compare human-computation systems, including online social networks and Wikipedia, by contrasting structure, functions, algorithms, and information dynamics.The same framework supports comparisons across local and global scales.
- 6 Conclusions: Computing networks and information theory can help design and self-monitor human-computation systems.Measuring information inputs, transfers, and outputs can help address both information overload and information poverty.
- 6 Conclusions: Information and computation offer measures and tools for making sense of overflowing data, while further challenges and opportunities remain.The chapter characterizes progress in describing human-computation systems as promising and encourages continued exploration.
A Shannon Information
Shannon information quantifies information in a sequence according to its probability distribution, using a binary logarithm for binary strings. The measure is minimal for certainty and maximal when binary outcomes are equally probable.
- A Shannon Information: Shannon information is defined for a string whose values follow a probability distribution P(x).The chapter introduces this measure as the information associated with the distribution of sequence values.
- A Shannon Information: For binary strings, Shannon information commonly uses a logarithm with base two.Binary strings are described as common in information and communication technology systems.
- A Shannon Information: H = 0 when P(1) = 1 and P(0) = 0, because future values are already known.Absolute certainty produces no new information.
- A Shannon Information: H = 1 when P(0) = P(1) = 0.5, because a future observation provides maximal information.The chapter also interprets Shannon information as a measure of uncertainty and identifies the unit of information as the bit.
- A Shannon Information: Figure 3 plots Shannon information H(X) for a binary string X across different probabilities P(x), with P(0) = 1 −P(1).The figure represents the binary-probability relationship described in the text.