用二叉树表示家谱关系并实现各种查找功能
 
目的：掌握二叉树遍历算法的应用，熟练使用先序、中序、后序3种递归遍历算法进行二叉树问题的求解。
内容：采用一棵二叉树表示一个家谱关系，要求具有以下功能：①、文件操作功能，即家谱记录的输入、家谱记录的输出、清除全部文件记录和将家谱记录存盘。②、家谱操作功能，即用括号表示法输出家谱二叉树、查找某人的所有儿子、查找某人的所有祖先。
 
需求分析：
 
 
模块1：功能选择
 
 
分析：功能选择模块函数，主要提供 1：文件操作 2：家谱操作 两个功能模块让用户选择。输入数字 1 的时候，出现界面 1：输入 2：输出3：清盘 4：更换始祖 0：存盘返回。返回后输入数字 2，出现界面1：括号表示法 2：二叉树表示法 3：找某人的所有儿子 4：找某人所有祖先 ，用户可以根据自己的需求进行选择。
 
 
模块2：二叉树的建立
 
 
分析：二叉树的结点有三个域，数据域和两个指针域，数据域用来存放数据，两个指针域用来分别存放指向该结点左右孩子的指针。并且还有个 root 结点，称二叉树的根节点。
 
 
模块3：家族成员信息的输入与输出
 
 
分析：依次输入一个家庭的父亲、母亲和孩子的姓名，先用定义好的结构体数组存储数据，并通过i/o流将它们保存在相应的文件里。通过循环依次输出fam数组中的数据，即输出每个家庭的父亲、母亲和孩子的姓名。
 
 
模块4：查找某人的儿子
 
 
分析：首先输入父亲的姓名，在二叉树中查找是否有此人，如果没有就输出不存在这样的父亲。如果有就先查看它的左孩子是否存在，不存在就输出这个父亲没有妻子，如果存在就查找左孩子的右孩子，没有右孩子就输出这个父亲没有孩子，存在就输出右孩子的姓名，即为查找到的儿子。
 
 
模块5：查找某人的祖先
 
 
分析：采用后序非递归遍历方法输入从根结点到*s 结点的路径，首先输入一个成员的姓名，用一个栈存入查找的路径，当找到时栈中的元素即为它的所有祖先。
 
 
模块6：二叉树的各种表示法
 
 
分析：①、括号表示法：通过先序遍历，先输出根节点，若根节点的左孩子结点或右孩子结点非空，则先输出（，然后递归左子树；如果根节点的右孩子结点非空，递归右子树，然后输出）。②、二叉树树形表示法：在二叉树凹入表示法的基础上，对母亲结点的左右子树如何输出做了一些控制，设置每一个结点的固定宽度，分清其左右结点，循环输出至为空。
 
 
具体存储方式如下图：
 
 
问题概述：设计一个对数据输入，输出，储存，查找的多功能程序，需要保存家族的基本信息，包括姓名及它们的关系，并采用二叉树来表示它们的关系，头结点作为父亲节点，他的左孩子为他的妻子，妻子结点的右孩子为他的孩子，依次存储每个家庭的信息。该题还需要具有保存文件的功能，以便下次直接使用先前存入的信息。家谱的功能是查询家族每个人的信息，并且输出它们的信息，而且还要具有查询输出的功能。

