26 April 2009

Viterbi search, minimum Bayes risk and laplacian eigenmaps

I've been slow at posting because I wanted to post on this current topic for a while, but wanted to work out some more details before doing so. Well, it didn't happen. So I'm writing sans details.

Let's think for a minute about non-linear dimensionality reduction, aka manifold learning. If we compare what, say, ISOMAP does with what laplacian eigenmaps (LE) does, they're really quite similar. In both cases, we construct a graph over our data points, usually a kNN graph or something, sometimes with edge weights, sometimes not. We then attempt to embed the points in a low dimensional space to minimize some sort of distortion. In ISOMAP, the distortion is based on the shortest path distance between the two points in our constructed graph. In LE, the distance is measures according to the Laplacian of the graph. The notion of a Laplacian of a graph is basically a discrete version of the more standard notion of the differential operator by the same name (that comes up in most standard analysis courses). In continuous land, it is the divergence of the differential, which essentially means that measures some form of diffusion (and has its original applications in physics). In discrete land, where we live, it can be thought of as a measure of flow on a graph.

The key difference, then, between ISOMAP and LE is whether you measure distances according to shortest path or to flow, which has a very "average path" feel to it. The advantage to LE is that it tends to be less susceptible to noise, which is easy to understand when viewed this way.

Now, getting back to NLP stuff, we often find ourselves doing some sort of shortest path search. It's well known that the much loved Viterbi algorithm is exactly an application of dynamic programming to search in the lattice defined by an HMM. This extends in well known ways to other structures. Of course, Viterbi search isn't the only game in town. There are two other popular approaches to "decoding" in HMMs. One is marginal decoding, where we individually maximize the probability of each node. The other is minimum Bayes risk decoding. Here, we take a user-supplied risk (aka loss) function and try to find the output that minimizes the expected risk, where the probabilities are given by our current model. MBR has been shown to outperform Viterbi in many applications (speech, MT, tagging, etc.). If your risk (loss) function is 0/1 loss, then these recover the same solution.

What I'm curious about is whether this is a connection here. I'm not exactly sure how the construction would go -- I'm thinking something like a graph defined over the lattice vertices with edges that reflect the loss function -- but there definitely seems to be a similarity between MBR and average path, which is approximately equal to a Laplacian operation (aka spectral operation). The reason I think this would be interesting is because a lot is known about spectral computations and we might be able to use this knowledge to our advantage (coming up with MBR algorithms is sometimes a bit painful). An additional complication (or bit of fun, if you see it that way) is that there are at least three standard ways to generalize the notion of a Laplacian to a hypergraph, which is what we would really need to do. Perhaps we can help pick out the "right" one through the MBR connection.

33 comments:

Suresh said...

Slightly OT, but if you think of what's the analogy of averaged shortest paths, then electrical flow is what comes to mind, with resistance acting as an edge cost (you might have to exponentiate or otherwise transform them to make it work quite right).

Another observation is that since the Laplacian captures various kinds of cuts (see the spectral clustering work), you'd want to show that MBR acts like it's finding a good cut or a good flow of some kind. Maybe even a dual formulation might be helpful to reveal such structure

Kevin said...

Hmm, this is interesting... but here's a question:

In decoding we ultimately want to compute a path, whether this path is shortest distance or average/MBR "distance". In manifold learning, the actual path between two points is not that important, since the emphasis is on the value or distance of that path (or average path). Do you think the spectral operators could still work for decoding then? (this isn't a rhetoric question--I don't know the answer)

Another question: I'm curious, what are the standard ways to turn Laplacian into a hypergraph?

Anonymous said...

網頁設計,情趣用品,情趣用品,情趣用品,情趣用品
色情遊戲,寄情築園小遊戲,情色文學,一葉情貼圖片區,情惑用品性易購,情人視訊網,辣妹視訊,情色交友,成人論壇,情色論壇,愛情公寓,情色,舊情人,情色貼圖,色情聊天室,色情小說,做愛,做愛影片,性愛

免費視訊聊天室,aio交友愛情館,愛情公寓,一葉情貼圖片區,情色貼圖,情色文學,色情聊天室,情色小說,情色電影,情色論壇,成人論壇,辣妹視訊,視訊聊天室,情色視訊,免費視訊,免費視訊聊天,視訊交友網,視訊聊天室,視訊美女,視訊交友,視訊交友90739,UT聊天室,聊天室,豆豆聊天室,尋夢園聊天室,聊天室尋夢園,080聊天室,080苗栗人聊天室,女同志聊天室,上班族聊天室,小高聊天室 

AV,AV女優
視訊,影音視訊聊天室,視訊交友
視訊,影音視訊聊天室,視訊聊天室,視訊交友,視訊聊天,視訊美女

Anonymous said...

