Exact and approximate rhythm matching algorithms

An interesting problem in music information retrieval is to classify songs according to rhythms. A rhythm is represented by a sequence of “Quick” (Q) and “Slow” (S) symbols, which correspond to the (relative) duration of notes, such that S?=?2Q. Christodoulakis et?al. presented an efficient algorithm that can be used to classify musical sequences according to rhythms. In this article, the above algorithm is implemented, along with a naive brute force algorithm to solve the same problem. The theoretical time complexity bounds are analyzed with the actual running times achieved by the experiments, and the results of the two algorithms are compared. Furthermore, new efficient algorithms are presented that take temporal errors into account. This, the approximate pattern matching version, could not be handled by the algorithms previously presented. The running times of two algorithmic variants are analyzed and compared and examples of their implementation are shown.     

Function evaluation by incremental computation,with applications

Simulation of physical systems often requires repetitive evaluation of functions such as sine, cosine, exponential etc. The arguments of these functions are physical quantities, which usually change very little from one computation cycle to the next. An approach to function evaluation is proposed, which utilizes the “slowness” property in order to reduce computation time. This approach — “incremental process” — is, in a sense, a numerical solution of a differential equation whose solution is the desired function. The main drawback of incremental methods lies in the possibility of error propagation and accumulation. This phenomenon is very noticeable when the argument oscillates around a fixed value, since the errors grow while the true solution is nearly constant (“rectification” error). It was proposed that “reversible” incremental processes may exist, which will limit error propagation, in certain situations, by regaining their (exact) initial value whenever their argument returns to its initial value. We show that such reversible processes cannot exist for transcendental functions if their argument increments may assume any value within a permissible range. Placing certain reasonable restrictions on the increment values does lead, however, to algorithms which save computer time in comparison with conventional function evaluation algorithms. Several examples are presented.     

Affective content analysis of music emotion through EEG

Emotion recognition of music objects is a promising and important research issues in the field of music information retrieval. Usually, music emotion recognition could be considered as a training/classification problem. However, even given a benchmark (a training data with ground truth) and using effective classification algorithms, music emotion recognition remains a challenging problem. Most previous relevant work focuses only on acoustic music content without considering individual difference (i.e., personalization issues). In addition, assessment of emotions is usually self-reported (e.g., emotion tags) which might introduce inaccuracy and inconsistency. Electroencephalography (EEG) is a non-invasive brain-machine interface which allows external machines to sense neurophysiological signals from the brain without surgery. Such unintrusive EEG signals, captured from the central nervous system, have been utilized for exploring emotions. This paper proposes an evidence-based and personalized model for music emotion recognition. In the training phase for model construction and personalized adaption, based on the IADS (the International Affective Digitized Sound system, a set of acoustic emotional stimuli for experimental investigations of emotion and attention), we construct two predictive and generic models \(AN\!N_1\) (“EEG recordings of standardized group vs. emotions”) and \(AN\!N_2\) (“music audio content vs. emotion”). Both models are trained by an artificial neural network. We then collect a subject’s EEG recordings when listening the selected IADS samples, and apply the \(AN\!N_1\) to determine the subject’s emotion vector. With the generic model and the corresponding individual differences, we construct the personalized model H by the projective transformation. In the testing phase, given a music object, the processing steps are: (1) to extract features from the music audio content, (2) to apply \(AN\!N_2\) to calculate the vector in the arousal-valence emotion space, and (3) to apply the transformation matrix H to determine the personalized emotion vector. Moreover, with respect to a moderate music object, we apply a sliding window on the music object to obtain a sequence of personalized emotion vectors, in which those predicted vectors will be fitted and organized as an emotion trail for revealing dynamics in the affective content of music object. Experimental results suggest the proposed approach is effective.     

On the sequential nature of interprocedural program-analysis problems

In this paper, we study two interprocedural program-analysis problems—interprocedural slicing and interprocedural dataflow analysis— and present the following results:

? Interprocedural slicing is log-space complete forP.

? The problem of obtaining “meet-over-all-valid-paths” solutions to interprocedural versions of distributive dataflow-analysis problems isP-hard.

? Obtaining “meet-over-all-valid-paths” solutions to interprocedural versions of distributive dataflow-analysis problems that involve finite sets of dataflow facts (such as the classical “gen/kill” problems) is log-space complete forP.

These results provide evidence that there do not exist fast (N?-class) parallel algorithms for interprocedural slicing and precise interprocedural dataflow analysis (unlessP =N?). That is, it is unlikely that there are algorithms for interprocedural slicing and precise interprocedural dataflow analysis for which the number of processors is bounded by a polynomial in the size of the input, and whose running time is bounded by a polynomial in the logarithm of the size of the input. This suggests that there are limitations on the ability to use parallelism to overcome compiler bottlenecks due to expensive interprocedural-analysis computations.     

