TKroneckerLL Class Reference

!!!!! MYUNGHWAN, CHECK! More...

#include <kronecker.h>

Collaboration diagram for TKroneckerLL:

Public Member Functions
	TKroneckerLL ()
	TKroneckerLL (const PNGraph &GraphPt, const TFltV &ParamV, const double &PermPSwapNd=0.2)
	TKroneckerLL (const PNGraph &GraphPt, const TKronMtx &ParamMtx, const double &PermPSwapNd=0.2)
	TKroneckerLL (const PNGraph &GraphPt, const TKronMtx &ParamMtx, const TIntV &NodeIdPermV, const double &PermPSwapNd=0.2)
int	GetNodes () const
int	GetKronIters () const
PNGraph	GetGraph () const
void	SetGraph (const PNGraph &GraphPt)
const TKronMtx &	GetProbMtx () const
const TKronMtx &	GetLLMtx () const
int	GetParams () const
int	GetDim () const
void	SetDebug (const bool Debug)
const TFltV &	GetLLHist () const
const TVec< TKronMtx > &	GetParamHist () const
bool	IsObsNode (const int &NId) const
bool	IsObsEdge (const int &NId1, const int &NId2) const
bool	IsLatentNode (const int &NId) const
bool	IsLatentEdge (const int &NId1, const int &NId2) const
void	SetPerm (const char &PermId)
void	SetOrderPerm ()
void	SetRndPerm ()
void	SetDegPerm ()
void	SetBestDegPerm ()
	!!!!! MYUNGHWAN, CHECK! More...
void	SetPerm (const TIntV &NodePermV)
void	SetIPerm (const TIntV &Perm)
	!!!!! MYUNGHWAN, CHECK! More...
const TIntV &	GetPermV () const
void	AppendIsoNodes ()
void	RestoreGraph (const bool RestoreNodes=true)
	!!!!! MYUNGHWAN, CHECK! More...
double	GetFullGraphLL () const
double	GetFullRowLL (int RowId) const
double	GetFullColLL (int ColId) const
double	GetEmptyGraphLL () const
double	GetApxEmptyGraphLL () const
void	InitLL (const TFltV &ParamV)
void	InitLL (const TKronMtx &ParamMtx)
void	InitLL (const PNGraph &GraphPt, const TKronMtx &ParamMtx)
double	CalcGraphLL ()
double	CalcApxGraphLL ()
double	GetLL () const
double	GetAbsErr () const
double	NodeLLDelta (const int &NId) const
double	SwapNodesLL (const int &NId1, const int &NId2)
bool	SampleNextPerm (int &NId1, int &NId2)
double	GetEmptyGraphDLL (const int &ParamId) const
double	GetApxEmptyGraphDLL (const int &ParamId) const
const TFltV &	CalcGraphDLL ()
const TFltV &	CalcFullApxGraphDLL ()
const TFltV &	CalcApxGraphDLL ()
double	NodeDLLDelta (const int ParamId, const int &NId) const
void	UpdateGraphDLL (const int &SwapNId1, const int &SwapNId2)
const TFltV &	GetDLL () const
double	GetDLL (const int &ParamId) const
void	SampleGradient (const int &WarmUp, const int &NSamples, double &AvgLL, TFltV &GradV)
double	GradDescent (const int &NIter, const double &LrnRate, double MnStep, double MxStep, const int &WarmUp, const int &NSamples)
double	GradDescent2 (const int &NIter, const double &LrnRate, double MnStep, double MxStep, const int &WarmUp, const int &NSamples)
void	SetRandomEdges (const int &NEdges, const bool isDir=true)
	!!!!! MYUNGHWAN, CHECK! More...
void	MetroGibbsSampleSetup (const int &WarmUp)
void	MetroGibbsSampleNext (const int &WarmUp, const bool DLLUpdate=false)
void	RunEStep (const int &GibbsWarmUp, const int &WarmUp, const int &NSamples, TFltV &LLV, TVec< TFltV > &DLLV)
double	RunMStep (const TFltV &LLV, const TVec< TFltV > &DLLV, const int &GradIter, const double &LrnRate, double MnStep, double MxStep)
void	RunKronEM (const int &EMIter, const int &GradIter, double LrnRate, double MnStep, double MxStep, const int &GibbsWarmUp, const int &WarmUp, const int &NSamples, const TKronEMType &Type=kronNodeMiss, const int &NMissing=-1)
TFltV	TestSamplePerm (const TStr &OutFNm, const int &WarmUp, const int &NSamples, const TKronMtx &TrueMtx, const bool &DoPlot=true)
TFltQu	TestKronDescent (const bool &DoExact, const bool &TruePerm, double LearnRate, const int &WarmUp, const int &NSamples, const TKronMtx &TrueParam)
void	GradDescentConvergence (const TStr &OutFNm, const TStr &Desc1, const bool &SamplePerm, const int &NIters, double LearnRate, const int &WarmUp, const int &NSamples, const int &AvgKGraphs, const TKronMtx &TrueParam)

Static Public Member Functions
static PKroneckerLL	New ()
static PKroneckerLL	New (const PNGraph &GraphPt, const TKronMtx &ParamMtx, const double &PermPSwapNd=0.1)
static PKroneckerLL	New (const PNGraph &GraphPt, const TKronMtx &ParamMtx, const TIntV &NodeIdPermV, const double &PermPSwapNd=0.2)
static double	CalcChainR2 (const TVec< TFltV > &ChainLLV)
static void	ChainGelmapRubinPlot (const TVec< TFltV > &ChainLLV, const TStr &OutFNm, const TStr &Desc)
static void	TestBicCriterion (const TStr &OutFNm, const TStr &Desc1, const PNGraph &G, const int &GradIters, double LearnRate, const int &WarmUp, const int &NSamples, const int &TrueN0)
static void	TestGradDescent (const int &KronIters, const int &KiloSamples, const TStr &Permutation)

Private Attributes
TCRef	CRef
PNGraph	Graph
TInt	Nodes
TInt	KronIters
TFlt	PermSwapNodeProb
TIntTrV	GEdgeV
TIntTrV	LEdgeV
TInt	LSelfEdge
TIntV	NodePerm
TIntV	InvertPerm
TInt	RealNodes
TInt	RealEdges
TKronMtx	ProbMtx
TKronMtx	LLMtx
TFlt	LogLike
TFltV	GradV
TKronEMType	EMType
TInt	MissEdges
TBool	DebugMode
TFltV	LLV
TVec< TKronMtx >	MtxV

Friends
class	TPt< TKroneckerLL >

Detailed Description

!!!!! MYUNGHWAN, CHECK!

Definition at line 116 of file kronecker.h.

Constructor & Destructor Documentation

TKroneckerLL::TKroneckerLL ( )

inline

Definition at line 150 of file kronecker.h.

Referenced by New().

: Nodes(-1), KronIters(-1), PermSwapNodeProb(0.2), RealNodes(-1), RealEdges(-1), LogLike(TKronMtx::NInf), EMType(kronNodeMiss), MissEdges(-1), DebugMode(false) { }

Here is the caller graph for this function:

TKroneckerLL::TKroneckerLL	(	const PNGraph &	GraphPt,
		const TFltV &	ParamV,
		const double &	PermPSwapNd = 0.2
	)

Definition at line 783 of file kronecker.cpp.

References InitLL().

                                                                                                : PermSwapNodeProb(PermPSwapNd) {
  InitLL(GraphPt, TKronMtx(ParamV));
}

Here is the call graph for this function:

TKroneckerLL::TKroneckerLL	(	const PNGraph &	GraphPt,
		const TKronMtx &	ParamMtx,
		const double &	PermPSwapNd = 0.2
	)

Definition at line 787 of file kronecker.cpp.

References InitLL().

                                                                                                      : PermSwapNodeProb(PermPSwapNd) {
  InitLL(GraphPt, ParamMtx);
}

Here is the call graph for this function:

TKroneckerLL::TKroneckerLL	(	const PNGraph &	GraphPt,
		const TKronMtx &	ParamMtx,
		const TIntV &	NodeIdPermV,
		const double &	PermPSwapNd = 0.2
	)

Definition at line 791 of file kronecker.cpp.

References InitLL(), NodePerm, and SetIPerm().

                                                                                                                                : PermSwapNodeProb(PermPSwapNd) {
  InitLL(GraphPt, ParamMtx);
  NodePerm = NodeIdPermV;
  SetIPerm(NodePerm);
}

Here is the call graph for this function:

Member Function Documentation

void TKroneckerLL::AppendIsoNodes

(

)

Definition at line 914 of file kronecker.cpp.

References TNGraph::AddNode(), TKronMtx::GetDim(), TNGraph::GetNodes(), Graph, KronIters, Nodes, and ProbMtx.

