Il est raisonnable de considérer qu'un auditeur ne perçoit pas la musique comme une simple séquence de sons, pas plus que le compositeur n'a conçu son morceau comme tel. La musique est en effet constituée de motifs dont l'organisation intrinsèque et les relations mutuelles participent à la structuration du propos musical, et ce à plusieurs échelles simultanément. Cependant, il est aujourd'hui encore très difficile de définir précisément le terme de concept musicale. L'un des principaux aspects de la musique est qu'elle est en grande partie constituée de redondances, sous forme de répétitions exactes et variées. L'organisation de ces redondances permet de susciter une attente chez l'auditeur. Une surprise peut alors être créée en présentant des éléments qui ne correspondent pas à cette attente. Ce travail de thèse se base sur l'hypothèse que les redondances, l'attente et la surprise sont des éléments essentiels pour la description de la structure musicale d'un segment. Un certain nombre de questions découlent de ce constat: quels sont les éléments musicaux qui participent à la structure d'un objet musical ? Quelles sont les dépendances entre ces éléments qui jouent un rôle essentiel dans la structuration d'un objet musical ? Comment peut-on décrire une relation entre deux éléments musicaux tels que des accords, des motifs rythmiques ou mélodiques ? Dans ce manuscrit, des éléments de réponse sont proposés par la formalisation et l'implémentation d'un modèle multi-échelle de description de la structure d'un segment musical : les Graphes Polytopiques à Relations Latentes (GPRL/PGLR). Dans ce travail, les segments considérés sont les sections successives qui forment une pièce musicale. Dans le cas de la pop, genre musical sur lequel se concentre ce travail, il s'agit typiquement d'un couplet ou d'un refrain, de 15 sec. environ, comprenant un début et une fin bien définis. En suivant le formalisme PGLR, les relations de dépendance prédominantes entre éléments musicaux d'un segment sont celles qui relient les éléments situés à des positions homologues sur la grille métrique du segment. Cette approche généralise sur le plan multi-échelle le modèle Système&Contraste qui décrit sous la forme d'une matrice 2×2 le système d'attente logique au sein d'un segment et la surprise qui découle de la réalisation de cette attente. Pour des segments réguliers de taille 2^n, le PGLR peut être représenté sur un n-cube (carré, cube, tesseract, ...), où n est le nombre d'échelles considérées. Chaque nœud du polytope correspond à un élément musical fondamental (accord, motif, note...), chaque arête représente une relation entre deux nœuds et chaque face représente un système de relations. La recherche du PGLR correspondant à la meilleure description de la structure d'un segment musical s'opère par l'estimation jointe : de la description du polytope (un n-polytope plus ou moins régulier) ; de la configuration du graphe sur le polytope, permettant de décrire le flux de dépendance et les interactions entre les éléments par des implications élémentaires systémiques au sein du segment ; la description de l'ensemble des relations entre les nœuds du graphe. Le but du modèle PGLR est à la fois de décrire les dépendances temporelles entre les éléments d'un segment et de modéliser l'attente logique et la surprise qui découlent de l'observation et de la perception des similarités et des différences entre ces éléments. Cette approche a été formalisée et implémentée pour décrire la structure de séquences d'accords ainsi que de segments rythmiques et mélodiques, puis évaluée par sa capacité à prédire des segments inconnus. La mesure utilisée pour cette évaluation est la perplexité croisée calculée à partir des données du corpus RWC POP. Les résultats obtenus donnent un large avantage à la méthode multi-échelle proposée, qui semble mieux à même de décrire efficacement la structure des segments testés. / In this thesis, we approach these questions by defining and implementing a multi-scale model for music segment structure description, called Polytopic Graph of Latent Relations (PGLR). In our work, a segment is the macroscopic constituent of the global piece. In pop songs, which is the main focus here, segments usually correspond to a chorus or a verse, lasting approximately 15 seconds and exhibiting a clear beginning and end. Under the PGLR scheme, relationships between musical elements within a musical segment are assumed to be developing predominantly between homologous elements within the metrical grid at different scales simultaneously. This approach generalises to the multi-scale case the System&Contrast framework which aims at describing, as a 2×2 square matrix, the logical system of expectation within a segment and the surprise resulting from that expectation. For regular segments of 2^n events, the PGLR lives on a n-dimensional cube (square, cube, tesseract, etc...), n being the number of scales considered simultaneously in the multi-scale model. Each vertex in the polytope corresponds to a low-scale musical element, each edge represents a relationship between two vertices and each face forms an elementary system of relationships. The estimation of the PGLR structure of a musical segment can then be obtained computationally as the joint estimation of : the description of the polytope (as a more or less regular n-polytope) ; the nesting configuration of the graph over the polytope, reflecting the flow of dependencies and interactions as elementary implication systems within the musical segment, the set of relations between the nodes of the graph. The aim of the PGLR model is to both describe the time dependencies between the elements of a segment and model the logical expectation and surprise that can be built on the observation and perception of the similarities and differences between elements with strong relationships. The approach is presented conceptually and algorithmically, together with an extensive evaluation of the ability of different models to predict unseen data, measured using the cross-perplexity value. These experiments have been conducted both on chords sequences, rhythmic and melodic segments extracted from the RWC POP corpus. Our results illustrate the efficiency of the proposed model in capturing structural information within such data.

