Manifold Learning, part 3

Part 1 here
Part 2 here

Non-linear dimensionality reduction

In an earlier post, we saw we can approximate higher dimensional data using dimensionality reduction techniques. However, PCA (and similar methods) have a weakness. It requires the constraints to line along or near straight lines. What about data that lie along curves?

Another Illustrated Example

Let us pretend again we have 2-dimensional data and our tools can only analyse one-dimensional data. We cannot use the trick we used earlier because the data no longer lies close to a straight line. However, we can cheat. Looking at it closely, we can see that our data (almost) lies along a spiral.

Just like before, we are going to use the projections of our data (red circles) onto the spiral as approximations of our data. We can do this as long as our data is "very close" to the spiral.

The final trick is to "unroll" the spiral and pretend it is a straight line. We can now use our tools for analysis. Just like in our previous approximation errors are introduced. As long as the data is "very close" to the spiral, the error introduced is small.

You may also notice that I skipped over how we actually unroll the spiral. We'll discuss one way to do it in the next post.

Clarification and Correction

I recently got interviewed by loQal about my research. You can read the article here. I guess I didn't explain some things clearly enough and I'd hate to give a false impression regarding the research. Here are some items I'd like to clarify or correct.

• The Filipino Sign Language (FSL) Archive project is a collaboration between:
  1. Philippine Deaf Resource Center (PDRC) - an NGO
  2. Philippine Federation of the Deaf (PFD) - an NGO
  3. Digital Signal Processing (DSP) Lab of the Electrical and Electronics Engineering Institute
  4. Computer Vision and Machine Intelligence Group (CVMIG) of the Department of Computer Science

  DSP and CVMIG are both of the College of Engineering, UP Diliman.

• The FSL Archive Project is a separate project from the Filipino Speech Corpus (PSC) project. For one thing, Sign is not Speech.
• As far as I know, the linguistics research is being done by PDRC and PFD, not UP.
• I don't have an application or system yet that can convert FSL into text. That is a long way off. What I have are experimental programs. Nothing practical. Also; syntax and semantics of FSL is currently poorly understood. Until we get a better handle on that, FSL to text sentences is not possible.
• FSL vs ASL (vs SEE vs MCE). It cannot be denied that American Sign Language (ASL), Manually Coded English (MCE) and Signing Exact English (SEE) has a huge influence on FSL; however, many Filipino Deaf refer to their language as Filipino Sign Language. This is a social, cultural and political issue in addition to a technical issue. For example, the Deaf I met in Cebu called their sign language Cebu Sign Language. And yes, there is a lot of variation between regions, and provinces.
• FSL vs English (vs Tagalog). This one confuses a lot of people. Sign is not Speech. FSL is not English. FSL is not Tagalog. FSL is a separate, distinct language. It helps if you think of Written English as a separate language from Spoken English. There is no equivalent "Written FSL". To facilitate research, signs are assigned a label called a GLOSS. It is a word or phrase borrowed from another language. Since many Deaf in the Philippines have Written English as a second language, the GLOSS is borrowed from Written English. It is often written in ALL CAPS to distinguish it from Written English (example: THINK-SKIP-MIND). Note that while the GLOSS is chosen to be as close to the meaning of the sign as possible, this is not a translation. This is one reason why you sometimes see Tagalog used as a GLOSS (example: LOLA).

I think that covers most of it. If you have more questions, leave a comment. Thanks for reading!

Bibliography

This is a partial dump of the references I have used so far.