Referenced by RunKronEM().

                                  {
  Nodes = (int) pow((double)ProbMtx.GetDim(), KronIters);
  // add nodes until filling the Kronecker graph model
  for (int nid = Graph->GetNodes(); nid < Nodes; nid++) {
          Graph->AddNode(nid);
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

const TFltV & TKroneckerLL::CalcApxGraphDLL

(

)

Definition at line 1194 of file kronecker.cpp.

References GetApxEmptyGraphDLL(), TKronMtx::GetApxNoEdgeDLL(), TKronMtx::GetEdgeDLL(), TNGraph::GetNI(), TNGraph::TNodeI::GetOutDeg(), TNGraph::TNodeI::GetOutNId(), GradV, Graph, KronIters, TKronMtx::Len(), LLMtx, NodePerm, and Nodes.

Referenced by GradDescentConvergence(), RunEStep(), RunMStep(), SampleGradient(), TestGradDescent(), TestKronDescent(), and TestSamplePerm().

                                           {
  for (int ParamId = 0; ParamId < LLMtx.Len(); ParamId++) {
    double DLL = GetApxEmptyGraphDLL(ParamId);
    for (int nid = 0; nid < Nodes; nid++) {
      const TNGraph::TNodeI Node = Graph->GetNI(nid);
      const int SrcNId = NodePerm[nid];
      for (int e = 0; e < Node.GetOutDeg(); e++) {
        const int DstNId = NodePerm[Node.GetOutNId(e)];
        DLL = DLL - LLMtx.GetApxNoEdgeDLL(ParamId, SrcNId, DstNId, KronIters)
          + LLMtx.GetEdgeDLL(ParamId, SrcNId, DstNId, KronIters);
      }
    }
    GradV[ParamId] = DLL;
  }
  return GradV;
}

Here is the call graph for this function:

Here is the caller graph for this function:

double TKroneckerLL::CalcApxGraphLL

(

)

Definition at line 1037 of file kronecker.cpp.

References GetApxEmptyGraphLL(), TKronMtx::GetApxNoEdgeLL(), TKronMtx::GetEdgeLL(), TNGraph::GetNI(), TNGraph::TNodeI::GetOutDeg(), TNGraph::TNodeI::GetOutNId(), Graph, KronIters, LLMtx, LogLike, NodePerm, and Nodes.

Referenced by GradDescentConvergence(), MetroGibbsSampleSetup(), RunEStep(), RunMStep(), SampleGradient(), TestGradDescent(), TestKronDescent(), and TestSamplePerm().

                                    {
  LogLike = GetApxEmptyGraphLL(); // O(N_0)
  for (int nid = 0; nid < Nodes; nid++) {
    const TNGraph::TNodeI Node = Graph->GetNI(nid);
    const int SrcNId = NodePerm[nid];
    for (int e = 0; e < Node.GetOutDeg(); e++) {
      const int DstNId = NodePerm[Node.GetOutNId(e)];
      LogLike = LogLike - LLMtx.GetApxNoEdgeLL(SrcNId, DstNId, KronIters)
        + LLMtx.GetEdgeLL(SrcNId, DstNId, KronIters);
    }
  }
  return LogLike;
}

Here is the call graph for this function:

Here is the caller graph for this function:

double TKroneckerLL::CalcChainR2 ( const TVec< TFltV > &  ChainLLV )

static

Definition at line 1895 of file kronecker.cpp.

References IAssert, TVec< TVal, TSizeTy >::Len(), McMcGetAvgAvg(), McMcGetAvgJ(), and TMath::Sqr().

Referenced by ChainGelmapRubinPlot().

                                                            {
  const double J = ChainLLV.Len();
  const double K = ChainLLV[0].Len();
  TFltV AvgJV;    McMcGetAvgJ(ChainLLV, AvgJV);
  double AvgAvg;  McMcGetAvgAvg(AvgJV, AvgAvg);
  IAssert(AvgJV.Len() == ChainLLV.Len());
  double InChainVar=0, OutChainVar=0;
  // between chain var
  for (int j = 0; j < AvgJV.Len(); j++) {
    OutChainVar += TMath::Sqr(AvgJV[j] - AvgAvg); }
  OutChainVar = OutChainVar * (K/double(J-1));
  printf("*** %g chains of len %g\n", J, K);
  printf("  ** between chain var: %f\n", OutChainVar);
  //within chain variance
  for (int j = 0; j < AvgJV.Len(); j++) {
    const TFltV& ChainV = ChainLLV[j];
    for (int k = 0; k < ChainV.Len(); k++) {
      InChainVar += TMath::Sqr(ChainV[k] - AvgJV[j]); }
  }
  InChainVar = InChainVar * 1.0/double(J*(K-1));
  printf("  ** within chain var: %f\n", InChainVar);
  const double PostVar = (K-1)/K * InChainVar + 1.0/K * OutChainVar;
  printf("  ** posterior var: %f\n", PostVar);
  const double ScaleRed = sqrt(PostVar/InChainVar);
  printf("  ** scale reduction (< 1.2): %f\n\n", ScaleRed);
  return ScaleRed;
}

Here is the call graph for this function:

Here is the caller graph for this function:

const TFltV & TKroneckerLL::CalcFullApxGraphDLL

(

)

Definition at line 1176 of file kronecker.cpp.

References TKronMtx::GetApxNoEdgeDLL(), TKronMtx::GetEdgeDLL(), GradV, Graph, TNGraph::IsEdge(), KronIters, TKronMtx::Len(), LLMtx, NodePerm, and Nodes.

                                               {
  for (int ParamId = 0; ParamId < LLMtx.Len(); ParamId++) {
    double DLL = 0.0;
    for (int NId1 = 0; NId1 < Nodes; NId1++) {
      for (int NId2 = 0; NId2 < Nodes; NId2++) {
        if (Graph->IsEdge(NId1, NId2)) {
          DLL += LLMtx.GetEdgeDLL(ParamId, NodePerm[NId1], NodePerm[NId2], KronIters);
        } else {
          DLL += LLMtx.GetApxNoEdgeDLL(ParamId, NodePerm[NId1], NodePerm[NId2], KronIters);
        }
      }
    }
    GradV[ParamId] = DLL;
  }
  return GradV;
}

Here is the call graph for this function:

const TFltV & TKroneckerLL::CalcGraphDLL

(

)

Definition at line 1158 of file kronecker.cpp.

References TKronMtx::GetEdgeDLL(), TKronMtx::GetNoEdgeDLL(), GradV, Graph, TNGraph::IsEdge(), KronIters, TKronMtx::Len(), LLMtx, NodePerm, and Nodes.

Referenced by TestKronDescent().

                                        {
  for (int ParamId = 0; ParamId < LLMtx.Len(); ParamId++) {
    double DLL = 0.0;
    for (int NId1 = 0; NId1 < Nodes; NId1++) {
      for (int NId2 = 0; NId2 < Nodes; NId2++) {
        if (Graph->IsEdge(NId1, NId2)) {
          DLL += LLMtx.GetEdgeDLL(ParamId, NodePerm[NId1], NodePerm[NId2], KronIters);
        } else {
          DLL += LLMtx.GetNoEdgeDLL(ParamId, NodePerm[NId1], NodePerm[NId2], KronIters);
        }
      }
    }
    GradV[ParamId] = DLL;
  }
  return GradV;
}

Here is the call graph for this function:

Here is the caller graph for this function:

double TKroneckerLL::CalcGraphLL

(

)

Definition at line 1022 of file kronecker.cpp.

References TKronMtx::GetEdgeLL(), GetEmptyGraphLL(), TNGraph::GetNI(), TKronMtx::GetNoEdgeLL(), TNGraph::TNodeI::GetOutDeg(), TNGraph::TNodeI::GetOutNId(), Graph, KronIters, LLMtx, LogLike, NodePerm, and Nodes.

Referenced by TestKronDescent().

                                 {
  LogLike = GetEmptyGraphLL(); // takes O(N^2)
  for (int nid = 0; nid < Nodes; nid++) {
    const TNGraph::TNodeI Node = Graph->GetNI(nid);
    const int SrcNId = NodePerm[nid];
    for (int e = 0; e < Node.GetOutDeg(); e++) {
      const int DstNId = NodePerm[Node.GetOutNId(e)];
      LogLike = LogLike - LLMtx.GetNoEdgeLL(SrcNId, DstNId, KronIters)
        + LLMtx.GetEdgeLL(SrcNId, DstNId, KronIters);
    }
  }
  return LogLike;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void TKroneckerLL::ChainGelmapRubinPlot ( const TVec< TFltV > &  ChainLLV, const TStr &  OutFNm, const TStr &  Desc  )

static

Definition at line 1924 of file kronecker.cpp.

References TVec< TVal, TSizeTy >::Add(), CalcChainR2(), TStr::CStr(), TStr::Fmt(), TVec< TVal, TSizeTy >::GetSubValV(), TVec< TVal, TSizeTy >::Len(), TMath::Mn(), and TGnuPlot::PlotValV().

                                                                                                         {
  TFltPrV LenR2V; // how does potential scale reduction chainge with chain length
  TVec<TFltV> SmallLLV(ChainLLV.Len());
  const int K = ChainLLV[0].Len();
  const int Buckets=1000;
  const int BucketSz = K/Buckets;
  for (int b = 1; b < Buckets; b++) {
    const int End = TMath::Mn(BucketSz*b, K-1);
    for (int c = 0; c < ChainLLV.Len(); c++) {
      ChainLLV[c].GetSubValV(0, End, SmallLLV[c]); }
    LenR2V.Add(TFltPr(End, TKroneckerLL::CalcChainR2(SmallLLV)));
  }
  LenR2V.Add(TFltPr(K, TKroneckerLL::CalcChainR2(ChainLLV)));
  TGnuPlot::PlotValV(LenR2V, TStr::Fmt("gelman-%s", OutFNm.CStr()), TStr::Fmt("%s. %d chains of len %d. BucketSz: %d.",
    Desc.CStr(), ChainLLV.Len(), ChainLLV[0].Len(), BucketSz), "Chain length", "Potential scale reduction");
}

Here is the call graph for this function:

double TKroneckerLL::GetAbsErr ( ) const

inline

Definition at line 205 of file kronecker.h.

References TNGraph::GetEdges(), and TKronMtx::GetMtxSum().

{ return fabs(pow((double)Graph->GetEdges(), 1.0/double(KronIters)) - ProbMtx.GetMtxSum()); }

Here is the call graph for this function:

double TKroneckerLL::GetApxEmptyGraphDLL

(

const int &

ParamId

)

const

Definition at line 1147 of file kronecker.cpp.

References TKronMtx::At(), KronIters, TKronMtx::Len(), ProbMtx, and TMath::Sqr().

Referenced by CalcApxGraphDLL().

                                                                 {
  double Sum=0.0, SumSq=0.0;
  for (int i = 0; i < ProbMtx.Len(); i++) {
    Sum += ProbMtx.At(i);
    SumSq += TMath::Sqr(ProbMtx.At(i));
  }
  // d/dx -sum(x_i) - 0.5sum(x_i^2) = d/dx sum(theta)^k - 0.5 sum(theta^2)^k
  return -KronIters*pow(Sum, KronIters-1) - KronIters*pow(SumSq, KronIters-1)*ProbMtx.At(ParamId);
}

Here is the call graph for this function:

Here is the caller graph for this function:

double TKroneckerLL::GetApxEmptyGraphLL

(

)

const

Definition at line 987 of file kronecker.cpp.

References TKronMtx::At(), KronIters, TKronMtx::Len(), ProbMtx, and TMath::Sqr().

Referenced by CalcApxGraphLL().

                                              {
  double Sum=0.0, SumSq=0.0;
  for (int i = 0; i < ProbMtx.Len(); i++) {
    Sum += ProbMtx.At(i);
    SumSq += TMath::Sqr(ProbMtx.At(i));
  }
  return -pow(Sum, KronIters) - 0.5*pow(SumSq, KronIters);
}

Here is the call graph for this function:

Here is the caller graph for this function:

int TKroneckerLL::GetDim ( ) const

inline

Definition at line 165 of file kronecker.h.

References TKronMtx::GetDim().

{ return ProbMtx.GetDim(); }

Here is the call graph for this function:

const TFltV& TKroneckerLL::GetDLL ( ) const

inline

Definition at line 218 of file kronecker.h.

References GradV.

{ return GradV; }

double TKroneckerLL::GetDLL ( const int &  ParamId ) const

inline

Definition at line 219 of file kronecker.h.

{ return GradV[ParamId]; }

double TKroneckerLL::GetEmptyGraphDLL

(

const int &

ParamId

)

const

Definition at line 1136 of file kronecker.cpp.

References TKronMtx::GetNoEdgeDLL(), KronIters, LLMtx, NodePerm, and Nodes.

                                                              {
  double DLL = 0.0;
  for (int NId1 = 0; NId1 < Nodes; NId1++) {
    for (int NId2 = 0; NId2 < Nodes; NId2++) {
      DLL += LLMtx.GetNoEdgeDLL(ParamId, NodePerm[NId1], NodePerm[NId2], KronIters);
    }
  }
  return DLL;
}

Here is the call graph for this function:

double TKroneckerLL::GetEmptyGraphLL

(

)

const

Definition at line 976 of file kronecker.cpp.

References TKronMtx::GetNodes(), TKronMtx::GetNoEdgeLL(), KronIters, and LLMtx.

Referenced by CalcGraphLL().

                                           {
  double LL = 0;
  for (int NId1 = 0; NId1 < LLMtx.GetNodes(KronIters); NId1++) {
    for (int NId2 = 0; NId2 < LLMtx.GetNodes(KronIters); NId2++) {
      LL = LL + LLMtx.GetNoEdgeLL(NId1, NId2, KronIters);
    }
  }
  return LL;
}

Here is the call graph for this function:

Here is the caller graph for this function:

double TKroneckerLL::GetFullColLL

(

int

ColId

)

const

Definition at line 966 of file kronecker.cpp.

References TKronMtx::GetColSum(), TKronMtx::GetDim(), KronIters, and LLMtx.

                                                 {
  double ColLL = 0.0;
  const int MtxDim = LLMtx.GetDim();
  for (int level = 0; level < KronIters; level++) {
    ColLL += LLMtx.GetColSum(ColId % MtxDim);
    ColId /= MtxDim;
  }
  return ColLL;
}

Here is the call graph for this function:

double TKroneckerLL::GetFullGraphLL

(

)

const

Definition at line 943 of file kronecker.cpp.

References TKronMtx::GetDim(), TKronMtx::GetMtxSum(), KronIters, LLMtx, and TMath::Power().

                                          {
  // the number of times a seed matrix element appears in
  // the full kronecker adjacency matrix after KronIter
  // kronecker multiplications
  double ElemCnt = 1;
  const double dim = LLMtx.GetDim();
  // count number of times x appears in the full kronecker matrix
  for (int i = 1; i < KronIters; i++) {
    ElemCnt = dim*dim*ElemCnt + TMath::Power(dim, 2*i);
  }
  return ElemCnt * LLMtx.GetMtxSum();
}

Here is the call graph for this function:

double TKroneckerLL::GetFullRowLL

(

int

RowId

)

const

Definition at line 956 of file kronecker.cpp.

References TKronMtx::GetDim(), TKronMtx::GetRowSum(), KronIters, and LLMtx.

                                                 {
  double RowLL = 0.0;
  const int MtxDim = LLMtx.GetDim();
  for (int level = 0; level < KronIters; level++) {
    RowLL += LLMtx.GetRowSum(RowId % MtxDim);
    RowId /= MtxDim;
  }
  return RowLL;
}

Here is the call graph for this function:

PNGraph TKroneckerLL::GetGraph ( ) const

inline

Definition at line 160 of file kronecker.h.

References Graph.

{ return Graph; }

int TKroneckerLL::GetKronIters ( ) const

inline

Definition at line 159 of file kronecker.h.

References KronIters.

Referenced by TestBicCriterion().

{ return KronIters; }

Here is the caller graph for this function:

double TKroneckerLL::GetLL ( ) const

inline

Definition at line 204 of file kronecker.h.

References LogLike.

Referenced by SampleGradient(), and TestSamplePerm().

{ return LogLike; }

Here is the caller graph for this function:

const TFltV& TKroneckerLL::GetLLHist ( ) const

inline

Definition at line 168 of file kronecker.h.

References LLV.

{ return LLV; }

const TKronMtx& TKroneckerLL::GetLLMtx ( ) const

inline

Definition at line 163 of file kronecker.h.

References LLMtx.

{ return LLMtx; }

int TKroneckerLL::GetNodes ( ) const

inline

Definition at line 158 of file kronecker.h.

References Nodes.

{ return Nodes; }

const TVec<TKronMtx>& TKroneckerLL::GetParamHist ( ) const

inline

Definition at line 169 of file kronecker.h.

References MtxV.

{ return MtxV; }

int TKroneckerLL::GetParams ( ) const

inline

Definition at line 164 of file kronecker.h.

References TKronMtx::Len().

Referenced by GradDescent(), GradDescent2(), GradDescentConvergence(), RunMStep(), TestKronDescent(), and TestSamplePerm().

{ return ProbMtx.Len(); }

Here is the call graph for this function:

Here is the caller graph for this function:

const TIntV& TKroneckerLL::GetPermV ( ) const

inline

Definition at line 185 of file kronecker.h.

References NodePerm.

{ return NodePerm; }

const TKronMtx& TKroneckerLL::GetProbMtx ( ) const

inline

Definition at line 162 of file kronecker.h.

References ProbMtx.

{ return ProbMtx; }

double TKroneckerLL::GradDescent	(	const int &	NIter,
		const double &	LrnRate,
		double	MnStep,
		double	MxStep,
		const int &	WarmUp,
		const int &	NSamples
	)

!!!!! MYUNGHWAN, CHECK!

!!!!! MYUNGHWAN, CHECK!

Definition at line 1299 of file kronecker.cpp.

References TVec< TVal, TSizeTy >::Add(), TKronMtx::At(), DebugMode, TKronMtx::Dump(), TVec< TVal, TSizeTy >::Gen(), TKronMtx::GetEdges(), TNGraph::GetEdges(), TKronMtx::GetLLMtx(), TKronMtx::GetMtxSum(), TKronMtx::GetNodes(), TNGraph::GetNodes(), GetParams(), Graph, KronIters, LLMtx, LLV, MtxV, ProbMtx, and SampleGradient().

Referenced by TestBicCriterion().

                                                                                                                                              {
  printf("\n----------------------------------------------------------------------\n");
  printf("Fitting graph on %d nodes, %d edges\n", Graph->GetNodes(), Graph->GetEdges());
  printf("Kron iters:  %d (== %d nodes)\n\n", KronIters(), ProbMtx.GetNodes(KronIters()));
  TExeTm IterTm, TotalTm;
  double OldLL=-1e10, CurLL=0;
  const double EZero = pow((double) Graph->GetEdges(), 1.0/double(KronIters));
  TFltV CurGradV, LearnRateV(GetParams()), LastStep(GetParams());
  LearnRateV.PutAll(LrnRate);
  TKronMtx NewProbMtx = ProbMtx;

  if(DebugMode) {  
          LLV.Gen(NIter, 0);
          MtxV.Gen(NIter, 0);
  }

  for (int Iter = 0; Iter < NIter; Iter++) {
    printf("%03d] ", Iter);
    SampleGradient(WarmUp, NSamples, CurLL, CurGradV);
    for (int p = 0; p < GetParams(); p++) {
      LearnRateV[p] *= 0.95;
      if (Iter < 1) {
        while (fabs(LearnRateV[p]*CurGradV[p]) > MxStep) { LearnRateV[p] *= 0.95; }
        while (fabs(LearnRateV[p]*CurGradV[p]) < 0.02) { LearnRateV[p] *= (1.0/0.95); } // move more
      } else {
        // set learn rate so that move for each parameter is inside the [MnStep, MxStep]
        while (fabs(LearnRateV[p]*CurGradV[p]) > MxStep) { LearnRateV[p] *= 0.95; printf(".");}
        while (fabs(LearnRateV[p]*CurGradV[p]) < MnStep) { LearnRateV[p] *= (1.0/0.95); printf("*");}
        if (MxStep > 3*MnStep) { MxStep *= 0.95; }
      }
      NewProbMtx.At(p) = ProbMtx.At(p) + LearnRateV[p]*CurGradV[p];
      if (NewProbMtx.At(p) > 0.9999) { NewProbMtx.At(p)=0.9999; }
      if (NewProbMtx.At(p) < 0.0001) { NewProbMtx.At(p)=0.0001; }
    }
    printf("  trueE0: %.2f (%d),  estE0: %.2f (%d),  ERR: %f\n", EZero, Graph->GetEdges(),
      ProbMtx.GetMtxSum(), ProbMtx.GetEdges(KronIters), fabs(EZero-ProbMtx.GetMtxSum()));
    printf("  currLL: %.4f, deltaLL: %.4f\n", CurLL, CurLL-OldLL); // positive is good
    for (int p = 0; p < GetParams(); p++) {
      printf("    %d]  %f  <--  %f + %9f   Grad: %9.1f   Rate: %g\n", p, NewProbMtx.At(p),
        ProbMtx.At(p), (double)(LearnRateV[p]*CurGradV[p]), CurGradV[p](), LearnRateV[p]());
    }
    if (Iter+1 < NIter) { // skip last update
      ProbMtx = NewProbMtx;  ProbMtx.GetLLMtx(LLMtx); }
    OldLL=CurLL;
    printf("\n");  fflush(stdout);

        if(DebugMode) {  
                LLV.Add(CurLL);
                MtxV.Add(NewProbMtx);
        }
  }
  printf("TotalExeTm: %s %g\n", TotalTm.GetStr(), TotalTm.GetSecs());
  ProbMtx.Dump("FITTED PARAMS", false);
  return CurLL;
}

Here is the call graph for this function:

Here is the caller graph for this function:

double TKroneckerLL::GradDescent2	(	const int &	NIter,
		const double &	LrnRate,
		double	MnStep,
		double	MxStep,
		const int &	WarmUp,
		const int &	NSamples
	)

Definition at line 1355 of file kronecker.cpp.

References TKronMtx::At(), TKronMtx::Dump(), TKronMtx::GetEdges(), TNGraph::GetEdges(), TKronMtx::GetLLMtx(), TKronMtx::GetMtxSum(), TKronMtx::GetNodes(), TNGraph::GetNodes(), GetParams(), Graph, KronIters, LLMtx, ProbMtx, and SampleGradient().

                                                                                                                                               {
  printf("\n----------------------------------------------------------------------\n");
  printf("GradDescent2\n");
  printf("Fitting graph on %d nodes, %d edges\n", Graph->GetNodes(), Graph->GetEdges());
  printf("Skip moves that make likelihood smaller\n");
  printf("Kron iters:  %d (== %d nodes)\n\n", KronIters(), ProbMtx.GetNodes(KronIters()));
  TExeTm IterTm, TotalTm;
  double CurLL=0, NewLL=0;
  const double EZero = pow((double) Graph->GetEdges(), 1.0/double(KronIters));
  TFltV CurGradV, NewGradV, LearnRateV(GetParams()), LastStep(GetParams());
  LearnRateV.PutAll(LrnRate);
  TKronMtx NewProbMtx=ProbMtx, CurProbMtx=ProbMtx;
  bool GoodMove = false;
  // Start
  for (int Iter = 0; Iter < NIter; Iter++) {
    printf("%03d] ", Iter);
    if (! GoodMove) { SampleGradient(WarmUp, NSamples, CurLL, CurGradV); }
    CurProbMtx = ProbMtx;
    // update parameters
    for (int p = 0; p < GetParams(); p++) {
      while (fabs(LearnRateV[p]*CurGradV[p]) > MxStep) { LearnRateV[p] *= 0.95; printf(".");}
      while (fabs(LearnRateV[p]*CurGradV[p]) < MnStep) { LearnRateV[p] *= (1.0/0.95); printf("*");}
      NewProbMtx.At(p) = CurProbMtx.At(p) + LearnRateV[p]*CurGradV[p];
      if (NewProbMtx.At(p) > 0.9999) { NewProbMtx.At(p)=0.9999; }
      if (NewProbMtx.At(p) < 0.0001) { NewProbMtx.At(p)=0.0001; }
      LearnRateV[p] *= 0.95;
    }
    printf("  ");
    ProbMtx=NewProbMtx;  ProbMtx.GetLLMtx(LLMtx);
    SampleGradient(WarmUp, NSamples, NewLL, NewGradV);
    if (NewLL > CurLL) { // accept the move
      printf("== Good move:\n");
      printf("  trueE0: %.2f (%d),  estE0: %.2f (%d),  ERR: %f\n", EZero, Graph->GetEdges(),
        ProbMtx.GetMtxSum(), ProbMtx.GetEdges(KronIters), fabs(EZero-ProbMtx.GetMtxSum()));
      printf("  currLL: %.4f  deltaLL: %.4f\n", CurLL, NewLL-CurLL); // positive is good
      for (int p = 0; p < GetParams(); p++) {
        printf("    %d]  %f  <--  %f + %9f   Grad: %9.1f   Rate: %g\n", p, NewProbMtx.At(p),
          CurProbMtx.At(p), (double)(LearnRateV[p]*CurGradV[p]), CurGradV[p](), LearnRateV[p]()); }
      CurLL = NewLL;
      CurGradV = NewGradV;
      GoodMove = true;
    } else {
      printf("** BAD move:\n");
      printf("  *trueE0: %.2f (%d),  estE0: %.2f (%d),  ERR: %f\n", EZero, Graph->GetEdges(),
        ProbMtx.GetMtxSum(), ProbMtx.GetEdges(KronIters), fabs(EZero-ProbMtx.GetMtxSum()));
      printf("  *curLL:  %.4f  deltaLL: %.4f\n", CurLL, NewLL-CurLL); // positive is good
      for (int p = 0; p < GetParams(); p++) {
        printf("   b%d]  %f  <--  %f + %9f   Grad: %9.1f   Rate: %g\n", p, NewProbMtx.At(p),
          CurProbMtx.At(p), (double)(LearnRateV[p]*CurGradV[p]), CurGradV[p](), LearnRateV[p]()); }
      // move to old position
      ProbMtx = CurProbMtx;  ProbMtx.GetLLMtx(LLMtx);
      GoodMove = false;
    }
    printf("\n");  fflush(stdout);
  }
  printf("TotalExeTm: %s %g\n", TotalTm.GetStr(), TotalTm.GetSecs());
  ProbMtx.Dump("FITTED PARAMS\n", false);
  return CurLL;
}

Here is the call graph for this function:

void TKroneckerLL::GradDescentConvergence	(	const TStr &	OutFNm,
		const TStr &	Desc1,
		const bool &	SamplePerm,
		const int &	NIters,
		double	LearnRate,
		const int &	WarmUp,
		const int &	NSamples,
		const int &	AvgKGraphs,
		const TKronMtx &	TrueParam
	)

Definition at line 2017 of file kronecker.cpp.

References TVec< TVal, TSizeTy >::Add(), TKronMtx::At(), CalcApxGraphDLL(), CalcApxGraphLL(), TVec< TVal, TSizeTy >::Clr(), TStr::CStr(), TKronMtx::Dump(), TKronMtx::Empty(), TStr::Empty(), TStr::Fmt(), TKronMtx::GenFastKronecker(), TSnap::GetAnfEffDiam(), TKronMtx::GetAvgAbsErr(), TKronMtx::GetEdges(), TNGraph::GetEdges(), TKronMtx::GetLLMtx(), TKronMtx::GetMtxSum(), TKronMtx::GetNodes(), TNGraph::GetNodes(), GetParams(), TExeTm::GetSecs(), TSnap::GetSngVals(), TExeTm::GetTmStr(), GradV, Graph, InitLL(), KronIters, LLMtx, LogLike, PlotTrueAndEst(), ProbMtx, TVec< TVal, TSizeTy >::PutAll(), SampleGradient(), SetDegPerm(), SetOrderPerm(), and TVec< TVal, TSizeTy >::Sort().

                                                                                                             {
  TExeTm IterTm;
  int Iter;
  double OldLL=0, MyLL=0, AvgAbsErr=0, AbsSumErr=0;
  TFltV MyGradV, SDevV;
  TFltV LearnRateV(GetParams());  LearnRateV.PutAll(LearnRate);
  TFltPrV EZeroV, DiamV, Lambda1V, Lambda2V, AvgAbsErrV, AvgLLV;
  TFltPrV TrueEZeroV, TrueDiamV, TrueLambda1V, TrueLambda2V, TrueLLV;
  TFltV SngValV;  TSnap::GetSngVals(Graph, 2, SngValV);  SngValV.Sort(false);
  const double TrueEZero = pow((double) Graph->GetEdges(), 1.0/double(KronIters));
  const double TrueEffDiam = TSnap::GetAnfEffDiam(Graph, false, 10);
  const double TrueLambda1 = SngValV[0];
  const double TrueLambda2 = SngValV[1];
  if (! TrueParam.Empty()) {
    const TKronMtx CurParam = ProbMtx;  ProbMtx.Dump();
    InitLL(TrueParam);  SetOrderPerm();  CalcApxGraphLL(); printf("TrueLL: %f\n", LogLike());
    OldLL = LogLike;  InitLL(CurParam);
  }
  const double TrueLL = OldLL;
  if (! SamplePerm) { SetOrderPerm(); } else { SetDegPerm(); }
  for (Iter = 0; Iter < NIters; Iter++) {
    if (! SamplePerm) {
      // don't sample over permutations
      CalcApxGraphDLL();  CalcApxGraphLL();   // fast
      MyLL = LogLike;  MyGradV = GradV;
    } else {
      // sample over permutations (approximate calculations)
      SampleGradient(WarmUp, NSamples, MyLL, MyGradV);
    }
    double SumDiam=0, SumSngVal1=0, SumSngVal2=0;
    for (int trial = 0; trial < AvgKGraphs; trial++) {
      // generate kronecker graph
      PNGraph KronGraph = TKronMtx::GenFastKronecker(ProbMtx, KronIters, true, 0); // approx
      //PNGraph KronGraph = TKronMtx::GenKronecker(ProbMtx, KronIters, true, 0); // true
      SngValV.Clr(true);  TSnap::GetSngVals(KronGraph, 2, SngValV);  SngValV.Sort(false);
      SumDiam += TSnap::GetAnfEffDiam(KronGraph, false, 10);
      SumSngVal1 += SngValV[0];  SumSngVal2 += SngValV[1];
    }
    // how good is the current fit
    AvgLLV.Add(TFltPr(Iter, MyLL));
    EZeroV.Add(TFltPr(Iter, ProbMtx.GetMtxSum()));
    DiamV.Add(TFltPr(Iter, SumDiam/double(AvgKGraphs)));
    Lambda1V.Add(TFltPr(Iter, SumSngVal1/double(AvgKGraphs)));
    Lambda2V.Add(TFltPr(Iter, SumSngVal2/double(AvgKGraphs)));
    TrueLLV.Add(TFltPr(Iter, TrueLL));
    TrueEZeroV.Add(TFltPr(Iter, TrueEZero));
    TrueDiamV.Add(TFltPr(Iter, TrueEffDiam));
    TrueLambda1V.Add(TFltPr(Iter, TrueLambda1));
    TrueLambda2V.Add(TFltPr(Iter, TrueLambda2));
    if (Iter % 10 == 0) {
      const TStr Desc = TStr::Fmt("%s. Iter: %d, G(%d, %d)  K(%d, %d)", Desc1.Empty()?OutFNm.CStr():Desc1.CStr(),
        Iter, Graph->GetNodes(), Graph->GetEdges(), ProbMtx.GetNodes(KronIters), ProbMtx.GetEdges(KronIters));
      PlotTrueAndEst("LL."+OutFNm, Desc, "Average LL", AvgLLV, TrueLLV);
      PlotTrueAndEst("E0."+OutFNm, Desc, "E0 (expected number of edges)", EZeroV, TrueEZeroV);
      PlotTrueAndEst("Diam."+OutFNm+"-Diam", Desc, "Effective diameter", DiamV, TrueDiamV);
      PlotTrueAndEst("Lambda1."+OutFNm, Desc, "Lambda 1", Lambda1V, TrueLambda1V);
      PlotTrueAndEst("Lambda2."+OutFNm, Desc, "Lambda 2", Lambda2V, TrueLambda2V);
      if (! TrueParam.Empty()) {
        PlotTrueAndEst("AbsErr."+OutFNm, Desc, "Average Absolute Error", AvgAbsErrV, TFltPrV()); }
    }
    if (! TrueParam.Empty()) {
      AvgAbsErr = TKronMtx::GetAvgAbsErr(ProbMtx, TrueParam);
      AvgAbsErrV.Add(TFltPr(Iter, AvgAbsErr));
    } else { AvgAbsErr = 1.0; }
    // update parameters
    AbsSumErr = fabs(ProbMtx.GetMtxSum() - TrueEZero);
    // update parameters
    for (int p = 0; p < GetParams(); p++) {
      LearnRateV[p] *= 0.99;
      while (fabs(LearnRateV[p]*MyGradV[p]) > 0.1) { LearnRateV[p] *= 0.99; printf(".");}
      while (fabs(LearnRateV[p]*MyGradV[p]) < 0.002) { LearnRateV[p] *= (1.0/0.95); printf("*");}
      printf("    %d]  %f  <--  %f + %9f   Grad: %9.1f,  Rate:%g\n", p, ProbMtx.At(p) + LearnRateV[p]*MyGradV[p],
        ProbMtx.At(p), (double)(LearnRateV[p]*MyGradV[p]), MyGradV[p](), LearnRateV[p]());
      ProbMtx.At(p) = ProbMtx.At(p) + LearnRateV[p]*MyGradV[p];
      // box constraints
      if (ProbMtx.At(p) > 1.0) { ProbMtx.At(p)=1.0; }
      if (ProbMtx.At(p) < 0.001) { ProbMtx.At(p)=0.001; }
    }
    printf("%d] LL: %g, ", Iter, MyLL);
    printf("  avgAbsErr: %.4f, absSumErr: %.4f, newLL: %.2f, deltaLL: %.2f\n", AvgAbsErr, AbsSumErr, MyLL, OldLL-MyLL);
    if (AvgAbsErr < 0.001) { printf("***CONVERGED!\n");  break; }
    printf("\n");  fflush(stdout);
    ProbMtx.GetLLMtx(LLMtx);  OldLL = MyLL;
  }
  TrueParam.Dump("True  Thetas", true);
  ProbMtx.Dump("Final Thetas", true);
  printf("  AvgAbsErr: %f\n  AbsSumErr: %f\n  Iterations: %d\n", AvgAbsErr, AbsSumErr, Iter);
  printf("Iteration run time: %s, sec: %g\n\n", IterTm.GetTmStr(), IterTm.GetSecs());
}

Here is the call graph for this function:

void TKroneckerLL::InitLL

(

const TFltV &

ParamV

)

Definition at line 996 of file kronecker.cpp.

Referenced by GradDescentConvergence(), TestSamplePerm(), and TKroneckerLL().

                                             {
  InitLL(TKronMtx(ParamV));
}

Here is the caller graph for this function:

void TKroneckerLL::InitLL

(

const TKronMtx &

ParamMtx

)

Definition at line 1000 of file kronecker.cpp.

References TVec< TVal, TSizeTy >::Gen(), TKronMtx::GetLLMtx(), GradV, IAssert, TKronMtx::IsProbMtx(), TVec< TVal, TSizeTy >::Len(), LLMtx, LogLike, TKronMtx::NInf, ProbMtx, and TVec< TVal, TSizeTy >::PutAll().

                                                  {
  IAssert(ParamMtx.IsProbMtx());
  ProbMtx = ParamMtx;
  ProbMtx.GetLLMtx(LLMtx);
  LogLike = TKronMtx::NInf;
  if (GradV.Len() != ProbMtx.Len()) {
    GradV.Gen(ProbMtx.Len()); }
  GradV.PutAll(0.0);
}

Here is the call graph for this function:

void TKroneckerLL::InitLL	(	const PNGraph &	GraphPt,
		const TKronMtx &	ParamMtx
	)

Definition at line 1010 of file kronecker.cpp.

References TVec< TVal, TSizeTy >::Gen(), TKronMtx::GetLLMtx(), GradV, IAssert, TKronMtx::IsProbMtx(), TVec< TVal, TSizeTy >::Len(), LLMtx, LogLike, TKronMtx::NInf, ProbMtx, TVec< TVal, TSizeTy >::PutAll(), and SetGraph().

                                                                          {
  IAssert(ParamMtx.IsProbMtx());
  ProbMtx = ParamMtx;
  ProbMtx.GetLLMtx(LLMtx);
  SetGraph(GraphPt);
  LogLike = TKronMtx::NInf;
  if (GradV.Len() != ProbMtx.Len()) {
    GradV.Gen(ProbMtx.Len()); }
  GradV.PutAll(0.0);
}

Here is the call graph for this function:

bool TKroneckerLL::IsLatentEdge ( const int &  NId1, const int &  NId2  ) const

inline

Definition at line 175 of file kronecker.h.

References IsObsEdge().

{ return !IsObsEdge(NId1, NId2);        }

Here is the call graph for this function:

bool TKroneckerLL::IsLatentNode ( const int &  NId ) const

inline

Definition at line 174 of file kronecker.h.

References IsObsNode().

{ return !IsObsNode(NId);       }

Here is the call graph for this function:

bool TKroneckerLL::IsObsEdge ( const int &  NId1, const int &  NId2  ) const

inline

Definition at line 173 of file kronecker.h.

References IAssert.

Referenced by IsLatentEdge(), and SetRandomEdges().

{ IAssert(RealNodes > 0);       return ((NId1 < RealNodes) && (NId2 < RealNodes));      }

Here is the caller graph for this function:

bool TKroneckerLL::IsObsNode ( const int &  NId ) const

inline

Definition at line 172 of file kronecker.h.

References IAssert.

Referenced by IsLatentNode().

{ IAssert(RealNodes > 0);       return (NId < RealNodes);       }

Here is the caller graph for this function:

void TKroneckerLL::MetroGibbsSampleNext	(	const int &	WarmUp,
		const bool	DLLUpdate = false
	)

Definition at line 1503 of file kronecker.cpp.

References TNGraph::DelEdge(), TVec< TVal, TSizeTy >::DelLast(), GEdgeV, TKronMtx::GetApxNoEdgeDLL(), TKronMtx::GetApxNoEdgeLL(), TKronMtx::GetEdgeDLL(), TKronMtx::GetEdgeLL(), TRnd::GetUniDevInt(), GradV, Graph, IAssertR, KronIters, TVec< TVal, TSizeTy >::Last(), LEdgeV, TKronMtx::Len(), TVec< TVal, TSizeTy >::Len(), LLMtx, LogLike, LSelfEdge, SampleNextPerm(), SetRandomEdges(), UpdateGraphDLL(), TTriple< TVal1, TVal2, TVal3 >::Val1, TTriple< TVal1, TVal2, TVal3 >::Val2, and TTriple< TVal1, TVal2, TVal3 >::Val3.

Referenced by RunEStep(), and RunMStep().

                                                                               {
        int NId1 = 0, NId2 = 0, hit = 0, GId = 0;
        TIntTr EdgeToRemove, NewEdge;
        double RndAccept;

        if(LEdgeV.Len()) {
                for(int i = 0; i < WarmUp; i++) {
                        hit = TKronMtx::Rnd.GetUniDevInt(LEdgeV.Len());

                        NId1 = LEdgeV[hit].Val1;        NId2 = LEdgeV[hit].Val2;
                        GId = LEdgeV[hit].Val3;
                        SetRandomEdges(1, true);
                        NewEdge = LEdgeV.Last();

                        RndAccept = (1.0 - exp(LLMtx.GetEdgeLL(NewEdge.Val1, NewEdge.Val2, KronIters))) / (1.0 - exp(LLMtx.GetEdgeLL(NId1, NId2, KronIters)));
                        RndAccept = (RndAccept > 1.0) ? 1.0 : RndAccept;

                        if(TKronMtx::Rnd.GetUniDev() > RndAccept) { //  reject
                                Graph->DelEdge(NewEdge.Val1, NewEdge.Val2);
                                if(NewEdge.Val1 != NewEdge.Val2) {      GEdgeV.DelLast();       }
                                else {  LSelfEdge--;    }
                                LEdgeV.DelLast();
                        } else {        //      accept
                                Graph->DelEdge(NId1, NId2);
                                LEdgeV[hit] = LEdgeV.Last();
                                LEdgeV.DelLast();
                                if(NId1 == NId2) {
                                        LSelfEdge--;
                                        if(NewEdge.Val1 != NewEdge.Val2) {
                                                GEdgeV[GEdgeV.Len()-1].Val3 = hit;
                                        }
                                } else {
                                        IAssertR(GEdgeV.Last().Val3 >= 0, "Invalid indexing");

                                        GEdgeV[GId] = GEdgeV.Last();
                                        if(NewEdge.Val1 != NewEdge.Val2) {
                                                GEdgeV[GId].Val3 = hit;
                                        }
                                        LEdgeV[GEdgeV[GId].Val3].Val3 = GId;
                                        GEdgeV.DelLast();
                                }

                        LogLike += LLMtx.GetApxNoEdgeLL(EdgeToRemove.Val1, EdgeToRemove.Val2, KronIters) - LLMtx.GetEdgeLL(EdgeToRemove.Val1, EdgeToRemove.Val2, KronIters);
                        LogLike += -LLMtx.GetApxNoEdgeLL(NewEdge.Val1, NewEdge.Val2, KronIters) + LLMtx.GetEdgeLL(NewEdge.Val1, NewEdge.Val2, KronIters);

                                if(DLLUpdate) {
                                        for (int p = 0; p < LLMtx.Len(); p++) {
                                                GradV[p] += LLMtx.GetApxNoEdgeDLL(p, EdgeToRemove.Val1, EdgeToRemove.Val2, KronIters) - LLMtx.GetEdgeDLL(p, EdgeToRemove.Val1, EdgeToRemove.Val2, KronIters);
                                                GradV[p] += -LLMtx.GetApxNoEdgeDLL(p, NewEdge.Val1, NewEdge.Val2, KronIters) + LLMtx.GetEdgeDLL(p, NewEdge.Val1, NewEdge.Val2, KronIters);
                                        }
                                }
                        }
                }
        }

//      CalcApxGraphLL();
        for (int s = 0; s < WarmUp; s++) {
                if(SampleNextPerm(NId1, NId2)) {
                        if(DLLUpdate)   UpdateGraphDLL(NId1, NId2);
                }
        }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void TKroneckerLL::MetroGibbsSampleSetup

(

const int &

WarmUp

)

Definition at line 1476 of file kronecker.cpp.

References CalcApxGraphLL(), EMType, TKronMtx::GetDim(), TKronMtx::GetMtxSum(), kronEdgeMiss, kronFutureLink, KronIters, MissEdges, Nodes, ProbMtx, RealNodes, RestoreGraph(), SampleNextPerm(), and SetRandomEdges().

Referenced by RunEStep().

                                                          {
        double alpha = log(ProbMtx.GetMtxSum()) / log(double(ProbMtx.GetDim()));
        int NId1 = 0, NId2 = 0;
        int NMissing;

        RestoreGraph(false);
        if(EMType == kronEdgeMiss) {
                CalcApxGraphLL();
                for (int s = 0; s < WarmUp; s++)        SampleNextPerm(NId1, NId2);
        }

        if(EMType == kronFutureLink) {
                NMissing = (int) (pow(ProbMtx.GetMtxSum(), KronIters) - pow(double(RealNodes), alpha));
        } else if(EMType == kronEdgeMiss) {
                NMissing = MissEdges;
        } else {
                NMissing = (int) (pow(ProbMtx.GetMtxSum(), KronIters) * (1.0 - pow(double(RealNodes) / double(Nodes), 2)));
        }
        NMissing = (NMissing < 1) ? 1 : NMissing;

        SetRandomEdges(NMissing, true);

        CalcApxGraphLL();
        for (int s = 0; s < WarmUp; s++)        SampleNextPerm(NId1, NId2);
}

Here is the call graph for this function:

Here is the caller graph for this function:

static PKroneckerLL TKroneckerLL::New ( )

inlinestatic

Definition at line 154 of file kronecker.h.

References TKroneckerLL().

{ return new TKroneckerLL(); }

Here is the call graph for this function:

PKroneckerLL TKroneckerLL::New ( const PNGraph &  GraphPt, const TKronMtx &  ParamMtx, const double &  PermPSwapNd = 0.1  )

static

Definition at line 797 of file kronecker.cpp.

References TKroneckerLL().

                                                                                                          {
  return new TKroneckerLL(GraphPt, ParamMtx, PermPSwapNd);
}

Here is the call graph for this function:

PKroneckerLL TKroneckerLL::New ( const PNGraph &  GraphPt, const TKronMtx &  ParamMtx, const TIntV &  NodeIdPermV, const double &  PermPSwapNd = 0.2  )

static

Definition at line 801 of file kronecker.cpp.

References TKroneckerLL().

                                                                                                                                    {
  return new TKroneckerLL(GraphPt, ParamMtx, NodeIdPermV, PermPSwapNd);
}

Here is the call graph for this function:

double TKroneckerLL::NodeDLLDelta	(	const int	ParamId,
		const int &	NId
	)		const

Definition at line 1214 of file kronecker.cpp.

References TKronMtx::GetApxNoEdgeDLL(), TKronMtx::GetEdgeDLL(), TNGraph::TNodeI::GetInDeg(), TNGraph::TNodeI::GetInNId(), TNGraph::GetNI(), TNGraph::TNodeI::GetOutDeg(), TNGraph::TNodeI::GetOutNId(), Graph, IAssert, TNGraph::IsEdge(), TNGraph::IsNode(), KronIters, LLMtx, and NodePerm.

Referenced by UpdateGraphDLL().

                                                                         {
  if (! Graph->IsNode(NId)) { return 0.0; } // zero degree node
  double Delta = 0.0;
  const TNGraph::TNodeI Node = Graph->GetNI(NId);
  const int SrcRow = NodePerm[NId];
  for (int e = 0; e < Node.GetOutDeg(); e++) {
    const int DstCol = NodePerm[Node.GetOutNId(e)];
    Delta += - LLMtx.GetApxNoEdgeDLL(ParamId, SrcRow, DstCol, KronIters)
      + LLMtx.GetEdgeDLL(ParamId, SrcRow, DstCol, KronIters);
  }
  const int SrcCol = NodePerm[NId];
  for (int e = 0; e < Node.GetInDeg(); e++) {
    const int DstRow = NodePerm[Node.GetInNId(e)];
    Delta += - LLMtx.GetApxNoEdgeDLL(ParamId, DstRow, SrcCol, KronIters)
      + LLMtx.GetEdgeDLL(ParamId, DstRow, SrcCol, KronIters);
  }
  // double counter self-edge
  if (Graph->IsEdge(NId, NId)) {
    Delta += + LLMtx.GetApxNoEdgeDLL(ParamId, SrcRow, SrcCol, KronIters)
      - LLMtx.GetEdgeDLL(ParamId, SrcRow, SrcCol, KronIters);
    IAssert(SrcRow == SrcCol);
  }
  return Delta;
}

Here is the call graph for this function:

Here is the caller graph for this function:

double TKroneckerLL::NodeLLDelta

(

const int &

NId

)

const

Definition at line 1055 of file kronecker.cpp.

References TKronMtx::GetApxNoEdgeLL(), TKronMtx::GetEdgeLL(), TNGraph::TNodeI::GetInDeg(), TNGraph::TNodeI::GetInNId(), TNGraph::GetNI(), TNGraph::TNodeI::GetOutDeg(), TNGraph::TNodeI::GetOutNId(), Graph, IAssert, TNGraph::IsEdge(), TNGraph::IsNode(), KronIters, LLMtx, and NodePerm.

Referenced by SwapNodesLL().

                                                     {
  if (! Graph->IsNode(NId)) { return 0.0; } // zero degree node
  double Delta = 0.0;
  const TNGraph::TNodeI Node = Graph->GetNI(NId);
  // out-edges
  const int SrcRow = NodePerm[NId];
  for (int e = 0; e < Node.GetOutDeg(); e++) {
    const int DstCol = NodePerm[Node.GetOutNId(e)];
    Delta += - LLMtx.GetApxNoEdgeLL(SrcRow, DstCol, KronIters)
      + LLMtx.GetEdgeLL(SrcRow, DstCol, KronIters);
  }
  //in-edges
  const int SrcCol = NodePerm[NId];
  for (int e = 0; e < Node.GetInDeg(); e++) {
    const int DstRow = NodePerm[Node.GetInNId(e)];
    Delta += - LLMtx.GetApxNoEdgeLL(DstRow, SrcCol, KronIters)
      + LLMtx.GetEdgeLL(DstRow, SrcCol, KronIters);
  }
  // double counted self-edge
  if (Graph->IsEdge(NId, NId)) {
    Delta += + LLMtx.GetApxNoEdgeLL(SrcRow, SrcCol, KronIters)
      - LLMtx.GetEdgeLL(SrcRow, SrcCol, KronIters);
    IAssert(SrcRow == SrcCol);
  }
  return Delta;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void TKroneckerLL::RestoreGraph

(

const bool

RestoreNodes = true

)

!!!!! MYUNGHWAN, CHECK!

Definition at line 923 of file kronecker.cpp.

References TVec< TVal, TSizeTy >::Clr(), TVec< TVal, TSizeTy >::Del(), TNGraph::DelEdge(), TNGraph::DelNode(), GEdgeV, TNGraph::GetNodes(), Graph, LEdgeV, TVec< TVal, TSizeTy >::Len(), LSelfEdge, and RealNodes.

Referenced by MetroGibbsSampleSetup(), and RunKronEM().

                                                       {
        //      remove from Graph
        int NId1, NId2;
        for (int e = 0; e < LEdgeV.Len(); e++) {
        NId1 = LEdgeV[e].Val1;  NId2 = LEdgeV[e].Val2;
                Graph->DelEdge(NId1, NId2);
//              GEdgeV.DelIfIn(LEdgeV[e]);
        }
        if(LEdgeV.Len() - LSelfEdge)
                GEdgeV.Del(GEdgeV.Len() - LEdgeV.Len() + LSelfEdge, GEdgeV.Len() - 1);
        LEdgeV.Clr();
        LSelfEdge = 0;

        if(RestoreNodes) {
                for(int i = Graph->GetNodes()-1; i >= RealNodes; i--) {
                        Graph->DelNode(i);
                }
        }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void TKroneckerLL::RunEStep	(	const int &	GibbsWarmUp,
		const int &	WarmUp,
		const int &	NSamples,
		TFltV &	LLV,
		TVec< TFltV > &	DLLV
	)

Definition at line 1567 of file kronecker.cpp.

References TVec< TVal, TSizeTy >::Add(), CalcApxGraphDLL(), CalcApxGraphLL(), TVec< TVal, TSizeTy >::Gen(), TExeTm::GetTmStr(), GradV, LogLike, MetroGibbsSampleNext(), MetroGibbsSampleSetup(), and TExeTm::Tick().

Referenced by RunKronEM().

                                                                                                                         {
        TExeTm ExeTm, TotalTm;
        LLV.Gen(NSamples, 0);
        DLLV.Gen(NSamples, 0);

        ExeTm.Tick();
        for(int i = 0; i < 2; i++)      MetroGibbsSampleSetup(WarmUp);
        printf("  Warm-Up [%u] : %s\n", WarmUp, ExeTm.GetTmStr());
        CalcApxGraphLL();
        for(int i = 0; i < GibbsWarmUp; i++)    MetroGibbsSampleNext(10, false);
        printf("  Gibbs Warm-Up [%u] : %s\n", GibbsWarmUp, ExeTm.GetTmStr());

        ExeTm.Tick();
        CalcApxGraphLL();
        CalcApxGraphDLL();
        for(int i = 0; i < NSamples; i++) {
                MetroGibbsSampleNext(50, false);

                LLV.Add(LogLike);
                DLLV.Add(GradV);

                int OnePercent = (i+1) % (NSamples / 10);
                if(OnePercent == 0) {
                        int TenPercent = ((i+1) / (NSamples / 10)) * 10;
                        printf("  %3u%% done : %s\n", TenPercent, ExeTm.GetTmStr());
                }
        }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void TKroneckerLL::RunKronEM	(	const int &	EMIter,
		const int &	GradIter,
		double	LrnRate,
		double	MnStep,
		double	MxStep,
		const int &	GibbsWarmUp,
		const int &	WarmUp,
		const int &	NSamples,
		const TKronEMType &	Type = kronNodeMiss,
		const int &	NMissing = -1
	)

Definition at line 1692 of file kronecker.cpp.

References TVec< TVal, TSizeTy >::Add(), AppendIsoNodes(), DebugMode, EMType, TVec< TVal, TSizeTy >::Gen(), TKronMtx::GetNodes(), KronIters, LLV, MissEdges, MtxV, ProbMtx, RealEdges, RealNodes, RestoreGraph(), RunEStep(), RunMStep(), and SetRndPerm().

                                                                                                                                                                                                                               {
        printf("\n----------------------------------------------------------------------\n");
        printf("Fitting graph on %d nodes, %d edges\n", int(RealNodes), int(RealEdges));
        printf("Kron iters:  %d (== %d nodes)\n\n", KronIters(), ProbMtx.GetNodes(KronIters()));

        TFltV LLV(NSamples);
        TVec<TFltV> DLLV(NSamples);
        //int count = 0;

        EMType = Type;
        MissEdges = NMissing;
        AppendIsoNodes();
        SetRndPerm();

        if(DebugMode) {
                LLV.Gen(EMIter, 0);
                MtxV.Gen(EMIter, 0);
        }

        for(int i = 0; i < EMIter; i++) {
                printf("\n----------------------------------------------------------------------\n");
                printf("%03d EM-iter] E-Step\n", i+1);
                RunEStep(GibbsWarmUp, WarmUp, NSamples, LLV, DLLV);
                printf("\n\n");

                printf("%03d EM-iter] M-Step\n", i+1);
                double CurLL = RunMStep(LLV, DLLV, GradIter, LrnRate, MnStep, MxStep);
                printf("\n\n");

                if(DebugMode) {
                        LLV.Add(CurLL);
                        MtxV.Add(ProbMtx);
                }
        }

        RestoreGraph();
}

Here is the call graph for this function:

double TKroneckerLL::RunMStep	(	const TFltV &	LLV,
		const TVec< TFltV > &	DLLV,
		const int &	GradIter,
		const double &	LrnRate,
		double	MnStep,
		double	MxStep
	)

Definition at line 1597 of file kronecker.cpp.

References TKronMtx::At(), CalcApxGraphDLL(), CalcApxGraphLL(), TKronMtx::Dump(), TKronMtx::GetDim(), TNGraph::GetEdges(), TKronMtx::GetLLMtx(), TKronMtx::GetMtxSum(), TNGraph::GetNodes(), GetParams(), TExeTm::GetTmStr(), GradV, Graph, TVec< TVal, TSizeTy >::Len(), LLMtx, LogLike, MetroGibbsSampleNext(), ProbMtx, RealEdges, RealNodes, and TExeTm::Tick().

Referenced by RunKronEM().

                                                                                                                                                 {
        TExeTm IterTm, TotalTm;
        double OldLL=LogLike, CurLL=0;
        const double alpha = log(double(RealEdges)) / log(double(RealNodes));
        const double EZero = pow(double(ProbMtx.GetDim()), alpha);

        TFltV CurGradV(GetParams()), LearnRateV(GetParams()), LastStep(GetParams());
        LearnRateV.PutAll(LrnRate);

        TKronMtx NewProbMtx = ProbMtx;
        const int NSamples = LLV.Len();
        const int ReCalcLen = NSamples / 10;

        for (int s = 0; s < LLV.Len(); s++) {
                CurLL += LLV[s];
                for(int p = 0; p < GetParams(); p++) { CurGradV[p] += DLLV[s][p]; }
        }
        CurLL /= NSamples;
        for(int p = 0; p < GetParams(); p++) { CurGradV[p] /= NSamples; }

        double MaxLL = CurLL;
        TKronMtx MaxProbMtx = ProbMtx;
        TKronMtx OldProbMtx = ProbMtx;

        for (int Iter = 0; Iter < GradIter; Iter++) {
                printf("    %03d] ", Iter+1);
                IterTm.Tick();

                for (int p = 0; p < GetParams(); p++) {
                        if (Iter < 1) {
                                while (fabs(LearnRateV[p]*CurGradV[p]) > MxStep) { LearnRateV[p] *= 0.95; }
                                while (fabs(LearnRateV[p]*CurGradV[p]) < 5 * MnStep) { LearnRateV[p] *= (1.0/0.95); } // move more
                        } else {
                        // set learn rate so that move for each parameter is inside the [MnStep, MxStep]
                                while (fabs(LearnRateV[p]*CurGradV[p]) > MxStep) { LearnRateV[p] *= 0.95; printf(".");}
                                while (fabs(LearnRateV[p]*CurGradV[p]) < MnStep) { LearnRateV[p] *= (1.0/0.95); printf("*");}
                                if (MxStep > 3*MnStep) { MxStep *= 0.95; }
                        }
                        NewProbMtx.At(p) = ProbMtx.At(p) + LearnRateV[p]*CurGradV[p];
                        if (NewProbMtx.At(p) > 0.9999) { NewProbMtx.At(p)=0.9999; }
                        if (NewProbMtx.At(p) < 0.0001) { NewProbMtx.At(p)=0.0001; }
                        LearnRateV[p] *= 0.95;
                }
                printf("  trueE0: %.2f (%u from %u),  estE0: %.2f (%u from %u),  ERR: %f\n", EZero, RealEdges(), RealNodes(), ProbMtx.GetMtxSum(), Graph->GetEdges(), Graph->GetNodes(), fabs(EZero-ProbMtx.GetMtxSum()));
                printf("      currLL: %.4f, deltaLL: %.4f\n", CurLL, CurLL-OldLL); // positive is good
                for (int p = 0; p < GetParams(); p++) {
                        printf("      %d]  %f  <--  %f + %9f   Grad: %9.1f   Rate: %g\n", p, NewProbMtx.At(p),
                        ProbMtx.At(p), (double)(LearnRateV[p]*CurGradV[p]), CurGradV[p](), LearnRateV[p]());
                }

                OldLL=CurLL;
                if(Iter == GradIter - 1) {
                        break;
                }

                CurLL = 0;
                CurGradV.PutAll(0.0);
                TFltV OneDLL;

                CalcApxGraphLL();
                CalcApxGraphDLL();

                for(int s = 0; s < NSamples; s++) {
                        ProbMtx = OldProbMtx;  ProbMtx.GetLLMtx(LLMtx);
                        MetroGibbsSampleNext(10, true);
                        ProbMtx = NewProbMtx;  ProbMtx.GetLLMtx(LLMtx);
                        if(s % ReCalcLen == ReCalcLen/2) {
                                CurLL += CalcApxGraphLL();
                                OneDLL = CalcApxGraphDLL();
                        } else {
                                CurLL += LogLike;
                                OneDLL = GradV;
                        }
                        for(int p = 0; p < GetParams(); p++) {
                                CurGradV[p] += OneDLL[p];
                        }
                }
                CurLL /= NSamples;

                if(MaxLL < CurLL) {
                        MaxLL = CurLL;  MaxProbMtx = ProbMtx;
                }

                printf("    Time: %s\n", IterTm.GetTmStr());
                printf("\n");  fflush(stdout);
        }
        ProbMtx = MaxProbMtx;   ProbMtx.GetLLMtx(LLMtx);

        printf("    FinalLL : %f,   TotalExeTm: %s\n", MaxLL, TotalTm.GetTmStr());
        ProbMtx.Dump("    FITTED PARAMS", false);

        return MaxLL;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void TKroneckerLL::SampleGradient	(	const int &	WarmUp,
		const int &	NSamples,
		double &	AvgLL,
		TFltV &	GradV
	)

Definition at line 1271 of file kronecker.cpp.

References CalcApxGraphDLL(), CalcApxGraphLL(), TVec< TVal, TSizeTy >::Gen(), GetLL(), TInt::GetMegaStr(), TExeTm::GetSecs(), TExeTm::GetTmStr(), GradV, TKronMtx::Len(), LLMtx, TVec< TVal, TSizeTy >::PutAll(), SampleNextPerm(), TExeTm::Tick(), and UpdateGraphDLL().

Referenced by GradDescent(), GradDescent2(), GradDescentConvergence(), and TestKronDescent().

                                                                                                        {
  printf("SampleGradient: %s (%s warm-up):", TInt::GetMegaStr(NSamples).CStr(), TInt::GetMegaStr(WarmUp).CStr());
  int NId1=0, NId2=0, NAccept=0;
  TExeTm ExeTm1;
  if (WarmUp > 0) {
    CalcApxGraphLL();
    for (int s = 0; s < WarmUp; s++) { SampleNextPerm(NId1, NId2); }
    printf("  warm-up:%s,", ExeTm1.GetTmStr());  ExeTm1.Tick();
  }
  CalcApxGraphLL(); // re-calculate LL (due to numerical errors)
  CalcApxGraphDLL();
  AvgLL = 0;
  AvgGradV.Gen(LLMtx.Len());  AvgGradV.PutAll(0.0);
  printf("  sampl");
  for (int s = 0; s < NSamples; s++) {
    if (SampleNextPerm(NId1, NId2)) { // new permutation
      UpdateGraphDLL(NId1, NId2);  NAccept++; }
    for (int m = 0; m < LLMtx.Len(); m++) { AvgGradV[m] += GradV[m]; }
    AvgLL += GetLL();
  }
  printf("ing");
  AvgLL = AvgLL / double(NSamples);
  for (int m = 0; m < LLMtx.Len(); m++) {
    AvgGradV[m] = AvgGradV[m] / double(NSamples); }
  printf(":%s (%.0f/s), accept %.1f%%\n", ExeTm1.GetTmStr(), double(NSamples)/ExeTm1.GetSecs(),
    double(100*NAccept)/double(NSamples));
}

Here is the call graph for this function:

Here is the caller graph for this function:

bool TKroneckerLL::SampleNextPerm	(	int &	NId1,
		int &	NId2
	)

Definition at line 1111 of file kronecker.cpp.

References GEdgeV, TRnd::GetUniDev(), TRnd::GetUniDevInt(), InvertPerm, TVec< TVal, TSizeTy >::Len(), LogLike, NodePerm, Nodes, PermSwapNodeProb, TVec< TVal, TSizeTy >::Swap(), and SwapNodesLL().

Referenced by MetroGibbsSampleNext(), MetroGibbsSampleSetup(), SampleGradient(), TestGradDescent(), and TestSamplePerm().

                                                      {
  // pick 2 uniform nodes and swap
  if (TKronMtx::Rnd.GetUniDev() < PermSwapNodeProb) {
    NId1 = TKronMtx::Rnd.GetUniDevInt(Nodes);
    NId2 = TKronMtx::Rnd.GetUniDevInt(Nodes);
    while (NId2 == NId1) { NId2 = TKronMtx::Rnd.GetUniDevInt(Nodes); }
  } else {
    // pick uniform edge and swap endpoints (slow as it moves around high degree nodes)
    const int e = TKronMtx::Rnd.GetUniDevInt(GEdgeV.Len());
    NId1 = GEdgeV[e].Val1;  NId2 = GEdgeV[e].Val2;
  }
  const double U = TKronMtx::Rnd.GetUniDev();
  const double OldLL = LogLike;
  const double NewLL = SwapNodesLL(NId1, NId2);
  const double LogU = log(U);
  if (LogU > NewLL - OldLL) { // reject
    LogLike = OldLL;
    NodePerm.Swap(NId2, NId1); //swap back
        InvertPerm.Swap(NodePerm[NId2], NodePerm[NId1]); // swap back
    return false;
  }
  return true; // accept new sample
}

Here is the call graph for this function:

Here is the caller graph for this function:

void TKroneckerLL::SetBestDegPerm

(

)

!!!!! MYUNGHWAN, CHECK!

Definition at line 842 of file kronecker.cpp.

References TKronMtx::At(), TVec< TVal, TSizeTy >::Gen(), TNGraph::TNodeI::GetDeg(), TKronMtx::GetDim(), TNGraph::GetNI(), Graph, KronIters, NodePerm, Nodes, ProbMtx, SetIPerm(), and TVec< TVal, TSizeTy >::Sort().

Referenced by SetPerm().

                                  {
  NodePerm.Gen(Nodes);
  const int NZero = ProbMtx.GetDim();
  TFltIntPrV DegV(Nodes), CDegV(Nodes);
  TFltV Row(NZero);
  TFltV Col(NZero);
  for(int i = 0; i < NZero; i++) {
          for(int j = 0; j < NZero; j++) {
                  Row[i] += ProbMtx.At(i, j);
                  Col[i] += ProbMtx.At(j, i);
          }
  }

  for(int i = 0; i < Nodes; i++) {
          TNGraph::TNodeI NodeI = Graph->GetNI(i);
          int NId = i;
          double RowP = 1.0, ColP = 1.0;
          for(int j = 0; j < KronIters; j++) {
                  int Bit = NId % NZero;
                  RowP *= Row[Bit];             ColP *= Col[Bit];
                  NId /= NZero;
          }
          CDegV[i] = TFltIntPr(RowP + ColP, i);
          DegV[i] = TFltIntPr(NodeI.GetDeg(), i);
  }
  DegV.Sort(false);             CDegV.Sort(false);
  for(int i = 0; i < Nodes; i++) {
          NodePerm[DegV[i].Val2] = CDegV[i].Val2;
  }
  SetIPerm(NodePerm);
}

Here is the call graph for this function:

Here is the caller graph for this function:

void TKroneckerLL::SetDebug ( const bool  Debug )

inline

Definition at line 167 of file kronecker.h.

{ DebugMode = Debug; }

void TKroneckerLL::SetDegPerm

(

)

Definition at line 828 of file kronecker.cpp.

References TVec< TVal, TSizeTy >::Add(), TNGraph::BegNI(), TNGraph::EndNI(), TVec< TVal, TSizeTy >::Gen(), Graph, TVec< TVal, TSizeTy >::Len(), NodePerm, SetIPerm(), and TVec< TVal, TSizeTy >::Sort().

Referenced by GradDescentConvergence(), SetPerm(), TKronMaxLL::SetPerm(), TestGradDescent(), and TestKronDescent().

                              {
  TIntPrV DegNIdV;
  for (TNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
    DegNIdV.Add(TIntPr(NI.GetDeg(), NI.GetId()));
  }
  DegNIdV.Sort(false);
  NodePerm.Gen(DegNIdV.Len(), 0);
  for (int i = 0; i < DegNIdV.Len(); i++) {
    NodePerm.Add(DegNIdV[i].Val2);
  }
  SetIPerm(NodePerm);
}

Here is the call graph for this function:

Here is the caller graph for this function:

void TKroneckerLL::SetGraph

(

const PNGraph &

GraphPt

)

Definition at line 882 of file kronecker.cpp.

References TVec< TVal, TSizeTy >::Add(), TNGraph::BegEI(), TNGraph::EndEI(), GEdgeV, TVec< TVal, TSizeTy >::Gen(), TKronMtx::GetDim(), TNGraph::GetEdges(), TNGraph::GetNIdV(), TNGraph::GetNodes(), TSnap::GetSubGraph(), Graph, IAssert, TNGraph::IsNode(), KronIters, LEdgeV, TKronMtx::Len(), LLMtx, LSelfEdge, Nodes, ProbMtx, RealEdges, and RealNodes.

Referenced by InitLL().

                                                  {
  Graph = GraphPt;
  bool NodesOk = true;
  // check that nodes IDs are {0,1,..,Nodes-1}
  for (int nid = 0; nid < Graph->GetNodes(); nid++) {
    if (! Graph->IsNode(nid)) { NodesOk=false; break; } }
  if (! NodesOk) {
    TIntV NIdV;  GraphPt->GetNIdV(NIdV);
    Graph = TSnap::GetSubGraph(GraphPt, NIdV, true);
    for (int nid = 0; nid < Graph->GetNodes(); nid++) {
      IAssert(Graph->IsNode(nid)); }
  }
  Nodes = Graph->GetNodes();
  IAssert(LLMtx.GetDim() > 1 && LLMtx.Len() == ProbMtx.Len());
  KronIters = (int) ceil(log(double(Nodes)) / log(double(ProbMtx.GetDim())));
  // edge vector (for swap-edge permutation proposal)
//  if (PermSwapNodeProb < 1.0) { /// !!!!! MYUNGHWAN, CHECK! WHY IS THIS COMMENTED OUT
    GEdgeV.Gen(Graph->GetEdges(), 0);
    for (TNGraph::TEdgeI EI = Graph->BegEI(); EI < Graph->EndEI(); EI++) {
      if (EI.GetSrcNId() != EI.GetDstNId()) {
        GEdgeV.Add(TIntTr(EI.GetSrcNId(), EI.GetDstNId(), -1));
      }
    }
//  }

  RealNodes = Nodes;
  RealEdges = Graph->GetEdges();
  LEdgeV = TIntTrV();
  LSelfEdge = 0;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void TKroneckerLL::SetIPerm

(

const TIntV &

Perm

)

!!!!! MYUNGHWAN, CHECK!

Definition at line 875 of file kronecker.cpp.

References TVec< TVal, TSizeTy >::Gen(), InvertPerm, and TVec< TVal, TSizeTy >::Len().

Referenced by SetBestDegPerm(), SetDegPerm(), SetOrderPerm(), SetPerm(), SetRndPerm(), and TKroneckerLL().

                                             {
        InvertPerm.Gen(Perm.Len());
        for (int i = 0; i < Perm.Len(); i++) {
                InvertPerm[Perm[i]] = i;
        }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void TKroneckerLL::SetOrderPerm

(

)

Definition at line 813 of file kronecker.cpp.

References TVec< TVal, TSizeTy >::Add(), TVec< TVal, TSizeTy >::Gen(), TNGraph::GetNodes(), Graph, NodePerm, Nodes, and SetIPerm().

Referenced by GradDescentConvergence(), SetPerm(), TKronMaxLL::SetPerm(), TestGradDescent(), TestKronDescent(), and TestSamplePerm().

                                {
  NodePerm.Gen(Nodes, 0);
  for (int i = 0; i < Graph->GetNodes(); i++) {
    NodePerm.Add(i); }
  SetIPerm(NodePerm);
}

Here is the call graph for this function:

Here is the caller graph for this function:

void TKroneckerLL::SetPerm

(

const char &

PermId

)

Definition at line 805 of file kronecker.cpp.

References FailR, SetBestDegPerm(), SetDegPerm(), SetOrderPerm(), and SetRndPerm().

Referenced by TestBicCriterion().

                                             {
  if (PermId == 'o') { SetOrderPerm(); }
  else if (PermId == 'd') { SetDegPerm(); }
  else if (PermId == 'r') { SetRndPerm(); }
  else if (PermId == 'b') { SetBestDegPerm(); }
  else FailR("Unknown permutation type (o,d,r)");
}

Here is the call graph for this function:

Here is the caller graph for this function:

void TKroneckerLL::SetPerm ( const TIntV &  NodePermV )

inline

Definition at line 183 of file kronecker.h.

References SetIPerm().

{ NodePerm = NodePermV; SetIPerm(NodePerm); }

Here is the call graph for this function:

void TKroneckerLL::SetRandomEdges	(	const int &	NEdges,
		const bool	isDir = true
	)

!!!!! MYUNGHWAN, CHECK!

Definition at line 1417 of file kronecker.cpp.

References TVec< TVal, TSizeTy >::Add(), TNGraph::AddEdge(), TKronMtx::At(), EMType, GEdgeV, TKronMtx::GetDim(), TKronMtx::GetMtxSum(), TRnd::GetUniDev(), Graph, InvertPerm, TNGraph::IsEdge(), IsObsEdge(), kronEdgeMiss, KronIters, LEdgeV, TVec< TVal, TSizeTy >::Len(), LSelfEdge, Nodes, and ProbMtx.

Referenced by MetroGibbsSampleNext(), and MetroGibbsSampleSetup().

                                                                     {
        int count = 0, added = 0, collision = 0;
        const int MtxDim = ProbMtx.GetDim();
        const double MtxSum = ProbMtx.GetMtxSum();
        TVec<TFltIntIntTr> ProbToRCPosV; // row, col position
        double CumProb = 0.0;

        for(int r = 0; r < MtxDim; r++) {
                for(int c = 0; c < MtxDim; c++) {
                        const double Prob = ProbMtx.At(r, c);
                        if (Prob > 0.0) {
                                CumProb += Prob;
                                ProbToRCPosV.Add(TFltIntIntTr(CumProb/MtxSum, r, c));
                        }
                }
        }

        int Rng, Row, Col, n, NId1, NId2;
        while(added < NEdges) {
                Rng = Nodes;    Row = 0;        Col = 0;
                for (int iter = 0; iter < KronIters; iter++) {
                        const double& Prob = TKronMtx::Rnd.GetUniDev();
                        n = 0; while(Prob > ProbToRCPosV[n].Val1) { n++; }
                        const int MtxRow = ProbToRCPosV[n].Val2;
                        const int MtxCol = ProbToRCPosV[n].Val3;
                        Rng /= MtxDim;
                        Row += MtxRow * Rng;
                        Col += MtxCol * Rng;
                }

                count++;

                NId1 = InvertPerm[Row]; NId2 = InvertPerm[Col];

                //      Check conflicts
                if(EMType != kronEdgeMiss && IsObsEdge(NId1, NId2)) {
                        continue;
                }

                if (! Graph->IsEdge(NId1, NId2)) {
                        Graph->AddEdge(NId1, NId2);
                        if(NId1 != NId2)        { GEdgeV.Add(TIntTr(NId1, NId2, LEdgeV.Len())); }
                        else { LSelfEdge++; }
                        LEdgeV.Add(TIntTr(NId1, NId2, GEdgeV.Len()-1));
                        added++;
                        if (! isDir) {
                                if (NId1 != NId2) {
                                   Graph->AddEdge(NId2, NId1);
                                   GEdgeV.Add(TIntTr(NId2, NId1, LEdgeV.Len()));
                                   LEdgeV.Add(TIntTr(NId2, NId1, GEdgeV.Len()-1));
                                   added++;
                                }
                        }
                } else { collision ++; }
        }
//      printf("total = %d / added = %d / collision = %d\n", count, added, collision);
}

Here is the call graph for this function:

Here is the caller graph for this function:

void TKroneckerLL::SetRndPerm

(

)

Definition at line 820 of file kronecker.cpp.

References TVec< TVal, TSizeTy >::Add(), TVec< TVal, TSizeTy >::Gen(), TNGraph::GetNodes(), Graph, NodePerm, Nodes, SetIPerm(), and TVec< TVal, TSizeTy >::Shuffle().

Referenced by RunKronEM(), SetPerm(), TKronMaxLL::SetPerm(), and TestGradDescent().

                              {
  NodePerm.Gen(Nodes, 0);
  for (int i = 0; i < Graph->GetNodes(); i++) {
    NodePerm.Add(i); }
  NodePerm.Shuffle(TKronMtx::Rnd);
  SetIPerm(NodePerm);
}

Here is the call graph for this function:

Here is the caller graph for this function:

double TKroneckerLL::SwapNodesLL	(	const int &	NId1,
		const int &	NId2
	)

Definition at line 1083 of file kronecker.cpp.

References TKronMtx::GetApxNoEdgeLL(), TKronMtx::GetEdgeLL(), Graph, InvertPerm, TNGraph::IsEdge(), KronIters, LLMtx, LogLike, NodeLLDelta(), NodePerm, and TVec< TVal, TSizeTy >::Swap().

Referenced by SampleNextPerm().

                                                                 {
  // subtract old LL (remove nodes)
  LogLike = LogLike - NodeLLDelta(NId1) - NodeLLDelta(NId2);
  const int PrevId1 = NodePerm[NId1], PrevId2 = NodePerm[NId2];
  // double-counted edges
  if (Graph->IsEdge(NId1, NId2)) {
    LogLike += - LLMtx.GetApxNoEdgeLL(PrevId1, PrevId2, KronIters)
      + LLMtx.GetEdgeLL(PrevId1, PrevId2, KronIters); }
  if (Graph->IsEdge(NId2, NId1)) {
    LogLike += - LLMtx.GetApxNoEdgeLL(PrevId2, PrevId1, KronIters)
      + LLMtx.GetEdgeLL(PrevId2, PrevId1, KronIters); }
  // swap
  NodePerm.Swap(NId1, NId2);
  InvertPerm.Swap(NodePerm[NId1], NodePerm[NId2]);
  // add new LL (add nodes)
  LogLike = LogLike + NodeLLDelta(NId1) + NodeLLDelta(NId2);
  const int NewId1 = NodePerm[NId1], NewId2 = NodePerm[NId2];
  // correct for double-counted edges
  if (Graph->IsEdge(NId1, NId2)) {
    LogLike += + LLMtx.GetApxNoEdgeLL(NewId1, NewId2, KronIters)
      - LLMtx.GetEdgeLL(NewId1, NewId2, KronIters); }
  if (Graph->IsEdge(NId2, NId1)) {
    LogLike += + LLMtx.GetApxNoEdgeLL(NewId2, NewId1, KronIters)
      - LLMtx.GetEdgeLL(NewId2, NewId1, KronIters); }
  return LogLike;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void TKroneckerLL::TestBicCriterion ( const TStr &  OutFNm, const TStr &  Desc1, const PNGraph &  G, const int &  GradIters, double  LearnRate, const int &  WarmUp, const int &  NSamples, const int &  TrueN0  )

static

Definition at line 2109 of file kronecker.cpp.

References TVec< TVal, TSizeTy >::Add(), TGnuPlot::AddPlot(), TKronMtx::Dump(), TNGraph::GetEdges(), TKronMtx::GetInitMtx(), GetKronIters(), TNGraph::GetNodes(), gpwLinesPoints, GradDescent(), LLV, TGnuPlot::SavePng(), SetPerm(), TGnuPlot::SetXYLabel(), and TMath::Sqr().

                                                                              {
  TFltPrV BicV, MdlV, LLV;
  const double rndGP = G->GetEdges()/TMath::Sqr(double(G->GetNodes()));
  const double RndGLL = G->GetEdges()*log(rndGP )+ (TMath::Sqr(double(G->GetNodes()))-G->GetEdges())*log(1-rndGP);
  LLV.Add(TFltPr(1, RndGLL));
  BicV.Add(TFltPr(1, -RndGLL + 0.5*TMath::Sqr(1)*log(TMath::Sqr(G->GetNodes()))));
  MdlV.Add(TFltPr(1, -RndGLL + 32*TMath::Sqr(1)+2*(log((double)1)+log((double)G->GetNodes()))));
  for (int NZero = 2; NZero < 10; NZero++) {
    const TKronMtx InitKronMtx = TKronMtx::GetInitMtx(NZero, G->GetNodes(), G->GetEdges());
    InitKronMtx.Dump("INIT PARAM", true);
    TKroneckerLL KronLL(G, InitKronMtx);
    KronLL.SetPerm('d'); // degree perm
    const double LastLL = KronLL.GradDescent(GradIters, LearnRate, 0.001, 0.01, WarmUp, NSamples);
    LLV.Add(TFltPr(NZero, LastLL));
    BicV.Add(TFltPr(NZero, -LastLL + 0.5*TMath::Sqr(NZero)*log(TMath::Sqr(G->GetNodes()))));
    MdlV.Add(TFltPr(NZero, -LastLL + 32*TMath::Sqr(NZero)+2*(log((double)NZero)+log((double)KronLL.GetKronIters()))));
    { TGnuPlot GP("LL-"+OutFNm, Desc1);
    GP.AddPlot(LLV, gpwLinesPoints, "Log-likelihood", "linewidth 1 pointtype 6 pointsize 2");
    GP.SetXYLabel("NZero", "Log-Likelihood");  GP.SavePng(); }
    { TGnuPlot GP("BIC-"+OutFNm, Desc1);
    GP.AddPlot(BicV, gpwLinesPoints, "BIC", "linewidth 1 pointtype 6 pointsize 2");
    GP.SetXYLabel("NZero", "BIC");  GP.SavePng(); }
    { TGnuPlot GP("MDL-"+OutFNm, Desc1);
    GP.AddPlot(MdlV, gpwLinesPoints, "MDL", "linewidth 1 pointtype 6 pointsize 2");
    GP.SetXYLabel("NZero", "MDL");  GP.SavePng(); }
  }
}

Here is the call graph for this function:

void TKroneckerLL::TestGradDescent ( const int &  KronIters, const int &  KiloSamples, const TStr &  Permutation  )

static

Definition at line 2138 of file kronecker.cpp.

References TVec< TVal, TSizeTy >::Add(), TGnuPlot::AddPlot(), CalcApxGraphDLL(), CalcApxGraphLL(), TStr::CStr(), FailR, TStr::Fmt(), TKronMtx::GenFastKronecker(), TNGraph::GetEdges(), TKronMtx::GetMtx(), TNGraph::GetNodes(), gpwLines, GradV, Graph, KronIters, SampleNextPerm(), TGnuPlot::SavePng(), SetDegPerm(), SetOrderPerm(), SetRndPerm(), TGnuPlot::SetXYLabel(), and UpdateGraphDLL().

                                                                                                        {
  const TStr OutFNm = TStr::Fmt("grad-%s%d-%dk", Permutation.CStr(), KronIters, KiloSamples);
  TKronMtx KronParam = TKronMtx::GetMtx("0.8 0.6; 0.6 0.4");
  PNGraph Graph  = TKronMtx::GenFastKronecker(KronParam, KronIters, true, 0);
  TKroneckerLL KronLL(Graph, KronParam);
  TVec<TFltV> GradVV(4), SDevVV(4);  TFltV XValV;
  int NId1 = 0, NId2 = 0, NAccept = 0;
  TVec<TMom> GradMomV(4);
  TExeTm ExeTm;
  if (Permutation == "r") KronLL.SetRndPerm();
  else if (Permutation == "d") KronLL.SetDegPerm();
  else if (Permutation == "o") KronLL.SetOrderPerm();
  else FailR("Unknown permutation (r,d,o)");
  KronLL.CalcApxGraphLL();
  KronLL.CalcApxGraphDLL();
  for (int s = 0; s < 1000*KiloSamples; s++) {
    if (KronLL.SampleNextPerm(NId1, NId2)) { // new permutation
      KronLL.UpdateGraphDLL(NId1, NId2);  NAccept++; }
    if (s > 50000) { //warm up period
      for (int m = 0; m < 4; m++) { GradVV[m].Add(KronLL.GradV[m]); }
      if ((s+1) % 1000 == 0) {
        printf(".");
        for (int m = 0; m < 4; m++) { GradVV[m].Add(KronLL.GradV[m]); }
        XValV.Add((s+1));
        if ((s+1) % 100000 == 0) {
          TGnuPlot GP(OutFNm, TStr::Fmt("Gradient vs. samples. %d nodes, %d edges", Graph->GetNodes(), Graph->GetEdges()), true);
          for (int g = 0; g < GradVV.Len(); g++) {
            GP.AddPlot(XValV, GradVV[g], gpwLines, TStr::Fmt("grad %d", g)); }
          GP.SetXYLabel("sample index","log Gradient");
          GP.SavePng();
        }
      }
    }
  }
  printf("\n");
  for (int m = 0; m < 4; m++) {
    GradMomV[m].Def();
    printf("grad %d: mean: %12f  sDev: %12f  median: %12f\n", m,
      GradMomV[m].GetMean(), GradMomV[m].GetSDev(), GradMomV[m].GetMedian());
  }
}

Here is the call graph for this function:

TFltQu TKroneckerLL::TestKronDescent	(	const bool &	DoExact,
		const bool &	TruePerm,
		double	LearnRate,
		const int &	WarmUp,
		const int &	NSamples,
		const TKronMtx &	TrueParam
	)

Definition at line 1942 of file kronecker.cpp.

References TKronMtx::At(), CalcApxGraphDLL(), CalcApxGraphLL(), CalcGraphDLL(), CalcGraphLL(), TKronMtx::Dump(), TKronMtx::GetAvgAbsErr(), TKronMtx::GetLLMtx(), TKronMtx::GetMtxSum(), GetParams(), TExeTm::GetSecs(), TExeTm::GetTmStr(), GradV, LLMtx, LogLike, ProbMtx, TVec< TVal, TSizeTy >::PutAll(), SampleGradient(), SetDegPerm(), and SetOrderPerm().

                                                                                                                                                                   {
  printf("Test gradient descent on a synthetic kronecker graphs:\n");
  if (DoExact) { printf("  -- Exact gradient calculations\n"); }
  else { printf("  -- Approximate gradient calculations\n"); }
  if (TruePerm) { printf("  -- No permutation sampling (use true permutation)\n"); }
  else { printf("  -- Sample permutations (start with degree permutation)\n"); }
  TExeTm IterTm;
  int Iter;
  double OldLL=0, MyLL=0, AvgAbsErr, AbsSumErr;
  TFltV MyGradV, SDevV;
  TFltV LearnRateV(GetParams());  LearnRateV.PutAll(LearnRate);
  if (TruePerm) {
    SetOrderPerm();
  }
  else {
    /*printf("SET EIGEN VECTOR PERMUTATIONS\n");
    TFltV LeftSV, RightSV;
    TGSvd::GetSngVec(Graph, LeftSV, RightSV);
    TFltIntPrV V;
    for (int v=0; v<LeftSV.Len();v++) { V.Add(TFltIntPr(LeftSV[v], v)); }
    V.Sort(false);
    NodePerm.Gen(Nodes, 0);
    for (int v=0; v < V.Len();v++) { NodePerm.Add(V[v].Val2); } //*/
    //printf("RANDOM PERMUTATION\n");   SetRndPerm();
    printf("DEGREE  PERMUTATION\n");  SetDegPerm();
  }
  for (Iter = 0; Iter < 100; Iter++) {
    if (TruePerm) {
      // don't sample over permutations
      if (DoExact) { CalcGraphDLL();  CalcGraphLL(); } // slow, O(N^2)
      else { CalcApxGraphDLL();  CalcApxGraphLL(); }   // fast
      MyLL = LogLike;  MyGradV = GradV;
    } else {
      printf(".");
      // sample over permutations (approximate calculations)
      SampleGradient(WarmUp, NSamples, MyLL, MyGradV);
    }
    printf("%d] LL: %g, ", Iter, MyLL);
    AvgAbsErr = TKronMtx::GetAvgAbsErr(ProbMtx, TrueParam);
    AbsSumErr = fabs(ProbMtx.GetMtxSum() - TrueParam.GetMtxSum());
    printf("  avgAbsErr: %.4f, absSumErr: %.4f, newLL: %.2f, deltaLL: %.2f\n", AvgAbsErr, AbsSumErr, MyLL, OldLL-MyLL);
    for (int p = 0; p < GetParams(); p++) {
      // set learn rate so that move for each parameter is inside the [0.01, 0.1]
      LearnRateV[p] *= 0.9;
      //printf("%d: rate: %f   delta:%f\n", p, LearnRateV[p], fabs(LearnRateV[p]*MyGradV[p]));
      while (fabs(LearnRateV[p]*MyGradV[p]) > 0.1) { LearnRateV[p] *= 0.9; }
      //printf("   rate: %f   delta:%f\n", LearnRateV[p], fabs(LearnRateV[p]*MyGradV[p]));
      while (fabs(LearnRateV[p]*MyGradV[p]) < 0.001) { LearnRateV[p] *= (1.0/0.9); }
      //printf("   rate: %f   delta:%f\n", LearnRateV[p], fabs(LearnRateV[p]*MyGradV[p]));
      printf("    %d]  %f  <--  %f + %f    lrnRate:%g\n", p, ProbMtx.At(p) + LearnRateV[p]*MyGradV[p],
        ProbMtx.At(p), (double)(LearnRateV[p]*MyGradV[p]), LearnRateV[p]());
      ProbMtx.At(p) = ProbMtx.At(p) + LearnRateV[p]*MyGradV[p];
      // box constraints
      if (ProbMtx.At(p) > 0.99) { ProbMtx.At(p)=0.99; }
      if (ProbMtx.At(p) < 0.01) { ProbMtx.At(p)=0.01; }
    }
    ProbMtx.GetLLMtx(LLMtx);  OldLL = MyLL;
    if (AvgAbsErr < 0.01) { printf("***CONVERGED!\n");  break; }
    printf("\n");  fflush(stdout);
  }
  TrueParam.Dump("True  Thetas", true);
  ProbMtx.Dump("Final Thetas", true);
  printf("  AvgAbsErr: %f\n  AbsSumErr: %f\n  Iterations: %d\n", AvgAbsErr, AbsSumErr, Iter);
  printf("Iteration run time: %s, sec: %g\n\n", IterTm.GetTmStr(), IterTm.GetSecs());
  return TFltQu(AvgAbsErr, AbsSumErr, Iter, IterTm.GetSecs());
}

Here is the call graph for this function:

TFltV TKroneckerLL::TestSamplePerm	(	const TStr &	OutFNm,
		const int &	WarmUp,
		const int &	NSamples,
		const TKronMtx &	TrueMtx,
		const bool &	DoPlot = true
	)

Definition at line 1795 of file kronecker.cpp.

References TVec< TVal, TSizeTy >::Add(), CalcApxGraphDLL(), CalcApxGraphLL(), TStr::CStr(), TKronMtx::Dump(), TKronMtx::Empty(), TStr::Fmt(), TVec< TVal, TSizeTy >::Gen(), TNGraph::GetEdges(), GetLL(), TInt::GetMegaStr(), TNGraph::GetNodes(), GetParams(), TExeTm::GetSecs(), TExeTm::GetTmStr(), GradV, Graph, InitLL(), TVec< TVal, TSizeTy >::Len(), LogLike, NodePerm, PermSwapNodeProb, PlotAutoCorrelation(), PlotGrad(), ProbMtx, TVec< TVal, TSizeTy >::PutAll(), SampleNextPerm(), SetOrderPerm(), TExeTm::Tick(), and UpdateGraphDLL().

                                                                                                                                          {
  printf("Sample permutations: %s (warm-up: %s)\n", TInt::GetMegaStr(NSamples).CStr(), TInt::GetMegaStr(WarmUp).CStr());
  int NId1=0, NId2=0, NAccept=0;
  TExeTm ExeTm;
  const int PlotLen = NSamples/1000+1;
  double TrueLL=-1, AvgLL=0.0;
  TFltV AvgGradV(GetParams());
  TFltPrV TrueLLV(PlotLen, 0); // true log-likelihood (under the correct permutation)
  TFltPrV EstLLV(PlotLen, 0);  // estiamted log-likelihood (averaged over last 1k permutation)
  TFltPrV AcceptV;             // sample acceptance ratio
  TFltV SampleLLV(NSamples, 0);
  TVec<TFltPrV> GradVV(GetParams());
  for (int g = 0; g < GetParams(); g++) {
    GradVV[g].Gen(PlotLen, 0); }
  if (! TrueMtx.Empty()) {
    TIntV PermV=NodePerm;  TKronMtx CurMtx=ProbMtx;  ProbMtx.Dump();
    InitLL(TrueMtx);  SetOrderPerm();  CalcApxGraphLL();  printf("TrueLL: %f\n", LogLike());
    TrueLL=LogLike;  InitLL(CurMtx); NodePerm=PermV;
  }
  CalcApxGraphLL();
  printf("LogLike at start:       %f\n", LogLike());
  if (WarmUp > 0) {
    EstLLV.Add(TFltPr(0, LogLike));
    if (TrueLL != -1) { TrueLLV.Add(TFltPr(0, TrueLL)); }
    for (int s = 0; s < WarmUp; s++) { SampleNextPerm(NId1, NId2); }
    printf("  warm-up:%s,", ExeTm.GetTmStr());  ExeTm.Tick();
  }
  printf("LogLike afterm warm-up: %f\n", LogLike());
  CalcApxGraphLL(); // re-calculate LL (due to numerical errors)
  CalcApxGraphDLL();
  EstLLV.Add(TFltPr(WarmUp, LogLike));
  if (TrueLL != -1) { TrueLLV.Add(TFltPr(WarmUp, TrueLL)); }
  printf("  recalculated:         %f\n", LogLike());
  // start sampling
  printf("  sampling (average per 1000 samples)\n");
  TVec<TFltV> SamplVV(5);
  for (int s = 0; s < NSamples; s++) {
    if (SampleNextPerm(NId1, NId2)) { // new permutation
      UpdateGraphDLL(NId1, NId2);  NAccept++; }
    for (int m = 0; m < AvgGradV.Len(); m++) { AvgGradV[m] += GradV[m]; }
    AvgLL += GetLL();
    SampleLLV.Add(GetLL());
    /*SamplVV[0].Add(GetLL()); // gives worse autocoreelation than the avg below
    SamplVV[1].Add(GradV[0]);
    SamplVV[2].Add(GradV[1]);
    SamplVV[3].Add(GradV[2]);
    SamplVV[4].Add(GradV[3]);*/
    if (s > 0 && s % 1000 == 0) {
      printf(".");
      for (int g = 0; g < AvgGradV.Len(); g++) {
        GradVV[g].Add(TFltPr(WarmUp+s, AvgGradV[g] / 1000.0)); }
      EstLLV.Add(TFltPr(WarmUp+s, AvgLL / 1000.0));
      if (TrueLL != -1) { TrueLLV.Add(TFltPr(WarmUp+s, TrueLL)); }
      AcceptV.Add(TFltPr(WarmUp+s, NAccept/1000.0));
      // better (faster decaying) autocorrelation when one takes avg. of 1000 consecutive samples
      /*SamplVV[0].Add(AvgLL);
      SamplVV[1].Add(AvgGradV[0]);
      SamplVV[2].Add(AvgGradV[1]);
      SamplVV[3].Add(AvgGradV[2]);
      SamplVV[4].Add(AvgGradV[3]); //*/
      if (s % 100000 == 0 && DoPlot) {
        const TStr Desc = TStr::Fmt("P(NodeSwap)=%g. Nodes: %d, Edges: %d, Params: %d, WarmUp: %s, Samples: %s", PermSwapNodeProb(),
          Graph->GetNodes(), Graph->GetEdges(), GetParams(), TInt::GetMegaStr(WarmUp).CStr(), TInt::GetMegaStr(NSamples).CStr());
        PlotGrad(EstLLV, TrueLLV, GradVV, AcceptV, OutFNm, Desc);
        for (int n = 0; n < SamplVV.Len(); n++) {
          PlotAutoCorrelation(SamplVV[n], 1000, TStr::Fmt("%s-n%d", OutFNm.CStr(), n), Desc); }
        printf("  samples: %d, time: %s, samples/s: %.1f\n", s, ExeTm.GetTmStr(), double(s+1)/ExeTm.GetSecs());
      }
      AvgLL = 0;  AvgGradV.PutAll(0);  NAccept=0;
    }
  }
  if (DoPlot) {
    const TStr Desc = TStr::Fmt("P(NodeSwap)=%g. Nodes: %d, Edges: %d, Params: %d, WarmUp: %s, Samples: %s", PermSwapNodeProb(),
      Graph->GetNodes(), Graph->GetEdges(), GetParams(), TInt::GetMegaStr(WarmUp).CStr(), TInt::GetMegaStr(NSamples).CStr());
    PlotGrad(EstLLV, TrueLLV, GradVV, AcceptV, OutFNm, Desc);
    for (int n = 0; n < SamplVV.Len(); n++) {
      PlotAutoCorrelation(SamplVV[n], 1000, TStr::Fmt("%s-n%d", OutFNm.CStr(), n), Desc); }
  }
  return SampleLLV; // seems to work better for potential scale reduction plot
}

Here is the call graph for this function:

void TKroneckerLL::UpdateGraphDLL	(	const int &	SwapNId1,
		const int &	SwapNId2
	)

Definition at line 1241 of file kronecker.cpp.

References TKronMtx::GetApxNoEdgeDLL(), TKronMtx::GetEdgeDLL(), GradV, Graph, TNGraph::IsEdge(), KronIters, TKronMtx::Len(), LLMtx, NodeDLLDelta(), NodePerm, and TVec< TVal, TSizeTy >::Swap().

Referenced by MetroGibbsSampleNext(), SampleGradient(), TestGradDescent(), and TestSamplePerm().

                                                                          {
  for (int ParamId = 0; ParamId < LLMtx.Len(); ParamId++) {
    // permutation before the swap (swap back to previous position)
    NodePerm.Swap(SwapNId1, SwapNId2);
    // subtract old DLL
    TFlt& DLL = GradV[ParamId];
    DLL = DLL - NodeDLLDelta(ParamId, SwapNId1) - NodeDLLDelta(ParamId, SwapNId2);
    // double-counted edges
    const int PrevId1 = NodePerm[SwapNId1], PrevId2 = NodePerm[SwapNId2];
    if (Graph->IsEdge(SwapNId1, SwapNId2)) {
      DLL += - LLMtx.GetApxNoEdgeDLL(ParamId, PrevId1, PrevId2, KronIters)
        + LLMtx.GetEdgeDLL(ParamId, PrevId1, PrevId2, KronIters); }
    if (Graph->IsEdge(SwapNId2, SwapNId1)) {
      DLL += - LLMtx.GetApxNoEdgeDLL(ParamId, PrevId2, PrevId1, KronIters)
        + LLMtx.GetEdgeDLL(ParamId, PrevId2, PrevId1, KronIters); }
    // permutation after the swap (restore the swap)
    NodePerm.Swap(SwapNId1, SwapNId2);
    // add new DLL
    DLL = DLL + NodeDLLDelta(ParamId, SwapNId1) + NodeDLLDelta(ParamId, SwapNId2);
    const int NewId1 = NodePerm[SwapNId1], NewId2 = NodePerm[SwapNId2];
    // double-counted edges
    if (Graph->IsEdge(SwapNId1, SwapNId2)) {
      DLL += + LLMtx.GetApxNoEdgeDLL(ParamId, NewId1, NewId2, KronIters)
        - LLMtx.GetEdgeDLL(ParamId, NewId1, NewId2, KronIters); }
    if (Graph->IsEdge(SwapNId2, SwapNId1)) {
      DLL += + LLMtx.GetApxNoEdgeDLL(ParamId, NewId2, NewId1, KronIters)
        - LLMtx.GetEdgeDLL(ParamId, NewId2, NewId1, KronIters); }
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

Friends And Related Function Documentation

friend class TPt< TKroneckerLL >

friend

Definition at line 245 of file kronecker.h.

Member Data Documentation

TCRef TKroneckerLL::CRef

private

Definition at line 119 of file kronecker.h.

TBool TKroneckerLL::DebugMode

private

Definition at line 141 of file kronecker.h.

Referenced by GradDescent(), and RunKronEM().

TKronEMType TKroneckerLL::EMType

private

Definition at line 138 of file kronecker.h.

Referenced by MetroGibbsSampleSetup(), RunKronEM(), and SetRandomEdges().

TIntTrV TKroneckerLL::GEdgeV

private

Definition at line 125 of file kronecker.h.

Referenced by MetroGibbsSampleNext(), RestoreGraph(), SampleNextPerm(), SetGraph(), and SetRandomEdges().

TFltV TKroneckerLL::GradV

private

Definition at line 136 of file kronecker.h.

Referenced by CalcApxGraphDLL(), CalcFullApxGraphDLL(), CalcGraphDLL(), GetDLL(), GradDescentConvergence(), InitLL(), MetroGibbsSampleNext(), RunEStep(), RunMStep(), SampleGradient(), TestGradDescent(), TestKronDescent(), TestSamplePerm(), and UpdateGraphDLL().

PNGraph TKroneckerLL::Graph

private

Definition at line 120 of file kronecker.h.

Referenced by AppendIsoNodes(), CalcApxGraphDLL(), CalcApxGraphLL(), CalcFullApxGraphDLL(), CalcGraphDLL(), CalcGraphLL(), GetGraph(), GradDescent(), GradDescent2(), GradDescentConvergence(), MetroGibbsSampleNext(), NodeDLLDelta(), NodeLLDelta(), RestoreGraph(), RunMStep(), SetBestDegPerm(), SetDegPerm(), SetGraph(), SetOrderPerm(), SetRandomEdges(), SetRndPerm(), SwapNodesLL(), TestGradDescent(), TestSamplePerm(), and UpdateGraphDLL().

TIntV TKroneckerLL::InvertPerm

private

Definition at line 129 of file kronecker.h.

Referenced by SampleNextPerm(), SetIPerm(), SetRandomEdges(), and SwapNodesLL().

TInt TKroneckerLL::KronIters

private

Definition at line 121 of file kronecker.h.

Referenced by AppendIsoNodes(), CalcApxGraphDLL(), CalcApxGraphLL(), CalcFullApxGraphDLL(), CalcGraphDLL(), CalcGraphLL(), GetApxEmptyGraphDLL(), GetApxEmptyGraphLL(), GetEmptyGraphDLL(), GetEmptyGraphLL(), GetFullColLL(), GetFullGraphLL(), GetFullRowLL(), GetKronIters(), GradDescent(), GradDescent2(), GradDescentConvergence(), MetroGibbsSampleNext(), MetroGibbsSampleSetup(), NodeDLLDelta(), NodeLLDelta(), RunKronEM(), SetBestDegPerm(), SetGraph(), SetRandomEdges(), SwapNodesLL(), TestGradDescent(), and UpdateGraphDLL().

TIntTrV TKroneckerLL::LEdgeV

private

Definition at line 126 of file kronecker.h.

Referenced by MetroGibbsSampleNext(), RestoreGraph(), SetGraph(), and SetRandomEdges().

TKronMtx TKroneckerLL::LLMtx

private

Definition at line 134 of file kronecker.h.

Referenced by CalcApxGraphDLL(), CalcApxGraphLL(), CalcFullApxGraphDLL(), CalcGraphDLL(), CalcGraphLL(), GetEmptyGraphDLL(), GetEmptyGraphLL(), GetFullColLL(), GetFullGraphLL(), GetFullRowLL(), GetLLMtx(), GradDescent(), GradDescent2(), GradDescentConvergence(), InitLL(), MetroGibbsSampleNext(), NodeDLLDelta(), NodeLLDelta(), RunMStep(), SampleGradient(), SetGraph(), SwapNodesLL(), TestKronDescent(), and UpdateGraphDLL().

TFltV TKroneckerLL::LLV

private

Definition at line 142 of file kronecker.h.

Referenced by GetLLHist(), GradDescent(), RunKronEM(), and TestBicCriterion().

TFlt TKroneckerLL::LogLike

private

Definition at line 135 of file kronecker.h.

Referenced by CalcApxGraphLL(), CalcGraphLL(), GetLL(), GradDescentConvergence(), InitLL(), MetroGibbsSampleNext(), RunEStep(), RunMStep(), SampleNextPerm(), SwapNodesLL(), TestKronDescent(), and TestSamplePerm().

TInt TKroneckerLL::LSelfEdge

private

Definition at line 127 of file kronecker.h.

Referenced by MetroGibbsSampleNext(), RestoreGraph(), SetGraph(), and SetRandomEdges().

TInt TKroneckerLL::MissEdges

private

Definition at line 139 of file kronecker.h.

Referenced by MetroGibbsSampleSetup(), and RunKronEM().

TVec<TKronMtx> TKroneckerLL::MtxV

private

Definition at line 143 of file kronecker.h.

Referenced by GetParamHist(), GradDescent(), and RunKronEM().

TIntV TKroneckerLL::NodePerm

private

Definition at line 128 of file kronecker.h.

Referenced by CalcApxGraphDLL(), CalcApxGraphLL(), CalcFullApxGraphDLL(), CalcGraphDLL(), CalcGraphLL(), GetEmptyGraphDLL(), GetPermV(), NodeDLLDelta(), NodeLLDelta(), SampleNextPerm(), SetBestDegPerm(), SetDegPerm(), SetOrderPerm(), SetRndPerm(), SwapNodesLL(), TestSamplePerm(), TKroneckerLL(), and UpdateGraphDLL().

TInt TKroneckerLL::Nodes

private

Definition at line 121 of file kronecker.h.

Referenced by AppendIsoNodes(), CalcApxGraphDLL(), CalcApxGraphLL(), CalcFullApxGraphDLL(), CalcGraphDLL(), CalcGraphLL(), GetEmptyGraphDLL(), GetNodes(), MetroGibbsSampleSetup(), SampleNextPerm(), SetBestDegPerm(), SetGraph(), SetOrderPerm(), SetRandomEdges(), and SetRndPerm().

TFlt TKroneckerLL::PermSwapNodeProb

private

Definition at line 123 of file kronecker.h.

Referenced by SampleNextPerm(), and TestSamplePerm().

TKronMtx TKroneckerLL::ProbMtx

private

Definition at line 134 of file kronecker.h.

Referenced by AppendIsoNodes(), GetApxEmptyGraphDLL(), GetApxEmptyGraphLL(), GetProbMtx(), GradDescent(), GradDescent2(), GradDescentConvergence(), InitLL(), MetroGibbsSampleSetup(), RunKronEM(), RunMStep(), SetBestDegPerm(), SetGraph(), SetRandomEdges(), TestKronDescent(), and TestSamplePerm().

TInt TKroneckerLL::RealEdges

private

Definition at line 132 of file kronecker.h.

Referenced by RunKronEM(), RunMStep(), and SetGraph().

TInt TKroneckerLL::RealNodes

private

Definition at line 131 of file kronecker.h.

Referenced by MetroGibbsSampleSetup(), RestoreGraph(), RunKronEM(), RunMStep(), and SetGraph().

---

The documentation for this class was generated from the following files:

• snap-adv/kronecker.h
• snap-adv/kronecker.cpp