[Formulae and special characters can only be approximated here. Please see the pdf version of the abstract for an accurate reproduction.] This thesis reviews, extends and applies to urban traffic analysis the entropy concept of Shannon and Luce's mathematical psychology in a fairly complex and mathematically demanding model of human decision making, if it is solved as a deeply nested structure of logit calculus. Recognising consumers' different preferences and the universal propensity to seek the best choice when going to some desired goal (k), a transparent mathematical program (MP) is developed: the equivalent of a nested multinomial logit model without its inherent computational difficulty. The MP model makes a statistical assessment of individual decisions based on a randomised (measurable) utility within a given choice structure: some path through a diagram (Rk, Dk), designed a priori, of a finite number of sequential choices. The Equivalence Theorem (ET) formalises the process and states a non-linear MP with linear constraints that maximises collective satisfaction: utility plus weighted entropy, where the weight (1/θn) is a behavioural parameter to be calibrated in each case, eg for the Perth CBD. An optimisation subject to feasible routes through the (Rk, Dk) network thus captures the rational behaviour of consumers on their individually different best-choice decision paths towards their respective goals (k). This theory has been applied to urban traffic assignment before: a Stochastic User Equi-librium (SUE). What sets this thesis apart is its focus on MP models that can be solved with standard Operations Research software (eg MINOS), models for which the ET is a conditio sine qua non. A brief list of SUE examples in the literature includes Fisk's logit SUE model in (impractically many) route flows. Dial's STOCH algorithm obviates path enumeration, yet is a logit multi-path assignment procedure, not an MP model; it is nei-ther destination oriented nor an optimisation towards a SUE. A revision of Dial's method is provided, named STOCH[k], that computes primal variables (node and link flows) and Lagrangian duals (the satisfaction difference n→k). Sheffi & Powell presented an unconstrained optimisation problem, but favoured a probit SUE, defying closed formulae and standard OR software. Their model corresponds to the (constrained) dual model here, yet the specifics of our primary MP model and its dual are possible only if one restricts himself to logit SUE models, including the ET, which is logit-specific. A real world application needs decomposition, and the Perth CBD example is iteratively solved by Partial Linearisation, switching from (measured) disutility minimisation to Sheffi & Powell's Method of Successive Averages near the optimum. The methodology is demonstrated on the Perth Central Business District (CBD). To that end, parameter Θ is calibrated on Main Roads' traffic count data over the years 1997/98 and 1998/99. The method is a revision of Liu & Fricker's simultaneous estimation of not only Θ but an appropriate trip matrix also. Our method handles the more difficult variable costs (congestion), incomplete data (missing observations) and observation errors (wrong data). Finally, again based on Main Roads' data (a sub-area trip matrix), a Perth CBD traffic assignment is computed, (a) as a logit SUE and - for comparison - (b) as a DUE (using the PARTAN method of Florian, Guélat and Spiess). The results are only superficially similar. In conclusion, the methodology has the potential to replace current DUE models and to deepen transport policy analysis, taking into account individual behaviour and a money-metric utility that quantifies 'social benefits', for instance in a cost-benefit-analysis.

