条件随机场在关系学习中的应用_条件随机场的应用资源-CSDN文库

需积分: 9 52 浏览量 2018-11-13 14:07:31 上传评论收藏 379KB PDF 举报

### 条件随机场在关系学习中的应用 #### 引言与背景关系数据具有两个主要特点：我们希望建模的实体之间存在着统计依赖关系；每个实体通常具有一系列丰富的特性，这些特性有助于分类。例如，在对网页文档进行分类时，页面的文字内容提供了大量关于类别标签的信息，而超链接则定义了页面之间的关联性，这种关联性能够进一步提高分类的准确性[Taskar等人, 2002]。 #### 图模型的应用图模型是一种自然的形式化方法，用于利用实体间的依赖结构。传统上，图模型被用来表示联合概率分布p(y, x)，其中变量y代表我们希望预测的实体属性，而输入变量x代表我们对于实体的观察知识。然而，当处理关系数据时，如果直接建模联合分布，则可能会遇到困难，尤其是当涉及到丰富的局部特征时。这是因为需要建模输入变量x的分布p(x)，这可能包含复杂的依赖关系。建模这些依赖关系可能会导致模型变得难以计算（即不切实际），而忽略它们则可能会降低模型的性能。 #### 条件随机场的解决方案为了解决上述问题，可以考虑直接建模条件分布p(y | x)，这是分类任务中所需要的。这就是条件随机场(CRF)所采取的方法[Lafferty等人, 2001]。条件随机场本质上就是一个具有相关图形结构的条件分布p(y | x)。由于模型是条件性的，因此不必显式地表示输入变量x之间的依赖关系，从而允许使用输入的丰富、全局特征。例如，在自然语言处理任务中，有用的特征包括相邻单词、词组、前缀和后缀、大写情况、属于特定领域的词汇表以及来自诸如WordNet等来源的语义信息。 #### 条件随机场的基本概念 - **定义**：条件随机场是一个无向图模型，它给定一组观察变量x的情况下，定义了一个关于标签变量y的条件概率分布p(y | x)。 - **无向图模型**：CRF是一个无向图模型，意味着图中的边没有方向，这使得模型更加灵活，可以更自由地表达实体之间的依赖关系。 - **全局最优解**：与传统的最大熵模型不同，CRF可以在全局范围内寻找最优解，而不是仅限于局部最优。这意味着在进行预测时，CRF能够考虑到所有特征的组合效应，而不是独立地评估每个特征。 - **特征函数**：CRF使用特征函数来捕获输入x和输出y之间的相互作用。特征函数可以设计得非常灵活，允许模型捕捉复杂的模式和关系。 - **训练过程**：CRF的训练目标是最小化一个损失函数，该损失函数通常是训练数据上的负对数似然函数。这个过程可以通过梯度下降法或其他优化算法实现。 #### 条件随机场在关系学习中的优势 1. **灵活性**：条件随机场能够处理非常复杂的关系数据，并且能够轻松地集成多种类型的数据源。 2. **全局最优**：条件随机场能够在全局范围内寻找最优解，而不是像其他模型那样只考虑局部最优。 3. **特征的使用**：条件随机场允许使用丰富的特征集，这些特征可以跨越多个实体和关系。 4. **模型的可解释性**：与许多深度学习模型相比，条件随机场模型通常更容易理解和解释，这对于需要透明度和可信度的应用场景非常重要。 5. **适应性**：条件随机场可以应用于多种任务，如序列标注、分类和其他关系学习任务。条件随机场作为一种强大的机器学习技术，在关系学习领域有着广泛的应用前景。通过直接建模条件概率分布p(y | x)，CRF能够有效地处理复杂的依赖关系和丰富的特征，从而提高了模型的准确性和实用性。随着更多应用场景的出现和技术的进步，条件随机场将在未来继续发挥重要作用。

资源推荐

资源详情

资源评论

1 An Introduction to Conditional Random

Fields for Relational Learning

Charles Sutton

Department of Computer Science

