On structured learning

This post is devoted to structured learning, a novel machine learning paradigm which may be used for solving different computer vision problems. For example, finding optimal parameters of graphical models is essentially a structured learning problem. I am going to give an introductory talk on structured learning for Dmitry Vetrov's graphical models class this Friday at 4:20 pm, so please feel free to drop by if you are in Moscow (the talk is to be in Russian).

Structured learning is basically a very general supervised learning setting. Consider the classification setting as a basic problem. One needs to find parameters of a function that maps a feature vector to one of the pre-defined class labels $\mathbb{R}^m \to \{c_1, c_2, \dots, c_K\}$. The fundamental property is the classes are unordered and orthogonal. The latest means the probabilities of objects classified as different labels are uncorrelated (some negative correlation is normal since strong classifying of an object as $c_i$ decreases the probability for rest of the labels).

Now consider regression, which is another supervised learning problem where feature vectors map to real values: $\mathbb{R}^m \to \mathbb{R}$. It might be considered a classification problem with infinite number of classes. There are two obvious flaws in this reduction. First, a training set is unlikely to have at least one example for each class. To overcome this one can quantize the codomain and train a classifier over a finite set of class labels. However, it leaves us with the second flaw: the method does not take into account correlation between the possible outcomes. The bins are ordered: the training features that correspond to neighbouring bins should be handled differently from those that correspond to distant bins. That's why some global methods (like linear regression) are used.

The similar situation is in the case of a structured outcome. In this case, one usually has a plenty of possible outcomes, but they are not independent. The techniques of structured learning are applicable when the outcomes have some underlying structure, and the elements of the structure have similar sets of features. Also, it should be possible to estimate how bad the prediction is (often in terms of incorrectly predicted elements), which is called structured loss. The methods allow small deviations from the ideal training outcome, which are possible e.g. because of noise, but penalize the substantial ones (just like regression!). The prediction function (parameters of which are tuned) can thus be formalized as a mapping $\mathbb{R}^{m \times l} \to \{c_1, c_2, \dots, c_K\}^l$.

The possible example is hidden Markov model learning, where the elements are emission potentials and transition potentials, and the loss can be defined as the number of wrong HMM outputs. According to the upper formalization, there are $l$ elements, each represented by $m$ features (in practice, $m$ can vary for different types of elements). Since the labels of transition elements are strictly defined by emission outputs, not every outcome is possible.

Another example of a structured prediction problem is natural language parsing. Given a sentence of a natural language, the corresponding parsing tree is to be constructed. Surprisingly, parsing trees could also be represented as high-dimensional vectors, with constraints applied. To summarize, structure prediction has outcome that is multivariate, correlated and constrained.

Ideally, the parameters of structured prediction should be tuned via likelihood maximization, but this turns out to be intractable due to the need of computing the partition function on each gradient optimization step. That's why the L²-regularized hinge loss is usually minimized. The prediction algorithm is represented as a scoring function over possible outcomes. The task of the learning algorithm is to find the parameters of the scoring function to make it return maximum values for the true outcomes on the training set, and low ones for the instances that are far from optimal. Given that, the margin between good and bad possible outcomes should be maximized (in terms of scoring function value).

You can learn more about structure learning from Ben Taskar's NIPS 2007 tutorial. See also our recent 3DIMPVT paper for an up-to-date survey of MRF/CRF training methods and their applications.

PS. I've installed MathJax equation engine into the blog. Seems to work, huh?

i have a slight obsession with the skirted table....especially an octagonal, tailored one.  let's add this to the very long list of things i need for my house :)

*images courtesy of amanda nisbet/style at home/effortless style, tom scheerer, ashley goforth design, lonny, palmer weiss

Finding Your Way In (Computer) Science

Today in The Difference Engine I write about self-esteem, inspired by some recent conversations with young FCSes.

Bola Voli

Permainan bola voli, awalnya disebut "mintonette" diciptakan pada tahun 1895 oleh William G. Morgan, setelah penemuan bola basket dengan hanya 4 tahun Morgan,. Lulusan Springfield College YMCA, permainan yang dirancang untuk menjadi kombinasi basket, tenis baseball, dan bola tangan.

Net bola voli pertama, dipinjam dari tenis, hanya 6'6 "tinggi (jika Anda perlu ingat bahwa Amerika rata-rata lebih pendek pada abad ke-19).

