Progress report

Last week I was working on two tasks: implementing required code changes in the Trajectory component and second is writing some ideas for the technical report.

Hacking progress:

• Time-series normalization: Initially I was normalizing the time series by simply dividing all values by the maximal one, last week I've changed this method to more appropriate one by following the method suggested by Dina Q. Goldin and Paris C. Kanellakis in the "On similarity queries for time-series data: Constraint specification and implementation" chapter of "Principles and Practice of Constraint Programming — CP '95" book.


• DTW improvement: I'm trying to move from the original DTW implementation towards the more customizable implementation using step functions suggested by Sakoe-Chiba:
  .
  Unfortunately hack is no moving fast, - I am working on the architecture design to make step and constraints functions pluggable into the "generic DTW" code. I think this is the most elegant solution. In the future it'll allow to plug any user-configured function in the code. Really want to benchmark the performance of all the options since for the speech and writing recognition it worked well.

Book: Information Retrieval for Music and Motion.

Want to share one of my findings: while collecting papers for the literature review, I found a very interesting book related to the research I am doing: "Information Retrieval for Music and Motion", Müller, Meinard, 2007, XVI, 318 p. 136 illus., 39 in color., Hardcover. ISBN: 978-3-540-74047-6.
After reviewing I've ordered it, waiting for the stuff to arrive.

A general scenario that has attracted a lot of attention for multimedia information retrieval is based on the query-by-example paradigm: retrieve all documents from a database containing parts or aspects similar to a given data fragment. However, multimedia objects, even though they are similar from a structural or semantic viewpoint, often reveal significant spatial or temporal differences. This makes content-based multimedia retrieval a challenging research field with many unsolved problems.

Meinard Müller details concepts and algorithms for robust and efficient information retrieval by means of two different types of multimedia data: waveform-based music data and human motion data. In Part I, he discusses in depth several approaches in music information retrieval, in particular general strategies as well as efficient algorithms for music synchronization, audio matching, and audio structure analysis. He also shows how the analysis results can be used in an advanced audio player to facilitate additional retrieval and browsing functionality. In Part II, he introduces a general and unified framework for motion analysis, retrieval, and classification, highlighting the design of suitable features, the notion of similarity used to compare data streams, and data organization. The detailed chapters at the beginning of each part give consideration to the interdisciplinary character of this field, covering information science, digital signal processing, audio engineering, musicology, and computer graphics.

This first monograph specializing in music and motion retrieval appeals to a wide audience, from students at the graduate level and lecturers to scientists working in the above mentioned fields in academia or industry. Lecturers and students will benefit from the didactic style, and each unit is suitable for stand-alone use in specialized graduate courses. Researchers will be interested in the detailed description of original research results and their application in real-world browsing and retrieval scenarios.

Working on the Trajectory UI.

I've enhanced the Trajectory DTW UI over the last week following my initial hand drawing:



It seems to be working fine and next week I am planning to implement the actual DTW algorithm enhancements.

Technical review outline.

During the Summer and Fall of '08 I was doing research focusing on the "telemetry trajectory" idea which resulted in the three software components, which are "in the development stage" and will constitute the three major chapters of my future report:

1. 
   Software development activity simulation package. I've developed the sensorbase-sim extension package based on the JADE framework. It is fairly simple agent-based application which generates software metrics data once provided with simulation parameters for the code, such as overall functional points requirements, points per class, LOC's per point etc... and developers data, such as number of developers and their expertize level.
   
   While I've found a large amount of the approach-justifying literature and methods to continue the simulation package was shalved till better times and I focused on the Trajectory-UI development.
   


2. 
   Second application I was working on was a stand-alone Java application for the visualizing trajectories in the 3D space.
   
   This work was following Philip's original idea about trajectory visualization.
   This application is based on the Java3D package and it's main purpose is the exploration of the trajectory visualization approach. While working on the visualization implementation I was going through the trajectory-visualization related materials review and discovered the vast amount of research done in the area of the complex trajectories matching. Part of the reviewed articles will stuff the report.
   