酒店經紀PRETTY GIRL 台北酒店經紀人 ,禮服店 酒店兼差PRETTY GIRL酒店公關 酒店小姐 彩色爆米花酒店兼職,酒店工作 彩色爆米花酒店經紀, 酒店上班,酒店工作 PRETTY GIRL酒店喝酒酒店上班 彩色爆米花台北酒店酒店小姐 PRETTY GIRL酒店上班酒店打工PRETTY GIRL酒店打工酒店經紀 彩色爆米花

samuel gerber said...

Laplacian eigenmaps is equivalent to embedding commute times of a random walk on the graph [ Huaijun and Hancock ].

Commute time can be interpreted as an electrical circuit - thus LE is an averaged shortest path for a graph with edges representing resistors.

Bob Carpenter said...

In MBR, we won't necessarily compute a path. For instance, consider POS tagging or NE chunking. If we take something like F-measure loss balanced to recall, then if there are two outputs with probability 0.4 each, we'll output them both to improve our recall at the cost of precision. We do this all the time for high recall named-entity chunking.

In practice, I haven't found per-tag decoding for POS tagging for for chunking to be much different in 0/1 performance from regular Viterbi -- we have both implemented in LingPipe's HMM and chunker decoders. Kakade, Teh and Roweis, on the other hand, found that training a MEMM with that loss had a huge effect.

Auto Car Rental said...

sorry to ask this here but… I really love your theme, would it happen to be a free one i can download somewhere, or is it a custom theme you had made? Soon i will be launching my own blog, however i’m not great with designs but i do like the style of your site so it would be excellent if i could find (or buy) something with a similar look as my last designer cannot finish my site. Thanks! Please come visit my site moving truck rental when you got time.

Car Accessories said...

Congratulations, you just earned yourself an entry in my feed reader, great blog. Please come visit my site cars accessories and give me any valuable feedbacks.

eda said...

情趣,G點,性感丁字褲,情趣,角色扮演服,吊帶襪,丁字褲,情趣用品,無線跳蛋,男女,

按摩棒,電動按摩棒,飛機杯,視訊,自慰套,自慰套,情趣用品,情趣內衣,

情趣按摩棒,自慰套,角色扮演,按摩棒,跳蛋,情趣跳蛋,
.,
潤滑液,SM,內衣,性感內衣,自慰器,充氣娃娃,AV,

rr8004 said...

Very nice information. Thanks for this. Please come visit my site Business Directory Fortworth when you got time.

rr8004 said...

Very nice information. Thanks for this. Please come visit my site Fortworth Directory when you got time.

rr8004 said...

I enjoyed reading your work! GREAT post! I looked around for this… but I found you! Anyway, would you mind if I threw up a backlink from my site? Please come visit my site Columbus Directory when you got time.

rr8004 said...

I enjoyed reading your work! GREAT post! I looked around for this… but I found you! Anyway, would you mind if I threw up a backlink from my site? Please come visit my site Columbus Business Phone Book when you got time.

Anonymous said...

Do you think the spectral operators could still work for decoding then? (this isn't a rhetoric question--I don't know the answer)
Buy Assignment | Buy Coursework | Buy Thesis

Anonymous said...

we'll output them both to improve our recall at the cost of precision. We do this all the time for high recall named-entity chunking.
Buy Dissertation | Buy Essay

Biz said...

Hey,
Thanks a lot for this amazing post. I look forward to reading more on the topic in the future. Keep up the good work! This blog is going to be great resource. Love reading it.

Business Plan Presentation

naomi said...

情趣,情趣,情趣用品,情趣用品,情趣商品,情趣商品,按摩棒,跳蛋,情趣按摩棒,充氣娃娃,保險套,飛機杯,潤滑液,情趣內衣,性感內衣,g點,持久液,按摩棒,跳蛋,情趣按摩棒,充氣娃娃,保險套,飛機杯,潤滑液,情趣內衣,性感內衣,g點,持久液,按摩棒,跳蛋,情趣按摩棒,充氣娃娃,保險套,飛機杯,潤滑液,情趣內衣,性感內衣,g點,持久液,按摩棒,跳蛋,情趣按摩棒,充氣娃娃,保險套,飛機杯,潤滑液

tariely said...

Классные мультики мультфильмы бесплатно на кинозоуне.
электронная почта без регистрации

Anonymous said...

электронная почта без регистрации

gamefan12 said...

I would definitely make a change here. Just a little bit more work and it will work good.
boca raton cosmetic sedation dentist

Custom Essays said...

Hi,
I think ISOMAP and LE are same thing. The only difference is what you have shared here. Thanks, I personally like your post. Keep it up.

Custom Essays

qishaya said...