• Rafaelito M. Abat and Liza B. Martinez. The history of sign language in the philippines: Piecing together the puzzle. In 9th Philippine Linguistics Congress, Diliman, Quezon City, Philippines, 2006.
• Julius Andrada and Raphael Domingo. Key findings for language planning from the national sign language committee (status report on the use of sign language in the philippines). In 9th Philippine Linguistics Congress, Diliman, Quezon City, Philippines, 2006.
• Yvette S. Apurado and Rommel L. Agravante. The phonology and regional variation of filipino sign language: Considerations for language policy. In 9th Philippine Linguistics Congress, Diliman, Quezon City, Philippines, 2006.
• Robin Battison. Lexical Borrowing in American Sign Language. Linstok Press, Silver Spring, MD, 1978.
• Marie Therese A.P. Bustos and Rowella B. Tanjusay. Filipino sign language in deaf education: Deaf and hearing perspectives. In 9th Philippine Linguistics Congress, Diliman, Quezon City, Philippines, 2006.
• Phil. Deaf Resource Center and Phil. Federation of the Deaf. Part 1: Understanding Structure. An Introduction to Filipino Sign Language. Phil. Deaf Resource Center, 2004.
• Phil. Deaf Resource Center and Phil. Federation of the Deaf. Part 2: Traditional and Emerging Signs. An Introduction to Filipino Sign Language. Phil. Deaf Resource Center, 2004.
• Heeyoul Choi, Brandon Paulson, and Tracy Hammond. Gesture recognition based on manifold learning. Structural, Syntactic, and Statistical Pattern Recognition, 5342:247–256, December 2008.
• Philippe Dreuw, Carol Neidle, Vassilis Athitsos, Stan Sclaroff, and Hermann Ney. Benchmark databases for video-based automatic sign language recognition. In International Conference on Language Resources and Evaluation, Marrakech, Morocco, May 2008. http://www-i6.informatik.rwth-aachen.de/~dreuw/ database.php.
• Raymond G. Gordon Jr., editor. Ethnologue: Languages of the World, 15th ed. SIL International, Dallas, Texas, 2005. http://www.ethnologue.com/.
• Sushmita Mitra and Tinku Acharya. Gesture recognition: A survey. IEEE Trans. Systems, Man & Cybernetics, 37(3):311–323, May 2007.
• Phil. National Statistics Office. Persons with disability comprised 1.23 percent of the total population. Special Release No. 150, March 2005. http://www.census.gov.ph/data/sectordata/sr05150tx.html.
• Sylvie C.W. Ong and Surendra Ranganath. Automatic sign language analysis: A survey and the future beyond lexical meaning. IEEE Trans. Pattern Analysis & Machine Intelligence, 27(6):873–891, June 2005.
• World Health Organization. Deafness and hearing impairment. Fact Sheet N300, March 2006. http://www.who.int/mediacentre/factsheets/fs300/ en/index.html.
• Sam T. Roweis and Lawrence K. Saul. Think globally, fit locally: Unsupervised learning of low dimensional manifolds. Science, 290(5500):2323–2326, December 2000.
• Joshua B. Tenenbaum, Vin de Silva, and John C. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, 290(5500):2319–2323, December 2000. http://waldron.stanford.edu/~isomap/.
• Christian Philipp Vogler. American Sign Language Recognition: Reducing the Complexity of the Task with Phoneme-Based Modeling and Parallel Hidden Markov Models. PhD thesis, University of Pennsylvania, 2003.

Manifold Learning - part 2

Dimensionality Reduction

Trying to make sense of 19,200 dimensions is asking for trouble. Fortunately for us poor humans, most data are constrained in some way. For example, the data varies but it doesn't vary along all 19,200 dimensions at the same time; it varies along some of the dimensions, some of the time. If we know how and when the data changes, we can approximate our data with a smaller set of dimensions. This is the known as dimensionality reduction.

An Illustrated Example

Let's take a two-dimensional example. Let's say the data we have collected come in pairs, and when we plot them it looks like this:

Unfortunately, the analytical tools that we have only work in one-dimension. We need to reduce the number of dimensions before we can analyse it. Fortunately for us, it seems the data we have (almost) fall along a straight line.

Let's rotate our plot such that the line becomes the new X-axis. It's still the same data, we just changed the way we look at it. Notice that the data (blue squares) are very close to the new axis (red line).

