crf_thread.cpp

pocket_crf_0.45

	vector<int> seq_key(seq.node_num);//preserve seq.nodes[i].key
	for(i=0;i<seq.node_num;i++){
		seq_key[i]=seq.nodes[i].key;
		seq.nodes[i].key=0;
		for(j=0;j<=c->order;j++){
			if(i+j>=c->order)
				seq.nodes[i].key=seq.nodes[i].key*c->ysize+bst_path[i+j-c->order];
		}
	}

	for(i=0;i<seq.node_num;i++)
	{
		bool is_err=false;
		node &nod=seq.nodes[i];
		for(j=0;j<nod.clique_num;j++)
		{
			if(!nod.cliques[j])
				continue;
			clique &cli=*(nod.cliques[j]);
			int key=0;
			for(k=0;k<cli.node_num;k++)
				key= key*c->ysize +cli.nodes[k]->key%c->ysize;
			//key = predict cli.key
			if(key!=cli.key)
			{
				is_err=true;
				for(k=0;k<cli.feature_num;k++)
				{
					int findex=c->fmap[cli.fvector[k]+key];
					if(findex>=0){
						c->lambda[findex]--;
						c->gradient[findex]-=times;
					}
					findex=c->fmap[cli.fvector[k]+cli.key];
					if(findex>=0)
					{
						c->lambda[findex]++;
						c->gradient[findex]+=times;
					}
				}
			}
		}
		if(is_err)
			obj++;
	}
	//recover
	for(i=0;i<seq.node_num;i++)
		seq.nodes[i].key=seq_key[i];
}

void crf_thread::pa_update(sequence &seq)
{
	int i,j,k;
	vector<int> seq_key(seq.node_num);//preserve seq.nodes[i].key
	for(i=0;i<seq.node_num;i++){
		seq_key[i]=seq.nodes[i].key;
		seq.nodes[i].key=0;
		for(j=0;j<=c->order;j++){
			if(i+j>=c->order)
				seq.nodes[i].key=seq.nodes[i].key*c->ysize+bst_path[i+j-c->order];
		}
	}

	//calculate \delta f(x,y) = f(x,y) - f(x,y~)
	map<int,double> res;
	double loss=0;
	for(i=0;i<seq.node_num;i++)
	{
		bool is_err=false;
		node &nod=seq.nodes[i];
		for(j=0;j<nod.clique_num;j++)
		{
			if(!nod.cliques[j])
				continue;
			clique &cli=*(nod.cliques[j]);
			int key=0;
			for(k=0;k<cli.node_num;k++)
				key= key*c->ysize +cli.nodes[k]->key%c->ysize;
			//key = predict cli.key
			if(key!=cli.key)
			{
				is_err=true;
				for(k=0;k<cli.feature_num;k++)
				{
					int findex=c->fmap[cli.fvector[k]+key];
					if(findex>=0){
						res[findex]++;
					}
					findex=c->fmap[cli.fvector[k]+cli.key];
					if(findex>=0)
					{
						res[findex]--;
					}
				}
			}
		}
		if(is_err){
			obj++;
			loss++;
		}
	}
	double r=0;
	map<int,double>::iterator it;
	for(it=res.begin();it!=res.end();it++)
	{
		loss+=c->lambda[it->first]*it->second;
		r+=it->second*it->second;
	}
	r=loss/r;
	if(r>c->sigma)
		r=c->sigma;
	for(it=res.begin();it!=res.end();it++)
	{
		c->lambda[it->first]-=r*it->second;
		c->gradient[it->first]-=r*it->second*times;
	}
	//recover
	for(i=0;i<seq.node_num;i++)
		seq.nodes[i].key=seq_key[i];
}