one day i went shopping outside,and in an ed hardy store,I found some kinds of ed hardy i love most they are Your website is really good Thank you for the information ed hardy ed hardy ed hardy clothing ed hardy clothing ed hardy shoes ed hardy shoes don ed hardy don ed hardy ed hardy clothes ed hardy clothes ed hardy bags ed hardy bags ed hardy swimwear ed hardy swimwear ed hardy jeans ed hardy jeans ed hardy mens ed hardy mens Thank you for the information

ally said...

Apart from these military fashion tops and ripped and torn jeans are also hip and happening this seasonwholesale LV handbags
monclerdiscount moncler jacketsmoncler coatsmoncler vestmoncler outletmoncler t-shirtmonclermoncler jacketsnew moncler coats
moncler vestmoncler outletmoncler polo t-shirtCoach handbags outletCoach TotesCheap Coach handbag 2010Discount Coach hand bagAuthentic Coach handbagNewest Coach handbags outletcoach outletLouis Vuitton TotesLouis Vuitton handbagsLV handbags 2010Discount LV handbagsCheap Louis Vuitton Outletnewest Louis Vuitton handbagscheap rain weardiscount rainweardog rain jacketscolorful rain bootsrainboots outletCheap Ture Religion Jeans outletDiesel JeansLevis JeansWholesale Ed Hardy JeansDiscount Dior Jeans outlet
cheap abercrombie fitch clothingdiscount abercrombie fitch T-shirtsdiscount abercrombie and fitch hoodiesabercrombie fitch outletwholesale abercrombie fitched hardy wholesaleLeather jackets are a must in the wardrobe this season.

ally said...

In the casual attire category tracksuits and tank tops rule for men.discount ed hardy wholesalewholesale ed hardyed hardy outletugg bootscheap ugg bootsdiscount ugg bootsclassic ugg bootsugg classic tall bootsdiscount abercrombie and fitch outletdiscount abercrombie outletdiscount abercrombie clothingdiscount abercrombie jacketdiscount abercrombie shirtdiscount abercrombie and fitch outletdiscount bercrombie and fitch clothesdiscount abercrombie and fitch hoodiediscount abercrombie and fitch shirtsdiscount abercrombie fitch jacketBesides, the urban trend, vintage clothing will also rule this season.

良哥 said...

Teenagers in a track adidas shoes can go through shoes rate adidas outlet teenage runner well knows that adidas sneakers to wear the right shoes air jordan 2010 any cross country among world jordan shoes especially important to the sportsman discount jordan shoes a young person growing up Pure GHD Not only do they want to bourke dooney handbags grow out of their shoes dooney bourke bags but shape of their feet changes which means every time we dooney bourke outlet the time comes to get dooney bourke totes a new pair of shoes eveyone NIKE SHOX a good choice to get NIKE SHOX SHOES it with a high material SHOX SHOES that breathes easily on random moncler They should be extended runs moncler jackets give enough support to athlets moncler coats especially around the ankles area moncler vest to avoid injury your ankles discount moncler outlet when you make your trip discount moncler t-shirt something in store possible fit cheap ugg boots his is also the way to discount ugg boots that don't fit properly only ugg boots it focuses on your convenience classic ugg boots but they are not returnable ugg classic tall boots

seldamuratim said...

Really trustworthy blog. Please keep updating with great posts like this one. I have booked marked your site and am about to email it to a few friends of mine that I know would enjoy reading..
sesli sohbetsesli chatkamerali sohbetseslisohbetsesli sohbet sitelerisesli chat siteleriseslichatsesli sohpetseslisohbet.comsesli chatsesli sohbetkamerali sohbetsesli chatsesli sohbetkamerali sohbet
seslisohbetsesli sohbetkamerali sohbetsesli chatsesli sohbetkamerali sohbet

cilemsin42 said...

Really trustworthy blog. Please keep updating with great posts like this one. I have booked marked your site and am about to email it to a few friends of mine that I know would enjoy reading..
sesli sohbetsesli chat
sesli sohbet siteleri

sesli chat siteleri sesli sohbetsesli chat
sesli sohbet siteleri
sesli chat siteleri
SesliChat
cılgın sohbet
güzel kızlar
bekar kızlar
dul bayanlar
seviyeli insanlar
yarışma
canlı müzik
izdivac
en güzel evlilik
hersey burada
sesliparti
seslisohbet odalari
Sesli adresi
Sesli Chat
SesliChat Siteleri
Sesli Chat sitesi
SesliChat sitesi
SesliSohbet
Sesli Sohbet
Sesli Sohbet Sitesi
SesliSohbet Sitesi
SesliSohbet Siteleri
Muhabbet Sitesi
kamerali chat
Görüntülü Sohbet
Hasret gülleri
Çet sitesi
SesliSohbet
Sesli Sohbet
Canli sohbet
Turkce sohbet
Kurtce Sohbet
Kurtce Chat
Kurtce Muhabbet
Kurtce Sohbet
Kurdish Chat
SesliChat
Sesli Chat
SesliSanal
Guncel Haber
sohbet Sitesi
Chat sitesi..