Unive rsity of Massachusetts, USA

casutton@cs.umass.edu

http://www.cs.umass.edu/∼casutton

Andrew McCallum

Department of Computer Science

Unive rsity of Massachusetts, USA

mccallum@cs.umass.edu

http://www.cs.umass.edu/∼mccallum

1.1 Introduction

Relational data has two characteristics: ﬁrst, statistical dependencies exist between

the entities we wish to model, and second, each entity often has a rich set of features

that can aid classiﬁcation. For example, when classifying Web documents, the

page’s text provides much information about the class label, but hyperlinks deﬁne

a relationship between pages that can improve classiﬁcation [Taskar et al., 2002].

Graphical models are a natural formalism for exploiting the dependence structure

among entities. Traditionally, graphical models have been used to represent the

joint probability distribution p(y, x), where the variables y represent the attributes

of the entities that we wish to predict, and the input variables x represent our

observed knowledge about the entities. But modeling the joint distribution can

lead to diﬃculties when using the rich local features that can occur in relational

data, because it requires modeling the distribution p(x), which can include complex

dependencies. Modeling these dependencies among inputs can lead to intractable

models, but ignoring them can lead to reduced performance.

A solution to this problem is to directly model the conditional distribution p(y|x),

which is suﬃcient for classiﬁcation. This is the approach taken by conditional ran-

dom ﬁelds [Laﬀerty et al., 2001]. A conditional random ﬁeld is simply a conditional

distribution p(y|x) with an assoc iated graphical structure. Because the model is

2 An Introduction to Conditional Random Fields for Relational Learning

conditional, dependencies among the input variables x do not need to be explicitly

represented, aﬀording the use of rich, global features of the input. For example,

in natural language tasks, useful features include neighboring words and word bi-

grams, preﬁxes and suﬃxes, capitalization, membership in domain-speciﬁc lexicons,

and semantic information from sources such as WordNet. Recently there has been

an explosion of interest in CRFs, with successful applications including text process-

ing [Taskar et al., 2002, Peng and McCallum, 2004, Settles, 2005, Sha and Pereira,

2003], bioinformatics [Sato and Sakakibara, 2005, Liu et al., 2005], and computer

vision [He et al., 2004, Kumar and Hebert, 2003].

This chapter is divided into two parts. First, we present a tutorial on current

training and inference techniques for conditional random ﬁelds. We discuss the

important special case of linear-chain CRFs, and then we generalize these to

arbitrary graphical structures. We include a brief discussion of techniques for

practical CRF implementations.

Second, we present an example of applying a general CRF to a practical relational

learning problem. In particular, we discuss the problem of information extraction,

that is, automatically building a relational database from information contained

in unstructured text. Unlike linear-chain models, general CRFs can capture long

distance dependencies between labels . For example, if the same name is mentioned

more than once in a document, all mentions probably have the s ame lab e l, and it

is useful to extract them all, because each mention may contain diﬀerent comple-

mentary information about the underlying entity. To represent these long-distance

dependencies, we propose a skip-chain CRF, a model that jointly performs seg-

mentation and collective labeling of extracted mentions. On a standard problem

of extracting speaker names from seminar announcements, the skip-chain CRF has

better performance than a linear-chain CRF.

1.2 Graphical Models

1.2.1 Deﬁnitions

We consider probability distributions over sets of random variables V = X ∪ Y ,

where X is a set of input variables that we assume are observed, and Y is a set of

output variables that we wish to predict. Every variable v ∈ V takes outcomes from

a set V, which can be either continuous or discrete, although we discuss only the

discrete case in this chapter. We denote an assignment to X by x, and we denote

an assignment to a set A ⊂ X by x

, and similarly for Y . We use the notation

{x=x

}

to denote an indicator function of x which takes the value 1 when x = x

and 0 otherwise.

A graphical model is a family of probability distributions that factorize according

to an underlying graph. The main idea is to represent a distribution over a large

number of random variables by a product of local functions that each depend on