void crf_thread::ap_update(sequence1 &seq1)//bst_path key is node.y, seq1.key is nodes.y
{
	int i,j;
	for(i=0;i<seq1.vertex_num;i++){
		vertex &vtx=seq1.vertexes[i];
		int key=0;
		for(j=0;j<2;j++){
			if(i+j>=1)
				key=key*c->ysize+bst_path[i+j-1];
		}
		bool is_err=false;
		if(key!=vtx.key)
		{
			is_err=true;
			int findex;
			for(j=0;j<vtx.feature_num;j++)
			{
				findex=c->fmap[vtx.fvector[j]+key%c->ysize];
				if(findex>=0)
				{
					c->lambda[findex]--;
					c->gradient[findex]-=times;
				}
				findex=c->fmap[vtx.fvector[j]+vtx.key%c->ysize];
				if(findex>=0)
				{
					c->lambda[findex]++;
					c->gradient[findex]+=times;
				}
			}
			if(i)
			{
				if(c->chain_type==SIMPLE_CHAIN)
				{
					findex=c->fmap[c->transit+key];
					if(findex>=0)
					{
						c->lambda[findex]--;
						c->gradient[findex]-=times;
					}
					findex=c->fmap[c->transit+vtx.key];
					if(findex>=0)
					{
						c->lambda[findex]++;
						c->gradient[findex]+=times;
					}
				}else if(c->chain_type==FIRST_CHAIN){
					edge &e=seq1.edges[i-1];
					for(j=0;j<e.feature_num;j++)
					{
						findex=c->fmap[e.fvector[j]+key];
						if(findex>=0)
						{
							c->lambda[findex]--;
							c->gradient[findex]-=times;
						}
						findex=c->fmap[e.fvector[j]+vtx.key];
						if(findex>=0)
						{
							c->lambda[findex]++;
							c->gradient[findex]+=times;
						}
					}
				}
			}
		}
		if(is_err)
			obj++;
	}
}


void crf_thread::pa_update(sequence1 &seq1)//bst_path key is node.y, seq1.key is nodes.y
{
	int i,j;
	//calculate \delta f(x,y) = f(x,y) - f(x,y~)
	map<int,double> res;
	double loss=0;
	for(i=0;i<seq1.vertex_num;i++){
		vertex &vtx=seq1.vertexes[i];
		int key=0;
		for(j=0;j<2;j++){
			if(i+j>=1)
				key=key*c->ysize+bst_path[i+j-1];
		}
		bool is_err=false;
		if(key!=vtx.key)
		{
			is_err=true;
			
			int findex;
			for(j=0;j<vtx.feature_num;j++)
			{
				findex=c->fmap[vtx.fvector[j]+key%c->ysize];
				if(findex>=0)
				{
					res[findex]++;
				}
				findex=c->fmap[vtx.fvector[j]+vtx.key%c->ysize];
				if(findex>=0)
				{
					res[findex]--;
				}
			}
			if(i)
			{
				if(c->chain_type==SIMPLE_CHAIN)
				{
					findex=c->fmap[c->transit+key];
					if(findex>=0)
					{
						res[findex]++;
					}
					findex=c->fmap[c->transit+vtx.key];
					if(findex>=0)
					{
						res[findex]--;
					}
				}else if(c->chain_type==FIRST_CHAIN){
					edge &e=seq1.edges[i-1];
					for(j=0;j<e.feature_num;j++)
					{
						findex=c->fmap[e.fvector[j]+key];
						if(findex>=0)
						{
							res[findex]++;
						}
						findex=c->fmap[e.fvector[j]+vtx.key];
						if(findex>=0)
						{
							res[findex]--;
						}
					}
				}
			}
		}
		if(is_err){
			obj++;
			loss++;
		}
	}
	double r=0;
	map<int,double>::iterator it;
	for(it=res.begin();it!=res.end();it++)
	{
		loss+=c->lambda[it->first]*it->second;
		r+=it->second*it->second;
	}
	r=loss/r;
	if(r>c->sigma)
		r=c->sigma;
	for(it=res.begin();it!=res.end();it++)
	{
		c->lambda[it->first]-=r*it->second;
		c->gradient[it->first]-=r*it->second*times;
	}
}