主程序流程：首先创建始祖名称，完成整个家谱的重构。进入主菜单界面，输入不同的数字进行不同的操作，1：文件操作；2：家谱操作；0：退出系统；输入其他选择，则报错。若输入的操作为1，则进入文件操作界面，1：输入 调用InputFam(fam,n)函数，完成数据输入操作；2：输出 调用OutputFile(fam,n)函数，完成数据的输出操作；3：一键清空 调用DelAll(fam,n)函数；0：存盘返回 调用SaveFile(fam,n)函数运用i/o流将已保存到数组的数据存到相应的文件中，输入其他选择，则报错。若输入的操作为2，则进入家谱操作界面，1：括号表示法 调用DispTree1(bt)函数，通过先序遍历，输出（，），完成其括号表示法的输出；2：二叉树家谱 调用DispTree2(bt)函数，在二叉树凹入表示法的基础上，对母亲结点的左右子树如何输出做了一些控制，设置每一个结点的固定宽度，分清其左右结点，循环输出至为空，以期望达到能够输出二叉树树形结构的目标；3：找某人所有儿子 调用FindSon(bt)函数 通过输入父亲姓名来检索该姓名所位于的位置，判断其是否有妻子、是否有儿子，如果有儿子将儿子输出；4：找某人所有祖先 调用Ancestor(bt)函数，输入某姓名，对该姓名先进行检索，若成功检索，调用Path（bt,p）路径函数，通过后序非递归遍历将该姓名所处位置的结点的祖先结点全部输出；0：返回；输入其他选择，则报错。
 
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <conio.h>
#include<iostream>
using namespace std;	
#define MaxSize 30	//代表了姓名字符、最大场宽、数组元素树		
typedef struct fnode
{
	char father[MaxSize];	//父
	char wife[MaxSize];	//母
	char son[MaxSize];	//子
} FamType;
typedef struct tnode
{
	char name[MaxSize];
	struct tnode *lchild,*rchild;
} BTree;					//家谱树类型

//创建二叉树
BTree *CreatBTree(char *root,FamType fam[],int n)	//从fam(含n个记录)递归创建一棵二叉树
{
	int i=0,j;
	BTree *bt,*p;
	bt=(BTree *)malloc(sizeof(BTree));	//创建父亲节点
	strcpy(bt->name,root);				//将root中的COPY复制到bt->name中
	bt->lchild=bt->rchild=NULL;
	while (i<n && strcmp(fam[i].father,root)!=0) //比较两个字符串是否相同
		i++;
	if (i<n)									//找到了该姓名的记录
	{
		p=(BTree *)malloc(sizeof(BTree));		//创建母亲节点
		p->lchild=p->rchild=NULL;
		strcpy(p->name,fam[i].wife);
		bt->lchild=p; 
		for (j=0;j<n;j++)						//找所有儿子
			if (strcmp(fam[j].father,root)==0)	//找到一个儿子
			{
				p->rchild=CreatBTree(fam[j].son,fam,n);
				p=p->rchild;
			}
	}
	return(bt);
}

//以括号表示法输出二叉树
void DispTree1(BTree *b)	//先序遍历
{	
	if (b!=NULL)
	{
		cout<<b->name;
		if (b->lchild!=NULL || b->rchild!=NULL)
		{
			cout<<"(";
			DispTree1(b->lchild);
			if (b->rchild!=NULL) 
				cout<<",";
			DispTree1(b->rchild);
			cout<<")";			//累计
		}
	}
}

//二叉树家谱表示法
void DispTree2(BTree *bt)	
{
	BTree *St[MaxSize],*p;
	int Level[MaxSize][2],top,n,i,x=0,width=4;
	int flag=0;
	if (bt!=NULL)
	{
		cout<<"  >>二叉树家谱表示法:"<<endl;
        top=1;
		St[top]=bt;				//根节点进栈
		Level[top][0]=width;
		
		while (top>0)
        {
			p=St[top];			//退栈并凹入显示该节点值
			n=Level[top][0];
			for (i=1;i<=n;i++)  //其中n为显示场宽,字符以右对齐显示
				cout<<" ";
			cout<<p->name<<endl;
			if(Level[top][1]==2&&p->lchild!=NULL)
			{
				cout<<p->lchild->name;
				flag=1;
				n=0;
			}
			top--;
			if (p->lchild!=NULL)
			{								//将左子树根节点进栈
				top++;
				St[top]=p->lchild;
				Level[top][0]=0;		//显示场宽增width
				Level[top][1]=1;			//为左孩子节点				
			}
			if(p->lchild!=NULL&&p->rchild!=NULL)
			{
				top++;
				St[top]=p->rchild;
				Level[top][0]=n+width;		//显示场宽增width
				Level[top][1]=2;			//为右孩子节点
			}
			if (p->rchild!=NULL&&p->lchild==NULL)
			{
											//将右子树根节点进栈
				top++;
				St[top]=p->rchild;
				Level[top][0]=n+width;		//显示场宽增width
				Level[top][1]=2;			//为右孩子节点
			}	
        }
	}
}

