每日算法 — 使用java实现条件随机场：线性链CRF与参数估计

条件随机场（Conditional Random Field，CRF）是概率图模型中的经典判别式方法，特别适用于序列标注任务，如命名实体识别、词性标注和分词等。与隐马尔可夫模型不同，CRF直接建模条件概率 P(Y|X)，避免了HMM的观测独立假设限制。本文用Java实现线性链CRF，讲解特征函数设计、前向-后向算法以及维特比解码，包含完整可运行的代码。

一、问题建模与数学基础

给定输入序列 X = (x₁, x₂, ..., xₙ) 和标注序列 Y = (y₁, y₂, ..., yₙ)，线性链CRF建模条件概率为：

P(Y|X) = (1/Z(X)) * exp(Σ_k λ_k * f_k(y_{t-1}, y_t, X, t))

其中：
– f_k 为特征函数（分为状态特征和转移特征）
– λ_k 为特征权重（模型参数）
– Z(X) 为归一化因子（配分函数）

特征函数分为两类：
– 转移特征：f(y_{t-1}, y_t, X, t)，依赖于相邻标签和当前位置
– 状态特征：f(y_t, X, t)，仅依赖当前标签和输入

二、特征工程与特征模板

import java.util.*;

/**
 * 特征模板：定义从序列中提取哪些特征
 */
public class FeatureTemplate {
    // 状态特征模板窗口大小
    public int windowSize;

    public FeatureTemplate(int windowSize) {
        this.windowSize = windowSize;
    }

    /**
     * 为位置t提取状态特征（基于输入序列X）
     * @param x 输入序列（如词序列）
     * @param t 当前位置
     * @return 特征名称列表
     */
    public List<String> extractStateFeatures(String[] x, int t) {
        List<String> features = new ArrayList<>();
        int n = x.length;

        // 当前词
        features.add("w0=" + x[t]);

        // 窗口内的词特征
        for (int offset = -windowSize; offset <= windowSize; offset++) {
            int pos = t + offset;
            if (pos >= 0 && pos < n) {
                features.add("w" + offset + "=" + x[pos]);
            } else {
                features.add("w" + offset + "=_BOS_"); // 序列开头
                if (pos >= n) features.set(features.size() - 1, "w" + offset + "=_EOS_");
            }
        }

        // 词的前缀/后缀特征（假设为中文）
        String word = x[t];
        if (word.length() >= 1) {
            features.add("first=" + word.charAt(0));
            features.add("last=" + word.charAt(word.length() - 1));
        }
        if (word.length() >= 2) {
            features.add("prefix2=" + word.substring(0, 2));
            features.add("suffix2=" + word.substring(word.length() - 2));
        }

        return features;
    }
}

三、特征字典与参数管理

/**
 * 特征-参数管理器
 */
public class FeatureManager {
    private final Map<String, Integer> featureToId = new HashMap<>();
    private final List<String> idToFeature = new ArrayList<>();
    private final Map<String, Integer> labelToId = new HashMap<>();
    private final List<String> idToLabel = new ArrayList<>();
    private double[] weights;  // 特征权重

    public int getOrCreateFeatureId(String feature) {
        return featureToId.computeIfAbsent(feature, k -> {
            int id = idToFeature.size();
            idToFeature.add(k);
            return id;
        });
    }

    public int getOrCreateLabelId(String label) {
        return labelToId.computeIfAbsent(label, k -> {
            int id = idToLabel.size();
            idToLabel.add(k);
            return id;
        });
    }

    public int getLabelId(String label) { return labelToId.getOrDefault(label, -1); }
    public String getLabel(int id) { return id < idToLabel.size() ? idToLabel.get(id) : null; }
    public int labelCount() { return idToLabel.size(); }
    public int featureCount() { return idToFeature.size(); }

    public void initWeights() {
        weights = new double[featureCount()];
        // 可设置小的随机初始化
        Random rand = new Random(42);
        for (int i = 0; i < weights.length; i++) {
            weights[i] = rand.nextGaussian() * 0.01;
        }
    }

    public double getWeight(int fid) { return weights[fid]; }
    public void setWeight(int fid, double w) { weights[fid] = w; }
    public void addWeight(int fid, double delta) { weights[fid] += delta; }
    public double[] getWeights() { return weights; }
}

四、前向-后向算法

前向-后向算法是CRF训练的核心，用于高效计算配分函数 Z(X) 和边缘概率。

/**
 * 线性链CRF模型
 */
public class LinearChainCRF {
    private final FeatureManager fm;
    private final FeatureTemplate template;
    private final double l2Reg;  // L2正则化系数

