Music as an information-bearing medium: extracting latent structure for theoretical and practical purposes

Music is an information-bearing medium, containing highly structured signals. Its complexity derives from its information-rich structure and enables music to be molded to the imagination of any creator, regardless of time or geography. This thesis investigates the rich information encoded in the temporal structure of music. It represents rhythm as a progression of musical event durations (a note or a silence), and uses similarities hidden in different layers of musical rhythm to construct a structural identity (temporal scale-free features). These temporal scale-free structures are used for longitudinal analysis of compositions in a composer's oeuvre, and are applied as composer descriptors for classification in two large Western and non-Western music score repertoires. That is, this work presents the scale-free structural features in rhythm as a universal, information-rich feature set. More precisely, temporal scale-free correlation exponents are computed for two major music categories: Western and non-Western compositions. Collections containing these categories --- 1165 and 1498 music pieces respectively --- are further sub-categorized by composer name (Western Collection) and geographical region or country of origin (non-Western Collection). The analysis provides a more granular, composer-by-composer validation of the scale-free structure of rhythm in the Western collection. This indicates that such exponents vary for composers of different musical eras, distinct time periods and various countries of origin. Moreover, for a particular composer, though there are key similarities between different compositions' temporal scale-free exponents, they exhibit non-negligible variation during the course of the composer's professional life. These variations can account for the high accuracy in the classification results for (1) Western composers from disparate eras or with distinct compositional styles (e.g., Gershwin versus Mozart); (2) non-Western regions of distinct musical style and heritage (e.g., Chinese versus Persian music); and (3) Western versus non-Western pieces. In the second part of this thesis, rich information in music and particular features of human musical cognition are used to expand the existing CAPTCHA paradigm --- wherein problems that are easy for humans but which cannot yet be solved efficiently by computer programs are used to distinguish between humans and automated music analysis programs (computational Turing test). The ubiquity of music across all cultures, its complex structure at different layers, and the perceptual characteristics and limitations of the human auditory system are leveraged to construct more accessible, aesthetically pleasing and secure computational Turing tests. Music-based CAPTCHAs, called mCaptchas, are introduced to improve Web accessibility for individuals with visual impairments, to help avoid susceptibility to security flaws of existing audio CAPTCHAs, and to improve the overall user experience. The mCaptcha scheme generates musical streams which can be heard as two by humans, but which appear as a single inseparable unit of music to the state-of-the-art automated programs. A user is presented with a contextual question based on a popular song which the user can identify in the composite music stream (challenge). The security of the scheme lies in the fact that state-of-the-art music analysis programs cannot yet solve the challenge correctly before the mCaptcha expires. Empirical evidence of the scheme's security is presented for over 2000 mCaptchas, while its usability is tested by approximately 500 individuals on the Amazon Mechanical Turk (AMT) online market. These results demonstrate that humans can efficiently and accurately solve the generated music-based challenges while sophisticated computer programs fail.La musique est un support d'information contenant des signaux hautement structurés. La complexité de la musique découle de la richesse informative de sa structure qui lui permet de se conformer à l'imaginaire de chaque créateur, quelle que soit l'époque ou la localisation géographique. La présente thèse examine la richesse informative dissimulée dans la structure temporelle de la musique. Cette thèse envisage le rythme comme une progression de la durée d'événements musicaux (une note ou un silence) et utilise les similarités dissimulées dans les différentes couches de rythme musical pour construire une identité structurelle (caractéristiques temporelles libres d'échelle). Ces structures temporelles libres d'échelle sont utilisées pour une analyse longitudinale d'un échantillon des compositions faisant partie de d'oeuvre d'un compositeur. Elles sont également appliquées comme des descripteurs de l'oeuvre d'un compositeur en vue d'une classification des compositions en deux grands répertoires, occidental et non-occidental. C'est-à-dire, ce travail présente les caractéristiques structurelles libres d'échelle du rythme comme un ensemble de caractéristiques universelles riches en information. Plus précisément, ces exposants de la corrélation temporelle libre d'échelle sont calculés dans deux catégories: compositions occidentales et non-occidentales. Ces catégories, contenant respectivement 1165 et 1498 pièces musicales, sont ensuite divisées en sous-catégories, par nom du compositeur (collection occidental) et sa région ou son pays d'origine (collection non-occidentales). Cette analyse fournisse une validation plus granulaire, compositeur par compositeur, de la structure rythmique libre d'échelle dans le répertoire occidental. Cela indique que de tels exposants varient pour les compositeurs de différentes époques musicales, différentes périodes et différents pays d'origine. De plus, malgré l'existence de similarités majeures entre les exposants temporels libres d'échelle des compositions d'un compositeur, ces exposants varient d'une manière significative au cours de la vie professionnelle. Ces variations peuvent expliquer la grande précision des résultats de la classification pour (1) les compositeurs occidentaux venant de différentes époques ou présentant des styles de composition différents (par ex., Gershwin versus Mozart); (2) les régions non-occidentales caractérisées par un style et un héritage musical particulier (par ex., musique chinoise versus musique perse); et (3) les morceaux de musique occidentale versus non-occidentale. Dans la deuxième partie de la présente thèse, la richesse informative de la musique et les caractéristiques particulières de la cognition musicale humaine sont utilisées afin d'élargir le paradigme CAPTCHA existant. Dans ce paradigme, des problèmes facilement résolus par les humains, mais que les programmes informatiques ne parviennent pas encore à résoudre, sont utilisés pour distinguer la manière dont ces problèmes sont résolus par les humains et les programmes d'analyse de la musique automatisés (test de Turing). L'ubiquité de la musique à travers toutes les cultures, la structure très complexe des différentes couches qui la constituent, ainsi que nos connaissances des caractéristiques et des limitations de la perception auditive humaine permettent aujourd'hui de construire des tests de Turing plus accessibles, plus agréables esthétiquement et mieux sécurisés. Je présente les mCAPTCHAs, CAPTCHAs basés sur la musique pour répondre à plusieurs objectifs: améliorer l'accessibilité au Web pour les individus souffrant de handicaps visuels, diminuer la vulnérabilité des CAPTCHAs audio existants aux brèches de sécurité, et améliorer l'expérience générale de l'utilisateur. Le schéma mCAPTCHA génère des flux musicaux pouvant être décomposés en 2 pièces musicale distinctes par ségrégation auditive chez les humains, tout en étant considérés comme des unités musicales monolithiques par les programmes automatisés actuels. Un utilisateur reçoit une question contextuelle basée sur une chanson populaire incluse dans ce flux musical généré (défi). La sécurité du schéma réside dans le fait que les programmes actuels les plus sophistiqués ne sont pas encore capables de résoudre correctement le défi avant l'expiration du mCAPTCHA. L'évidence empirique de la sécurité de ces schémas est présentée pour plus de 2000 mCAPTCHAs, tandis que sa convivialité a été testée par environ 500 individus sur le marché en ligne Amazon MechanicalTurk. Ces résultats démontrent que les humains peuvent efficacement et correctement résoudre les défis musicaux générés, là où les logiciels les plus sophistiqués échouent