//以凹入表示法输出
void DispTree3(BTree *bt)	
{
	BTree *St[MaxSize],*p;
	int Level[MaxSize][2],top,n,i,width=4;
	if (bt!=NULL)
	{
		cout<<"  >>家谱凹入表示法:"<<endl;
        top=1;
		St[top]=bt;				//根节点进栈
		Level[top][0]=width;
		while (top>0)
        {
			p=St[top];			//退栈并凹入显示该节点值
			n=Level[top][0];
			for (i=1;i<=n;i++)  //其中n为显示场宽,字符以右对齐显示
				cout<<" ";
			cout<<p->name;
			if (Level[top][1]==1)
				cout<<"(l)";
			else
				cout<<"(r)";
			for (i=n+1;i<=MaxSize-6;i+=2)
				cout<<"--";
			cout<<endl;
			top--;
			if (p->rchild!=NULL)
			{								//将右子树根节点进栈
				top++;
				St[top]=p->rchild;
				Level[top][0]=n+width;		//显示场宽增width
				Level[top][1]=2;			//为右孩子节点
			}
			if (p->lchild!=NULL)
			{								//将左子树根节点进栈
				top++;
				St[top]=p->lchild;
				Level[top][0]=n+width;		//显示场宽增width
				Level[top][1]=1;			//为左孩子节点
			}
        }
	}
}

//采用先序递归算法找name为xm的节点
BTree *FindNode(BTree *bt,char xm[]) 
{
	BTree *p=bt;
	if (p==NULL) 
		return(NULL);
	else
	{
		if (strcmp(p->name,xm)==0)
			return(p);
		else
		{
			bt=FindNode(p->lchild,xm);
			if (bt!=NULL) 
				return(bt);
			else 
				return(FindNode(p->rchild,xm));
		}
	}
}

//输出某人的所有儿子
void FindSon(BTree *bt)	
{
	char xm[MaxSize];
	BTree *p;
	cout<<"  >>父亲姓名:";
	cin>>xm;
	p=FindNode(bt,xm);
	if (p==NULL)
		cout<<"  >>不存在"<<xm<<"的父亲"<<endl;
	else
	{
		p=p->lchild;
		if (p==NULL)
			cout<<"  >>"<<xm<<"没有妻子"<<endl;
		else
		{
			p=p->rchild;
			if (p==NULL)
				cout<<"  >>"<<xm<<"没有儿子!"<<endl;
			else
			{
				cout<<"  >>"<<xm<<"的儿子:"<<" ";
				while (p!=NULL)
				{
					cout<<p->name<<" ";
					p=p->rchild;
				}
				cout<<endl;
			}
		} 
	}
}

//采用后序非递归遍历方法输出从根节点到*s节点的路径
int Path(BTree *bt,BTree *s)	
{
	BTree *St[MaxSize];
	BTree *p;
	int i,flag,top=-1;				//栈指针置初值
	do
	{
		while (bt)                 	//将bt的所有左节点进栈
		{	
			top++;
			St[top]=bt;
			bt=bt->lchild;
		}
		p=NULL;                   	//p指向当前节点的前一个已访问的节点
		flag=1;                   	//设置bt的访问标记为已访问过
		while (top!=-1 && flag)
		{	
			bt=St[top];          	//取出当前的栈顶元素
			if (bt->rchild==p)      //右子树不存在或已被访问,访问之
			{	if (bt==s)          //当前访问的节点为要找的节点,输出路径
				{	
					cout<<"  >>所有祖先:";
					for (i=0;i<top;i++) 
					   	cout<<St[i]->name<<" ";
					cout<<endl;
				   	return 1;
					
				}
				else
				{	
					top--;
				   	p=bt;           //p指向则被访问的结
				}
			}
			else
			{	
				bt=bt->rchild;      //bt指向右子树
				flag=0;            	//设置未被访问的标记
			}
		}
	} while (top!=-1);				//栈不空时循环
	return 0;						//其他情况时返回0
}

