Projektförslag

Title: Optimal fingering for piano keyboards

Theme: Sound and Music Computing

Subject: Keyboard players use complex strategies for organizing their fingering. The task is specified in the musical score giving the sequence and (approximate) timing for the key presses. The decision of which finger should be used for playing a certain note is left to the player. In sight-reading (playing the piece for the first time) the first choice is to unconsciously apply well-established fingering solutions to common sequences of notes. This skill is acquired through endless hours of practicing. In rehearsed performances, conscious considerations of the fingering based on the musical intentions and interpretation of the piece may alter the ‘natural’ basic scheme.    

Possible essay project: Design and implement a basic optimal fingering algorithm for piano keyboards. The repertoire is limited to a single melody line (only one note at a time). The input is a sequence of notes in MIDI-format and the output is a string of numbers indicating the fingering.  The algorithm is evaluated on a small set of melody excerpts (from easy to difficult level) by a novice player and a (semi)professional pianist.       

References:

Parncutt R., Sloboda J., Clarke E., Raekallio M. and Desain P. “An ergonomic model of keyboard fingering for melodic fragments,” Music Perception,  Vol.14, pp. 341 - 382 (1997).

Hart M., Bosch R., and  Tsai E. “Finding optimal piano fingerings” The Undergraduate Mathematics and Its Applications Journal, UMAP, 2000, pp. 1-10.

Kasimi A., Nichols E., and Raphael C. “Automatic fingering system (AFS)”   Proc. 6th International Conference on Music Information Retrieval ISMIR (2005).

Supervisor: Anders Askenfelt


 

Title: Optimal fingering for guitar performance

Theme: Sound and Music Computing

Subject: Guitar players face similar problems as keyboards players (see above), when choosing a fingering scheme for depressing the strings with the left hand. The complexity of organizing the fingering is  higher than for keyboards as the same note can be played on different strings. The alternatives are, however, not at all equivalent from musical and physiological points of view. As a consequence the guitarist is faced with a number of alternatives of fingering a single note and a much larger number of ways of fingering a couple of notes. Even for a short musical excerpt there is an explosion in the number of possible fingering combinations. The best choice depends on a combination of motoric and musical constraints.       

Possible essay project: Design and implement a basic optimal fingering algorithm for the guitar with six strings. The primary guiding principle should be ‘ease of playing.’ The repertoire is limited to a single melody line (only one note at a time). The input is a sequence of notes in MIDI-format and the output is a string of numbers indicating the fingering (string and finger). The algorithm is evaluated on a small set of melody excerpts (from easy to difficult level) by a novice player and a (semi)professional guitarist.        

References:

Sayegh S. “Fingering for string instruments with the optimum path paradigm,” Computer Music Journal, Vol. 13, pp. 76-84, (1989).

Radicioni D. & Lombardo V. “Guitar fingering for music performance,”  Proc. of International Computer Music Conference,  Barcelona, Spain (2005).

Radisavljevic A. & Driessen P. “Path difference learning for guitar fingering problem,” Proc. of the International Computer Music Conference, Miami, USA (2004).

Supervisor: Anders Askenfelt


 

Title: A superior isomorphic keyboard

Theme: Sound and Music Computing

Subject: The piano keyboard has been used for 500 years and is the standard interface to many new  digital instruments. This lasting success indicates that the design has some advantages. There are disadvantages as well, it is long (150 cm) and requires frequent shifts of hand position, the fingering is completely changed if a melody is transposed into a different key, and pressing two adjacent keys by mistake causes strongly disharmonic sounds. Many alternative designs have been developed, in particular isomorphic keyboards which avoid the three disadvantages above. The success is limited to a few instruments of which only the button accordion has received widespread acceptance.  

Possible essay project: Develop a system for automatic conversion of established piano fingerings of typical note sequences in different keys (diatonic and chromatic scales, basic chords, melodic fragments) to an isomorphic keyboard. The system should take ergonomic costs into account (e.g.shift and rotation of hand position), as well as musical performance aspects (e.g. inter-note delays and tempo constraints). Evaluate the ‘ease of playing’ by implementing a small isomorphic keyboard on a QWERTY keyboard  and compare the playing skills in different keys of two novice subjects after a short time of practicing on a piano and isomorphic keyboard, respectively.

References

Overview on Wikipedia: isomorphic keyboard, Wicki layout, Janko keyboard, harmonic table.

Milne A., Sethares W., Plamondon J. “Isomorphic controllers and dynamic tuning: Invariant fingering over a tuning continuum,” Computer Music Journal, Vol. 31(4), 15-32 (2007).

Supervisor: Anders Askenfelt


 

Title: Automatic violin bowing pattern generator

Theme: Sound and Music Computing