void crf_thread::node_margin(sequence &seq, vector<vector<double> >&node_p, double &z)
{
	int i,j;
	node_p.resize(seq.node_num);
	for(i=0;i<seq.node_num;i++)
		node_p[i].resize(c->ysize);
	vector<int> first_cal(c->ysize*seq.node_num,1);
	for(i=0;i<seq.node_num;i++)
	{	
		int *cur_first=&first_cal[c->ysize*i];
		double *cur_p=&node_p[i][0];
		for(j=0;j<c->node_anum;j++)
		{
			int index = j % c->ysize;
			if(cur_first[index])
			{
				cur_first[index]=0;
				cur_p[index]=alpha[i*c->node_anum+j]+beta[i*c->node_anum+j];
			}else
				cur_p[index]=log_sum_exp(alpha[i*c->node_anum+j]+beta[i*c->node_anum+j],cur_p[index]);
		}
		for(j=0;j<c->ysize;j++)
			cur_p[j]=exp(cur_p[j]-z);
	}
}


void crf_thread::viterbi(sequence &seq)
{
	int i,j;
	int i1,j1,k1,i2,j2,k2;
	//last node: i1 th node, j1 th tag, k1 th best
	//current node: i2 th node, j2 th tag, k2 th best
	if(final_path.size()==0)
		final_path.resize(c->node_anum);
	fill(final_path.begin(),final_path.end(),0);
	last_best.clear();
	last_best.resize(c->node_anum);
	// i th tag, j th best: last_best[i][j]
	cur_best.clear();
	cur_best.resize(c->node_anum);
	best_prev.clear();
	best_prev.resize(seq.node_num+1);
	//best_prev of i th node j th tag, k th best: best_prev[i][j][k]
	best_link.clear();
	best_link.resize(seq.node_num+1);
	//index of the path from i th node j th tag, k th best to i-1 th node best_prev[i][j][k].first th tag, best_prev[i][j][k].second th best
	bst_path.clear();
	bst_path.resize(seq.node_num);
	best_path.clear();
	for(i=0;i<=seq.node_num;i++)
	{
		i2=i;
		//current node: i2 th node
		i1=i-1;
		//last node: i1 th node
		double *cur_path;
		if(i<seq.node_num)
		{
			best_prev[i].resize(c->node_anum);
			best_link[i].resize(c->path_num);
			cur_path=&path[c->path_num*i];
		}else{
			best_prev[i].resize(1);
			best_link[i].resize(1);
			cur_path=&final_path[0];
		}

		//search n-best path
		if(i>0)
		{
			last_best=cur_best;
			for(j=0;j<c->node_anum;j++)
				cur_best[j].clear();
			if(i==seq.node_num)
				cur_best.resize(1);
		}else{
			vector<double> init_best(1,0);
			last_best[0]=init_best;
		}
		int routine_num=i<seq.node_num?c->path_num:c->node_anum;
		for(j=0;j<routine_num;j++)
		{
			if(i<seq.node_num)
			{	
				j2 = j % c->node_anum;//current node, j2 th tag
				j1 = j / c->ysize;//last node, j1 th tag
			}else{
				j2 = 0;
				j1 = j;
			}
			for(k1=0;k1<last_best[j1].size();k1++)
			{

				double cost=last_best[j1][k1];
				cost+=cur_path[j];
				
				//last node : j1 th tag,  k1 th best
				int k_pos;
				vector_search(cur_best[j2],cost,k_pos,k2,inverse_cmp<double>());
				//current node : j2 th tag, k2 th best, now, search for k2
				if(k2<c->nbest)
				{
					vector_insert(cur_best[j2],cost,k2);
					pair<int,int> q=make_pair(j1,k1);
					vector_insert(best_prev[i2][j2], q ,k2);
					vector_insert(best_link[i2][j2], j, k2);
					//for current node, i.e. i2 th node, its j2 th tag, k2 th 
					//best previous is the j1 th tag, k1 th best of last node
					if(cur_best[j2].size()>c->nbest)//drop the nbest+1 th candidate
					{
						cur_best[j2].pop_back();
						best_prev[i2][j2].pop_back();
						best_link[i2][j2].pop_back();
					}
				}else{
					break;
				}
			}
		}
	}
	for(i=0;i<best_prev[seq.node_num][0].size();i++)
	{
		k2=i;
		j2=0;
		for(i2=seq.node_num;i2>0;i2--)
		{
			
			pair<int ,int> p=best_prev[i2][j2][k2];
			j2=p.first;
			k2=p.second;
			bst_path[i2-1]=best_link[i2-1][j2][k2] % c->ysize;
		}
		best_path.push_back(bst_path);
	}
}