    public LinearChainCRF(FeatureManager fm, FeatureTemplate template, double l2Reg) {
        this.fm = fm;
        this.template = template;
        this.l2Reg = l2Reg;
    }

    /**
     * 计算位置t、标签y的局部特征分数（状态特征+转移特征）
     * @param x 输入序列
     * @param t 位置
     * @param yCurrent 当前标签ID
     * @param yPrev 前一标签ID（-1表示无）
     */
    public double score(String[] x, int t, int yCurrent, int yPrev) {
        double s = 0;

        // 状态特征分数
        List<String> stateFeats = template.extractStateFeatures(x, t);
        String labelStr = fm.getLabel(yCurrent);
        for (String feat : stateFeats) {
            String key = feat + "@" + labelStr;
            int fid = fm.getOrCreateFeatureId(key);
            s += fm.getWeight(fid);
        }

        // 转移特征分数
        if (yPrev >= 0) {
            String prevLabel = fm.getLabel(yPrev);
            String transKey = prevLabel + "->" + labelStr;
            int transFid = fm.getOrCreateFeatureId(transKey);
            s += fm.getWeight(transFid);
        }

        return s;
    }

    /**
     * 前向算法：计算alpha（对数域避免溢出）
     * @return alpha[t][y] = 到位置t、标签y的累计对数概率（未归一化）
     */
    public double[][] forward(String[] x) {
        int n = x.length;
        int L = fm.labelCount();
        double[][] alpha = new double[n][L];

        // 初始化t=0
        for (int y = 0; y < L; y++) {
            alpha[0][y] = score(x, 0, y, -1);
        }

        // 递推
        for (int t = 1; t < n; t++) {
            for (int y = 0; y < L; y++) {
                double maxVal = Double.NEGATIVE_INFINITY;
                for (int yp = 0; yp < L; yp++) {
                    double val = alpha[t - 1][yp] + score(x, t, y, yp);
                    if (val > maxVal) maxVal = val;
                }
                // 数值稳定：log-sum-exp技巧
                double sum = 0;
                for (int yp = 0; yp < L; yp++) {
                    sum += Math.exp(alpha[t - 1][yp] + score(x, t, y, yp) - maxVal);
                }
                alpha[t][y] = maxVal + Math.log(sum);
            }
        }

        return alpha;
    }

    /**
     * 后向算法
     */
    public double[][] backward(String[] x) {
        int n = x.length;
        int L = fm.labelCount();
        double[][] beta = new double[n][L];

        // 初始化t=n-1
        for (int y = 0; y < L; y++) {
            beta[n - 1][y] = 0; // log(1) = 0
        }

        for (int t = n - 2; t >= 0; t--) {
            for (int y = 0; y < L; y++) {
                double maxVal = Double.NEGATIVE_INFINITY;
                for (int yn = 0; yn < L; yn++) {
                    double val = beta[t + 1][yn] + score(x, t + 1, yn, y);
                    if (val > maxVal) maxVal = val;
                }
                double sum = 0;
                for (int yn = 0; yn < L; yn++) {
                    sum += Math.exp(beta[t + 1][yn] + score(x, t + 1, yn, y) - maxVal);
                }
                beta[t][y] = maxVal + Math.log(sum);
            }
        }

        return beta;
    }

    /**
     * 计算配分函数 Z(X)
     */
    public double logZ(String[] x) {
        double[][] alpha = forward(x);
        int n = x.length;
        double maxVal = Double.NEGATIVE_INFINITY;
        for (int y = 0; y < fm.labelCount(); y++) {
            if (alpha[n - 1][y] > maxVal) maxVal = alpha[n - 1][y];
        }
        double sum = 0;
        for (int y = 0; y < fm.labelCount(); y++) {
            sum += Math.exp(alpha[n - 1][y] - maxVal);
        }
        return maxVal + Math.log(sum);
    }

    /**
     * 计算边缘概率 P(y_t = y | X)
     */
    public double[][] marginalProb(String[] x) {
        double[][] alpha = forward(x);
        double[][] beta = backward(x);
        double logz = logZ(x);
        int n = x.length;
        int L = fm.labelCount();
        double[][] prob = new double[n][L];

        for (int t = 0; t < n; t++) {
            for (int y = 0; y < L; y++) {
                prob[t][y] = Math.exp(alpha[t][y] + beta[t][y] - logz);
            }
        }
        return prob;
    }
}

五、维特比解码算法

维特比算法用于预测时寻找概率最大的标注序列，是动态规划在序列问题中的经典应用。

