linear_chain_crf_op.cc 11.9 KB
Newer Older
C
caoying03 已提交
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
/* Copyright (c) 2016 PaddlePaddle Authors. All Rights Reserve.

Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at

    http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License. */

#include "paddle/operators/linear_chain_crf_op.h"

namespace paddle {
namespace operators {

C
caoying03 已提交
20
class LinearChainCRFOpMaker : public framework::OpProtoAndCheckerMaker {
C
caoying03 已提交
21
 public:
C
caoying03 已提交
22
  LinearChainCRFOpMaker(framework::OpProto* proto,
C
caoying03 已提交
23 24
                        framework::OpAttrChecker* op_checker)
      : OpProtoAndCheckerMaker(proto, op_checker) {
C
Cao Ying 已提交
25
    AddInput("Emission",
K
kexinzhao 已提交
26 27
             "(LoDTensor, default LoDTensor<float>) "
             "A 2-D LoDTensor with shape [N x D], where N is the size of the "
C
Cao Ying 已提交
28 29 30
             "mini-batch and D is the total tag number. The unscaled emission "
             "weight matrix for the linear chain CRF. ");
    AddInput("Transition",
K
kexinzhao 已提交
31
             "(Tensor, default Tensor<float>) A 2-D Tensor with shape "
C
Cao Ying 已提交
32 33 34
             "[(D + 2) x D]. The learnable parameter for the linear_chain_crf "
             "operator. See more details in the operator's comments.");
    AddInput("Label",
K
kexinzhao 已提交
35
             "(LoDTensor, default LoDTensor<int>) A LoDTensor with shape "
C
Cao Ying 已提交
36 37
             "[N x 1], where N is the total element number in a mini-batch. "
             "The ground truth.");
C
caoying03 已提交
38 39
    AddOutput(
        "Alpha",
K
kexinzhao 已提交
40
        "(Tensor, default Tensor<float>) A 2-D Tensor with shape [N x D]. "
C
Cao Ying 已提交
41 42 43 44 45
        "The forward vectors for the entire batch. Denote it as \f$\alpha\f$. "
        "\f$\alpha$\f is a memo table used to calculate the normalization "
        "factor in CRF. \f$\alpha[k, v]$\f stores the unnormalized "
        "probabilites of all possible unfinished sequences of tags that end at "
        "position \f$k$\f with tag \f$v$\f. For each \f$k$\f, "
C
caoying03 已提交
46 47 48 49
        "\f$\alpha[k, v]$\f is a vector of length \f$D$\f with a component for "
        "each tag value \f$v$\f. This vector is called a forward vecotr and "
        "will also be used in backward computations.")
        .AsIntermediate();
C
Cao Ying 已提交
50 51
    AddOutput(
        "EmissionExps",
K
kexinzhao 已提交
52
        "(Tensor, default Tensor<float>) A 2-D Tensor with shape [N x D]. "
C
Cao Ying 已提交
53 54 55
        "The exponentials of Input(Emission). This is an intermediate "
        "computational result in forward computation, and will be reused in "
        "backward computation.")
C
caoying03 已提交
56
        .AsIntermediate();
C
Cao Ying 已提交
57 58
    AddOutput(
        "TransitionExps",
K
kexinzhao 已提交
59
        "(Tensor, default Tensor<float>) A 2-D Tensor with shape "
C
Cao Ying 已提交
60 61 62
        "[(D + 2) x D]. The exponentials of Input(Transition). This is an "
        "intermediate computational result in forward computation, and "
        "will be reused in backward computation.")
C
caoying03 已提交
63
        .AsIntermediate();
C
caoying03 已提交
64 65
    AddOutput(
        "LogLikelihood",
K
kexinzhao 已提交
66
        "(Tensor, default Tensor<float>) The logarithm of the conditional "
C
caoying03 已提交
67 68
        "likelihood of each training sample in a mini-batch. This is a 2-D "
        "tensor with shape [S x 1], where S is the sequence number in a "
C
caoying03 已提交
69 70
        "mini-batch. Note: S is equal to the sequence number in a mini-batch. "
        "The output is no longer a LoDTensor.");
C
caoying03 已提交
71
    AddComment(R"DOC(
K
kexinzhao 已提交
72 73
LinearChainCRF Operator.

C
caoying03 已提交
74 75 76 77 78 79 80 81
Conditional Random Field defines an undirected probabilistic graph with nodes
denoting random variables and edges denoting dependencies between these
variables. CRF learns the conditional probability \f$P(Y|X)\f$, where
\f$X = (x_1, x_2, ... , x_n)\f$ are structured inputs and
\f$Y = (y_1, y_2, ... , y_n)\f$ are labels for the inputs.

Linear chain CRF is a special case of CRF that is useful for sequence labeling
task. Sequence labeling tasks do not assume a lot of conditional
C
caoying03 已提交
82 83 84
independences among inputs. The only constraint they impose is that the input
and output must be linear sequences. Thus, the graph of such a CRF is a simple
chain or a line, which results in the linear chain CRF.
C
caoying03 已提交
85

C
caoying03 已提交
86
This operator implements the Forward-Backward algorithm for the linear chain
K
kexinzhao 已提交
87 88
CRF. Please refer to http://www.cs.columbia.edu/~mcollins/fb.pdf and
http://cseweb.ucsd.edu/~elkan/250Bwinter2012/loglinearCRFs.pdf for details.
C
caoying03 已提交
89 90

Equation:
K
kexinzhao 已提交
91 92
1. Denote Input(Emission) to this operator as \f$x\f$ here.
2. The first D values of Input(Transition) to this operator are for starting
93
weights, denoted as \f$a\f$ here.
K
kexinzhao 已提交
94
3. The next D values of Input(Transition) of this operator are for ending
95
weights, denoted as \f$b\f$ here.
K
kexinzhao 已提交
96
4. The remaning values of Input(Transition) are for transition weights,
97
denoted as \f$w\f$ here.
K
kexinzhao 已提交
98
5. Denote Input(Label) as \f$s\f$ here.
C
caoying03 已提交
99 100

The probability of a sequence \f$s\f$ of length \f$L\f$ is defined as:
K
kexinzhao 已提交
101
\f$P(s) = (1/Z) \exp(a_{s_1} + b_{s_L}
C
caoying03 已提交
102 103 104 105 106 107
                 + \sum_{l=1}^L x_{s_l}
                 + \sum_{l=2}^L w_{s_{l-1},s_l})\f$
where \f$Z\f$ is a normalization value so that the sum of \f$P(s)\f$ over
all possible sequences is \f$1\f$, and \f$x\f$ is the emission feature weight
to the linear chain CRF.

K
kexinzhao 已提交
108
Finally, the linear chain CRF operator outputs the logarithm of the conditional
C
caoying03 已提交
109 110 111 112 113 114 115
likelihood of each training sample in a mini-batch.

NOTE:
1. The feature function for a CRF is made up of the emission features and the
transition features. The emission feature weights are NOT computed in
this operator. They MUST be computed first before this operator is called.

C
caoying03 已提交
116
2. Because this operator performs global normalization over all possible
C
caoying03 已提交
117 118 119 120
sequences internally, it expects UNSCALED emission feature weights.
Please do not call this op with the emission feature being output of any
nonlinear activation.

121
3. The 2nd dimension of Input(Emission) MUST be equal to the tag number.
C
caoying03 已提交
122 123 124 125 126

)DOC");
  }
};

C
caoying03 已提交
127
class LinearChainCRFOp : public framework::OperatorWithKernel {
C
caoying03 已提交
128 129 130
 public:
  using framework::OperatorWithKernel::OperatorWithKernel;

C
caoying03 已提交
131 132 133 134 135 136 137 138 139
  void InferShape(framework::InferShapeContext* ctx) const override {
    PADDLE_ENFORCE(ctx->HasInput("Emission"),
                   "Input(Emission) should be not null.");
    PADDLE_ENFORCE(ctx->HasInput("Transition"),
                   "Input(Transition) should be not null.");
    PADDLE_ENFORCE(ctx->HasInput("Label"), "Input(Label) should be not null.");

    PADDLE_ENFORCE(ctx->HasOutput("Alpha"),
                   "Output(Alpha) should be not null.");
C
caoying03 已提交
140 141 142 143
    PADDLE_ENFORCE(ctx->HasOutput("EmissionExps"),
                   "Output(EmissionExps) should be not null.");
    PADDLE_ENFORCE(ctx->HasOutput("TransitionExps"),
                   "Output(TransitionExps) should be not null.");
C
caoying03 已提交
144 145 146 147 148
    PADDLE_ENFORCE(ctx->HasOutput("LogLikelihood"),
                   "Output(LogLikelihood) should be not null.");

    auto emission_dims = ctx->GetInputDim("Emission");
    PADDLE_ENFORCE_EQ(emission_dims.size(), 2UL,
149
                      "The Input(Emission) should be a 2-D tensor.");
C
caoying03 已提交
150 151 152
    PADDLE_ENFORCE(emission_dims[0], "An empty mini-batch is not allowed.");

    auto transition_dims = ctx->GetInputDim("Transition");
C
caoying03 已提交
153
    PADDLE_ENFORCE_EQ(transition_dims.size(), 2UL,
154
                      "The Input(Transition) should be a 2-D tensor.");
C
caoying03 已提交
155
    PADDLE_ENFORCE_EQ(
156 157
        transition_dims[0] - 2, transition_dims[1],
        "An invalid dimension for the Input(Transition), which should "
C
caoying03 已提交
158
        "be a 2-D tensor with shape [(D + 2) x D].");
C
caoying03 已提交
159 160
    PADDLE_ENFORCE_EQ(
        emission_dims[1], transition_dims[1],
161
        "The 2nd dimension of the Input(Emission) and the Input(Transition) "
C
caoying03 已提交
162
        "should be equal to the tag number.");
C
caoying03 已提交
163 164

    auto label_dims = ctx->GetInputDim("Label");
C
caoying03 已提交
165
    PADDLE_ENFORCE(label_dims.size() == 2UL && label_dims[1] == 1UL,
166 167 168 169 170 171
                   "The Input(Label) should be a 2-D tensor with the 2nd "
                   "dimensions fixed to 1.");
    PADDLE_ENFORCE_EQ(
        emission_dims[0], label_dims[0],
        "The height of Input(Emission) and the height of Input(Label) "
        "should be the same.");
C
caoying03 已提交
172 173

    ctx->SetOutputDim("Alpha", emission_dims);
C
caoying03 已提交
174 175
    ctx->SetOutputDim("EmissionExps", emission_dims);
    ctx->SetOutputDim("TransitionExps", transition_dims);
C
caoying03 已提交
176
    // TODO(caoying) This is tricky. The 1st dimension of Output(LogLikelihood)
177
    // is the sequence number in a mini-batch. The dimension set here should be
C
caoying03 已提交
178 179
    // resized to its correct size in the function Compute. Fix this once we can
    // get LoD information in the InferShape interface.
C
caoying03 已提交
180 181 182
    ctx->SetOutputDim("LogLikelihood", {emission_dims[0], 1});
  }

C
caoying03 已提交
183
 protected:
C
Cao Ying 已提交
184 185
  // Explicitly set that the data type of computation kernel of linear_chain_crf
  // is determined by its input "Emission".
C
caoying03 已提交
186 187
  framework::DataType IndicateDataType(
      const framework::ExecutionContext& ctx) const override {
C
caoying03 已提交
188
    return framework::ToDataType(ctx.Input<LoDTensor>("Emission")->type());
C
caoying03 已提交
189
  }
C
caoying03 已提交
190 191
};

C
caoying03 已提交
192
class LinearChainCRFGradOp : public framework::OperatorWithKernel {
C
caoying03 已提交
193 194 195
 public:
  using framework::OperatorWithKernel::OperatorWithKernel;

C
caoying03 已提交
196 197 198 199 200 201 202 203 204 205 206
  void InferShape(framework::InferShapeContext* ctx) const override {
    PADDLE_ENFORCE(ctx->HasInput("EmissionExps"),
                   "Input(EmissionExps) should be not null.");
    PADDLE_ENFORCE(ctx->HasInput("TransitionExps"),
                   "Input(TransitionExps) should be not null.");
    PADDLE_ENFORCE(ctx->HasInput(framework::GradVarName("LogLikelihood")),
                   "Input(LogLikelihood@GRAD) shoudl be not null.");

    auto emission_exps_dims = ctx->GetInputDim("EmissionExps");
    PADDLE_ENFORCE_EQ(emission_exps_dims.size(), 2UL,
                      "The Input(EmissionExps) should be a 2-D tensor.");
C
caoying03 已提交
207 208 209
    PADDLE_ENFORCE(emission_exps_dims[0],
                   "An empty mini-batch is not allowed.");

210
    auto transition_exps_dims = ctx->GetInputDim("TransitionExps");
C
caoying03 已提交
211 212 213 214 215 216 217 218 219 220
    PADDLE_ENFORCE_EQ(transition_exps_dims.size(), 2UL,
                      "The Input(TransitionExps) should be a 2-D tensor.");
    PADDLE_ENFORCE_EQ(
        transition_exps_dims[0] - 2, transition_exps_dims[1],
        "An invalid dimension for the Input(TransitionExps), which should "
        "be a 2-D tensor with shape [(D + 2) x D].");
    PADDLE_ENFORCE_EQ(
        emission_exps_dims[1], transition_exps_dims[1],
        "The 2nd dimension of the Input(EmissionExps) and the "
        "Input(TransitionExps) should be equal to the tag number.");
C
caoying03 已提交
221 222

    auto label_dims = ctx->GetInputDim("Label");
C
caoying03 已提交
223 224 225 226 227 228 229 230
    PADDLE_ENFORCE(label_dims.size() == 2UL && label_dims[1] == 1UL,
                   "The Input(Label) should be a 2-D tensor with the 2nd "
                   "dimensions fixed to 1.");
    PADDLE_ENFORCE_EQ(
        emission_exps_dims[0], label_dims[0],
        "The height of Input(EmissionExps) and the height of Input(Label) "
        "should be the same.");

C
caoying03 已提交
231 232 233 234 235 236 237
    if (ctx->HasOutput(framework::GradVarName("Emission"))) {
      ctx->SetOutputDim(framework::GradVarName("Emission"), emission_exps_dims);
    }
    if (ctx->HasOutput(framework::GradVarName("Transition"))) {
      ctx->SetOutputDim(framework::GradVarName("Transition"),
                        transition_exps_dims);
    }
C
caoying03 已提交
238
  }
C
caoying03 已提交
239 240 241

