This post is about the use of Viterbi search in NLP applications. Skip the next paragraph if you recall readily how VS works.

The easiest formulation of VS is for a sequence labeling problem: given an input x, find a label vector y1,...,yN that maximizes the score [ f(x,y0,y1) + f(x,y1,y2) + ... + f(x,y{N-1},yN) ]. (Here, y0 is some special <s> symbol.) When there are K possible values for each label, VS solves this by filling in a dynamic programming matrix a of size (N+1)*K, where a(0,k) is zero if k is <s> and negative infinity otherwise. Recursively, a(n+1,k') is [ max_k [ a(n,k) + f(x,k,k') ] ]. The largest a(N+1, . ) gives the highest score; by storing backpointers (which k was the largest) in another matrix, we can recover the whole sequence once we reach the end. This runs in time O(NK^2), as opposed to O(N^K) as a naive implementation would run.

I am becoming somewhat notorious for not using Viterbi search, even for sequence labeling problems (ironic, given that I am part of the Viterbi School of Engineering). The purpose of this post is to show that this is not unreasonable.

My evolving feeling on this has two angles:

- Viterbi is good for something like an HMM where we can't model the whole input as features and so we need to talk back-and-forth via Viterbi. But when we get to use any feature at any time (as in any modern model), this advantage goes away.
- I think people ascribe some "magic" to Viterbi. At least in NLP, the Viterbi algorithm and its generalizations (inside-outside, etc.) are treated as stand alone units. They're not. They're simply based on the observation that under certain constraints, when executing search, one can do efficient memoization. If you throw away the "magic" of Viterbi and treat it as jsut another search algorithm, you see that there's nothing special there.

The "magic" of Viterbi is that it efficiently integrates all information from the different sources assuming that the conditional independences hold and assuming that all conditional probabilities are correctly estimated. But we know this is not the case.

That said, I think there is something to be said for later decisions being able to influence earlier ones. But I don't take this as given. And I don't think it's always the case. This is a big open question for me. By using a more complex search algorithm, you're forcing more decisions to be made but are (we hope) making these decisions easier. This is a trade-off. One angle is not a priori better than the other.

## 8 comments:

Hi, can I have a look at the Viterbi algorithm? Or do you know any web that show the Viterbi algorithm? Thank you... ^^

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

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 hardyed hardyed hardy clothinged hardy clothinged hardy shoesed hardy shoesdon ed hardydon ed hardyed hardy clothesed hardy clothesed hardy bagsed hardy bagsed hardy swimweared hardy swimweared hardy jeansed hardy jeansed hardy mensed hardy mens Thank you for the informationReally 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

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

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.

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.

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

Post a Comment