only a small number of variables. Given a collection of subsets A ⊂ V , we deﬁne

1.2 Graphical Models 3

an undirected graphical model as the set of all distributions that can be written in

the form

p(x, y) =

, y

), (1.1)

for any choice of factors F = {Ψ

}, where Ψ

: V

→ <

. (These functions are

also called local functions or compatibility functions.) We will occasionally use the

term random ﬁeld to refer to a particular distribution among those deﬁned by an

undirected model. To reiterate, we will consistently use the term model to refer to a

family of distributions, and random ﬁeld (or more commonly, distribution) to refer

to a single one.

The constant Z is a normalization factor deﬁned as

Z =

x,y

, y

), (1.2)

which ensures that the distribution sums to 1. The quantity Z, considered as a

function of the set F of factors, is called the partition function in the statistical

physic s and graphical models communities. Computing Z is intractable in general,

but much work exists on how to approximate it.

Graphically, we represent the factorization (1.1) by a factor graph [Kschischang

et al., 2001]. A factor graph is a bipartite graph G = (V, F, E) in which a variable

node v

∈ V is connected to a factor node Ψ

∈ F if v

is an argument to Ψ

. An

example of a factor graph is shown graphically in Figure 1.1 (right). In that ﬁgure,

the circles are variable nodes, and the shaded boxes are factor nodes.

In this chapter, we will assume that each local function has the form

, y

) = exp

(

, y

)

, (1.3)

for some real-valued parameter vector θ

, and for some set of feature functions or

suﬃcient statistics {f

}. This form ensures that the family of distributions over V

parameterized by θ is an exponential family. Much of the discussion in this chapter

actually applies to exponential families in general.

A directed graphical model, also known as a Bayesian network, is based on a directed

graph G = (V, E). A directed model is a family of distributions that factorize as:

p(y, x) =

v ∈V

p(v|π(v)), (1.4)

where π(v) are the parents of v in G. An example of a directed model is shown in

Figure 1.1 (left).

We use the term generative model to refer to a directed graphical model in which

the outputs topologically precede the inputs, that is, no x ∈ X can be a parent of

an output y ∈ Y . Essentially, a generative model is one that directly describes how

the outputs probabilistically “generate” the inputs.

4 An Introduction to Conditional Random Fields for Relational Learning

Figure 1.1 The naive Bayes classiﬁer, as a directed model (left), and as a factor

graph (right).

1.2.2 Applications of graphical models

In this section we discuss a few applications of graphical models to natural language

processing. Although these examples are well-known, they serve both to clarify the

deﬁnitions in the previous section, and to illustrate some ideas that will arise again

in our discussion of conditional random ﬁelds. We devote special attention to the

hidden Markov model (HMM), because it is closely related to the linear-chain CRF.

1.2.2.1 Classiﬁcation

First we discuss the problem of classiﬁcation, that is, predicting a single class

variable y given a vector of features x = (x

, x

, . . . , x

). One simple way to

accomplish this is to assume that once the class label is known, all the features

are independent. The resulting classiﬁer is called the naive Bayes classiﬁer. It is

based on a joint probability model of the form:

p(y, x) = p(y)

k=1

p(x

|y). (1.5)

This model can be described by the directed model shown in Figure 1.1 (left). We

can also write this model as a factor graph, by deﬁning a factor Ψ(y) = p(y), and

a factor Ψ

(y, x

) = p(x

|y) for each feature x

. This factor graph is shown in

Figure 1.1 (right).

Another well-known classiﬁer that is naturally represented as a graphical model is

logistic regression (sometimes known as the maximum entropy classiﬁer in the NLP

community). In statistics, this classiﬁer is motivated by the assumption that the log

probability, log p(y|x), of each class is a linear function of x, plus a normalization

constant. This leads to the conditional distribution:

p(y|x) =

Z(x)

exp







j=1

y ,j







, (1.6)

where Z(x) =

exp{λ

j=1

y , j

} is a normalizing constant, and λ

is a

