% function [nll, grad] = InstanceNegLogLikelihood(X, y, theta, modelParams)

% returns the negative log-likelihood and its gradient, given a CRF with parameters theta,

% on data (X, y).

%

% Inputs:

% X            Data.                           (numCharacters x numImageFeatures matrix)

%              X(:,) is all ones, i.e., it encodes the intercept/bias term.

% y            Data labels.                    (numCharacters x  vector)

% theta        CRF weights/parameters.         (numParams x  vector)

%              These are shared among the various singleton / pairwise features.

% modelParams  Struct with three fields:

%   .numHiddenStates     in our case, set to  ( possible characters)

%   .numObservedStates   in our case, set to   (each pixel is either on or off)

%   .lambda              the regularization parameter lambda

%

% Outputs:

% nll          Negative log-likelihood of the data.    (scalar)

% grad         Gradient of nll with respect to theta   (numParams x  vector)

%

% Copyright (C) Daphne Koller, Stanford Univerity, 

function [nll, grad] = InstanceNegLogLikelihood(X, y, theta, modelParams)

    % featureSet is a struct with two fields:

    %    .numParams - the number of parameters in the CRF (this is not numImageFeatures

    %                 nor numFeatures, because of parameter sharing)

    %    .features  - an array comprising the features in the CRF.

    %

    % Each feature is a binary indicator variable, represented by a struct

    % with three fields:

    %    .var          - a vector containing the variables in the scope of this feature

    %    .assignment   - the assignment that this indicator variable corresponds to

    %    .paramIdx     - the index in theta that this feature corresponds to

    %

    % For example, if we have:

    %

    %   feature = struct('var', [ ], 'assignment', [ ], 'paramIdx', );

    %

    % then feature is an indicator function over X_2 and X_3, which takes on a value of

    % if X_2 =  and X_3 =  (which would be 'e' and 'f'), and  otherwise.

    % Its contribution to the log-likelihood would be theta() if it's 1, and 0 otherwise.

    %

    % If you're interested in the implementation details of CRFs,

    % feel free to read through GenerateAllFeatures.m and the functions it calls!

    % For the purposes of this assignment, though, you don't

    % have to understand how this code works. (It's complicated.)

    featureSet = GenerateAllFeatures(X, modelParams); %因为拟合的是条件概率，所以需要使用X

    % Use the featureSet to calculate nll and grad.

    % This is the main part of the assignment, and it is very tricky - be careful!

    % You might want to code up your own numerical gradient checker to make sure

    % your answers are correct.

    %

    % Hint: you can use CliqueTreeCalibrate to calculate logZ effectively.

    %       We have halfway-modified CliqueTreeCalibrate; complete our implementation

    %       if you want to use it to compute logZ.

    nll = ;

    grad = zeros(size(theta));

    %%%

    % Your code here:

    % 计算cost

    ctree = CliqueTreeFromFeatrue(featureSet.features, theta, modelParams); %对整个展开的CRF对应的graph而言

    [ctree,logZ] = CliqueTreeCalibrate(ctree, ); %对tree进行校正，并求出划分函数的对数

    [featureCnt,weightCnt] = WeightFeatureCnt(y, featureSet.features, theta);

    weightedFeatureCnt = sum(weightCnt);

    regCost = (modelParams.lambda/)*(theta * theta');

    nll = logZ-weightedFeatureCnt+regCost;

    % 计算grad

    mFeatureCnt = ModelFeatureCount (ctree, featureSet.features, theta);%求模型期望时，不能使用y信息

    regGrad = modelParams.lambda* theta;

    grad = mFeatureCnt-featureCnt+regGrad;

end

%% 该函数实现的功能是对每个特征都建立一个factor

function ctree = CliqueTreeFromFeatrue(features, theta, modelParams)

    n = length(features);

    factors = repmat(EmptyFactorStruct(),n,);

    for i=:n

        factors(i).var = features(i).var;

        factors(i).card = ones(,length(features(i).var))*modelParams.numHiddenStates; %难道都是y变量？

        factors(i).val = ones(, prod(factors(i).card));

        % 给该factor赋特征值

        factors(i) = SetValueOfAssignment(factors(i), features(i).assignment, exp(theta(features(i).paramIdx)));

    end

    ctree = CreateCliqueTree(factors);

end

%% 该函数是求输入样本是否满足各个特征，如果满足特征i，则counts(i)=,且weighted(i)填入相应的权值。

function [counts, weighted] = WeightFeatureCnt(y, features, theta) %这里要使用y值，因为要用y来计算指示特征

    %注意特征向量的长度和参数向量的长度并不相同,因为多个特征可以共用一个参数，所以一般参数向量要短些

    counts = zeros(,length(theta));

    weighted = zeros(length(theta), );

    for i = :length(features)

        feature = features(i);

        if all(y(feature.var)==feature.assignment) %判断所给的y是否满足特征所描述的

            counts(feature.paramIdx) = ;

            weighted(i) = theta(feature.paramIdx);

        end

    end

end

%% 该函数是计算模型的特征期望值，利用模型对应校正好的clique tree来计算，每个特征由其对应的clique中归一化的val构成

function mFeatureCnt = ModelFeatureCount (ctree, features, theta)

    mFeatureCnt = zeros(,length(theta)); %提前开辟空间有利于matlab运算速度

    for i = :length(features)

        mIdx = features(i).paramIdx;

        cliqueIdx = ;

        for j = :length(ctree.cliqueList)

            if all(ismember(features(i).var,ctree.cliqueList(j).var))

                cliqueIdx = j; %在clique tree上找到包含第i个特征所有元素的clique

                break;

            end

        end

        eval = setdiff(ctree.cliqueList(cliqueIdx).var, features(i).var);

        featureFactor = FactorMarginalization(ctree.cliqueList(cliqueIdx),eval); %得到只包含该特征变量的factor

        idx = AssignmentToIndex(features(i).assignment,featureFactor.card);

        mFeatureCnt(mIdx) = mFeatureCnt(mIdx) + featureFactor.val(idx) / sum(featureFactor.val);%归一化

    end

end