Subject: The bowed string instruments like violin and cello are notoriously hard to play. Each note requires that a large set of control parameters are continuously coordinated and kept within certain limits.  For example, the motion of the bow relative to the strings has 6 degrees of freedom which all are used by the player to control the sound and timbre of the notes. The preferred motion pattern of the bow is basically defined by the musical score, which gives the pitches, durations and dynamic levels of the notes. It is, however, left to the player to organize the bow strokes (the direction of the bow motion and turning points) into a manageable execution pattern. This seemingly simple task turns out to be an intriguing optimization problem that requires years of playing experience to master to some extent. 

Possible essay project: Design and implement a basic bow stroke organizer which takes the finite length of the bow, the dynamic level, phrasing, articulation (staccato - legato) and accents into account. The choice of motion direction (downbow – upbow) and turning points should be based on physical constraints as well as established violin playing practice. The input is a sequence of notes in MIDI-format supplemented with musical performance symbols. The algorithm is evaluated on a small set of melody excerpts (from easy to difficult level) by a professional violinist.      

References

Maestre E., Blaauw W., Bonada J., Guaus E. and Peréz A. ”Statistical modeling of bowing control applied to violin sound synthesis,” IEEE Transactions on Audio, Speech, and Language Processing, Vol. 18(4), 855-871 (2010).

Maestre E. “Modeling instrumental gestures: An analysis/synthesis framework for violin playing,” PhD thesis, Universitat  Pompeu  Fabra, Barcelona (2009).

Askenfelt  A. “Measurement of the bowing parameters in violin playing. II: Bow–bridge distance, dynamic range, and limits of bow force,” J. Acoustical  Society of America, Vol. 86, 503-516 (1989).

Supervisor: Anders Askenfelt


 

Title: Perceptual identification of musical genre

Theme: Sound and Music Computing

Subject: Music Information Retrieval (MIR) is about using audio features and meta information in order to make predictions about different musical aspects. It can be related to both high-level descriptions such as predicting genre, music similarity (“if you like this one you may also like…”), musical moods, as well as more specific things like melodic recognition and retrieval or tempo estimation. Advanced signal processing methods are used for computing audio features. For mapping features to descriptions often machine learning methods or statistical inference methods are used.

Possible essay project: Investigate how humans decide the classification of genre based on different parts of the music. For example, is it mainly the percussions that determine the genre? The approach would be to put together a database of music examples divided in several tracks, make a web-based listening experiment and evaluate the results. The analysis will be based on statistical analysis, possibly including machine learning methods. The project will contribute to ongoing research about perceptual features in music information retrieval.

References

Scaringella N., Zoia G and Mlynek D. "Automatic genre classification of music content: a survey." IEEE Signal Processing Magazine  Vol. 23(2),  133-141 (2006).

Tzanetakis G., and Cook P. "Musical genre classification of audio signals." IEEE transactions on Speech and Audio Processing, Vol. 10(5), 293-302 (2002).

Friberg A., Schoonderwaldt E. and Hedblad A. "Perceptual ratings of musical parameters." In von Loesch, H., & Weinzierl, S. (Eds.), Gemessene Interpretation - Computergestützte Aufführungsanalyse im Kreuzverhör der Disziplinen (pp. 237-253). Mainz: Schott 2011, (Klang und Begriff 4).

Supervisor: Anders Askenfelt & Anders Friberg


 

Title: Sonification of heartbeat rate for sport and/or health applications

Theme: Sound and Music Computing/Biofeedback

Subject: In the last couple of years many apps for real-time monitoring physiological parameters such as heartbeat rate during running have been developed for both iPhone and Android mobiles. This enables runners to check theirs own heartbeat rate by looking at the mobile phone display. Patients can send their heart information to a medical doctor. Sonification ("visualization" by sound) of physiological parameters is a much more attractive way to explore in order to e.g. synchronize and monitor athletesâ¤â movements for optimal performance or for medical diagnosis, monitoring and evaluation of treatment. By sonification complex structures in physiological data can be detected and evaluated in real time.

Possible essay projects: Study and survey the performance of the most popular running log programs analyzing heartbeat rate, and/or of the most popular heartbeat monitoring programs for health applications. Based on an overview of literature for heartbeat rate sonification for professional purposes, suggest a better design for sonification of heartbeat rate, which can guide elite runners to continuously optimize their running actions during performance, and/or providing patients and medical doctors with helpful non-visual information. The new design is implemented in a mobile and evaluated under field conditions.

References:

Ballora, M., Pennycook, B., Ivanov, P.Ch., Goldberger, A., & Glass, L. (2000) Detection of obstructive sleep apnea through auditory display of heart rate variability, Computers in Cardiology, 739-740

Ballora, M., Pennycook, B., Ivanov, P.Ch., Glass, L., & Goldberger, A.L. (2004) Heart Rate Sonification: A New Approach to Medical Diagnosis, Leonardo, February 2004, Vol. 37, No. 1, 41-46

Benson, R., Connolly, D., & Benson, R. (2011) Heart Rate Training, Human Kinetics Publishers

Burke, E. (1998) Precision Heart Rate Training, Human Kinetics Publishers

Hermann, T., Hunt, A., Neuhoff, J.G. (2011) The sonification handbook.