//输出某人的所有祖先
void Ancestor(BTree *bt)	
{
	BTree *p;
	char xm[MaxSize];
	cout<<"  >>输入姓名:";
	cin>>xm;
	p=FindNode(bt,xm);
	if (p!=NULL)
		Path(bt,p);
	else
		cout<<"  >>查无此人"<<endl;
}

//清除家谱文件全部记录
void DelAll(FamType fam[],int &n)	
{
	FILE *fp;
	if ((fp=fopen("fam.dat","wb"))==NULL) 
	{	
		cout<<"  >>不能打开家谱文件"<<endl;
		return;
	}
	n=0;
	fclose(fp);
}

//读家谱文件存入fam数组中
void ReadFile(FamType fam[],int &n) 
{
	FILE *fp;
	long len;
	int i;
	if ((fp=fopen("fam.dat","rb"))==NULL) 
	{
		n=0;
		return;
	}
	fseek(fp,0,2);				//家谱文件位置指针移到家谱文件尾
	len=ftell(fp);    			//len求出家谱文件长度
	rewind(fp);					//家谱文件位置指针移到家谱文件首
	n=len/sizeof(FamType); 		//n求出家谱文件中的记录个数
	for (i=0;i<n;i++)
		fread(&fam[i],sizeof(FamType),1,fp);//将家谱文件中的数据读到fam中
	fclose(fp);
}

//将fam数组存入数据家谱文件
void SaveFile(FamType fam[],int n) 
{
	int i;
	FILE *fp;
	if ((fp=fopen("fam.dat","wb"))==NULL) 
	{	
		cout<<"  >>数据家谱文件不能打开"<<endl;;
		return;
	}
	for (i=0;i<n;i++)
		fwrite(&fam[i],sizeof(FamType),1,fp);
	fclose(fp);
}

//添加一个记录
void InputFam(FamType fam[],int &n)		
{
	cout<<"  >>输入父亲、母亲和儿子姓名:";
	cin>>fam[n].father;
	cin>>fam[n].wife;
	cin>>fam[n].son;
	n++;
}

//输出家谱文件全部记录
void OutputFile(FamType fam[],int n)
{
	int i;
	if (n<=0)
	{
		cout<<"  >>没有任何记录"<<endl;
		return;
	}
	cout<<"          父亲     母亲      儿子"<<endl;
	cout<<"       ------------------------------"<<endl;
	for (i=0;i<n;i++)
		printf("  %10s%10s%10s\n",fam[i].father,fam[i].wife,fam[i].son);
	cout<<"       ------------------------------"<<endl;
}


 
算法结果与分析：
 
菜单函数功能测试：
 
 
输入功能函数测试
 
 
输出功能函数测试
 
 
查询功能函数测试
 

 
 
二叉树的各种表示法函数测试
 

 
 
心得体会：
 程序的关键是掌握二叉树的相关操作、二叉树的创建和运用、结点的查找、祖宗结点的查找等。在编程的过程中，出现了很多问题，如二叉树无法建立、程序内存读取不了、忘了添加头文件等错误。在单步调试和添加提示输出的情况下修改程序运行正确。查找首先要判断该结点是否为空，再与查找到的结点比较，否则会内存无法读取，强行结束程序。祖宗结点的查找一直是个大问题，在参考书的帮助下想到了后序遍历，是可以从孩子往上找到。家谱的功能是查询家族每个人的信息，并且输出它们的信息，还要具有查询输出功能。这样复习了一下查询、插入、删除函数的应用。并学习了i/o流的文件储存及调用功能，复习了子函数和递归调用功能，并熟练运用这些函数。