seldamuratim said...

Really trustworthy blog. Please keep updating with great posts like this one. I have booked marked your site and am about to email it to a few friends of mine that I know would enjoy reading..

sesli sohbet
seslisohbet
sesli chat
seslichat
sesli sohbet sitesi
sesli chat sitesi
sesli sohpet
kamerali sohbet
kamerali chat
webcam sohbet

combattery84 said...

HP dv9700 battery
HP F4809A Battery
HP nc8000 battery
HP nc8230 battery
HP pavilion zd8000 battery
HP f2024b battery
HP f4812a battery
HP Pavilion ZV5000 battery
HP Pavilion DV1000 battery
HP Pavilion ZD7000 Battery
HP Pavilion DV2000 battery
HP Pavilion DV4000 Battery
HP Pavilion dv6000 Battery
HP Pavilion DV9000 Battery
HP F4098A battery
HP pavilion zx6000 battery
HP omnibook xe4400 battery
HP omnibook xe4500 battery
HP omnibook xe3 battery
Notebook NX9110 battery
IBM 02K6821 battery
IBM 02K7054 battery
IBM 08K8195 battery
IBM 08K8218 battery
IBM 92P1089 battery
IBM Thinkpad 390 Series battery
IBM Thinkpad 390X battery
IBM ThinkPad Z61m Battery
IBM 02K7018 Battery
IBM thinkpad t41p battery
IBM THINKPAD T42 Battery

combattery84 said...

IBM ThinkPad R60 Battery
IBM ThinkPad T60 Battery
IBM ThinkPad T41 Battery
IBM ThinkPad T43 Battery
IBM ThinkPad X40 Battery
Thinkpad x24 battery
ThinkPad G41 battery
IBM thinkpad r52 battery
Thinkpad x22 battery
IBM thinkpad t42 battery
IBM thinkpad r51 battery
Thinkpad r50 battery
IBM thinkpad r32 battery
Thinkpad x41 battery
SONY VGP-BPS2 Battery
SONY VGP-BPS2C Battery
SONY VGP-BPS5 battery
SONY VGP-BPL2C battery
SONY VGP-BPS2A battery
SONY VGP-BPS2B battery
SONY PCGA-BP1N battery
SONY PCGA-BP2E battery
SONY PCGA-BP2NX battery
SONY PCGA-BP2S battery
SONY PCGA-BP2SA battery
SONY PCGA-BP2T battery
SONY PCGA-BP2V battery
SONY PCGA-BP4V battery
SONY PCGA-BP71 battery
SONY PCGA-BP71A battery
SONY VGP-BPL1 battery
SONY VGP-BPL2 battery

DiSCo said...

Really trustworthy blog. Please keep updating with great posts like this one. I have booked marked your site and am about to email it

to a few friends of mine that I know would enjoy reading..
seslisohbet
seslichat
sesli sohbet
sesli chat
sesli
sesli site
görünlütü sohbet
görüntülü chat
kameralı sohbet
kameralı chat
sesli sohbet siteleri
sesli chat siteleri
görüntülü sohbet siteleri
görüntülü chat siteleri
kameralı sohbet siteleri
canlı sohbet
sesli muhabbet
görüntülü muhabbet
kameralı muhabbet
seslidunya
seslisehir
sesli sex

Anonymous said...

guoweigangSpeaking to the Ed Hardy Sale Gazette earlier this year, Mr abercrombie and fitch Gifford said he was hopeful ed hardy clothing the company could rally. He said: "I am Abercrombie Outlet reasonably confident that there are investors out there who will support us. It's a great company. We just need to get the financial side in order."I am sure we can recover the position of the number one company in the market."
The corporate clothing firm employs 220 people Ed Hardy store in Thornbury and a further 50 in nearby Aztec West. Nationally, at shops and warehouses, the company employs nearly 500 people.
Alexandra Plc first started as a small shop in Bristol, in 1854. The company started to sell work wear in the 1950s and was first floated on the stock market in 1985.

Sesli Chat said...

Really trustworthy blog. Please keep updating with great posts like this one. I have booked marked your site and am about to email it

to a few friends of mine that I know would enjoy reading..
seslisohbet
seslichat
sesli sohbet
sesli chat
sesli
sesli site
görünlütü sohbet
görüntülü chat
kameralı sohbet
kameralı chat
sesli sohbet siteleri
sesli chat siteleri
sesli muhabbet siteleri
görüntülü sohbet siteleri
görüntülü chat siteleri
görüntülü muhabbet siteleri
kameralı sohbet siteleri
kameralı chat siteleri
kameralı muhabbet siteleri
canlı sohbet
sesli muhabbet
görüntülü muhabbet
kameralı muhabbet
birsesver
birses
seslidunya
seslisehir
sesli sex