The TreeQ package is a set of C-language applications that implement machine learning algorithms using a tree-structured classifier. This approach is particularly effective for high-dimensional continuous data such as audio and video. Written in vanilla C, TreeQ is highly portable, depends on no external libraries, and is released under a BSD license. TreeQ is being used by research groups and companies worldwide. Because TreeQ is a tree-based Vector Quantizer, "TreeQ" is pronounced "tree-cue," to rhyme with "VQ."

About TreeQ

The following diagrams show how TreeQ can be used to build an audio classifier. First, the audio waveform is processed into a spectral representation, stored in data files in the "fff" format. (Note that TreeQ does not do this first step; use HCopy from the HTK tools available from Cambridge University. fff files are compatible with HTK files.)

TreeQ block diagram


The next step is to "quantize" each vector using a quantization tree computed by TreeQ. This recursively divides the vector space into bins, each of which corresponds to a leaf of the tree. The growtreeprogram in TreeQ constructs a quantization tree given training data such that different kinds of audio will tend to wind up in different bins, as shown here:

TreeQ tree generation

Once a tree has been constructed, it can be used to quantize input data, using the TreeQ program probtree. Any input vector will fall into one and only one bin. Given any input data, the distribution of the vectors in the various bins characterize that data. For each input file, counting how many vectors fall into each bin yields a histogram file that is used in the distance measure.

Once histograms have been computed, they can be used as a compact representation of the source audio. Similar audio will have similar histograms, and a distance measure between the histograms can classify and rank audio by similarity. The histdist program computes the distance between histograms, using a number of possible distance measures. A straightforward use of histdist is a search engine for audio. Given a number of audio examples, they can be ranked by similarity to produce a ranked list like a conventional text search engine.

Computing the distance between TreeQ histograms

Another use of histdist is shown in the diagram above. Reference histograms are computed for a number of different classes, say, speech and music given example training data. An unknown audio sample may be classified by how similar it is to the  reference histograms. If the input data has the smallest histogram distance from the music histogram, then the unknown data is classified as music.


TreeQ Applications

This section lists some systems using TreeQ:


TreeQ Publications

Publications describing research use of TreeQ: