Tagging Problems and Hidden Markov Models - Overview

Aug 28, 2026

Upload by Jake

Tagging Problems and Hidden Markov Models讲解了在监督学习框架下的序列标注任务，包括从训练集归纳函数，将新句子映射到标注序列。内容涵盖生成模型与噪声信道模型、隐马尔可夫模型（HMM）标注器，以及标注的基本定义与参数估计方法。文中还介绍Viterbi算法用于最优路径解码，并展示词性标注、命名实体识别及把命名实体提取形式化为标注问题的方法。

LanguageEnglish

CategoryTechnology

FormatPDF

Pages38

Reading Time1 h 36 min

AccessFree to download

The Tagging Problem

Generative and noisy-channel models for supervised learning

Hidden Markov Model (HMM) taggers

Basic definitions

Parameter estimation

The Viterbi algorithm

Part-of-Speech Tagging

Named Entity Recognition

Named Entity Extraction as Tagging

Our Goal

Training set and inducing a mapping function

Two Types of Constraints

Inﬂuential preferences

Contextual preferences

Supervised Learning Problems

Learning conditional models p(y|x)

Tagging Problems, and Hidden Markov Models Michael Collins, Columbia University Overview I The Tagging Problem I Generative models, and the noisy-channel model, for supervised learning I Hidden Markov Model (HMM) taggers I Basic de􀀌nitions I Parameter estimation I The Viterbi algorithm Part-of-Speech Tagging INPUT: Pro􀀌ts soared at Boeing Co. , easily topping forecasts on Wall Street, as their CEO Alan Mulally announced 􀀌rst quarter results. OUTPUT: Pro􀀌ts/N soared/V at/P Boeing/N Co. /N ,/, easily/ADV topping/V forecasts/N on/P Wall/N Street/N ,/, as/P their/POSS CEO/N Alan/N Mulally/N announced/V 􀀌rst/ADJ quarter/N results/N . / . N = Noun V = Verb P = Preposition Adv = Adverb Adj = Adjective: : : Named Entity Recognition INPUT: Pro􀀌ts soared at Boeing Co. , easily topping forecasts on Wall Street, as their CEO Alan Mulally announced 􀀌rst quarter results. OUTPUT: Pro􀀌ts soared at [Company Boeing Co.], easily topping forecasts on [Location Wall Street], as their CEO [Person Alan Mulally] announced 􀀌rst quarter results. Named Entity Extraction as Tagging INPUT: Pro􀀌ts soared at Boeing Co. , easily topping forecasts on Wall Street, as their CEO Alan Mulally announced 􀀌rst quarter results. OUTPUT: Pro􀀌ts/NA soared/NA at/NA Boeing/SC Co. /CC ,/NA easily/NA topping/NA forecasts/NA on/NA Wall/SL Street/CL ,/NA as/NA their/NA CEO/NA Alan/SP Mulally/CP announced/NA 􀀌rst/NA quarter/NA results/NA . /NA NA = No entity SC = Start Company CC = Continue Company SL = Start Location CL = Continue Location : : : Our Goal Training set: 1 Pierre/NNP Vinken/NNP ,/, 61/CD years/NNS old/JJ ,/, will/MD join/VB the/DT board/NN as/IN a/DT nonexecutive/JJ director/NN Nov. /NNP 29/CD . / . 2 Mr. /NNP Vinken/NNP is/VBZ chairman/NN of/IN Elsevier/NNP N.V. /NNP ,/, the/DT Dutch/NNP publishing/VBG group/NN . / . 3 Rudolph/NNP Agnew/NNP ,/, 55/CD years/NNS old/JJ and/CC chairman/NN of/IN Consolidated/NNP Gold/NNP Fields/NNP PLC/NNP,/, was/VBD named/VBN a/DT nonexecutive/JJ director/NN of/IN this/DT British/JJ industrial/JJ conglomerate/NN . / . : : : 38,219 It/PRP is/VBZ also/RB pulling/VBG 20/CD people/NNS out/IN of/IN Puerto/NNP Rico/NNP ,/, who/WP were/VBD helping/VBGHuricane/NNP Hugo/NNP victims/NNS ,/, and/CC sending/VBG them/PRP to/TO San/NNP Francisco/NNP instead/RB . / . I From the training set, induce a function/algorithm that maps new sentences to their tag sequences. Two Types of Constraints In􀀍uential/JJ members/NNS of/IN the/DT House/NNP Ways/NNP and/CC Means/NNP Committee/NNP introduced/VBD legislation/NN that/WDT would/MD restrict/VB how/WRB the/DT new/JJ savings-and-loan/NN bailout/NN agency/NN can/MD raise/VB capital/NN . / . I \Local": e.g. , can is more likely to be a modal verb MD rather than a noun NN I \Contextual": e.g. , a noun is much more likely than a verb to follow a determiner I Sometimes these preferences are in con􀀍ict: The trash can is in the garage Overview I The Tagging Problem I Generative models, and the noisy-channel model, for supervised learning I Hidden Markov Model (HMM) taggers I Basic de􀀌nitions I Parameter estimation I The Viterbi algorithm Supervised Learning Problems I We have training examples x (i); y (i) for i = 1 : : : m. Each x (i) is an input, each y (i) is a label. I Task is to learn a function f mapping inputs x to labels f (x) Supervised Learning Problems I We have training examples x (i); y (i) for i = 1 : : : m. Each x (i) is an input, each y (i) is a label. I Task is to learn a function f mapping inputs x to labels f (x) I Conditional models: I Learn a distribution p (yj x) from training examples I For any test input x, de􀀌ne f (x) = arg max y p(yj x)

FAQs

什么是标注问题（Tagging Problem）？

标注问题的目标是学习一个函数，把输入句子映射到对应的标签序列。通过训练集归纳该函数后，可对新句子给出标签序列。

HMM 标注器在序列标注中扮演什么角色？

HMM 标注器使用隐状态与转移/发射思想来对序列进行建模，并结合解码算法寻找最优标签序列。内容同时给出基本定义与参数估计。

Viterbi 算法用于解决什么问题？

Viterbi算法用于在给定模型条件下高效地找到最优路径，从而得到最可能的标签序列。

Aug 28, 2026

Upload by Jake