void crf_thread::viterbi(sequence1 &seq1)
{
	int i,j;
	int i1,j1,k1,i2,j2,k2;
	//last node: i1 th node, j1 th tag, k1 th best
	//current node: i2 th node, j2 th tag, k2 th best
	if(final_path.size()==0)//initialize
		final_path.resize(c->ysize);
	fill(final_path.begin(),final_path.end(),0);
	last_best.clear();
	cur_best.clear();
	last_best.resize(c->ysize);
	cur_best.resize(c->ysize);
	// i th tag, j th best: last_best[i][j]
	best_prev.clear();
	best_prev.resize(seq1.vertex_num+1);
	//best_prev of i th node j th tag, k th best: best_prev[i][j][k]
	best_link.clear();
	best_link.resize(seq1.vertex_num+1);
	//index of the path from i th node j th tag, k th best to i-1 th node best_prev[i][j][k].first th tag, best_prev[i][j][k].second th best
	bst_path.clear();
	bst_path.resize(seq1.vertex_num);
	best_path.clear();
	for(i=0;i<=seq1.vertex_num;i++)
	{
		int cur_path_offset=i?(c->path_num+ c->ysize)*i-c->path_num:0;
		i2=i;
		//current node: i2 th node
		i1=i-1;
		//last node: i1 th node
		double *cur_path;
		if(i<seq1.vertex_num)
		{
			best_prev[i].resize(c->ysize);
			best_link[i].resize(c->path_num);
			cur_path=&path[cur_path_offset];
		}else{
			best_prev[i].resize(1);
			best_link[i].resize(1);
			cur_path=&final_path[0];
		}

		//search n-best path
		if(i>0)
		{
			last_best=cur_best;
			for(j=0;j<c->ysize;j++)
				cur_best[j].clear();
			if(i==seq1.vertex_num)
				cur_best.resize(1);
		}else{
			vector<double> init_best(1,0);
			last_best[0]=init_best;
		}
		int routine_num=i<seq1.vertex_num?c->path_num:c->ysize;
		for(j=0;j<routine_num;j++)
		{
			if(i<seq1.vertex_num)
			{	
				j2 = j % c->ysize;//current node, j2 th tag
				j1 = j / c->ysize;//last node, j1 th tag
			}else{
				j2 = 0;
				j1 = j;
			}
			for(k1=0;k1<last_best[j1].size();k1++)
			{
				double cost=last_best[j1][k1];
				if(i && i<seq1.vertex_num)
					cost+=cur_path[j+c->ysize];//edge weight
				cost+=cur_path[j%c->ysize];//node weight
				//last node : j1 th tag,  k1 th best
				int k_pos;
				vector_search(cur_best[j2],cost,k_pos,k2,inverse_cmp<double>());
				//current node : j2 th tag, k2 th best, now, search for k2
				if(k2<c->nbest)
				{
					vector_insert(cur_best[j2],cost,k2);
					pair<int,int> q=make_pair(j1,k1);
					vector_insert(best_prev[i2][j2], q ,k2);
					vector_insert(best_link[i2][j2], j, k2);
					//for current node, i.e. i2 th node, its j2 th tag, k2 th 
					//best previous is the j1 th tag, k1 th best of last node
					if(cur_best[j2].size()>c->nbest)//drop the nbest+1 th candidate
					{
						cur_best[j2].pop_back();
						best_prev[i2][j2].pop_back();
						best_link[i2][j2].pop_back();
					}
				}else{
					break;
				}
			}
		}
	}
	for(i=0;i<best_prev[seq1.vertex_num][0].size();i++)
	{
		k2=i;
		j2=0;
		for(i2=seq1.vertex_num;i2>0;i2--)
		{
			
			pair<int ,int> p=best_prev[i2][j2][k2];
			j2=p.first;
			k2=p.second;
			bst_path[i2-1]=best_link[i2-1][j2][k2] % c->ysize;
		}
		best_path.push_back(bst_path);
	}
}