Gaya ofensif pengaturan dan spiking telah dibuktikan di Filipina pada 1916. Dalam tahun-tahun berikutnya, menjadi jelas bahwa aturan baku yang dibutuhkan untuk turnamen, dan oleh karena itu USVBA (Amerika Serikat Voli Association) dibentuk pada tahun 1928.

Dua tahun kemudian, permainan 2-pria voli pantai pertama dimainkan, meskipun sisi profesional olahraga tidak muncul sampai lama kemudian. Tidak mengherankan, asosiasi voli pantai pertama kali muncul di California (1965), dan pemain profesional bersama di bawah naungan AVP (Amerika Voli Profesional) pada tahun 1983.

Selama Olimpiade 1984 di Los Angeles, pria Amerika dan wanita telah memenangkan emas dan perak dalam kompetisi bola voli indoor. Empat tahun kemudian di Olimpiade di Korea, orang-orang sekali lagi mencetak gol emas. Sejak tahun 1996, voli pantai 2-manusia secara resmi diperkenalkan kepada Olimpiade. Saat ini ada lebih dari 800 juta pemain bola voli di seluruh dunia, 46 juta di antaranya di Amerika Serikat

Sebuah kronologi peristiwa PENTING Bola Voli.

Pada tahun 1900, bola khusus dirancang untuk olahraga.

Pada tahun 1916, Filipina, gaya ofensif bola melewati lintasan tinggi untuk disambar oleh pemain lain (permainan dan ujung) diperkenalkan.

Pada tahun 1917, permainan berubah 21-15 poin.

Pada 1920, tiga hits per sisi dan aturan barisan belakang serangan yang dilembagakan.

Pada tahun 1922, YMCA pertama kejuaraan nasional yang diadakan di Brooklyn, NY. 27 tim dari 11 negara bagian diwakili.

Pada tahun 1928, menjadi jelas bahwa turnamen dan aturan yang diperlukan, Amerika Serikat Voli Asosiasi (USVBA, sekarang USA Voli) dibentuk. The U. S. Terbuka pertama dipentaskan, bahwa lapangan terbuka untuk pasukan non-YMCA.

Pada tahun 1930, memainkan lagu pertama laki-laki dimainkan.

Pada tahun 1934, persetujuan dan pengakuan wasit voli nasional.

Pada tahun 1937, ketika AUA di Boston, tindakan yang diambil untuk mengenali U. S. Voli Asosiasi sebagai pemerintahan nasional resmi AS

Pada tahun 1947, Federation Internationale de Volleyball (FIVB) didirikan.

Pada tahun 1948, pantai pertama turnamen dua orang terjadi.

Pada tahun 1949, Kejuaraan Dunia awal diselenggarakan di Praha, Cekoslowakia.

Pada tahun 1964, bola voli diperkenalkan di Olimpiade Tokyo.

Pada tahun 1965, California Voli Pantai Association (CBVA) dibentuk.

Pada tahun 1974, Kejuaraan Dunia di Meksiko yang dirilis di Jepang.

Pada tahun 1975, Perempuan Tim Nasional Amerika Serikat mulai rejimen pelatihan sepanjang tahun di Pasadena, Texas (pindah ke Colorado Springs pada tahun 1979, Coto de Caza dan Fountain Valley, CA pada tahun 1980, dan San Diego, CA pada tahun 1985).

Pada tahun 1977, Men Tim Nasional Amerika Serikat mulai rejimen pelatihan sepanjang tahun di Dayton, Ohio (pindah ke San Diego, CA pada tahun 1981).

Pada tahun 1983, Asosiasi Voli Profesional (AVP) dibentuk.

Pada tahun 1984, Amerika Serikat memenangkan medali pertama mereka di Olimpiade di Los Angeles. Orang-orang memenangkan medali emas, wanita dan uang.

Pada tahun 1986, Women's Voli Profesional Association (WPVA) dibentuk.

Pada tahun 1988, U. S. Pria mengulangi Emas di Olimpiade di Korea.

Pada tahun 1990, Liga Dunia diciptakan.

Pada tahun 1995, olahraga Voli adalah 100 tahun!

Pada tahun 1996, voli pantai 2-orang akan menjadi olahraga Olimpiade.