If the variation along the new Y-axis is much, much smaller than the variation along the new X-axis, we can approximate our data by it's projection along the new X-axis. We can pretend that the projections (red circles) are our data (blue squares) if our data is very, very close to the new X-axis (red line)*.

We can now use the projections in our tools because it has only one dimension. We have reduced the number of dimensions of our data from two to one. Yes, errors will be introduced since the projections are not the same as our data. As long as the variations along one (new) axis is much, much larger than the other (new) axis, the error will be small.

Principal Component Analysis (PCA) is one such method that does this, applicable in many problem domains.

* Let's ignore what we mean by "very, very close" for now.

Manifold Learning - part 1

Background: How many dimensions?

When we talk of dimensions in casual conversation, we often recall high school geometry. A point has zero dimensions, a line segment has one dimension (length), a rectangle has two dimensions (length & width), and a block has three dimensions (length, width & height).

We can also think of dimensions as a tuple, or a set of numbers, and this set of numbers describe something. For example, you can think of color in terms of Red, Green, and Blue components. We can say color has three dimensions (R, G and B). The same color can be represented with a different set of numbers; Cyan, Yellow, Magenta, and blacK. This time, color has four dimensions (C,Y,M, and K). If we are consistent with our set of numbers, we can describe many things. eHarmony supposedly has 29 dimensions to describe each person. It simply means they use 29 numbers to describe a person, whatever those numbers are supposed to measure.

Now analysing three dimensions is straightforward. We can turn it into graphs and plots, and it is easy to visualize. Four dimensions, a little harder but doable (look up color solid or color space sometime). But, 29 dimensions? How about 19,200 dimensions? We need help for those.

Video to Data

or How Do We Represent Video as an Input to Our Various Algorithms?

What is video anyway? To oversimplify, video is a series of images shown one after another. There are many display and storage formats; but, in essence, they are all just a set of images. How fast, how often the images are presented is measured in frames-per-second (fps). For example, television in usually shown at 30 fps. Each frame is one image or picture; so, television will show us 30 images* per second, one after another. You can think of video as time-series data.

Let's turn our attention to each frame (image) in the video. How many numbers do we need to represent an image? It depends on the size of the image. For illustration purposes, let's assume that our image is 160 pixels high and 120 pixels wide**. That means we have 19,200 pixels (160 x 120) to represent the image. If we have a color image/video, each pixel has color information -- what colors are present at that particular pixel of the image. Depending on how color was encoded, we could have 3 or 4 numbers to represent color. If we have a gray scale image, each pixel will only have the intensity information -- how dark or bright is that particular pixel. Thus, a gray scale image will need 19,200 numbers to represent it. If we treat video as time-series data, each data point will have 19,200 numbers associated with it. And that is exactly how the FSL recognition system we implemented treats video data. We can do this because all the images (frames) in a video has the same size.

* For TV, it's actually half-images per second. To keep the discussion simple, I'm ignoring that.

** It doesn't matter what storage format was used in the original video; at some point, it will have to be displayed on the screen, which has pixels.

back from the dead

I haven't been posting as much lately and for that I apologize to my readers (all three of you). I have successfully defended my thesis proposal (CS298) and I am now in thesis proper (CS300). I plan to do my final thesis defense 2nd week of October.

What have we learned during the Marathon?

• Sign language recognition is hard. Sign language linguistics are decades behind spoken language linguistics. The field is wide open for different approaches to the problem.
• Data! Data! Data! A lot of data is needed. Collecting and documenting FSL, its many variants, and the local signs are of vital importance if we hope to understand the underlying structure.
• Focus the work. Far too many times we want the paper to be perfect when we are finished; and we don't start writing until we have all the pieces. Guess what? That's not going to happen. The papers and reports will always have something missing. We should always keep the big picture in mind, and focus on our little corner.
• Keep writing. Edit later. This applies to many things, not just reports and papers. In free/open source software terms, release early and release often. That's what your editor is for (and if you don't have and editor, your adviser). They tell you what is clear and what is not; what needs reworking; what's missing.
• Matlab is expensive. Too expensive it turns out. Since I don't have access to the Matlab installation 24/7 in the lab, I am forced to look at alternatives. Octave, Scilab and R are my candidates.

Onward!

marathon day 18: small steps

FSL video progress

• 90 out of 127 signs (9 out of 13 groups) recorded
• 2 out of 3 signers recorded
• 90 out of 328 recorded samples processed

Proposal/Thesis Paper writing

• configured LaTeX templates
• draft Chapter 1: Introduction
• draft Chapter 2: Related Literature
• draft Chapter 3: Research Problem

marathon day 15: I lost my nose

It is time to re-evaluate our progress. What have we accomplished? What have we learned?

Accomplishments

1. Created a screencast of the prototype of the visualization tool for demonstrations.
2. Incremental improvements in the visualization tool.
3. Standardized the mencoder options for my data files. mencoder is part of the MPlayer project.
4. Scheduled additional recording sessions with the Deaf next week.
5. Edited two groups of FSL video recordings. I am looking into automating this with video segmentation.
6. Started working on the problem of metrics. How do I measure similarities between (recorded) signs?

Non-Accomplishments

1. Re-organized the files under my thesis directory. Includes updates to the back-up scripts.
2. Added to the goals for the marathon: video segmentation module
3. Added to the goals for the marathon: hand shape recognition
4. Added to the goals for the marathon: hand tracking
5. Constantly underestimate the scope of sign language complexity.

marathon day 4: nose to the grindstone

From the recording sessions, I now have 89 unique FSL signs. Each sign was recorded for both Rommel and Mary Jane, making a total of 178 samples. Sometimes there two or more takes per sample, meaning I'll end up with more than 178 samples in all. Right now I am editing and resizing the video files into small 160x120 clips - one clip per sign.

20 out of 178 done

marathon day 1: Procrastination

I have forgotten all about this: Structured Procrastination. Combined with mini-milestones, this approach works very well for me.

Mini-milestones, for those unfamiliar with the term, are very small tasks with only two possible statuses - NOT DONE and DONE. There is no 80% Done, it is either finished or not finished. This means the tasks must be small and straight-forward. We break down projects into smaller and smaller sub-projects, modules, functions and tasks until we have small, easily finished to-do items.

Structured procrastination exploits these small tasks. Large to-do items are broken up into small tasks making it easy to switch projects. If I don't feel like doing Project A, there are several mini-milestones from Project B I can accomplish. Once I get bored, switch back to Project A or yet another Project C.

marathon day 0

This summer, starting April 20, the lab is doing a Research Marathon. Forty-two days of nose-to-the grindstone research grunt work. The goals of the marathon is to (a) produce solid experimental data to back up the thesis; and (b) to produce a paper or report ready for publication. In my case, I will add a third goal: (c) my thesis proposal defense.

I am simultaneously excited and terrified, although I'm long past the stage where fear and excitement are indistinguishable. I have no idea what's going to happen and that's a good thing! You could say I am taking the pessimistic approach: I'll be pleasantly surprised more often.

stuck in a rut

Sometimes, when doing research, we find going in circles. We keep hitting a wall. We run faster and faster only to find we hardly moved. That's where I was this past two weeks. I found that I loose interest quickly if I cannot see the goal. Or I can see the goal, but I cannot see the next milestone. The solution I found would be to look at the research roadmap and figure out where to go from there.

I also found that I am very vulnerable to mental fatigue. Tedious, repetitive tasks (like editing and converting videos), reading too much (so. many. papers.) or thinking about one particular problem (like algorithm design) pound my poor brain into mush. The solution that works for me is to switch tasks; when I start to feel fatigued, I go do something else, preferably something very different from what I was originally doing. Hobbies become very critical for maintaining sanity.

It's nice to see that I can still learn something new about myself.