Supervisor: Roberto Bresin


Title: App for the sonification of walking and running

Theme: Sound and Music Computing/Biofeedback

Subject: In the last couple of years many apps for real-time monitoring and logging of casual sport activities such as running have been developed for both iPhone and Android mobiles. This enables casual athletes to check theirs own performance by looking at the mobile phone display and by listening to voice messages. These apps, so fare, are not designed for monitoring the body posture of runners and walkers, which is an important parameter for optimizing energy consumption while training, or in rehabilitation. Sonification ("visualization" by sound) of body posture parameters is a promising way to explore in order to e.g. synchronize and monitor athletesâ¤â movements for optimal performance or for medical diagnosis, monitoring and evaluation of treatment. By sonification posture errors can be detected and adjusted in real time.

Possible essay projects: Study and survey the performance of the most popular programs and technologies for analyzing of body posture in walking and running. Based on an overview of literature, suggest a better design for sonification of walking and running posture, which can guide runners and walkers to continuously adjust their posture while running and walking, and/or providing patients and medical doctors with helpful information in rehabilitation. The new design is implemented in a mobile and evaluated under field conditions.

References:

Alexander, R.M. (1996) Walking and Running. The Mathematical Gazette, Vol. 80, No. 488 (Jul., 1996), 262-266 

Bolíbar, J. (2012). Kinect Audio-Runner: Audio Feedback for Improving Performance in Long-Distance Running. Master thesis, KTH. 

Branko Skof & Stanko Stuhec. Kinematic analysis of Jolanda Ceplak's running technique

Eriksson, M., & Bresin, R. (2010). Improving running mechanics by use of interactive sonification. In Bresin, R., Hermann, T., & Hunt, A. (Eds.), Proceedings of the Interaction Sonification workshop (ISon) 2010 (pp. 95-98). Stockholm, Sweden: KTH Royal Institute of Technology. 

Hermann, T., Hunt, A., Neuhoff, J.G. (2011) The sonification handbook.

Jessica Gonowon. 2007. The Physics of Efficient Running

Tom F. Novacheck. 1997. The biomechanics of running. Gait and Posture 7 (1998) 77-95.

Steve Magness. 2010. How to run: running with proper biomechanics

Supervisor: Roberto Bresin


Title: Sound feedback as alternative to visual feedback in interaction with mobile devices

Theme: Sound and Music Computing/Affective Computing/Human-machine interaction

Subject: Smartphones or tablets offer a large range of possibilities for incorporating sound in the interaction with the user. Interaction can e.g. be multi-modal with gesture-based interface but how these features can support meaningful and novel ways of interaction with the user is to a large extent an unexplored field.

Possible essay projects: Design and implement a system for efficient and expressive sound interaction on a smartphone or tablet. The focus can be in one of three areas: human-machine interaction (e.g. usability), medical/clinical use, or art. For example, by sonifying finger gestures/swipes on a touch screen it could be possible to provide information about the nature and quality of gestures. Implement the basic features of the proposed system on a smartphone, and compare the suggested mode of interaction with graphic-based alternatives. Evaluate the expressive capabilities of the system and efficiency in interaction.

References:

New Interfaces for Musical Expression 

Hermann, T., Hunt, A., Neuhoff, J.G. (2011) The sonification handbook.

Supervisor: Roberto Bresin


Title: Reaching a target: Can sound improve the performance defined by the Fitts's law?

Theme: Sound and Music Computing/Human-machine interaction/Game design

Subject: According to Fitts's law, the time required by a human movement for reaching a target depends both on the distance to the target, and its size. In situations in which visualization is problematic, sound can be used for supporting user's interaction with a device. 

Possible essay project: First, implement use cases that make use of gesture devices such as mouse, kinect, leap motion, for verifying Fitts's law. Second, add the use of sound, for example for guiding the user towards the target, and/or for signalling that the target has been reached. Third, verify if the use of sound helps in improving the performance predicted by Fitts's Law, i.e. it decreases the time needed for hitting the target.

References:

Fitt's Law: http://en.wikipedia.org/wiki/Fitts's_law

Hermann, T., Hunt, A., Neuhoff, J.G. (2011) The sonification handbook.

Davide Rocchesso and Stefano Delle Monache. 2012. Perception and replication of planar sonic gestures. ACM Trans. Appl. Percept. 9, 4, Article 18 (October 2012), 21 pages. 

Supervisor: Roberto Bresin


Title: Swype for desktops

Theme: Speech Technology

Subject: Swype is a text input method for touch screen-based mobile telephones. It makes it easy to input words by drawing gestures on a virtual keyboard instead of pointing at each key singularly. The system can be based on machine learning methods that learn how to classify gestures into words. Other approaches are possible as well.  

Possible essay project: Develop and test a swype system for a computer by using mouse or touch screen input. Important steps include implementation of a virtual keyboard that accepts input from a pointing device, recording of swyped word examples, and implementation of some algorithm(s) for recognition of the gestures as words. The system is evaluated on a limited number of words.

References