Emergent songs by social robots

This paper reports the first results of an innovative approach to modelling music cognition based on the emergent behaviour of interacting autonomous systems. A group of interactive autonomous singing robots were programmed to develop a shared repertoire of songs from scratch, after a period of spontaneous creations, adjustments and memory reinforcements. The robots interact with each other by means of vocal-like sounds. They use real sounds as opposed to software simulation. They are furnished with a physical model of the vocal tract, which synthesises vocal singing-like intonations, and a listening mechanism, which extracts pitch sequences from audio signals. The robots learn to imitate each other by babbling heard intonation patterns in order to evolve vectors of motor control parameters to synthesise the imitations. Models of the basic mechanisms underlying the emergence of songs are of great interest for musicians looking for hitherto unexplored ways to create music with interactive machines.     

Partitioned EDF scheduling: a closer look

The partitioned EDF scheduling of implicit-deadline sporadic task systems upon identical multiprocessor platforms is considered. The problem is known to be intractable, but many different polynomial-time algorithms have been proposed for solving it approximately. These different approximation algorithms have previously been compared using utilization bounds; they are compared here using a different metric—the speedup factor. It is shown that from the perspective of their speedup factors, the best partitioning algorithms are those that (i) assign the tasks in decreasing order of utilization; and (ii) are “reasonable” in the sense that they will assign a task if there is capacity available on some processor—such algorithms include the widely-used First-Fit Decreasing, Best-Fit Decreasing, and Worst-Fit Decreasing partitioning heuristics.     

Audio thumbnailing of popular music using chroma-based representations

With the growing prevalence of large databases of multimedia content, methods for facilitating rapid browsing of such databases or the results of a database search are becoming increasingly important. However, these methods are necessarily media dependent. We present a system for producing short, representative samples (or "audio thumbnails") of selections of popular music. The system searches for structural redundancy within a given song with the aim of identifying something like a chorus or refrain. To isolate a useful class of features for performing such structure-based pattern recognition, we present a development of the chromagram, a variation on traditional time-frequency distributions that seeks to represent the cyclic attribute of pitch perception, known as chroma. The pattern recognition system itself employs a quantized chromagram that represents the spectral energy at each of the 12 pitch classes. We evaluate the system on a database of popular music and score its performance against a set of "ideal" thumbnail locations. Overall performance is found to be quite good, with the majority of errors resulting from songs that do not meet our structural assumptions.     

A method to integrate an atom in a molecule without explicit representation of the interatomic surface

A method to obtain accurate integrated properties according to the theory of “Atoms in Molecules” for any atom is proposed. Classical integration algorithms using explicit representations of the interatomic surfaces (IAS) bounding the integrated atom suffer from the presence of regions where the charge density is extremely flat. This phenomenon is typically caused by ring critical points and leads to unacceptable integration errors. The present paper extends a previously published integration algorithm (Mol. Phys. 87 (1996) 1169) by introducing a procedure that can find an atomic boundary if the interatomic surface is not explicitly known. This hybrid algorithm — which uses analytical interatomic surfaces whenever they are available and adequate but does not necessarily require them — enables the accurate and efficient integration of any atom. A robust and effective code is implemented in MORPHY97 and applied to two representative examples.     

Generalized predictive control—Part I. The basic algorithm

Current self-tuning algorithms lack robustness to prior choices of either dead-time or model order. A novel method—generalized predictive control or GPC—is developed which is shown by simulation studies to be superior to accepted techniques such as generalized minimum-variance and pole-placement. This receding-horizon method depends on predicting the plant's output over several steps based on assumptions about future control actions. One assumption—that there is a “control horizon” beyond which all control increments become zero—is shown to be beneficial both in terms of robustness and for providing simplified calculations. Choosing particular values of the output and control horizons produces as subsets of the method various useful algorithms such as GMV, EPSAC, Peterka's predictive controller (1984, Automatica, 20, 39–50) and Ydstie's extended-horizon design (1984, IFAC 9th World Congress, Budapest, Hungary). Hence GPC can be used either to control a “simple” plant (e.g. open-loop stable) with little prior knowledge or a more complex plant such as nonminimum-phase, open-loop unstable and having variable dead-time. In particular GPC seems to be unaffected (unlike pole-placement strategies) if the plant model is overparameterized. Furthermore, as offsets are eliminated by the consequence of assuming a CARIMA plant model, GPC is a contender for general self-tuning applications. This is verified by a comparative simulation study.     

Pattern recognition by means of disjoint principal components models

