Rethinking Signaling systems via the lens of compositionality

I was introduced to the subject of language evolution by Brian Skryms in his book “Signals: Evolution, Learning, and Information” where he discusses the evolution of signaling systems and the emergence of language. In it he discusses the role of compositionality in the emergence of language and how it is a key feature of human language. Signals provides a coherent yet multifaceted views of the problem - philosophy, signaling system creation and assimilation via evolution or reinforcement learning. Skryms also considers Logic and complex signaling systems. Yet a unifying theme for this work is a reductionist view of the problem and his attempt to reduce the problem to a model that follows closely the Lewis Signaling Game.

I like this reductionist approach but I like to also to turn it on its head. By looking at how the problem takes form in more challenging and realistic settings can often uncover the true nature of the problem. Since language emergence is so open ended one might also use it to consider how it empowers agents to coordinate on better decision in ever more challenging problems and settings.

I first became frustrated with complex signaling systems when I read the chapters in Signals and realized that unlike the other chapters Skryms had not summarized how researchers in the field had come up with a definitive solution to the problem. I reread it a couple of times and finally realized that although he made some very interesting claims this topic was still unresolved. There are many interesting results but there are at least as many open questions.

The second time I became frustrated was when I tried to convert the simple signaling RL games into complex ones. Just the material in the book had versions with multiple agents signaling in parallel, one agent signaling without sequence, and agents signaling in sequence. The book also hints at cases where agents may make mistakes and that this is important for the evolution of signaling systems.

I also was coming across more and more research that isn’t covered in the book that looks at morphology and syntax in the emergence of language. Further more people were using deep learning to overcome the lewis signaling game inability of of arriving decoders for complex signals.

At this point I realized that there might be three problems that are being conflated in nature and that we might want to consider them separately as well as together.

1. the coordination problem - how agents learn a common convention for signaling and what is the most effective form of the solution.
2. the serialization problem - how the medium will e.g. a noisy channel can introduce additional desireable contraints like shorter signals, saliency, early decoding, (compression, error detection and correction, easy decoding, signal distributions, ). This problem is one which is solved by a descion tree. But the different options for the settings will lead to different optimal solutions. These are hidden by the symmetric form of the rewards in the lewis game.
3. the signal composition problem - given a simple signaling systems and a encoder decoder for the channel how can we add aggregation to the signaling system to make it more efficient. (more expressive, easier to learn, easier to extend, more robust to different errors.)

This might help answer questions like - why does english use just 39-44 phonems instead of the full we have a languages making a full use of human phonemes (600 consonants and 200 vowels) ?

What became apparent to me is that the nature of a complex signaling system, depends very much on the game being played by the agents.

Metrics:

• Total number of signals

• Minimal set of signals needed to learn the signalling system with n-learners with full observability of signal, action and reward by all learners.

• How long to learn saliency (the distribution states of the world) of signals perhaps adjusted by risk (the distribution of malleuses for wrong action in the each state of the world)

• How long to coordinate on a basic system with N states and N actions

• How to learn to coordinate on a huffman cannonical code to optimize a signaling system

• Learning and Coordinating via templates for complex signals

  • Degree of morphology
  • Degree of syntax
  • Degree of contextual meaning
  • Degree of coordination (and aggreement in templates) and its error correction capacity)

• Message entropy

• Robustness to error in sender, receiver, and channel

• Mean

• Regarding complex signaling systems he points out a couple of ideas:

  • Complex signals might be composed by simple signals from multiple senders.
    • The reciever needs to both decode and aggregate the simple signals to infer the state of the world encoded in the complex signal.
    • This is particularly interesting and less artificial once consider realize it leads to a partially observed markov decision process (PMDP).
      • senders have partial observability of the state of the world and
      • recievers need to reconstruct the state by aggregating partial messages
    • If we might also give the agents types and make the game a bayesian game.
      • Types are
        • Knights - with messages that are always true as well as thier atoms
        • Knaves - with messages that are always false.
        • Normals - with messages that are sometimes true and sometimes false.
        • Insane - who think that thier messages are always true but are actually always false.
        • etc
  • Complex signals might be composed by multiple simple signals from a single sender.
    • The complex signal is a bag of signals (i.e. aggregation is not unordered - buy via a conjunction of signals i.e. A and B = B and A).
    • The complex signal is ordered sequence of signals sequence of signals i.e. (A,B) \neq (B,A) .
    • Sequences of sequences can capture morphology.
    • Natural language adds the notion of recursion - which in terms of mathematically boils down to a a partial ordering of simple signals to form complex signals.

• There is a natural tendency to think about the Chomsky hierarchy of languages at this point.

• Also once there are sequences of signals we will naturally consider ideas from information theory.

  • Entropy of a signal
  • Error detection
  • Error correction
  • Source coding (compression)
  • Easy decoding of messages

• Errors are stated as important in the evolution of signaling systems in the paper of Nowak and Krakauer (1999).

  • we

• Compression and easy decoding are also important too but this came up later when people noticed that thier agents were learning very inefficient signaling systems (with very long signals)

  • this suggests that we add a parameter to the game to penalize long signals.
  • and to reward early decoding of the signal.

• Logic is also discussed in the

has an extensive bibliography and I have been following up on some of the references.

This is a quick summary of a talk by Marco Baroni on the topic of compositionality in language. In it he outlines some of his work and his collegues/students work on the topic and the conclusions he has drawn from it.