3. 
   The most active development and research I am conducting right now now is on the Trajectory component of the Hackystat-ProjectBrowser application. Currently I am exploring the DTW algorithm application for the software telemetry data. Considering the amount of the work and research I've done this would be the major component of my report describing in the details the DTW application to the telemetry data.
   

UI design

Some of the time during last week I've dedicated to the DTW related research and UI design: I was thinking about laying out the workspace for the DTW analysis since after all it suppose to be somehow interactive and iterative. It's very important that UI must be responsive and keep user focused on the analysis aspects. By following the UI-First Software Development principle I've spend about 10-20 minutes just drawing the draft of UI laying out information blocks and parameters at the left screen "control panel".
.
The function which is underlying under UI design is pretty simple, and I outlined three major steps on my drawing:

1. User sees the input time-series statistics and two accompanying plots: one for the raw timeseries data with gaps and non-normalized peaks representing the data collected from the sensors and second one, with normalized series and gaps filled accordingly to the telemetry type.


2. Based on the provided information and visualization user selects specific DTW options and actually fires the timeseries alignment action.


3. Once trajectories aligned, the third plot showing aligned warped timeseries and alignment statistics updated. After evaluating analysis results user makes a decision to alter parameters and run alignment again or just accepts the alignment results.

Currently I'm altering the Wicket application code, HTMLs and CSS styles to implement the UI.

Some issues with DTW I'm working on.

In couple of previous posts (except one about precision) I was discussing two issues in pattern matching which are apparently similar in the speech recognition (utterance matching) and in the software metrics matching analysis. I read the article by
Rabiner, L.; Rosenberg, A.; Levinson, S., "Considerations in dynamic time warping algorithms for discrete word recognition," Acoustics, Speech and Signal Processing, IEEE Transactions on , vol.26, no.6, pp. 575-582, Dec 1978 and trying to rephrase the reasoning applying it to the software metrics alignment.

• Most recently discussed issue: the assumption that the telemetry time series should be the same length. In my opinion this constraint is very strong and we should not consider this in the most cases. Whether or not waterfall or agile processes are considered there are certain activity patterns (phases) already identified. What is not canonized is the length of each of the phases and we should be considering an "open-ended" alignment algorithm to match those process features.


• The second issue discussed before is the allowable changes in the warping function. By adjusting this allowances we basically adjusting the sensitivity of the algorithm to recognize peaks of activities as the independent events. Question is what is the range of optimal allowances?


• The last issue I was thinking of is whether or not there are some hidden preferences in the choice of the "query" or "template" time series. So far I would say that there are no difference, but I would work on the experimental proof that the warping function is symmetric (or not?).

While researching, I discovered this book, which potentially is the greatest answers source for my questions. Readings in Speech Recognition By Alex Waibel, Kai-Fu Lee

I've seen the following figure in the article and in the book and it seems to be illustrating two first questions I am asking here: first two plots are illustrating the effect of allowances in the warping function, while the third plot (UELM) illustrates the "open-ended alignment" approach.

Open-ended alignment.

So... precision errors... Once I've made through this I hit another bump: in my previous tests I was always comparing time-series of the exact same length, 15 days. Meanwhile the Trajectory interface allows you to select time series of arbitrary length and moreover to introduce indent before data, which more likely makes time-series lengths different. :). For example like this:



What would happen once I'll hit the Do DTW Analysis button? Right - Exception, due to the difference in length.



While I can restrict users to do only the same length time-series analysis, it is very strong constraints. It would require huge amount of the eye-matching before actually going into the DTW. ...

To be continued later today.

Precision errors....

If you were following my posts you might have noticed that there is significant difference in the appearance of the plots after DTW between the R implementation and my Java implementation. It was a point of my frustration for the couple of weeks. I spent hours trying to extract the underlying numbers and debug what is going on. Guess what? Precision errors contribute to that.