结构学习
英语学习：
recurrence：循环
exhausitively：详尽的
orderings：排序
brute force：强力，蛮力
enumerate：枚举
cache：隐藏物
caching：缓存
metric：度量标准
argument：参数
refinement：求精
acyclicity：无环
empirical：经验主义的
crude convergence diagnostic：原油收敛性诊断
sever：割断
incoming：进来的
intervention：干预
induce：诱导
latent：潜伏的
inductive causation：归纳原因
fan：风扇，扇形物
cheat：作弊
orgasm：高潮
coital：性交
masturbatory：手淫
merit：优点
otherwise：另外，别的方式，否则
presumably：大概是
结构学习分类.png
结构学习有基于限制思维的，以及基于搜寻得分的，前者基于一个全连接图，然后通过寻找数据间的条件独立关系逐条剔除，后者基于在几个模型中选择最优模型，后者的应用更为广泛，这里我们只讨论后者。以下是图的数量与节点数量的关系。
超级指数.png
有于数量是超级指数级的，我们不会详尽的考虑每一个算法，可以使用局部的贪婪搜索算法或者全局的马尔科夫链蒙特卡罗算法。
如果我们已知节点的顺序，可以虑运用K2算法，它的基本思想是独立的找到每一个节点的最佳父节点。
果我们不知道节点顺序，我们可以找出节点顺序，这比找到图模型要简单的多了。
下面讲讲评价函数，贝叶斯信息标准（BIC）的定义如下：
logP(D|theta_hat)-0.5dlog(N)
其中，D代表样本数据，theta_hat代表预测的参数估计，d是参数的数量，N样本案例的数量。BIC的优势在于不需要知道先验分布。实践中样本数据不需要很大就能得到好的效果 。
1、马尔可夫等价性
马尔可夫等价性：如果两个图模型包含相同的条件独立性关系，我们称它们之间具有马尔可夫等价性。
在进行结构学习的时候，划分马尔可夫等价类是非常重要的，马尔可夫等价类就是一系列具有马尔可夫等价性的图模型。
2、详尽搜索
详尽搜索就是例举每一个图模型，并对它们进行评价，它是评价其它结构学习算法的黄金准则。
程序：
dags=mk_all_dags(N);
score=score_dags(data,ns,dags);
代码解释：
第一行的N代表训练集的个数，dags代表得到的所有图模型的集合；第二行data{i,m}代表案例m的第i个节点特征，ns代表节点的大小。得到的是每个模型的得分。
代码：
params=cell(1,N);
for i=1:N
params{i}={'prior','unif'};
end
score=score_dags(data,ns,dags,'params',params);
代码解释：
为了构造先验均匀分布模型
贝叶斯评分度量适用于离散数据，对于混合数据，要用BIC评价标准
代码：
score=score_dags(data,ns,dags,'discrete',[3 4],'params',[],'type',{'gaussian','gaussian','softmax','softmax'},'scoring_fn','bic');
代码解释：
上述这个评价模型之中，1和2节点是gaussian节点，3和4节点是softmax节点，运用的评价方法是BIC。
在实际中，当样本超过5个我们就不可能列举出所有图模型了，但是我们可以列举得到的最佳模型的几个相近的模型，依次做出评判
3、K2算法
K2算法是贪婪搜索算法的一种，它的核心思想是为没有父节点的节点添加父节点，如果添加的父节点能够增加评分函数得分，就继续添加，否则停止添加，由于我们一开始已经确定了节点的顺序，所以这里只需要单独的为每个节点添加父节点。
代码：
order=[C S R W];
max_fan_in=2;
sz=5:5:100;
for i=1:length(sz)
dag2=learn_struct_K2(data(:,1:sz(i)),node_sizes,order,'max_fan_in',max_fan_in);
correct(i)=isequal(dag,dag2);
end
4、爬山算法
爬山算法的基本步骤是找出一个空间中的特定点，然后从它的邻近点中找出与它组合得分最高的点，如果找到的得分最高组合小于原有模型，就停止寻找。
5、MCMC算法
全称是马尔科夫链蒙特卡罗算法，我们能够利用此方法搜索全部的图模型空间，然后找出某模型的相近的模型。
代码：
[sampled_graphs,accept_ratio]=learn_struct_MCMC(data,ns,'nsamples',100,'burnin',10);
代码解释：
通过输入数据，节点大小，样本数量，筛选模型数量，得到邻近的几个得分较高图模型。
代码：
all_dags=mk_all_dags(N);
mcmc_post=mcmc_sample_to_hist(sampled_graphs,all_dags);
代码解释：
显示全部的直方图
代码：
score=score_dags(data,ns,all_dags);
post=normalise(exp(score));
代码解释：
检验图模型的性能
代码：
subplot(2,1,1);
bar(post);
subplot(2,1,2);
bar(mcmc_post);
代码：
clf
plot(accept_ratio)
代码解释：
原油收敛性诊断
尽管理论上MCMC是多项式级别的，在实际应用中能处理的节点数量不超过10个
6、主动结构学习
无论提供多少样本数据，结构学习最多学到马尔可夫等价性原则上面。我们必须设置干预数据，也就是强制某一个节点是特定的取值。
7、结构性EM
当有部分的数据不能被观测到时，我们就采用贝叶斯评分。
由于树多元混合分布，最终采用BIC评分
传统的搜寻算法在每一步都要计算EM，所以发展了局部搜索算法，叫结构性EM，可能收敛到局部最大的BIC评分。
8、基于限制的方法
IC算法用于归纳原因；FCI算法用于快速因果推理；
代码：
pdag=learn_struct_pdag_pc('dsep',N,max_fan_in,dag);
代码解释：
pdag(i,j)=-1表示i->j；pdag(i,j)=1表示j->i。
代码：
max_fan_in=4;
nsamples=281;
alpha=0.05;
pdag=learn_struct_pdag_pc('cond_indep_fisher_z',n,max_fan_in,C,nsamples,alpha);
代码解释：
解释代码.png