这里将连续信号和离散信号的频谱的几个式子总结在一起。方便使用时查阅。
 
一个时域连续信号x(t)，假设其能量有限，并且频域带宽有限，则可以对其进行傅立叶变换求其频谱。
 

 
 
 
上面的式子中，X(Ω)称为信号的频谱。如果我们在频域用f来作为自变量。则上面的式子改写为：
 

 
 
 
这两种频谱表示间的关系很简单。
 

 
 
 
相应的，有所谓的能量等式：
 

 
 
 
对连续信号进行采样，就得到了离散信号。设采集频率为 fs，采样时间间隔为Δ。那么离散信号x[n] 与连续信号 x(t) 的关系如下：
 

 
 
 
离散信号的频谱通常写为：
 

 
 
 
这里的ω与连续信号的Ω之间的关系如下：
 

 
 
 
如果用f作为频域自变量，则：
 

 
 
 
这里用了X’(f) 是为了与连续信号频谱表示相区别。X’(f) 与连续信号频谱X(f) 有什么关系呢？简单的推导可知当信号采样频率满足乃奎斯特采样定律时，X’(f) 与连续信号频谱X(f) 有简单的联系。
 

 
 
 
有些教科书上（比如程乾生教授所著的数字信号处理教材），会给出这样的离散信号频谱的定义：
 

 

 
 
 
对应的能量等式如下：
 

 
 
从上面能量等式，还可以得到如下关系：
 

 
 
这其实就是积分近似计算中常用的矩形算法。相应的，信号通过一个线性系统（用h(t)表示）后的输出y(t)与x(t) 的关系如下；
 

 
 
 
如果我们对x(t)、h(t) 和y(t)都进行采样，得到x[n]、h[n]和y[n]，并且采样过程满足采样定律的要求。那么我们利用 x[n]和h[n] 就应该可以计算出 y[n]。
 

 
 
 
实际应用中，我们不可能采集无限长时间的数据，因此我们用于处理的离散信号通常都限定在一定长度。这时它的频谱为：
 
 
 
对于N个数据点的序列，我们实际上只需要计算N个频点的值。
 

 
 
 
因此，可以得到有限离散频谱公式如下：
 
 

 
 

最近在写模糊搜索的时候，使用mangodb对数据库进行查询。需求是输入框中可以供用户输入多个搜索项，需要返回的字段满足这多个搜索项的内容。
 
刚开始摸不着头脑，一般用正则都是写的或的关系，最后还是在文档里找到了答案。
 
/(?=.*失败)(?=.*成功了)/
 
类似上面的方法，每个（）表示你所要放置的一个条件，该正则匹配的结果必须满足每一个括号中的内容。括号里的内容需要以?=开始，.*表示任意个其他字符。
 
其实很简单，这样以括号区分的话，就不要求先后顺序，只要共同包含这些字段即可

 
 
笔者：整理2016-2017年ACL、EMNLP、SIGIR、IJCAI、AAAI等国际知名会议中实体关系推理与知识图谱补全的相关论文，供自然语言处理研究人员，尤其知识图谱领域的学者参考，如有错误理解之处请指出，不胜感激！（如需转载，请联系本人：jtianwen2014，并注明出处）
 
 
https://www.cnblogs.com/jtianwen2014/p/7000190.html
 
ACL 2016
 
Unsupervised Person Slot Filling based on Graph Mining
 
 
 
作者：Dian Yu, Heng Ji 
机构：Computer Science Department, Rensselaer Polytechnic Institute 
 
本文的任务为槽填充（Slot Filling），即从大规模的语料库中抽取给定实体（query）的被明确定义的属性（slot types）的值（slot fillers）。对于此任务，本文叙述目前主流的方法可以分为两类：有监督的分类方法，设计分类器识别给定的实体与值所属的关系类型，分类器的训练往往使用如活动学习、利用距离监督的噪声标注等方法；模式匹配方法，从文本中自动或半自动地抽取和生成词法或句法的模式，以用于关系的抽取，但因为关系所表述的方式千差万别，这种模式匹配方法无法拥有较好的召回率。
 