/**
 * 维特比解码：寻找最优标签序列
 */
public class ViterbiDecoder {

    /**
     * @param crf 模型
     * @param x 输入序列
     * @return 最优标签ID序列
     */
    public static int[] decode(LinearChainCRF crf, String[] x, FeatureManager fm) {
        int n = x.length;
        int L = fm.labelCount();

        // dp[t][y] = 到位置t、标签y的最大分数
        double[][] dp = new double[n][L];
        int[][] path = new int[n][L]; // 记录前驱标签

        // 初始化
        for (int y = 0; y < L; y++) {
            dp[0][y] = crf.score(x, 0, y, -1);
            path[0][y] = -1;
        }

        // 递推
        for (int t = 1; t < n; t++) {
            for (int y = 0; y < L; y++) {
                double maxScore = Double.NEGATIVE_INFINITY;
                int bestPrev = -1;
                for (int yp = 0; yp < L; yp++) {
                    double s = dp[t - 1][yp] + crf.score(x, t, y, yp);
                    if (s > maxScore) {
                        maxScore = s;
                        bestPrev = yp;
                    }
                }
                dp[t][y] = maxScore;
                path[t][y] = bestPrev;
            }
        }

        // 回溯
        int[] bestPath = new int[n];
        double bestFinal = Double.NEGATIVE_INFINITY;
        for (int y = 0; y < L; y++) {
            if (dp[n - 1][y] > bestFinal) {
                bestFinal = dp[n - 1][y];
                bestPath[n - 1] = y;
            }
        }
        for (int t = n - 2; t >= 0; t--) {
            bestPath[t] = path[t + 1][bestPath[t + 1]];
        }

        return bestPath;
    }
}

六、参数估计：SGD训练

/**
 * CRF训练器（SGD + L2正则）
 */
public class CRFTrainer {

    /**
     * 单样本梯度计算与参数更新
     */
    public static void trainStep(LinearChainCRF crf, FeatureManager fm,
                                  String[] x, int[] yTrue,
                                  double lr, double l2Reg) {
        int n = x.length;
        int L = fm.labelCount();

        // 前向-后向
        double[][] alpha = crf.forward(x);
        double[][] beta = crf.backward(x);
        double logz = crf.logZ(x);

        // 计算转移边缘概率 P(y_{t-1}, y_t | X)
        double[][][] transProb = new double[n][L][L];
        for (int t = 1; t < n; t++) {
            for (int yp = 0; yp < L; yp++) {
                for (int y = 0; y < L; y++) {
                    transProb[t][yp][y] = Math.exp(
                        alpha[t - 1][yp] + crf.score(x, t, y, yp) + beta[t][y] - logz
                    );
                }
            }
        }

        // 计算状态边缘概率
        double[][] stateProb = new double[n][L];
        for (int t = 0; t < n; t++) {
            for (int y = 0; y < L; y++) {
                stateProb[t][y] = Math.exp(alpha[t][y] + beta[t][y] - logz);
            }
        }

        // 计算特征期望并更新权重
        // 真实路径的特征计数
        Map<Integer, Integer> trueFeatureCount = new HashMap<>();
        for (int t = 0; t < n; t++) {
            List<String> feats = crf.template.extractStateFeatures(x, t);
            String label = fm.getLabel(yTrue[t]);
            for (String f : feats) {
                int fid = fm.getOrCreateFeatureId(f + "@" + label);
                trueFeatureCount.merge(fid, 1, Integer::sum);
            }
            if (t > 0) {
                String trans = fm.getLabel(yTrue[t - 1]) + "->" + label;
                int fid = fm.getOrCreateFeatureId(trans);
                trueFeatureCount.merge(fid, 1, Integer::sum);
            }
        }

        // 模型期望 - 真实计数 = 负梯度
        // 状态特征期望
        for (int t = 0; t < n; t++) {
            List<String> feats = crf.template.extractStateFeatures(x, t);
            for (int y = 0; y < L; y++) {
                String label = fm.getLabel(y);
                for (String f : feats) {
                    int fid = fm.getOrCreateFeatureId(f + "@" + label);
                    double modelExpect = stateProb[t][y];
                    double trueCount = trueFeatureCount.getOrDefault(fid, 0);
                    // 只更新真实路径出现过的特征（简化）
                    if (trueFeatureCount.containsKey(fid)) {
                        double grad = modelExpect - trueCount;
                        fm.addWeight(fid, -lr * (grad + l2Reg * fm.getWeight(fid)));
                    }
                }
            }
        }

        // 转移特征期望
        for (int t = 1; t < n; t++) {
            for (int yp = 0; yp < L; yp++) {
                for (int y = 0; y < L; y++) {
                    String trans = fm.getLabel(yp) + "->" + fm.getLabel(y);
                    int fid = fm.getOrCreateFeatureId(trans);
                    if (trueFeatureCount.containsKey(fid)) {
                        double grad = transProb[t][yp][y] - trueFeatureCount.getOrDefault(fid, 0);
                        fm.addWeight(fid, -lr * (grad + l2Reg * fm.getWeight(fid)));
                    }
                }
            }
        }
    }
}