Un stable (ou ensemble indépendant) est un ensemble de sommets qui sont deux à deux non adjacents. De nombreux résultats classiques en optimisation combinatoire portent sur le nombre de stabilité (défini comme la plus grande taille d'un stable), et les stables se classent certainement parmi les structures les plus simples et fondamentales en théorie des graphes.<p><p>La thèse est divisée en deux parties, toutes deux liées à la notion de stables dans un graphe. Dans la première partie, nous étudions un problème de coloration de graphes, c'est à dire de partition en stables, où le but est de minimiser l'entropie de la partition. C'est une variante du problème classique de minimiser le nombre de couleurs utilisées. Nous considérons aussi une généralisation du problème aux couvertures d'ensembles. Ces deux problèmes sont appelés respectivement minimum entropy coloring et minimum entropy set cover, et sont motivés par diverses applications en théorie de l'information et en bioinformatique. Nous obtenons entre autres une caractérisation précise de la complexité de minimum entropy set cover :le problème peut être approximé à une constante lg e (environ 1.44) près, et il est NP-difficile de faire strictement mieux. Des résultats analogues sont prouvés concernant la complexité de minimum entropy coloring.<p><p>Dans la deuxième partie de la thèse, nous considérons les graphes dont le nombre de stabilité augmente dès qu'une arête est enlevée. Ces graphes sont dit être "alpha-critiques", et jouent un rôle important dans de nombreux domaines, comme la théorie extrémale des graphes ou la combinatoire polyédrique. Nous revisitons d'une part la théorie des graphes alpha-critiques, donnant à cette occasion de nouvelles démonstrations plus simples pour certains théorèmes centraux. D'autre part, nous étudions certaines facettes du polytope des ordres totaux qui peuvent être vues comme une généralisation de la notion de graphe alpha-critique. Nous étendons de nombreux résultats de la théorie des graphes alpha-critiques à cette famille de facettes.<p> / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

The problem of identifying clusters arising in the context of topic models and related approaches is important in the area of machine learning. The problem concerning traversals on Concept Association Networks is of great interest in the area of cognitive modelling. Cluster identification is the problem of finding the right number of clusters in a given set of points(or a dataset) in different settings including topic models and matrix factorization algorithms. Traversals in Concept Association Networks provide useful insights into cognitive modelling and performance. First, We consider the problem of authorship attribution of stylometry and the problem of cluster identification for topic models. For the problem of authorship attribution we show empirically that by using stop-words as stylistic features of an author, vectors obtained from the Latent Dirichlet Allocation (LDA) , outperforms other classifiers. Topics obtained by this method are generally abstract and it may not be possible to identify the cohesiveness of words falling in the same topic by mere manual inspection. Hence it is difficult to determine if the chosen number of topics is optimal. We next address this issue. We propose a new measure for topics arising out of LDA based on the divergence between the singular value distribution and the L1 norm distribution of the document-topic and topic-word matrices, respectively. It is shown that under certain assumptions, this measure can be used to find the right number of topics. Next we consider the Non-negative Matrix Factorization(NMF) approach for clustering documents. We propose entropy based regularization for a variant of the NMF with row-stochastic constraints on the component matrices. It is shown that when topic-splitting occurs, (i.e when an extra topic is required) an existing topic vector splits into two and the divergence term in the cost function decreases whereas the entropy term increases leading to a regularization. Next we consider the problem of clustering in Concept Association Networks(CAN). The CAN are generic graph models of relationships between abstract concepts. We propose a simple clustering algorithm which takes into account the complex network properties of CAN. The performance of the algorithm is compared with that of the graph-cut based spectral clustering algorithm. In addition, we study the properties of traversals by human participants on CAN. We obtain experimental results contrasting these traversals with those obtained from (i) random walk simulations and (ii) shortest path algorithms.