本文认为，以上两类方法都无法很好的应对新的语言或是出现新的关系类型的情况，即移植性不强；而且，两种方法都只是专注于实体和候选值之前的平坦表示，并没有考虑到它们之间的全局结构关系，以及语句中其他的关系事实的影响。本文重要的算法思想基于以下两个观察：
 
在句子的依存图中，触发词结点（trigger）经常是和实体（query）与值（filler）结点都很相关的，并且是图中的重要节点；
当实体（query）与值（filler）结点通过一个关系明确的触发词强关联起来，往往意味着存在一定的关系（slot type）。
基于以上两个观察，本文的提出了一种基于图的槽填充的方法：首先，利用简单的启发式规则，从句子中识别出候选实体与属性值；然后，对于给定候选实体与属性值对，利用PageRank图算法和AP（Affinity Propagation）聚类算法自动识别触发词；最后，根据识别的触发词对属性类型（slot type）进行分类。
 
下图为利用PageRank算法对候选触发词结点打分： 
 
 
下图为利用AP算法对候选触发词进行聚类（关系触发词可能不止一个单词），以选定最终触发词。如下图最终选定“divorced”为最终触发词。 
 
 
 
 
笔者：本文主要的思想与创新点在于，以属性触发词为切入点进行关系的挖掘，将PageRank算法与AP算法引入其中，将槽填充问题转换为图上的挖掘问题。候选实体与属性值的识别、属性类型的分类这两个部分使用了启发式的规则与外部的词典资源。但这中图挖掘的方法，由于应用句法依存与PageRank算法有可能在计算复杂性上存在问题。
 
 
Knowledge Base Completion via Coupled Path Ranking
 
 
 
作者：Quan Wang†, Jing Liu‡, Yuanfei Luo†, Bin Wang†, Chin-Yew Lin‡ 
机构†：Institute of Information Engineering, Chinese Academy of Sciences 
机构‡：Microsoft Research 
 
本文的任务为知识库补全，即通过考察知识库中已经存在的事实，自动推理出丢失的事实。本文叙述这项任务的方法大体分为三种：
 
Path Ranking 算法（PRA），通过连接实体的已有路径来预测实体间的潜在关系；
基于表示学习的模型，将实体和关系映射为空间中的向量，通过空间中向量的运算来进行推理（如TransE）；
概率图模型，如马尔科夫逻辑网络及其衍生物。
由于PRA方法具有较好的解释性，并且不需要额外的逻辑规则，本文主要使用PRA方法对其改进。在利用PRA进行关系推理时，以往的方法都是在推理阶段，利用PRA为每个关系独立建模，也就是为每个关系学习一个独立的分类器。
 
本文的初衷是：如果使用PRA对某些关系集体建模是否会得到更好的效果，尤其是当这些关系彼此紧密联系的时候，比如，“出生”和“生长于”这两个关系极有可能共同拥有一些关系路径：“国籍->首都”等。很多研究表明这种多任务学习相比单任务学习而言，往往具有更好的效果。本文提出CPRA的方法，该方法所要解决两个问题：（1）哪些关系需要组合在一起学习？（2）如何组合在一起学习？
 
（1）哪些关系需要组合在一起学习？本文提出了一种基于公共路径的相似度度量方法，并在此基础上将关系聚成不同的组，同组的关系共同学习。公共路径的相似度具体值依据两个关系（或簇）的路径交集数量占比。
 
（2）如何组合在一起学习？依循多任务学习的原则，对于共同训练的分类器使用两部分参数，即共享参数和私有参数。共享参数可以体现相似关系之间的得共性，私有参数用于描述不同关系之间的特性。这两类参数在训练过程中是联合学习的。
 
 
 