七、完整演示：中文分词

public class CRFDemo {
    public static void main(String[] args) {
        // 简化版中文分词：BIES标注
        // B=词首, I=词中, E=词尾, S=单字词
        String[][] trainX = {
            "今天 天气 真好".split(" "),
            "我 喜欢 编程".split(" "),
            "自然 语言 处理 很 有趣".split(" "),
            "机器 学习 是 热门 领域".split(" "),
            "深度 学习 改变 世界".split(" "),
        };
        String[][] trainY = {
            "B E B E B E".split(" "),
            "S B E B E".split(" "),
            "B E B E B E S B E".split(" "),
            "B E B E S B E B E".split(" "),
            "B E B E B E B E".split(" "),
        };

        FeatureManager fm = new FeatureManager();
        FeatureTemplate template = new FeatureTemplate(1);

        // 注册所有标签
        for (String[] labels : trainY) {
            for (String l : labels) fm.getOrCreateLabelId(l);
        }
        fm.initWeights();

        LinearChainCRF crf = new LinearChainCRF(fm, template, 0.01);

        // 训练
        System.out.println("Training CRF...");
        int epochs = 100;
        for (int epoch = 0; epoch < epochs; epoch++) {
            double totalLoss = 0;
            for (int i = 0; i < trainX.length; i++) {
                int[] yIds = new int[trainY[i].length];
                for (int j = 0; j < trainY[i].length; j++) {
                    yIds[j] = fm.getLabelId(trainY[i][j]);
                }
                CRFTrainer.trainStep(crf, fm, trainX[i], yIds, 0.01, 0.01);

                // 计算对数似然损失
                double logz = crf.logZ(trainX[i]);
                double trueScore = 0;
                for (int t = 0; t < trainX[i].length; t++) {
                    int yp = (t > 0) ? yIds[t - 1] : -1;
                    trueScore += crf.score(trainX[i], t, yIds[t], yp);
                }
                totalLoss += logz - trueScore;
            }
            if (epoch % 20 == 0) {
                System.out.printf("Epoch %d: loss=%.4f\n", epoch, totalLoss);
            }
        }

        // 测试解码
        System.out.println("\nTesting Viterbi decoding...");
        String[] testX = "深度 学习 非常 强大".split(" ");
        int[] predIds = ViterbiDecoder.decode(crf, testX, fm);
        System.out.print("Predicted: ");
        for (int id : predIds) {
            System.out.print(fm.getLabel(id) + " ");
        }
        System.out.println();

        // 另一测试
        String[] testX2 = "自然 语言".split(" ");
        int[] predIds2 = ViterbiDecoder.decode(crf, testX2, fm);
        System.out.print("Predicted: ");
        for (int id : predIds2) {
            System.out.print(fm.getLabel(id) + " ");
        }
        System.out.println();

        // 展示前向-后向的概率分布
        System.out.println("\nMarginal probabilities for testX2:");
        double[][] marg = crf.marginalProb(testX2);
        for (int t = 0; t < testX2.length; t++) {
            System.out.printf("  %s: ", testX2[t]);
            for (int y = 0; y < fm.labelCount(); y++) {
                System.out.printf("%s=%.3f ", fm.getLabel(y), marg[t][y]);
            }
            System.out.println();
        }
    }
}

八、CRF与HMM对比

九、复杂度分析

其中 T 为序列长度，L 为标签数，F 为特征数。

十、总结

本文完整实现了线性链条件随机场的核心算法：

• 特征模板设计：定义状态特征（基于输入窗口）和转移特征（基于相邻标签），灵活表达序列上下文
• 前向-后向算法：对数域动态规划高效计算配分函数与边缘概率，避免数值下溢
• 维特比解码：基于动态规划寻找全局最优标注序列，时间复杂度 O(T·L²)
• SGD参数估计：通过对比模型期望与真实路径特征计数进行梯度下降训练

CRF作为序列标注的标准基线模型，其全局归一化和灵活特征设计使其在实际NLP任务中表现稳定可靠。