http://www.swype.com

Rabiner L.”A tutorial on hidden markov models and selected applications in speech recognition,” Proc. of the IEEE,  257-286 (1989).

Overviews on Wikipedia: Hidden Markov Model, Baum-Welch algorithm, Vitterbi algoritm

Supervisor: Anders Askenfelt & Giampiero Salvi


 

Title: Sing me your status

Theme: Speech and Music Technology

Subject: A system capable of singing short text messages (SMS, twitter-tweets, chat messages, status updates) could be a useful way of enhancing the content and bring it into prominence.

Possible essay project: Composing a melody to a given text requires artistic skill and inspiration, but a rule-based matching strategy can probably produce decent results.  One approach could be to use text-to-speech software to transcribe the text into a sequence of phonemes, and then analyze the phrasing and the placement of focused syllables. This data set could be matched against a set of known melodies, according to rhythmic criteria based on intelligibility and artistic considerations. The result can be listened to through a singing speech synthesizer. The evaluation will show why and how a human composer would have performed much better.

References

Engstrand O. Fonetikens grunder, Studentlitteratur, Lund 2004.

Juslin PN, Laukka P Communication of emotions in vocal expression and music performance: different channels, same code?, Psychol Bull. 2003 Sep;129(5):770-814.

Rodma R. Computer Speech Technology, Astech House, Boston 1999.

Supervisor: Anders Askenfelt & Jonas Beskow


Title: Readability algorithms

Theme: Language Technology

Subject: A readability test uses an algorithm to compute the readability of a text, ranging from very simple (children’ literature) to very hard (academic/bureaucratic texts). In Sweden there is an index called LIX (which can be tested online). LIX was invented by the pedagogue Carl-Hugo Björnsson in 1968 and has a very simple algorithm, which has been criticized for not predicting readability so well. It should be possible to improve the algorithm with more advanced methods.

Possible essay projects: Study the research done on readability (in Sweden and elsewhere) and the criticism against LIX. Propose your own algorithm for measuring readability. Evaluate your algorithm by letting subjects rank the readability of a set of texts and see if your algorithm can predict this ranking better than LIX.

Supervisor: Gabriel Skantze


 

Title: Chatbot trained on movie scripts

Theme: Language Technology

Subject: A chatbot is a computer program that can engage in a (written) chat with a user. One of the earliest examples is ELIZA, a simulated Rogerian psychotherapist implemented by Joseph Weizenbaum in 1964. Today, the technology is used in commercial applications for customer support on websites, developed by companies such as Artificial Solutions. Every year, the Loebner Price is awarded to the most human-like chatbot. Simple chatbots (such as ELIZA) only use predefined scripts that recognize some keywords in the user input and then say something using this keyword. It should be possible to instead train the chatbot on a large database of interactions. On source of interactions are movie scripts, which are available in large quantities on the Internet (subtitle repositories or movie script databases).

Possible essay projects: Extract movie scripts from the internet. Propose an algorithm for matching the user input to the utterances in the database to find a relevant response. How can you make the dialogue coherent with this strategy? How can you evaluate the system?

Supervisor: Gabriel Skantze


 

Title: Recognizing faces and expressions using Kinect

Theme: Speech technology

Subject: Microsoft Kinect uses a depth camera to track humans and build a skeleton model, but it can also track the faces and extract facial features. These facial features could be used for a number of different applications.

 Possible essay projects:

Choose one of the following applications (or propose another one):

  • Face identity recognition: Use the facial features to recognize who the person is.
  • Emotion recognition: Recognize different emotions or facial expressions, regardless of who the person is.
  • Speaker detection: In dialogue systems interacting with many users at the same time, or where there is background noise (such as for human-robot interaction), it can be hard to detect who is speaking. If lip movements are tracked (possibly along with audio from the Kinect array microphone), it should be possible to detect who is speaking.

For all these projects you have to collect some data using Kinect to train a model (using machine learning) and then evaluate your model.

Supervisor: Gabriel Skantze


 

Title: Poetry Writing Assistant

Theme: Language Technology

Subject: Traditional poetry (and song lyrics) has to conform to a number of constraints when it comes to rhyme, stress and syllables. For some conventional forms, such as a Limerick or a Sonnet, these constraints are very specific. Using a pronunciation lexicon it should be possible to check a given poem whether it confirms to these constraints and which parts are incorrect (much like the spelling correction in word). Using a language model (trained on general newspaper texts or a large set of poems extracted from the web), it should also be possible to suggest words or even complete phrases to the writer that conforms to the constraints given by the chosen poem form and the parts written so far.   

Possible essay projects: Implement a Poetry Writing Assistant and explore different ways of assisting the writer along the lines outlined above. If it is not possible to meet all constraints in some part of the poem, is it possible to loosen up some of them? How should this be done? How can you evaluate your program?

Supervisor: Gabriel Skantze


 

Title: Brain signal pattern recognition

Theme:  Algorithms, Pattern recognition, Machine learning