 protected:
  // Explicitly set that the data type of output of the linear_chain_crf_grad
C
caoying03 已提交
242
  // operator is determined by its input: gradients of LogLikelihood.
C
caoying03 已提交
243 244
  framework::DataType IndicateDataType(
      const framework::ExecutionContext& ctx) const override {
245 246
    return framework::ToDataType(
        ctx.Input<LoDTensor>(framework::GradVarName("LogLikelihood"))->type());
C
caoying03 已提交
247
  }
C
caoying03 已提交
248 249 250 251 252 253
};

}  // namespace operators
}  // namespace paddle

namespace ops = paddle::operators;
C
caoying03 已提交
254 255
REGISTER_OP(linear_chain_crf, ops::LinearChainCRFOp, ops::LinearChainCRFOpMaker,
            linear_chain_crf_grad, ops::LinearChainCRFGradOp);
256 257
REGISTER_OP_CPU_KERNEL(
    linear_chain_crf,
C
caoying03 已提交
258 259
    ops::LinearChainCRFOpKernel<paddle::platform::CPUPlace, float>,
    ops::LinearChainCRFOpKernel<paddle::platform::CPUPlace, double>);
260 261
REGISTER_OP_CPU_KERNEL(
    linear_chain_crf_grad,
C
caoying03 已提交
262 263
    ops::LinearChainCRFGradOpKernel<paddle::platform::CPUPlace, float>,
    ops::LinearChainCRFGradOpKernel<paddle::platform::CPUPlace, double>);