Logic and Rational Interaction

19 March 2010

REPORT: Philosophy of the Information and Computing Sciences — Mathematical Foundations of Information Discussion Group

Posted by Rasmus Rendsvig under: Conference and workshop reports .

Information provided by

Jeremy Seligman

REPORT:
Philosophy of the Information and Computing Sciences
Mathematical Foundations of Information Discussion Group

http://www.lorentzcenter.nl/lc/web/2010/374/info.php3?wsid=374
Lorentz Center, Februrary 8-12, 2010

Jeremy Seligman

On February 8-12, the Workshop on the Philosophy of the Information and Computing Sciences, arranged by Jan van Leeuwen, was held at the Lorentz Centre at the University of Leiden. Along with a full program of presentations and posters, the Workshop also involved a series of discussion groups. Our group discussed the Mathematical Foundations of Information:

Orientation:

We considered a number of mathematical models of information and information flow, and focussed our discussion on various questions about them.

Do they conflict with each other or can they live peacefully? Is there a reduction of any one to any other?
Do they even share a common subject matter or only the use of the word `information’?
Are there prospects for producing a unified theory of information?
Is there any need for such a theory?

Quantitative models:

Classical information theory: The conception of communication as involving information flow along a channel from source to receiver, as measured by the extent to which the receiver’s knowledge may be expected to reduce uncertainty about the source.
Algorithmic information theory: A measurement of the amount of information in an object, given by the length of its shortest description. The measure is relative to the choice of description language but asymptotically absolute in the sense that any two such choices result in measures that can only differ by a fixed finite amount.

Logico-semantic models:

Dynamic epistemic logic: A language and calculus for describing the knowledge of communicating agents. Information flow is understand as the effect of various events, such as public announcement, on the agents’ knowledge.
Channel theory: An algebraic model of the dependencies between classifications by source and receiver. Information flow is analysed as the movement of inference patterns along channels arranged in a network.

There are many other approaches that we did not consider, such as information algebras, models of abstract data types, etc.

Day 1: Classical and Algorithmic Information Theory:

Notions of information as entropy: outline of a unifying theory, with problems:

Good news:

Basic intuitions:

Gibbs entropy (ca. 1870): the entropy of a system is defined in terms of a probability distribution over the microstates with the same macroscopic qualities
Shannon Information (1948): the entropy of a set of messages is defined in terms of a probability distribution of the a collection of messages
Kolmogorov complexity (1964): Entropy of a binary string is defined in terms of its algorithmic compressability. Observation by Li and Vitanyi: The Kolmogorov entropy of a binary string = its Gibb’s entropy. Think of a binary string as a 1d gas frozen in time.

Conclusion: at least from a mathematical point of view these notions are very related.

Observations:

Kolmogorov complexity was developed by Solomonov with the, at least partial, objective to solve the philosophical problem of a general theory of induction (as stated by Carnap).
Shannon: from probability to compression. Shannon Information can be used to find an optimal compression for a sequence of messages (optimal code).
Kolmogorov complexity: from compression to probability. Kolmogorov complexity can be used to define an ‘optimal’ probability distribution for binary strings: the universal distribution.
Kolmogorov complexity and Shannon information seem to be dual notions: the shortest code for a binary string in the sense of Kolmogorov Complexity is it’s optimal code in he sense of Shannon Information using the universal distribution (Levin’s coding theorem, 1974).

Bad news:

(Philosophical) problems:

Gibbs entropy is only defined for closed systems in equilibrium. Shannon and Kolmogorov also seem to capture non-equilibrium notions of entropy. What is their relation? Philosophical debate about the correct interpretation of the notion of Gibbs entropy still not closed (See recent paper by Fleming Topsoe: Towards operational interpretations of generalized entropies.
In Gibbs and Kolmogorov the notion of an agent is absent. Johan van Benthem: Big Information versus small information?
Counter intuitive results: most information rich sets are random? Facticity as a measure for meaningfulness of information (Adriaans).
According to these measures, computation can never generate information: recursive functions are information discarding functions. Is this what we want?
Is the mathematical connection misleading?
Aboutness, semantics, intentionality?

Day 2: Channels and Dynamic Epistemic Logic:

Several proposals for understanding the relationship between Channels and Dynamic Epistemic Logic were discussed in some detail. This should result in a definite outcome – a theorem at least – showing at least that the two models are compatible in some respects.

One main difference is that the logic model puts all of the structure into the language, which serve both to describe the content of agent’s knowledge and the act of communication between agents. These are separated in the channel model.

Advantage (for Channel model): the model makes no assumptions about the classificatory power of the agents.
Advantage (for Logic model): easier to account for higher-order dependencies, such as information about information possessed by other agents, the effects of possible acts of communication, and so forth.

There was some discussion of general issues involved in modelling dynamics: to have a big model in which all possible changes are included or a smaller model together with actions that change the model.

Day 3: Algorithmic and Logical Approaches: Content

The distinction between qualitative and quantitative notions of information is characterised by the paradoxical situation that the notions of information modelled by the most successful theories (Shannon and Kolmogorov) do not correspond to the ordinary notion of information:

When information is measured, the actual content of a signal (the thing we are really interested in) is ignored.

We focused on two aspects:

Dretkse’s attempt to show that Shannon’s theory is relevant for semantic aspects of information, and
the lack of semantic aspects in Kolmogorov complexity theory.

The common ground between Shannon’s information theory and semantic notions of information is the inverse relationship principle which equates informational content with a reduction of uncertainty. We considered one problem with Dretske’s proposal, namely the interpretation of his use of conditional probability 1 in the definition of informational content:

A signal r carries the information that s is F = the conditional probability of s’s being F, given r (and k), is 1 (but, given k alone, less than 1).

One problem with this definition is that it isn’t equivalent to saying that r and k entail that s is F. This is due to the fact that not every Boolean algebra is measurable. If we want to relate quantitative measures of information to qualitative individuations of informational content (logical notions of information), we need an algebraic criterion to select those Boolean algebra’s that are measurable.

Because algorithmic information theory doesn’t refer to such a reduction in uncertainty, it remains silent when it comes to semantic issues. Semantic phenomena cannot directly be modelled, but only indirectly (outside the theory).

An issue we didn’t explicitly discuss, is the \emph{relation between information and meaning}. This is a problem most qualitative accounts have to deal with. On Dretske’s account meaning and the semantically relevant sense of information are distinct. In Barwise and Perry’s situation semantics, there is no difference between information and meaning; the former is used to naturalise the latter.

There was some discussion of Peirce’s theory of signs. Peirce introduced a semiotic theory that suits a computation interpretation. An important aspect of his theory is a dynamic perspective of information, enabling a more refined understanding of interpretation as a process generating “meaning”. But a process view of interpretation is only one side of the coin. Any model of interpretation should also respect at least some of the properties of cognitive activity.

Day 4: Algorithmic and Logical Approaches: Agency

Taking an agent as a system, we noted that agency permeates all theories of information. Information flow takes as a necessary condition a channel transmitting just this, information.

For the channel’s payload to be rightly understood as information, the payload’s processability must not be in doubt.

The action of processing at the receiving and of the channel is carried out by an agent, be this agent artificial or not. In the case where there is no receiver, the structure of the signal presupposes the potential agency.

It is in this sense that information is always information for something, with this something being a system of information processing, or agent.

We understand this account of agency to be robustly multi-modal, in that it underpins the information flow involved in human agents engaged in processing visual information or communicative scenarios, as well as artificial agents engaged in acts of signal transmission.

An interesting further issue concerns whether or not we can usefully think of the subsystems of information processing operations as agents in their own right. In this case, and at this level of abstraction, various states of of a system might be usefully thought of as agents in their own right.