Subject:   Pattern recognition and machine learning have significantly advanced the field of biological data analysis leading in consequence to the development of effective diagnostic tools and supporting research efforts. The contribution of novel pattern recognition methods has been particularly appreciated in brain data mining as this new approach allows for exploratory search for spatio-temporal patterns in large quantities of high-dimensional nonstationary recordings of brain activity.The emerging trend is to combine machine learning techniques with brain-inspired computing algorithms to address increasingly demanding objectives of brain signal analysis in novel applications.

Below you can find a set of alternative projects (they can be treated individually or in combination).

Possible essay projects:

1)      Survey and examine some of the state-of-the-art methods that involve a machine learning and/or brain-inspired connectionist approach to a well-defined class of brain pattern signal recognition problems (see 2)

2)      Select or propose a method with novel aspects, alternatively select and compare a few existing approaches (prototypes) to a specific brain signal pattern recognition problem, e.g. electroencephalograpic (EEG) signal classification for a brain-computer interface, search for epileptic seizure precursors in high-dimensional brain signal recordings, multivariate analysis and identification of distributed spatial patterns of brain activity for diagnostic purposes.

3)      Discuss key challenges, emerging trends and propose future applications for brain signal recognition methodology.

Supervisor: Pawel Herman


 

Title: Computer-aided medical diagnostics

Theme:  Artificial intelligence, Classification, Machine learning, Algorithms

Subject:   Computer-aided diagnosis has been extensively validated in various medical domains, ranging from biomedical image or signal analysis to expert systems facilitating the process of decision making in clinical settings. Although the usefulness of computational approaches to medical diagnostics is beyond any doubt, there is still a lot of room for improvement to enhance the sensitivity and specificity of algorithms. The diagnostic problems are particularly challenging given the complexity as well as diversity of disease symptoms and pathological manifestations. In the computational domain, a diagnostic problem can often be formulated as a classification or inference task in the presence of multiple sources of uncertain or noisy information. This pattern recognition framework lies at the heart of medical diagnostics projects proposed here.

Below you can find a set of alternative projects (they can be treated individually or in combination).

Possible essay projects:

1)      Define a diagnostic problem within the medical domain and examine the suitability of machine learning, connectionist (artificial network-based), statistical or soft computing methods to your problem.

2)      Survey the state-of-the-art in computational tools supporting classification of disease symptoms and comparatively examine the diagnostic performance of some of them on a wide range of available benchmark data sets. Define a measure for diagnostic performance.

3)      Discuss most recent trends in the field and challenges for computer-assisted diagnostics in medicine.

Supervisor: Pawel Herman


 

Title: Automated scheduling, e.g. university timetabling

Theme:  Artificial intelligence, Machine learning, Algorithms, Optimisation

Subject:   Planning is one of the key aspects of our private and professional life. Whereas planning our own daily activities is manageable, scheduling in large multi-agent systems with considerable amounts of resources to be allocated in time and space subject to multitude of constraints is a truly daunting task. In consequence, scheduling or timetabling as prime representatives of hard combinatorial problems have increasingly become addressed algorithmically with the use of computational power of today's computers. This computer-assisted practice in setting up timetables for courses, students and lecturers has also gained a lot of interest at universities around the world and still constitutes an active research topic.

In this project, students can address a scheduling problem of their own choice or they can use available university timetabling benchmark data and tailor it to the project's needs. An important aspect of such project would be to select or compare different algorithms for combinatorial optimisation, and define a multi-criterion optimisation objective. It could be an opportunity to test computational intelligence and machine learning methodology.

Supervisor: Pawel Herman


 

Title: Stock forecasting, financial data mining

Theme:  Machine learning, Algorithms

Subject:  Stock trading is one of the most common economic activities in the world. Stock prices are very dynamic and commonly undergo quick changes due to the intrinsic nature of the financial domain. From a computational perspective, intelligent trading can be formulated as a data (or more specifically, time-series) prediction problem that involves both known parameters and unknown factors. The overarching idea is to design an algorithm that provides accurate prediction thus allowing for making optimal trading decisions. In this domain, machine learning and oft computing methods have recently proven great potential.

Below you can find a set of alternative projects (they can be treated individually or in combination).

Possible essay projects:

1)      Compare some of the most recent approaches to financial time series prediction and validate their performance on available benchmark data sets (e.g., http://www.stockhistoricaldata.com/download).

2)      Propose a method with your own novel component and verify its suitability for the problem of financial time series analysis on different benchmark data sets.

3)      Discuss urgent challenges and emerging trends in computer-based stock forecasting. Reflect on the statistical nature of the data that reflects complex characteristics of financial markets.

Supervisor: Pawel Herman


 

Title: Inference about simulated neural systems from spiking data

Theme: Algorithms, Simulations