笔者：PRA的方法的应用可能存在局限，比如对于开放域知识图谱，如Reverb等，其关系类型多样且未事先定义，则无法对于每个类别训练分类器；而且这种每个类别训练分类器的方法消耗实在较大，更不利于给定实体对的关系推理。是否可以统一为一个分类器，或者不是分类器，而是生成器，生成给定实体对的可能关系，这样就应用于关系类型体系未知的开放域知识图谱。
 
 
Compositional Learning of Embeddings for Relation Paths in Knowledge Bases and Text
 
 
 
作者：Kristina Toutanova, Xi Victoria Lin∗, Wen-tau Yih, Hoifung Poon, Chris Quirk
机构：Microsoft Research
机构∗：University of Washington
 
本文的任务为知识图谱补全，推理预测实体间潜在的关系。本文叙述，当前的一些学者将关系路径信息融入到知识库嵌入式表示中，取得了非常显著的结果。知识库嵌入式表示，指的是将知识库中实体和关系映射到低维稠密的空间中，知识的推理转化为实体与关系所关联的向量或矩阵之间的运算。这种嵌入式的表示，操作花销较小，推理的效率较高。为了进一步提升基于嵌入式表示的关系推理，一些学者将关系路径信息融入其中。
 
本文发现，目前的将关系路径融入知识库的嵌入式表示方法存在如下问题：首先，当关系的路径总类增多时，时间开销较大，严重影响推理的效率；另外，目前的方法只考虑了路径信息，没有考虑结点的信息，即使是相同路径，包含不同结点也拥有不同的信息。本文提出了一种动态规划的方法，可以高效地将关系路径融入到知识库的嵌入式表示，并且同时对路径上的关系类型和结点进行表示。
 
本文以基因调控网络为例，网络的节点是基因，边为两个关键的关系：正调控、负调控，为了联合表示文本信息，将基因共现的文本语句的依存关系嵌入到网络中，所下图所示，红色边为原网络的调控关系，灰色边为文本依存信息：
 
 
基本的知识图谱嵌入式表示学习的方法是，首先学习实体和关系的向量（或矩阵）表示，然后一用学习到的参数θθ和函数f(s,r,t|θ)f(s,r,t|θ)为可能的三元组进行打分。其中，双线性模型（BILINEAR）用矩阵表征关系，向量表征实体，打分函数ff定义为：f(s,r,t|θ)=xTsWrxtf(s,r,t|θ)=xsTWrxt。
 
另外，为了减少参数，本文介绍了另一种模型双线性-对角模型，即将关系矩阵WW替换为对角矩阵。
 
将关系路径引入嵌入式表示一般有两种方法：（1）利用关系路径生成辅助的三元组用于训练(通过随机游走获得路径，端点实体的关系用关系路径代替)；（2）将关系路径作为特征用于打分，打分函数替换为f(s,r,t|θ,∏s,t)f(s,r,t|θ,∏s,t)，∏s,t∏s,t为路径上关系嵌入式表示的加权求和。对于双线性模型，关系路径ππ的嵌入式表示一般为：Φπ=Wr1...WrnΦπ=Wr1...Wrn。
 
本文更偏向于第二种方法，因为其对路径上的关系进行剪枝。本文对f(s,r,t|θ,∏s,t)f(s,r,t|θ,∏s,t)做了详细设计与定义：用F(s,t)F(s,t)代表∏s,t∏s,t，用P(t|s,π)P(t|s,π)代表头实体经过路径到达尾实体的概率，令：F(s,t)=∑πw|π|P(t|s,π)Φ(π)F(s,t)=∑πw|π|P(t|s,π)Φ(π)。最终f(s,r,t|θ,∏s,t)f(s,r,t|θ,∏s,t)定义为：
 
 
 
f(s,r,t)=xTWrxt+vec(F(s,t))Tvec(Wr)f(s,r,t)=xTWrxt+vec(F(s,t))Tvec(Wr)
 