Pattern recognition based on modelling each separate class by a separate principal components (PC) model is discussed. These PC models are shown to be able to approximate any continuous variation within a single class. Hence, methods based on PC models will, provided that the data are sufficient, recognize any pattern that exists in a given set of objects. In addition, fitting the objects in each class by a separate PC model will, in a simple way, provide information about such matters as the relevance of single variables, “outliers” among the objects and “distances” between different classes. Application to the classical Iris-data of Fisher is used as an illustration.     

Yield grammar analysis and product optimization in a domain-specific language for dynamic programming

Dynamic programming algorithms are traditionally expressed by a set of matrix recurrences—a low level of abstraction, which renders the design of novel dynamic programming algorithms difficult and makes debugging cumbersome.Bellman's GAP is a declarative, domain-specific language, which supports dynamic programming over sequence data. It implements the algebraic style of dynamic programming and allows one to specify algorithms by combining so-called yield grammars with evaluation algebras. Products on algebras allow to create novel types of analyses from already given ones, without modifying tested components. Bellman's GAP extends the previous concepts of algebraic dynamic programming in several respects, such as an “interleaved” product operation and the analysis of multi-track input.Extensive analysis of the yield grammar and the evaluation algebras is required for generating efficient imperative code from the algebraic specification. This article gives an overview of the analyses required and presents several of them in detail. Measurements with “real-world” applications demonstrate the quality of the code produced.     

TopPI: An efficient algorithm for item-centric mining

In this paper, we introduce item-centric mining, a new semantics for mining long-tailed datasets. Our algorithm, TopPI, finds for each item its top-k most frequent closed itemsets. While most mining algorithms focus on the globally most frequent itemsets, TopPI guarantees that each item is represented in the results, regardless of its frequency in the database.TopPI allows users to efficiently explore Web data, answering questions such as “what are the k most common sets of songs downloaded together with the ones of my favorite artist?”. When processing retail data consisting of 55 million supermarket receipts, TopPI finds the itemset “milk, puff pastry” that appears 10,315 times, but also “frangipane, puff pastry” and “nori seaweed, wasabi, sushi rice” that occur only 1120 and 163 times, respectively. Our experiments with analysts from the marketing department of our retail partner demonstrate that item-centric mining discover valuable itemsets. We also show that TopPI can serve as a building-block to approximate complex itemset ranking measures such as the p-value.Thanks to efficient enumeration and pruning strategies, TopPI avoids the search space explosion induced by mining low support itemsets. We show how TopPI can be parallelized on multi-cores and distributed on Hadoop clusters. Our experiments on datasets with different characteristics show the superiority of TopPI when compared to standard top-k solutions, and to Parallel FP-Growth, its closest competitor.     

基于情感向量空间模型的歌曲情感标签预测模型

音乐的情感标签预测对音乐的情感分析有着重要的意义。该文提出了一种基于情感向量空间模型的歌曲情感标签预测算法,首先,提取歌词中的情感特征词构建情感空间向量模型,然后利用SVM分类器对已知情感标签的音乐进行训练,通过分类技术找到与待预测歌曲情感主类一致的歌曲集合,最后,通过歌词的情感相似度计算找到最邻近的k首歌曲,将其标签推荐给待预测歌曲。实验发现本文提出的情感向量空间模型和“情感词—情感标签”共现的特征降维方法比传统的文本特征向量模型能够更好地提高歌曲情感分类准确率。同时,在分类基础上进行的情感标签预测方法可以有效地防止音乐“主类情感漂移”,比最近邻居方法达到更好的标签预测准确率。     

An Analysis of Linear Subspace Approaches for Computer Vision and Pattern Recognition

Linear subspace analysis (LSA) has become rather ubiquitous in a wide range of problems arising in pattern recognition and computer vision. The essence of these approaches is that certain structures are intrinsically (or approximately) low dimensional: for example, the factorization approach to the problem of structure from motion (SFM) and principal component analysis (PCA) based approach to face recognition. In LSA, the singular value decomposition (SVD) is usually the basic mathematical tool. However, analysis of the performance, in the presence of noise, has been lacking. We present such an analysis here. First, the “denoising capacity” of the SVD is analysed. Specifically, given a rank-r matrix, corrupted by noise—how much noise remains in the rank-r projected version of that corrupted matrix? Second, we study the “learning capacity” of the LSA-based recognition system in a noise-corrupted environment. Specifically, LSA systems that attempt to capture a data class as belonging to a rank-r column space will be affected by noise in both the training samples (measurement noise will mean the learning samples will not produce the “true subspace”) and the test sample (which will also have measurement noise on top of the ideal clean sample belonging to the “true subspace”). These results should help one to predict aspects of performance and to design more optimal systems in computer vision, particularly in tasks, such as SFM and face recognition. Our analysis agrees with certain observed phenomenon, and these observations, together with our simulations, verify the correctness of our theory.     