Subject: The proliferation of neural modelling studies along with rapidly expanding dimensions of microscopic  and mesoscopic recordings of neuronal activities in the brain have not been matched yet with effective algorithms for their processing. It is particularly insightful to study so-called spiking dynamics exhibited by individual cells as it provides direct evidence about functional and structural aspects of the information about the underlying neural circuits. The problem amounts to parallel processing of high-dimensional nonstationary point processes and designing a model for inference about various characteristics of the neural source (system) of interest. The methods investigated in the project will be evaluated on the existing data sets generated in neural simulations.

Below you can find a set of alternative projects (they can be treated individually or in combination).

Possible essay projects:

1)      Addressing one of urgent and computationally demanding problems in spiking data analysis, e.g. massively parallel search for spatio-temporal patterns, identification of complex synchronous effects and their validation, clustering and quantifying the distance between time series  of spikes etc.

2)      Providing a tool for fundamental analysis of spike data and visualisation of the results.

3)      Probabilistic (or other alternatives inclusing heuristic approaches) modelling of an inference mechanism for deducing various characteristics (to be closely defined) of the underlying spike generating system (a spiking neural model of cortical circuits). Here for example a structure of neural connectivity (network structure) can be inferred from spiking data or a mode of operation can be deduced. The problem and its difficulty level will be adjusted to the project and student's requirements on an individual basis..

Supervisor: Pawel Herman


 

Title: Visualisation of neural data

Theme: Visualisation, Simulations

Subject: Visualisation is one of the most neglected aspect of a rapidly developing field of computational biology. Only recently can we observe an emerging trend for combining neural simulation frameworks with visualisation software. Still there are a plethora of challenging problems that need to be urgently addressed (high-dimensional data, pre-processing, integration with a simulation software, demands  for purely visual aspects, interactive environment) to render visualisation a practical tool in computational studies. This is envisaged to facilitate computational modelling and assist in demonstrating scientific findings.

Possible essay projects:

1)      Visualisation of existing data produced by models (different types of high-dimensional spatiotemporal data are available).

2)      Conceptual integration with simulating environment to help with data pre-processing (or post-procesing) and facilitate iteractive mode with the user.

3)      Review of the state-of-the-art methodology and a motivated choice of a tool for the computational problem at hand.

Supervisor: Pawel Herman


 

Title: Optimisation and parameter search in computational modelling

Theme: Algorithms

Subject: Model's parameters have a decisive effect on its behaviour and dynamics. Search for parameters is at the same time the most tedious component of computational modelling. Neural simulations are no exception. On the contrary since they account for nonlinear and stochastic effects in brain data, parameters need to be carefully tuned to obtain a desirable functional and/or dynamical outcome. This optimisation procedure is commonly carried out manually on a trial-and-error basis. It is thus desirable to automatise this tedious process by providing an effective parameter search and optimisation scheme. One of key challenges to address is computational efficiency of the implemented method and the definition of a cost function based on the existing "manual" evaluation criteria. Tests in the project will be perfomed with the use of existing neural models or a low-scale simulation demo will be developed.

Possible essay projects:

1)      Define the cost function that reflects the fundamental model evaluation criteria and propose an effective way of its calculation.

2)      Propose a computationally efffective way of evaluating the cost function (p. 1)

3)      Review and propose a parameter search method (from the existing approaches) that match the specificity of computational modelling.

Supervisor: Pawel Herman


Title: QA Systems (how well do they really work?)

Subject: QA systems treat free text kind of like a database and use simple English queries as the query  language. So if the text is 'the Twelve Caesars' by Suetonius, and the query is, ‘Who killed Julius Caesar?’, then the answer should be 'Brutus' or, better, the sentence or paragraph in which the killing was done. Write a thesis which explores the state of the art in Question Answering systems. You should focus on either closed domain or open domain systems. And you should do some experiments where you compare and contrast various approaches and systems using a test corpus that you develop yourself or find on the internet. Critically discuss your findings. Are these types of systems reliable enough for common use cases? If not what are the missing ingredients?

Supervisor: Michael Minock


TitleGo Go!

Subject: Why is the ancient game of Go so hard for computers? Write a player that wins on n x n boards. How large can you get n to be where the system still beats you, the programmer? Discuss some of what others have tried to make competitive Go players. Do you think Go programs will beat all human players on the 19x19 Go board by 2050?  Give arguments.

Supervisor: Michael Minock


TitleIsovists Indexes.

Subject: In navigation systems it is important to be able to quickly calculate which buildings/objects are viewable from a given x,y position. Let's investigate the 2D case. Simple polygons in the neighborhood of other simple polygons have a viewability area which defines the area from which the polygon may be seen. This area may be delimited via a (set of) polygon(s), not necessarily simple. Write a routine to compute these viewability polygons (aka Isovists) and implement it in a PostGIS index scheme to calculate the polygons viewable from any x,y point. Compare the performance of your result with naive line-of-sight run-time methods.

Supervisor: Michael Minock


TitlePostgreSQL Replication.

