Mind and Computation Talk, Monday, Dec. 3

November 28, 2007

Musicat: a Model of Musical Expectation

Eric Nichols
Computer Science Department

Monday, Dec. 3, 2007, 4:00-5:30    
Ballantine Hall 005

In the field of music cognition, melodic expectation has been a topic of much interest in the past several decades. Several theoretical and computer models have been developed by experts in the field, but I contend that these models differ in significant ways from the way humans generate expectations. For instance, Margulis’ (2005) model, a synthesis of many major prior models, represents the state of the art: given an input piece of music, it simulates the process of listening to the music, one beat at a time, computing an expectation for each beat as a probability distribution over all possible successive notes. This distribution is based primarily on the shape of the melody in the preceding few notes and the harmonic context; a small set of formulas deterministically computes the probabilities. Absent from the model is flexible perception of the input; there is no room for creativity in the generated expectations.

The new model discussed in this talk, called Musicat (after Copycat and Metacat), extends Hofstadter and Mitchell’s Copycat architecture for use in a musical domain. Whereas Copycat and related programs operated on essentially static inputs, Musicat will take into account the temporal nature of music. Musicat will model the dynamic experience of listening as music unfolds through time, where representations and expectations are formed and quickly revised as new notes are perceived and previously perceived notes fade into memory.

In this talk I will first describe a pilot study in-progress to study melodic expectation. I recruited music students and recorded their improvised, sung responses to two-note melodic fragments. I will share preliminary results from analysis of this data and discuss how these results might influence the development of Musicat. Second, I will describe the overall architecture of Musicat and share some ideas for novel elements I hope to include in the program which were not present in earlier FARG models.


The Mind and Computation Talk Series is a forum for Indiana University Computer Science and Informatics students and faculty, as well as visitors to IU, who work in the areas of artificial intelligence and cognitive science to make presentations about their research. The talks are open to the general IU public and will be announced to the mailing lists of Computer Science, Informatics, and Cognitive Science. Students in the Cognitive Science PhD Program or in the Joint PhD Program in Cognitive Science and Computer Science or Informatics may satisfy the program’s public colloquium requirement by giving a talk in this series.


Knuth: Generating All Combinations

November 17, 2007

I ran into a tricky little problem today: efficiently generating all combinations of k elements from a set of size N. I came up with some ideas but they weren’t efficient enough. I turned to a Knuth Volume 4 preprint on his website, and found all sorts of crazy algorithms for it. Here is a C# implementation I just coded up and tested that people might find useful. It allows you to make a Combination object, and use foreach on it to get all the members.

Note that I had a chance to use the C# 2.0 yield statement; it let me do a fairly direct translation from the pseudocode, although I made a few tiny changes to simplify things. See the comments for a few ways to improve efficiency a tiny bit but it doesn’t affect time complexity. If I understood Knuth, this algorithm runs in O(N choose t) – it’s linear in the number of elements in the output.

Combination class code: Combination.cs

Test class: CombinationsTest.cs

See also: Combinadic on Wikipedia

Sample output:

***** CombinationsTest.CombinationTest.Enumerate2_5
0 1
0 2
1 2
0 3
1 3
2 3
0 4
1 4
2 4
3 4

0 1 2
0 1 3
0 2 3
1 2 3
0 1 4
0 2 4
1 2 4
0 3 4
1 3 4
2 3 4


Computer music composition patent

July 15, 2007

These patents are rather amusing:



More interesting are some composition-related programs, such as these:



…and an interesting idea on an application for improvised music in a computer gam.


Brazilian Fluid Concepts Class Library, etc.

June 20, 2007

Alexandre Linhares is teaching a seminar about Fluid Concepts, and has started a discussion on Google Groups related to the development of a general class library. It seems to be written in Delphi (Pascal) but I’m hoping he switches to Java. In any case, I think it’s long overdue and I’m looking forward to helping develop the library.

In other news, I just hauled another load of books over to my CRCC office. I have a ton of projects going on here over the summer, including recording people singing – it’s a melodic expectation experiment. We set up some recording gear and even recruited a few participants already. In parallel with the experiments, I’ll be working on my melodic expectation model, which I’ve named Musicat, to distinguish it from the older Seek Well programs and the Seek Well microdomain. Musicat uses an expanded version of the Seek Well domain to make things more musically plausible, at the expense of handling additional complexity. It’s a rather big “micro”-domain now.