Deviation Analysis: A New Use of Model Checking

Inaccuracies, or deviations, in the measurements of monitored variables in a control system are facts of life that control software must accommodate. Deviation analysis can be used to determine how a software specification will behave in the face of such deviations. Deviation analysis is intended to answer questions such as “What is the effect on output O if input I is off by 0 to 100?”. This property is best checked with some form of symbolic execution approach. In this report we wish to propose a new approach to deviation analysis using model checking techniques. The key observation that allows us to use model checkers is that the property can be restated as “Will there be an effect on output O if input I is off by 0 to 100?”—this restatement of the property changes the analysis from an exploratory analysis to a verification task suitable for model checking.     

An experimental study of energy dips for speech and music

Speech signals generally have many intervals with low energy “energy dips”. For music signals, energy dips are not always remarkable. We studied stochastic features of energy dips for speech and music signals. A certain difference was found between the signals in the length of energy dips. Also, the number of energy dips in a time window and their distribution were investigated. From this distribution, a threshold number of energy dips was estimated which provided a scheme for the discrimination of speech from music.     

Classification accuracy is not enough

We argue that an evaluation of system behavior at the level of the music is required to usefully address the fundamental problems of music genre recognition (MGR), and indeed other tasks of music information retrieval, such as autotagging. A recent review of works in MGR since 1995 shows that most (82 %) measure the capacity of a system to recognize genre by its classification accuracy. After reviewing evaluation in MGR, we show that neither classification accuracy, nor recall and precision, nor confusion tables, necessarily reflect the capacity of a system to recognize genre in musical signals. Hence, such figures of merit cannot be used to reliably rank, promote or discount the genre recognition performance of MGR systems if genre recognition (rather than identification by irrelevant confounding factors) is the objective. This motivates the development of a richer experimental toolbox for evaluating any system designed to intelligently extract information from music signals.     

Multilayer grid embeddings for VLSI

In this paper we propose two new multilayer grid models for VLSI layout, both of which take into account the number of contact cuts used. For the first model in which nodes “exist” only on one layer, we prove a tight area × (number of contact cuts) = Θ(n ²) tradeoff for embeddingn-node planar graphs of bounded degree in two layers. For the second model in which nodes “exist” simultaneously on all layers, we give a number of upper bounds on the area needed to embed groups using no contact cuts. We show that anyn-node graph of thickness 2 can be embedded on two layers inO(n ²) area. This bound is tight even if more layers and any number of contact cuts are allowed. We also show that planar graphs of bounded degree can be embedded on two layers inO(n ^3/2(logn)²) area. Some of our embedding algorithms have the additional property that they can respect prespecified grid placements of the nodes of the graph to be embedded. We give an algorithm for embeddingn-node graphs of thicknessk ink layers usingO(n ³) area, using no contact cuts, and respecting prespecified node placements. This area is asymptotically optimal for placement-respecting algorithms, even if more layers are allowed, as long as a fixed fraction of the edges do not use contact cuts. Our results use a new result on embedding graphs in a single-layer grid, namely an embedding ofn-node planar graphs such that each edge makes at most four turns, and all nodes are embedded on the same line.     

Action graphs and user performance analysis

A user operating an interactive system performs actions such as “pressing a button” and these actions cause state transitions in the system. However to perform an action, a user has to do what amounts to a state transition themselves, from the state of having completed the previous action to the state of starting to perform the next action; this user transition is out of step with the system's transition. This paper introduces action graphs, an elegant way of making user transitions explicit in the arcs of a graph derived from the system specification. Essentially, a conventional transition system has arcs labeled in the form “user performs action A” whereas an action graph has arcs labelled in the form “having performed action P, the user performs Q.” Action graphs support many modelling techniques (such as GOMS, KLM or shortest paths) that could have been applied to the user's actions or to the system graph, but because it combines both, the modelling techniques can be used more powerfully.Action graphs can be used to directly apply user performance metrics and hence perform formal evaluations of interactive systems. The Fitts Law is one of the simplest and most robust of such user modelling techniques, and is used as an illustration of the value of action graphs in this paper. Action graphs can help analyze particular tasks, any sample of tasks, or all possible tasks a device supports—which would be impractical for empirical evaluations. This is an important result for analyzing safety critical interactive systems, where it is important to cover all possible tasks in testing even when doing so is not feasible using human participants because of the complexity of the system.An algorithm is presented for the construction of action graphs. Action graphs are then used to study devices (a consumer device, a digital multimeter, an infusion pump) and results suggest that: optimal time is correlated with keystroke count, and that keyboard layout has little impact on optimal times. Many other applications of action graphs are suggested.