Subject: There is a need these days for database systems that are horizontally scalable (being able to add additional servers to a running system and improve performance). PostgreSQL has the ability to replicate databases across servers. Is it possible to implement ACID transactions across multiple postgreSQL instances. In principle, the answer seems to be yes, but it is certainly not easy -- consider distributed two-phase commit. Thus the transaction model must be something more like BASE. Specifically categorize and implement simple examples of the types of transactions that can be supported over PostgreSQL with replication 'out of the box'.

Supervisor: Michael Minock


TitleFly Catcher

Subject: If flies would stay put, it would be easy to catch them. If we wanted to determine which flies we would catch in a n-dimensional rectangle, we could just index fly positions using an R-Tree. But flies move about randomly. This is an instance of a 'moving objects database problem' and it has recently attracted a fair bit of attention. Review the literature on moving objects databases and implement and compare several approaches in terms of how many flies can be tracked and caught in a real time simulation. Compare no-index approaches, base-line R-Tree implementations, and then one or more of the moving object indexes from the literature.

Supervisor: Michael Minock


TitleSkärgården

Subject: There is a constant stream of spatial-temporal data, mostly numerical, that provides sea and weather prognoses for that magical, awe inspiring place that we call 'Skärgården' (or the Stockholm Archipelago). Investigate methods to turn this flood data into natural language reports (e.g. "It will be calm with scattered clouds Saturday morning and afternoon in Trälhavet, but at night the wind will pick up to 7 knots, blowing to the South.") Investigate and potentially reuse the methods developed by the natural language generation group in Aberdeen, Scotland who generated weather reports for North Sea drilling operations.

Supervisor: Michael Minock


TitleReplication of Precise. 

Subject: The paper 'Towards a theory of natural language interfaces to databases' by Popescu, Etzioni and Kautz, Proc of IUI, 2003, developed a novel method to support natural language interfaces to databases. Over the graph of tokens representing the database, max-flow is computed over the tokens represented in the user's natural language query. From the resulting sub-graph an SQL expression is trivially generated. Crucially, the approach claims that it can identify 'semantically tractable' queries that can be answered with 100% confidence. The paper presented results over the GEO corpus. In this work, attempt to replicate their results and then critically evaluate their claims.

Supervisor: Michael Minock


 

TitleReplication of Lambda-WASP.

Subject: Baby hears word sequences coupled with baby's pre-linguistic understandings of objects and events in the world. From this baby learns knowledge that lets baby map from word sequences to meaning expressions (natural language understanding) and map from meaning expressions to word sequences (natural language generation). Raymond Mooney's group looked at this problem for natural language understanding in their 2007 paper 'Learning Synchronous Grammars for Semantic Parsing with Lambda Calculus'. Attempt to replicate the results of this work and evaluate their claims. Time permitting, review additional work that has looked at this problem more recently. Critically discuss.

Supervisor: Michael Minock


Title"Give me something like ..."

Subject: In large databases it is sometime reasonable to ask a query such as, “give me the n objects most similar to a given object.”  There is a well developed literature on the similarity problem. Review the literature on the computation of similarity in databases. Apply this to a large data set (e.g. MusicBrains, OpenStreetMaps, etc.) and evaluate alternative approaches. It is quite likely that you will specialize your literature search and implementation to the single database/domain that you decide to focus on.  Note this will involve you securing and focusing on a large open databases in your domain of interest.

Supervisor: Michael Minock


Title: Learning for Robocup Soccer

Theme: Artificial intelligence / Simulation

Subject: Robocup soccer simulation league is a yearly competition that drives development of multi agent artificial intelligence. The task is to implement behaviours for 11 individual agents playing simulated soccer, and then have these agents playing each other.

Possible essay projects: Study earlier work on team behaviour and strategy, design and implement your own team, and test it in the simulator. Implement machine learning for your team and/or individual players to improve their playing over time. What learning methods are applicable and efficient for this task? How should one evaluate the performance of a learning method in this scenario?

References:

 http://sourceforge.net/projects/sserver/ (link)

 http://www.youtube.com/watch?v=cDhSjSYPvdE (link)

 http://wiki.robocup.org/wiki/Soccer_Simulation_League (link)

Supervisor: Christian Smith


 

Title: Motion recognition and prediction

Theme: Pattern recognition, machine learning, human/machine interfaces

Subject: Several type of human interface devices for computers take human hand motion as input (ex: Computer mouse, touchpad, touchscreen, accelerometers, etc.). A major difference between these and keyboards, is that input is continuous, and consists of a series of position readings along a trajectory. It could therefore be possible to determine the intended input before the entire sequence is entered. If the system can accurately guess what input a user intends to give beforehand, this can be used for preloading or preprocessing data needed for the most probable action, thus making the computer more responsive. Alternatively, predictions can be used to remove lag in online applications.

Possible essay projects:  How accurately can one predict user inputs, and how far ahead of time? How does this vary with different types of devices? What are good methods to use for the estimations and predictions?

References:

 www.csc.kth.se/~ccs/Publications/iros09b.pdf

 www.csc.kth.se/~ccs/Publications/mech10.pdf

 www.lospi.net/home/predictinghumanmovementwithmicrosoftkinect