In addition to those things, I’m working on an algorithm problem that came out of my music informatics research with Chris Raphael. I’m co-presenting a paper and a poster at ISMIR in Vienna this September, and this new problem will extend the work from the poster – it’s on automatic generation of fingerings for piano scores. It works surprisingly well. Also, I’m very pleased to be reviewing a draft of a new book by Dave Cope, and I’m curious to see how many of my suggestions end up getting incorporated into the published version; I’ve never done book reviewing/editing before.


Computational Aesthetics

February 6, 2007

The Winter 2006 AI Magazine (vol. 27, no. 4) mentions a workshop in the field of Computational Aesthetics and I’m intrigued that such a thing exists. The article describes the field as an interdisciplinary group of researchers “working quite directly on the modeling and manipulation of people’s perceptions of beauty and happiness.” Sadly, it seems to be a silly bunch of things such as “laughter detection”, “automatic dream analysis”, and “affect-based story rewriting”, whatever that is supposed to mean. One sentence caught my eye though:

Aesthetic reactions such as the sense of novelty and the genre of suspense are often the result of expectation violation and may be governed by underlying “sweet-spot” equilibriums.

The AAAI digital library has papers from the workshop – I may have to see if there is anything interesting, or if they define “sweet-spot”.


Review: Music and Probability (ch. 1-3)

January 24, 2007

This is my initial summary of chapters 1-3 of David Temperley’s new book. More to come as I read through the book!Music and Probability presents a collection of Temperley’s new Bayesian models for both monophonic and polyphonic rhythm detection and key detection from symbolic (MIDI-like) data. It also reviews several other Bayesian approaches to various problems in music perception. The first two chapters provide some motivation for the Bayesian approach and a basic review of conditional probability and cross-entropy.

Monophonic rhythm model

The first new model presented is for the detection of rhythm in monophonic data. The data consist of note onsets and off times. Pitch is also available in the dataset, but I believe this model does not use pitch information in any way. The output of the model is a metrical grid that has been aligned with the input data. The grid provides three levels of metric information: the mid-level tactus (corresponding, say, to quarter notes in 3/4 time), a higher-level (the measure level in this example) and a lower level (eighth notes). Either level can have a duple or triple relation to neighboring levels. Additionally, the model supports the “phase” of the upper level with respect to the tactus (there can be tactus pickup notes).

Input to the model is in terms of imprecise (expressive) human performance. Without any other information such as a score, the model determines the most likely metrical grid to fit the data. In essence, the model simply computes the most likely metrical structure given the surface-level performance, using Bayes’ rule: P(structure|surface) is proportional to P(surface|structure) * P(structure). In terms of his model, the goal is to find the metrical grid that maximizes P(grid|onset pattern). This is computed by maximizing P(onset pattern|grid) * P(grid).

These two probability expressions are computed using a generative model for metrical grids and onset patterns based on such grids. For instance, the model starts by making a probabilistic choice of duple vs. triple meter at the tactus level. These probabilities are derived from a training corpus (based on the Essen folksong collection). For example, there is a 76% chance of choosing duple meter (and 24% to choose triple). All these choice points in the generative model yield probabilities that can be multiplied together to give the overall probability of generating a particular metrical grid, and also for generating the given onset pattern based on the generated grid. (i.e. the data likelihood is computed given the grid). This likelihood is computed over all possible grids — a seemingly intractable problem that is naturally solved via dynamic programming.

Several paragraphs at the end of the chapter point out differences between this model and Raphael (2002). Results are given that show how Temperley’s earlier meter model (1999) performed better than this new Bayesian model, although he argues that this is not grounds for dismissing the model. As an aside, Temperley presents a useful metric for comparing results of rhythm models.



January 11, 2007

I’ve come across several interesting articles by Paul Smolensky recently. I’d never read any of his stuff before. There are a couple of papers in the CRCC files on the topic of temperature/simulated annealing and his “harmony theory” that seem useful. I also found his short chapter in Mind Design II titled “Connectionist Modeling: Neural Computation/Mental Connections” (1989). It looks to have a clear discussion about the subsymbolic paradigm.