bias weight that acts like log p(y) in naive Bayes. Rather than using one vector per

class, as in (1.6), we can use a diﬀerent notation in which a single set of weights is

shared across all the classes. The trick is to deﬁne a set of feature functions that are

1.2 Graphical Models 5

nonzero only for a single class. To do this, the feature functions can be deﬁned as

(y, x) = 1

=y }

for the feature weights and f

(y, x) = 1

=y }

for the bias

weights. Now we can use f

to index each feature function f

, and λ

to index

its corresponding weight λ

. Using this notational trick, the logistic regression

model becomes:

p(y|x) =

Z(x)

exp

(

k=1

(y, x)

)

. (1.7)

We introduce this notation because it mirrors the usual notation for conditional

random ﬁelds.

1.2.2.2 Sequence Models

Classiﬁers predict only a single class variable, but the true power of graphical

models lies in their ability to model many variables that are interdependent. In this

section, we discuss perhaps the simplest form of dependency, in which the output

variables are arranged in a sequence. To motivate this kind of model, we discuss an

application from natural language proces sing, the tas k of named-entity recognition

(NER). NER is the problem of identifying and classifying proper names in text,

including locations, such as China; people, such as George Bush; and organizations,

such as the United Nations. The named-entity recognition task is, given a sentence,

ﬁrst to segment which words are part of entities, and then to classify each entity

by type (person, organization, location, and so on). The challenge of this problem

is that many named entities are too rare to appear even in a large training set, and

therefore the system must identify them based only on context.

One approach to NER is to classify each word independently as one of either

Person, Location, Organization, or Other (meaning not an entity). The

problem with this approach is that it assumes that given the input, all of the named-

entity labels are independent. In fact, the named-entity labels of neighboring words

are dependent; for example, while New York is a location, New York Times is an

organization.

This independence assumption can be relaxed by arranging the output variables in

a linear chain. This is the approach take n by the hidden Markov model (HMM)

[Rabiner, 1989]. An HMM models a sequence of observations X = {x

}

t=1

assuming that there is an underlying sequence of states Y = {y

}

t=1

draw n from a

ﬁnite state set S. In the named-entity example, each observation x

is the identity

of the word at position t, and each state y

is the named-entity label, that is, one

of the entity types Person, Location, Organization, and Other.

To model the joint distribution p(y, x) tractably, an HMM makes two independence

assumptions. First, it assumes that each state depends only on its immediate

predecessor, that is, each state y

is independent of all its ancestors y

, y

, . . . , y

t−2

given its previous state y

t−1

. Second, an HMM assumes that each observation

variable x

depends only on the current state y

. With these assumptions, we can

剩余34页未读，继续阅读

评论收藏

内容反馈

无bug不编程

粉丝: 0
资源: 1

条件随机场在关系学习中的应用

crf条件随机场在动作识别方面应用

条件随机场介绍

条件随机场学习

条件随机场学习课件

条件随机场在二维图像中的应用

条件随机场

条件随机场资料

条件随机场的经典论文

python中文分词：基于条件随机场模型的中文分词实现及改进全项目.zip

数学模型条件随机场的原理

机器学习工具——条件随机场模型

基于条件随机场的轻微暂停标记边界识别。 计算机应用学报

Decode-CRF:基于解码学习的条件随机场

OpenSextantCRF:基于 JCarafe 条件随机场代码的机器学习门处理资源

matlab说话代码-marbl:基于边界学习的条件随机场参数

使用条件随机场进行维吾尔语词干分析

HCRF2.0b条件随机场CRF C语言板 处理图像目标检测等

条件随机场1

条件随机场详细讲解

CRF条件随机场

ML_9月机器学习在线班 课程 18.条件随机场.pdf

条件随机场工具包完整版

条件随机场原理

最新资源

基于条件随机场的轻微暂停标记边界识别。计算机应用学报

HCRF2.0b条件随机场CRF C语言板处理图像目标检测等

ML_9月机器学习在线班课程 18.条件随机场.pdf