其中F(s,t)F(s,t)的计算时间消耗较大，本文通过使用动态规划的方法ALL-PATH高效学习与计算该打分函数，使得可以高效地将关系路径融入到知识库的嵌入式表示，并且同时对路径上的关系类型和结点进行表示。本文用参数weiwei用于表示对经过实体eiei路径的影响，对于双线性模型：Φπ=Wr1tanh(we1)...Wrntanh(wen)Φπ=Wr1tanh(we1)...Wrntanh(wen)。用Fl(s,t)Fl(s,t)表示实体ss和tt之间长度为ll的路径的加权和，则有：
 
 
 
F(s,t)=∑l=1...LwlFls,tF(s,t)=∑l=1...LwlFls,t
 
其中，Fls,t=∑π∈Pl(s,t)P(t|s,π)ΦπFls,t=∑π∈Pl(s,t)P(t|s,π)Φπ,Pl(s,t)Pl(s,t)表示实体ss和tt之间长度为ll的路径。
 
动态规划算法如下图所示：
 
 
 
 
笔者：本文针对以往融合路径信息的嵌入式表示方法的时间复杂度进行优化，并加入节点信息，旨在高效运算并融入更充分的信息。本文的方法ALL-PATH在时间和效果上优于之前的方法。本文的方法的实现基于的是双线性模型，这里应该只是示例，完全可以将双线性替换为其他模型，这种关系路径集成的思想可以应用于很多已有的嵌入式表示学习方法，所以本文的最大亮点应该在于动态规划的提出，用以高效的计算。
 
 
TransG : A Generative Model for Knowledge Graph Embedding
 
 
 
作者：Han Xiao, Minlie Huang, Xiaoyan Zhu
机构：Dept. of Computer Science and Technology, Tsinghua University
 
本文的任务为知识图谱表示学习，旨在将知识图谱映射到低维稠密的向量空间里。与以往研究工作不同，本文将目光聚焦于“多语义关系”，即同一名相的关系可能具有不同的语义含义，如对于关系“HasPart”，对于实体“桌子”和“桌腿”有这种关系，对于“英国”和“伦敦”也同样具有这样的关系，但二者所表达的含义却不尽相同。
 
不止于感性层面上，本文对TransE的知识图谱向量表示进行可视化（PCA降维）：抽取四种不同关系，将具有给定关系的实体对向量相减（据TransE思想，可以得到关系的向量），将结果向量展示在二维空间里。理想情况下，对于每个关系应该只和一个簇对应，但真实的结果是每个关系不止一个簇，而是多个明显分开的簇。这也从另一个角度说明了关系的多语义性质。
 
针对这一问题，本文提出TransG模型，利用贝叶斯非参数无限混合嵌入式表示模型来生成关系的多语义表示。TransG可以自动发现关系的多语义簇，并且利用关系的混合语义对实体对进行翻译操作，以进行关系推理。
 
本文利用了两个重要的模型和算法，分别是贝叶斯非参数无限混合嵌入式表示模型和中餐馆过程算法。具体的实体与关系嵌入式表示生成过程如下：
 
 
通过该过程会获得初始化的实体与关系向量，三元组的打分函数为：
 
 
 
∑m=1Mrπr,me−||uh+ur,m−ut||22σ2h+σ2t∑m=1Mrπr,me−||uh+ur,m−ut||22σh2+σt2
 
不同于以往的方法，本文对于关系的描绘更为细化，对于实体对，可以确切获得多语义关系的明确语义：
 
 
 
m∗(h,r,t)=argmaxm=1...Mr(πr,me−||uh+ur,m−ut||22σ2h+σ2t)m(h,r,t)∗=argmaxm=1...Mr(πr,me−||uh+ur,m−ut||22σh2+σt2)
 
 
 
h+ur,m∗(h,r,t)≈th+ur,m(h,r,t)∗≈t
 
学习过程是是的正例的分数不断提高，负例的分数不断减少，最终获得实体与关系的表示。
 
 
 
笔者：本文的切入点是多语义关系存在于知识库中，而之前的模型没有考察并解决这一问题。本文使用非参数贝叶斯模型，借助CRP算法用于对关系多语义的识别与生成。本文主要的贡献在于提出了多语义关系的问题，并借助CRP解决这一问题。