Current MS Students/Steven Emory/Thesis Prospectus
From CSWiki
Thesis: GA-Based Musical Transcription for Guitar
Contents |
[edit] What I am planning to accomplish
Musical transcription (Figure 1), the process of converting a musical score meant for one set of instruments to another, is still a very open problem in computer science. Transcriptions are very common and popular, especially for polyphonic target instruments such as the piano and guitar, where the process of transcription is difficult because playability problems oftentimes arise, making the transcription process challenging even for a knowledgeable musician.
The primary goals for this thesis are to explore ways (old and new) of generating transcriptions for the guitar that are as good as, or better than, what a knowledgeable human musician would make following the same set of rules.
The rules are:
- You can delete notes (Figure 1)
- You can shorten notes (Figure 2)
- You can shift notes in octaves (Figure 3)
- You can change keys signatures (Figure 4)
- You can use alternate instrument tunings (preferably only common ones)
- You cannot add new notes that are not present in the original score
Figure 1
Deleting Notes: Moonlight Sonata Excerpt
The notes labeled in red are not considered in the transcription because they are not playable on the guitar. Top two staffs are Piano, bottom two staffs are guitar and guitar tablature.
Figure 2
Shortening Notes: Moonlight Sonata Excerpt
The C# (red note) had to be shortened to make this specific transcription playable because the finger holding down that note is needed to play other (latter) notes. A few notes also had to be deleted (blue notes).
Figure 4
Changing Key Signatures Notes: Moonlight Sonata Excerpt
The top guitar piece is in the original key of C# minor, the bottom piece is in the transposed key of A minor. Having it in a key more natural to the guitar typically increases playability.
[edit] Issues to be investigated
The Playability/Fingering Problem
Previous research into the transcription problem has formulated it as a problem in heuristic optimization, with greedy hill climbing, genetic algorithms, and artificial neural networks as potential ways to solve the problem. However, previous authors have noted that these methods are particularly slow (especially the genetic algorithm based one) because playability testing (also known as The Fingering Problem -- given an input score for an instrument, determine if the piece is playable and return the most optimal way to play it), which needs to occur for every guess at a potential transcription, is a slow process. For each guess, the transcription algorithm has to search the entire “fingering space” for the best possible fingering because a transcription is oftentimes partially judged on how hard or easy it is to play. This is most important for the guitar, where the “fingering space” is quite large.
Therefore, instead of using genetic algorithms to find the best fingering, other algorithms such as A* will be tested, since the fingering problem is essentially a minimal-weight graph path-finding problem.
The Transcription Problem
Likewise, the transcription problem should also be able to be solved using other heuristic-based optimization methods such as other types of genetic algorithms, evolutionary strategies, and particle swarm optimization. A comparison and analysis of different optimization techniques will be discussed.
Alternate Key Signatures
The normal guitar tuning is E-A-D-G-B-E, which is why scores written in flat and sharp keys are very uncommon to the guitar. Therefore most popular classical guitar pieces transcribed from other instruments have been transposed to different keys for transcription. This is typically done to fit original scores written in sharp and flat keys that are unnatural and uncommon to the guitar (like Bb) to more common ones (like Amaj, Emaj, Cmaj, GMaj, DMaj, Amin, and Emin). Adding this search space to the original problem might increase our chances of finding a good and playable solution.
Alternate Tunings
For many classical pieces written in D, it is very common to change the normal guitar tuning to D-A-D-G-B-E or D-A-D-G-B-D instead. The question here is, what alternate tuning is optimal (generates the highest playable fitness)? An if there is an optimal alternate tuning, do we even really want to use it (most guitarists will scoff at too many odd tunings)? However alternate tunings such as D-A-D-G-B-E, D-A-D-G-B-D, D-G-D-G-B-E, E-A-D-F#-B-E are very common and can be added to the search space.
Minimal Instruments
If an original musical score is too complex, there may be no choice but to arrange it for multiple guitars. Guitar duets, trios, and quartets are quite common so it would be interesting to see if a computer algorithm can determine the minimal number of instruments needed to play a complex piece and which instrument plays which parts in such a way that no instruments goes too long without playing anything (how to evenly divide the piece to make all instrumentalists happy).
Human Assistance
Since there is no obvious or concrete fitness function that defines the transcription problem, there might be some cases where human computation would be useful (a human decides what specific notes are necessary and lets the computer algorithm handle the rest). However, this would require a user interface.
[edit] Annotated table of contents
Introduction
This section describes the transcription problem, and explains why it's important to those researching music topics in computer science. It will also explain why the problem is difficult to solve, how others have previously tried solving it, and summary of my contributions to it as well.
Preprocessing Steps
Before running any transcription algorithm, the entire original musical score has to be converted to the key(s) of the target instrument(s). Previous research has shown that it is also helpful to have all melodies, counter melodies, harmony, and bass lines clearly defined so that the transcription algorithm can weight the fitness of eliminated notes based on their importance to the overall score. For example, notes in the melody are more important than notes in the harmony.
The Playability Problem
Since the playability problem needs to be solved for each guess at a transcription, a discussion on the techniques used to solve it will occur here. It is very important to have an efficient and fast algorithm to determine playability because this test is a known bottleneck in the transcription problem.
Also, since anything that enhances the chance of the transcription algorithm of finding a playable transcription with a high fitness quickly, improves the algorithm, a discussion on things that help improve playability on a target instrument, such as transposition and alternate tunings, will occur here.
- Introduction
- Genetic Algorithm Based Approaches
- Graph Search and Minimal Weight Path Finding Based Approaches
- A Comparison and Analysis of Approaches
The Transcription Problem
Once playability can be determined, the transcription problem is a fairly straightforward heuristic-based optimization problem. However, because the search space for even fairly short pieces of music is very large, finding a practical solution suitable for commercial use may be a challenge.
- Introduction
- Transcription Fitness
- Genetic Algorithm Based Approaches
- Graph Search and Minimal Weight Path Finding Based Approaches
- Particle Swarm Optimization Approaches
- Other Methods and Approaches
- A Comparison and Analysis of Approaches
Human-Assisted Computation
- Introduction
- Types of Human Assistance
- User Interface
- Results
Conclusions
[edit] Why this is academically interesting
[edit] Intended audience
The transcription problem is important to musicians, music notation software developers, and computer scientists studying music.
Since transcribing music is a time-consuming process even for a human, it would be nice to have software that can generate transcriptions fast, reliably, and as good as a human can generate. There currently exists no software, professional (Sibelius, Finale), free, or otherwise, available commercially that always generates both playable and accurate guitar transcriptions of orchestral scores.
The transcription problem is of particular interest to computer scientists because this form of the transcription problem is part of a more advanced, if not impossible, version of the transcription problem called the Automatic Transcription Problem. In the Automatic Transcription Problem, the source music is not a score, but digital audio. Digital audio is converted to a written score which can then be transcribed using the transcription algorithm described in this work.
[edit] Why this is MS-level work
Computers and music. There is such a rich history between computer science and music that there exists several computer science related journals and conferences exclusively dedicated to problems in music. While much of the research, of course, focuses on sound synthesis and problems in creating and interpreting music, the problem of converting (transcribing) musical scores from one form to another, is an interesting problem that to this day still doesn't have a concrete and efficient solution primarily because there is no exact way of determining if one transcription is better than another. There is also a need for this type of software, as many aspiring musicians enjoy playing transcriptions, yet there is no reliable or efficient software out on the market to create transcription for them. If a musician wants a transcription, pretty much the only option today is to still transcribe it yourself!
[edit] Previous work
[edit] Literature review
- Transcription
- [2004] Arranging Music for Guitar with GAs and ANNs
A Masters thesis that covers the playability and transcription problem for guitar, using genetic algorithms and artificial neural networks. - [2006] GA-based Music Arranging for Guitar
Pretty much the same work as above, by the same authors, but as a published journal article and without the discussion on ANNs.
- [2004] Arranging Music for Guitar with GAs and ANNs
- Playability and Fingering
- [2004] Path Difference Learning for Guitar Fingering Problem
Discusses the playability problem for the guitar as a dynamic programming algorithm. - [2004] A Segmentation-Based Prototype to Compute Fingering
Discusses a graph-search prototype algorithm that examines music in segments rather than optimized as whole. - [2005] Automatic Fingering System
Another graph modeling algorithm, based on physical costs (stretching, reaching of the hand). - [2007] Automatic Decision of Piano Fingering Based on Hidden Markov Models
Discusses the fingering problem regarding to the piano. Uses a Hidden Markov Model to find an optimal sequence of smooth state fingering transitions. It is mentioned that this method can be applied to the guitar as well (future work).
- [2004] Path Difference Learning for Guitar Fingering Problem
[edit] Anticipated challenge(s)
[edit] Challenge(s)
The main challenge in this work is getting the transcription algorithm to run fast enough for commercial purposes, or at least as fast as a human can do it. Previous research describes algorithms that run in the 15 to 60 minute range for short musical phrases (they did not specify how short, however). Since I plan to extend the work in such a way that increases the search space, it is imperative to find a more efficient way to solve the transcription problem.
[edit] Anticipated approach to each challenge
I anticipate implementing many of the different playability and fingering approaches and trying different search algorithms and see what my experience with the guitar and computer science can bring to the problem.
[edit] What I bring to this work
[edit] My relevant background and experience
I have played the classical guitar for a very long time, albeit off-and-on. I am classically-trained, so things like reading music and knowing fundamental music theory is not a problem. I also have an interest in transcribing classical and modern music.
[edit] What I find interesting about this work
I find it amazing that as many transcriptions there are for guitar and piano, there was only one research article on the topic. There are a few authors currently working on the fingering/transcription problem for piano using Hidden Markov Models, but just the fingering part was done and transcription was remarked as just an application of the fingering problem.