Supervisor: Christian Smith


 

Title: Kinnect-based Robot Control

Theme: Robotics, human/machine interfaces

Subject: The kinnect full-body motion tracker has been used to for different kinds of robot control - the most intuitive is of course to let a humanoid mimick the motions of a human. As the robot we want to control becomes less and less human, the mapping between the controlling human and the robot becomes less obvious. How can we solve the problem of intuitive control with the Kinnect?

Possible essay projects: Design and evaluate different ways to control different robots using the Kinnect interface. Compare how different schemes and control spaces fit different (simulated) robots and tasks.

References: http://wiki.ros.org/openni/Contests/ROS%203D/Skeleton%20Tracker%20Teleoperation%20Package%20for%20Mobile%20Robot

Supervisor: Christian Smith


 

Title: Virtual Inputs

Theme: Human tracking, human/machine interfaces

Subject: Given the advanced hand tracking capabilities of a Kinnect with the right software running, it should be possible to implement a number of different virtual input devices.

Possible essay projects:  Design, implement, and evaluate the usability of different kinds of virtual input devices, such as a keyboard, a mouse, a piano or other musical instrument (Thermin?). What feedback is necessary for practical use? How accurate does hand tracking need to be for different kinds of interface devices?

References:

http://www.openni.org/files/3d-hand-tracking-library/

Supervisor: Christian Smith


Title: Optimal Yatzee

Theme: Algorithms

Subject: Construct a program that plays Yatzee well, preferably optimally. The program should, given the current result and the current values of the dice, determine which dice to save or, if all three throws have been used in this round, determine where to put the score. There are several variations of this problem. The simplest one is to always maximize the expected points you will get, and a probably more difficult one is to, given both your own and an opponents current score, maximize the likelyhood of winning, provided the opponent also aims to win. There are also variations depending on the exact rules used.    

Supervisor: Vahid Mosavat


 

Title: Sudoko solvers

Theme: Algorithms

Subject: In principle Sudoku can be solved using a brute-force algorithm but it is more interesting to find an efficient sudoku solver. The task is to study and implement som sudoku solving algorithms, and hopefully to design your own solution or variation. The algorithms should be tested and bench marked against sudoku instances of varying difficulty.      

Supervisor: Vahid Mosavat


Title: Silverfish simulation

Theme: Simulations/Genetics

Subject: You have all seen them when you switch on the bathroom light: little bugs, either scurrying to safety or playing dead. Their behaviour has of course been optimized by millions of years of evolution. Is it possible to simulate this? Will the simulated silverfish act more and more intelligently for each generation?  

Project highlights:

•       Decide how the bathroom floor, the light, your foot and the bug are represented.

•       Decide on the rules for the life and death of a bug.

•       Program it and simulate your foot and the light interactively.

•       Decide on rules for mutation and run many generations.

•       Report results!

References

http://www.simulatedevolution.com/

Supervisor: Vahid Mosavat


Title: Analysis of neuronal morphology

Theme: Biological Modelling

Subject: Many modern biological simulation techniques rely on precise specification of the shape of individual cells, e.g. neurons. Acquisition of morphological data is a tedious semi-automated process prone to human operator errors. In this situation data validation is indispensable measure in modelling and simulations.

Possible essay projects: Make a survey of existing morphological databases and digital reconstruction tools paying attention to freely available data and open source software. Write a program for automatic validation of neuronal morphological data files with respect to logical errors and violation of common features and characteristics.

References: NeuroMorpho.org; CNIC; INCF; NEURON

Supervisor: Alexander Kozlov


 

Title: Making the complex simple

Theme: Biological Modelling/Algorithms

Subject: Complexity of biological models ranges from detailed and realistic to abstract and simplified. Transitions between the levels of abstraction are not always analytically possible or even clearly defined.

To support the choice of parameters of an abstract model, an automatic procedure can be applied. Consider two representations of rhythm generation in live organisms, a large-scale bilogically detailed neural network and a simple oscillator. Parameters of the latter can be tuned to fit the output of the large network via optimization and parameter search.

Possible essay projects: Review parameter search algorithms and apply one or compare several methods with respect to the problem. Network simulation data are available.

References/keywords: optimization, parameter search, large-scale neural network, neural oscillation.

Supervisor: Alexander Kozlov


Title: Faktorisera heltal med SAT-lösare

 Att faktorisera stora heltal är ett okänt beräkningsproblem som antas vara svårt att lösa effektivt, ett antagande som mycket av modern kryptografi är baserat på.  En möjlig ansats för att lösa faktorisering är att reducera till det (kanske ännu svårare) SAT-problemet och använda en modern SAT-lösare.  En poäng med detta är att mycket energi har lagts ned på att konstruera optimerade SAT-lösare de senaste åren. Projektet går ut på att undersöka hur väl denna ansats står sig mot specialiserade faktoriseringsalgoritmer, både att undersöka vad tidigare forskning kommit fram till samt att genomföra egna experiment.

Supervisor: Per Austrin

Feedback News