SNAP Library 4.0, User Reference  2017-07-27 13:18:06
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
TKroneckerLL Class Reference

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

#include <kronecker.h>

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 TKronMtxGetProbMtx () const
 
const TKronMtxGetLLMtx () const
 
int GetParams () const
 
int GetDim () const
 
void SetDebug (const bool Debug)
 
const TFltVGetLLHist () 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 TIntVGetPermV () 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 TFltVCalcGraphDLL ()
 
const TFltVCalcFullApxGraphDLL ()
 
const TFltVCalcApxGraphDLL ()
 
double NodeDLLDelta (const int ParamId, const int &NId) const
 
void UpdateGraphDLL (const int &SwapNId1, const int &SwapNId2)
 
const TFltVGetDLL () 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< TKronMtxMtxV
 

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.

static const double NInf
Definition: kronecker.h:13
TFlt LogLike
Definition: kronecker.h:135
TFlt PermSwapNodeProb
Definition: kronecker.h:123
TBool DebugMode
Definition: kronecker.h:141
TInt RealEdges
Definition: kronecker.h:132
TInt KronIters
Definition: kronecker.h:121
TInt MissEdges
Definition: kronecker.h:139
TInt RealNodes
Definition: kronecker.h:131
TKronEMType EMType
Definition: kronecker.h:138
TKroneckerLL::TKroneckerLL ( const PNGraph GraphPt,
const TFltV ParamV,
const double &  PermPSwapNd = 0.2 
)

Definition at line 783 of file kronecker.cpp.

783  : PermSwapNodeProb(PermPSwapNd) {
784  InitLL(GraphPt, TKronMtx(ParamV));
785 }
TFlt PermSwapNodeProb
Definition: kronecker.h:123
void InitLL(const TFltV &ParamV)
Definition: kronecker.cpp:996
TKroneckerLL::TKroneckerLL ( const PNGraph GraphPt,
const TKronMtx ParamMtx,
const double &  PermPSwapNd = 0.2 
)

Definition at line 787 of file kronecker.cpp.

787  : PermSwapNodeProb(PermPSwapNd) {
788  InitLL(GraphPt, ParamMtx);
789 }
TFlt PermSwapNodeProb
Definition: kronecker.h:123
void InitLL(const TFltV &ParamV)
Definition: kronecker.cpp:996
TKroneckerLL::TKroneckerLL ( const PNGraph GraphPt,
const TKronMtx ParamMtx,
const TIntV NodeIdPermV,
const double &  PermPSwapNd = 0.2 
)

Definition at line 791 of file kronecker.cpp.

791  : PermSwapNodeProb(PermPSwapNd) {
792  InitLL(GraphPt, ParamMtx);
793  NodePerm = NodeIdPermV;
795 }
void SetIPerm(const TIntV &Perm)
!!!!! MYUNGHWAN, CHECK!
Definition: kronecker.cpp:875
TFlt PermSwapNodeProb
Definition: kronecker.h:123
TIntV NodePerm
Definition: kronecker.h:128
void InitLL(const TFltV &ParamV)
Definition: kronecker.cpp:996

Member Function Documentation

void TKroneckerLL::AppendIsoNodes ( )

Definition at line 914 of file kronecker.cpp.

914  {
915  Nodes = (int) pow((double)ProbMtx.GetDim(), KronIters);
916  // add nodes until filling the Kronecker graph model
917  for (int nid = Graph->GetNodes(); nid < Nodes; nid++) {
918  Graph->AddNode(nid);
919  }
920 }
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:499
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graph.cpp:236
TInt KronIters
Definition: kronecker.h:121
TKronMtx ProbMtx
Definition: kronecker.h:134
int GetDim() const
Definition: kronecker.h:30
PNGraph Graph
Definition: kronecker.h:120
const TFltV & TKroneckerLL::CalcApxGraphDLL ( )

Definition at line 1194 of file kronecker.cpp.

1194  {
1195  for (int ParamId = 0; ParamId < LLMtx.Len(); ParamId++) {
1196  double DLL = GetApxEmptyGraphDLL(ParamId);
1197  for (int nid = 0; nid < Nodes; nid++) {
1198  const TNGraph::TNodeI Node = Graph->GetNI(nid);
1199  const int SrcNId = NodePerm[nid];
1200  for (int e = 0; e < Node.GetOutDeg(); e++) {
1201  const int DstNId = NodePerm[Node.GetOutNId(e)];
1202  DLL = DLL - LLMtx.GetApxNoEdgeDLL(ParamId, SrcNId, DstNId, KronIters)
1203  + LLMtx.GetEdgeDLL(ParamId, SrcNId, DstNId, KronIters);
1204  }
1205  }
1206  GradV[ParamId] = DLL;
1207  }
1208  return GradV;
1209 }
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:548
int Len() const
Definition: kronecker.h:31
double GetEdgeDLL(const int &ParamId, int NId1, int NId2, const int &NKronIters) const
Definition: kronecker.cpp:207
TIntV NodePerm
Definition: kronecker.h:128
double GetApxNoEdgeDLL(const int &ParamId, int NId1, int NId2, const int &NKronIters) const
Definition: kronecker.cpp:240
double GetApxEmptyGraphDLL(const int &ParamId) const
Definition: kronecker.cpp:1147
TInt KronIters
Definition: kronecker.h:121
int GetOutDeg() const
Returns out-degree of the current node.
Definition: graph.h:402
TKronMtx LLMtx
Definition: kronecker.h:134
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:379
PNGraph Graph
Definition: kronecker.h:120
TFltV GradV
Definition: kronecker.h:136
int GetOutNId(const int &NodeN) const
Returns ID of NodeN-th out-node (the node the current node points to).
Definition: graph.h:412
double TKroneckerLL::CalcApxGraphLL ( )

Definition at line 1037 of file kronecker.cpp.

1037  {
1038  LogLike = GetApxEmptyGraphLL(); // O(N_0)
1039  for (int nid = 0; nid < Nodes; nid++) {
1040  const TNGraph::TNodeI Node = Graph->GetNI(nid);
1041  const int SrcNId = NodePerm[nid];
1042  for (int e = 0; e < Node.GetOutDeg(); e++) {
1043  const int DstNId = NodePerm[Node.GetOutNId(e)];
1044  LogLike = LogLike - LLMtx.GetApxNoEdgeLL(SrcNId, DstNId, KronIters)
1045  + LLMtx.GetEdgeLL(SrcNId, DstNId, KronIters);
1046  }
1047  }
1048  return LogLike;
1049 }
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:548
double GetApxNoEdgeLL(int NId1, int NId2, const int &NKronIters) const
Definition: kronecker.cpp:191
double GetEdgeLL(int NId1, int NId2, const int &NKronIters) const
Definition: kronecker.cpp:175
TFlt LogLike
Definition: kronecker.h:135
TIntV NodePerm
Definition: kronecker.h:128
double GetApxEmptyGraphLL() const
Definition: kronecker.cpp:987
TInt KronIters
Definition: kronecker.h:121
int GetOutDeg() const
Returns out-degree of the current node.
Definition: graph.h:402
TKronMtx LLMtx
Definition: kronecker.h:134
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:379
PNGraph Graph
Definition: kronecker.h:120
int GetOutNId(const int &NodeN) const
Returns ID of NodeN-th out-node (the node the current node points to).
Definition: graph.h:412
double TKroneckerLL::CalcChainR2 ( const TVec< TFltV > &  ChainLLV)
static

Definition at line 1895 of file kronecker.cpp.

1895  {
1896  const double J = ChainLLV.Len();
1897  const double K = ChainLLV[0].Len();
1898  TFltV AvgJV; McMcGetAvgJ(ChainLLV, AvgJV);
1899  double AvgAvg; McMcGetAvgAvg(AvgJV, AvgAvg);
1900  IAssert(AvgJV.Len() == ChainLLV.Len());
1901  double InChainVar=0, OutChainVar=0;
1902  // between chain var
1903  for (int j = 0; j < AvgJV.Len(); j++) {
1904  OutChainVar += TMath::Sqr(AvgJV[j] - AvgAvg); }
1905  OutChainVar = OutChainVar * (K/double(J-1));
1906  printf("*** %g chains of len %g\n", J, K);
1907  printf(" ** between chain var: %f\n", OutChainVar);
1908  //within chain variance
1909  for (int j = 0; j < AvgJV.Len(); j++) {
1910  const TFltV& ChainV = ChainLLV[j];
1911  for (int k = 0; k < ChainV.Len(); k++) {
1912  InChainVar += TMath::Sqr(ChainV[k] - AvgJV[j]); }
1913  }
1914  InChainVar = InChainVar * 1.0/double(J*(K-1));
1915  printf(" ** within chain var: %f\n", InChainVar);
1916  const double PostVar = (K-1)/K * InChainVar + 1.0/K * OutChainVar;
1917  printf(" ** posterior var: %f\n", PostVar);
1918  const double ScaleRed = sqrt(PostVar/InChainVar);
1919  printf(" ** scale reduction (< 1.2): %f\n\n", ScaleRed);
1920  return ScaleRed;
1921 }
#define IAssert(Cond)
Definition: bd.h:262
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
static double Sqr(const double &x)
Definition: xmath.h:12
void McMcGetAvgAvg(const TFltV &AvgJV, double &AvgAvg)
Definition: kronecker.cpp:1876
void McMcGetAvgJ(const TVec< TFltV > &ChainLLV, TFltV &AvgJV)
Definition: kronecker.cpp:1883
const TFltV & TKroneckerLL::CalcFullApxGraphDLL ( )

Definition at line 1176 of file kronecker.cpp.

1176  {
1177  for (int ParamId = 0; ParamId < LLMtx.Len(); ParamId++) {
1178  double DLL = 0.0;
1179  for (int NId1 = 0; NId1 < Nodes; NId1++) {
1180  for (int NId2 = 0; NId2 < Nodes; NId2++) {
1181  if (Graph->IsEdge(NId1, NId2)) {
1182  DLL += LLMtx.GetEdgeDLL(ParamId, NodePerm[NId1], NodePerm[NId2], KronIters);
1183  } else {
1184  DLL += LLMtx.GetApxNoEdgeDLL(ParamId, NodePerm[NId1], NodePerm[NId2], KronIters);
1185  }
1186  }
1187  }
1188  GradV[ParamId] = DLL;
1189  }
1190  return GradV;
1191 }
int Len() const
Definition: kronecker.h:31
double GetEdgeDLL(const int &ParamId, int NId1, int NId2, const int &NKronIters) const
Definition: kronecker.cpp:207
TIntV NodePerm
Definition: kronecker.h:128
double GetApxNoEdgeDLL(const int &ParamId, int NId1, int NId2, const int &NKronIters) const
Definition: kronecker.cpp:240
bool IsEdge(const int &SrcNId, const int &DstNId, const bool &IsDir=true) const
Tests whether an edge from node IDs SrcNId to DstNId exists in the graph.
Definition: graph.cpp:363
TInt KronIters
Definition: kronecker.h:121
TKronMtx LLMtx
Definition: kronecker.h:134
PNGraph Graph
Definition: kronecker.h:120
TFltV GradV
Definition: kronecker.h:136
const TFltV & TKroneckerLL::CalcGraphDLL ( )

Definition at line 1158 of file kronecker.cpp.

1158  {
1159  for (int ParamId = 0; ParamId < LLMtx.Len(); ParamId++) {
1160  double DLL = 0.0;
1161  for (int NId1 = 0; NId1 < Nodes; NId1++) {
1162  for (int NId2 = 0; NId2 < Nodes; NId2++) {
1163  if (Graph->IsEdge(NId1, NId2)) {
1164  DLL += LLMtx.GetEdgeDLL(ParamId, NodePerm[NId1], NodePerm[NId2], KronIters);
1165  } else {
1166  DLL += LLMtx.GetNoEdgeDLL(ParamId, NodePerm[NId1], NodePerm[NId2], KronIters);
1167  }
1168  }
1169  }
1170  GradV[ParamId] = DLL;
1171  }
1172  return GradV;
1173 }
int Len() const
Definition: kronecker.h:31
double GetEdgeDLL(const int &ParamId, int NId1, int NId2, const int &NKronIters) const
Definition: kronecker.cpp:207
TIntV NodePerm
Definition: kronecker.h:128
bool IsEdge(const int &SrcNId, const int &DstNId, const bool &IsDir=true) const
Tests whether an edge from node IDs SrcNId to DstNId exists in the graph.
Definition: graph.cpp:363
TInt KronIters
Definition: kronecker.h:121
TKronMtx LLMtx
Definition: kronecker.h:134
PNGraph Graph
Definition: kronecker.h:120
TFltV GradV
Definition: kronecker.h:136
double GetNoEdgeDLL(const int &ParamId, int NId1, int NId2, const int &NKronIters) const
Definition: kronecker.cpp:220
double TKroneckerLL::CalcGraphLL ( )

Definition at line 1022 of file kronecker.cpp.

1022  {
1023  LogLike = GetEmptyGraphLL(); // takes O(N^2)
1024  for (int nid = 0; nid < Nodes; nid++) {
1025  const TNGraph::TNodeI Node = Graph->GetNI(nid);
1026  const int SrcNId = NodePerm[nid];
1027  for (int e = 0; e < Node.GetOutDeg(); e++) {
1028  const int DstNId = NodePerm[Node.GetOutNId(e)];
1029  LogLike = LogLike - LLMtx.GetNoEdgeLL(SrcNId, DstNId, KronIters)
1030  + LLMtx.GetEdgeLL(SrcNId, DstNId, KronIters);
1031  }
1032  }
1033  return LogLike;
1034 }
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:548
double GetEdgeLL(int NId1, int NId2, const int &NKronIters) const
Definition: kronecker.cpp:175
double GetEmptyGraphLL() const
Definition: kronecker.cpp:976
TFlt LogLike
Definition: kronecker.h:135
TIntV NodePerm
Definition: kronecker.h:128
TInt KronIters
Definition: kronecker.h:121
int GetOutDeg() const
Returns out-degree of the current node.
Definition: graph.h:402
double GetNoEdgeLL(int NId1, int NId2, const int &NKronIters) const
Definition: kronecker.cpp:186
TKronMtx LLMtx
Definition: kronecker.h:134
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:379
PNGraph Graph
Definition: kronecker.h:120
int GetOutNId(const int &NodeN) const
Returns ID of NodeN-th out-node (the node the current node points to).
Definition: graph.h:412
void TKroneckerLL::ChainGelmapRubinPlot ( const TVec< TFltV > &  ChainLLV,
const TStr OutFNm,
const TStr Desc 
)
static

Definition at line 1924 of file kronecker.cpp.

1924  {
1925  TFltPrV LenR2V; // how does potential scale reduction chainge with chain length
1926  TVec<TFltV> SmallLLV(ChainLLV.Len());
1927  const int K = ChainLLV[0].Len();
1928  const int Buckets=1000;
1929  const int BucketSz = K/Buckets;
1930  for (int b = 1; b < Buckets; b++) {
1931  const int End = TMath::Mn(BucketSz*b, K-1);
1932  for (int c = 0; c < ChainLLV.Len(); c++) {
1933  ChainLLV[c].GetSubValV(0, End, SmallLLV[c]); }
1934  LenR2V.Add(TFltPr(End, TKroneckerLL::CalcChainR2(SmallLLV)));
1935  }
1936  LenR2V.Add(TFltPr(K, TKroneckerLL::CalcChainR2(ChainLLV)));
1937  TGnuPlot::PlotValV(LenR2V, TStr::Fmt("gelman-%s", OutFNm.CStr()), TStr::Fmt("%s. %d chains of len %d. BucketSz: %d.",
1938  Desc.CStr(), ChainLLV.Len(), ChainLLV[0].Len(), BucketSz), "Chain length", "Potential scale reduction");
1939 }
static const T & Mn(const T &LVal, const T &RVal)
Definition: xmath.h:36
static double CalcChainR2(const TVec< TFltV > &ChainLLV)
Definition: kronecker.cpp:1895
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TPair< TFlt, TFlt > TFltPr
Definition: ds.h:99
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
char * CStr()
Definition: dt.h:476
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
static void PlotValV(const TVec< TVal1 > &ValV, const TStr &OutFNmPref, const TStr &Desc="", const TStr &XLabel="", const TStr &YLabel="", const TGpScaleTy &ScaleTy=gpsAuto, const bool &PowerFit=false, const TGpSeriesTy &SeriesTy=gpwLinesPoints)
Definition: gnuplot.h:398
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:430
void GetSubValV(const TSizeTy &BValN, const TSizeTy &EValN, TVec< TVal, TSizeTy > &ValV) const
Fills ValV with elements at positions BValN...EValN.
Definition: ds.h:1170
double TKroneckerLL::GetAbsErr ( ) const
inline

Definition at line 205 of file kronecker.h.

205 { return fabs(pow((double)Graph->GetEdges(), 1.0/double(KronIters)) - ProbMtx.GetMtxSum()); }
double GetMtxSum() const
Definition: kronecker.cpp:140
int GetEdges() const
Returns the number of edges in the graph.
Definition: graph.cpp:313
TInt KronIters
Definition: kronecker.h:121
TKronMtx ProbMtx
Definition: kronecker.h:134
PNGraph Graph
Definition: kronecker.h:120
double TKroneckerLL::GetApxEmptyGraphDLL ( const int &  ParamId) const

Definition at line 1147 of file kronecker.cpp.

1147  {
1148  double Sum=0.0, SumSq=0.0;
1149  for (int i = 0; i < ProbMtx.Len(); i++) {
1150  Sum += ProbMtx.At(i);
1151  SumSq += TMath::Sqr(ProbMtx.At(i));
1152  }
1153  // d/dx -sum(x_i) - 0.5sum(x_i^2) = d/dx sum(theta)^k - 0.5 sum(theta^2)^k
1154  return -KronIters*pow(Sum, KronIters-1) - KronIters*pow(SumSq, KronIters-1)*ProbMtx.At(ParamId);
1155 }
int Len() const
Definition: kronecker.h:31
static double Sqr(const double &x)
Definition: xmath.h:12
const double & At(const int &Row, const int &Col) const
Definition: kronecker.h:46
TInt KronIters
Definition: kronecker.h:121
TKronMtx ProbMtx
Definition: kronecker.h:134
double TKroneckerLL::GetApxEmptyGraphLL ( ) const

Definition at line 987 of file kronecker.cpp.

987  {
988  double Sum=0.0, SumSq=0.0;
989  for (int i = 0; i < ProbMtx.Len(); i++) {
990  Sum += ProbMtx.At(i);
991  SumSq += TMath::Sqr(ProbMtx.At(i));
992  }
993  return -pow(Sum, KronIters) - 0.5*pow(SumSq, KronIters);
994 }
int Len() const
Definition: kronecker.h:31
static double Sqr(const double &x)
Definition: xmath.h:12
const double & At(const int &Row, const int &Col) const
Definition: kronecker.h:46
TInt KronIters
Definition: kronecker.h:121
TKronMtx ProbMtx
Definition: kronecker.h:134
int TKroneckerLL::GetDim ( ) const
inline

Definition at line 165 of file kronecker.h.

165 { return ProbMtx.GetDim(); }
TKronMtx ProbMtx
Definition: kronecker.h:134
int GetDim() const
Definition: kronecker.h:30
const TFltV& TKroneckerLL::GetDLL ( ) const
inline

Definition at line 218 of file kronecker.h.

218 { return GradV; }
TFltV GradV
Definition: kronecker.h:136
double TKroneckerLL::GetDLL ( const int &  ParamId) const
inline

Definition at line 219 of file kronecker.h.

219 { return GradV[ParamId]; }
TFltV GradV
Definition: kronecker.h:136
double TKroneckerLL::GetEmptyGraphDLL ( const int &  ParamId) const

Definition at line 1136 of file kronecker.cpp.

1136  {
1137  double DLL = 0.0;
1138  for (int NId1 = 0; NId1 < Nodes; NId1++) {
1139  for (int NId2 = 0; NId2 < Nodes; NId2++) {
1140  DLL += LLMtx.GetNoEdgeDLL(ParamId, NodePerm[NId1], NodePerm[NId2], KronIters);
1141  }
1142  }
1143  return DLL;
1144 }
TIntV NodePerm
Definition: kronecker.h:128
TInt KronIters
Definition: kronecker.h:121
TKronMtx LLMtx
Definition: kronecker.h:134
double GetNoEdgeDLL(const int &ParamId, int NId1, int NId2, const int &NKronIters) const
Definition: kronecker.cpp:220
double TKroneckerLL::GetEmptyGraphLL ( ) const

Definition at line 976 of file kronecker.cpp.

976  {
977  double LL = 0;
978  for (int NId1 = 0; NId1 < LLMtx.GetNodes(KronIters); NId1++) {
979  for (int NId2 = 0; NId2 < LLMtx.GetNodes(KronIters); NId2++) {
980  LL = LL + LLMtx.GetNoEdgeLL(NId1, NId2, KronIters);
981  }
982  }
983  return LL;
984 }
TInt KronIters
Definition: kronecker.h:121
double GetNoEdgeLL(int NId1, int NId2, const int &NKronIters) const
Definition: kronecker.cpp:186
TKronMtx LLMtx
Definition: kronecker.h:134
int GetNodes(const int &NIter) const
Definition: kronecker.cpp:119
double TKroneckerLL::GetFullColLL ( int  ColId) const

Definition at line 966 of file kronecker.cpp.

966  {
967  double ColLL = 0.0;
968  const int MtxDim = LLMtx.GetDim();
969  for (int level = 0; level < KronIters; level++) {
970  ColLL += LLMtx.GetColSum(ColId % MtxDim);
971  ColId /= MtxDim;
972  }
973  return ColLL;
974 }
double GetColSum(const int &ColId) const
Definition: kronecker.cpp:154
TInt KronIters
Definition: kronecker.h:121
int GetDim() const
Definition: kronecker.h:30
TKronMtx LLMtx
Definition: kronecker.h:134
double TKroneckerLL::GetFullGraphLL ( ) const

Definition at line 943 of file kronecker.cpp.

943  {
944  // the number of times a seed matrix element appears in
945  // the full kronecker adjacency matrix after KronIter
946  // kronecker multiplications
947  double ElemCnt = 1;
948  const double dim = LLMtx.GetDim();
949  // count number of times x appears in the full kronecker matrix
950  for (int i = 1; i < KronIters; i++) {
951  ElemCnt = dim*dim*ElemCnt + TMath::Power(dim, 2*i);
952  }
953  return ElemCnt * LLMtx.GetMtxSum();
954 }
double GetMtxSum() const
Definition: kronecker.cpp:140
static double Power(const double &Base, const double &Exponent)
Definition: xmath.h:25
TInt KronIters
Definition: kronecker.h:121
int GetDim() const
Definition: kronecker.h:30
TKronMtx LLMtx
Definition: kronecker.h:134
double TKroneckerLL::GetFullRowLL ( int  RowId) const

Definition at line 956 of file kronecker.cpp.

956  {
957  double RowLL = 0.0;
958  const int MtxDim = LLMtx.GetDim();
959  for (int level = 0; level < KronIters; level++) {
960  RowLL += LLMtx.GetRowSum(RowId % MtxDim);
961  RowId /= MtxDim;
962  }
963  return RowLL;
964 }
TInt KronIters
Definition: kronecker.h:121
int GetDim() const
Definition: kronecker.h:30
TKronMtx LLMtx
Definition: kronecker.h:134
double GetRowSum(const int &RowId) const
Definition: kronecker.cpp:147
PNGraph TKroneckerLL::GetGraph ( ) const
inline

Definition at line 160 of file kronecker.h.

160 { return Graph; }
PNGraph Graph
Definition: kronecker.h:120
int TKroneckerLL::GetKronIters ( ) const
inline

Definition at line 159 of file kronecker.h.

159 { return KronIters; }
TInt KronIters
Definition: kronecker.h:121
double TKroneckerLL::GetLL ( ) const
inline

Definition at line 204 of file kronecker.h.

204 { return LogLike; }
TFlt LogLike
Definition: kronecker.h:135
const TFltV& TKroneckerLL::GetLLHist ( ) const
inline

Definition at line 168 of file kronecker.h.

168 { return LLV; }
const TKronMtx& TKroneckerLL::GetLLMtx ( ) const
inline

Definition at line 163 of file kronecker.h.

163 { return LLMtx; }
TKronMtx LLMtx
Definition: kronecker.h:134
int TKroneckerLL::GetNodes ( ) const
inline

Definition at line 158 of file kronecker.h.

158 { return Nodes; }
const TVec<TKronMtx>& TKroneckerLL::GetParamHist ( ) const
inline

Definition at line 169 of file kronecker.h.

169 { return MtxV; }
TVec< TKronMtx > MtxV
Definition: kronecker.h:143
int TKroneckerLL::GetParams ( ) const
inline

Definition at line 164 of file kronecker.h.

164 { return ProbMtx.Len(); }
int Len() const
Definition: kronecker.h:31
TKronMtx ProbMtx
Definition: kronecker.h:134
const TIntV& TKroneckerLL::GetPermV ( ) const
inline

Definition at line 185 of file kronecker.h.

185 { return NodePerm; }
TIntV NodePerm
Definition: kronecker.h:128
const TKronMtx& TKroneckerLL::GetProbMtx ( ) const
inline

Definition at line 162 of file kronecker.h.

162 { return ProbMtx; }
TKronMtx ProbMtx
Definition: kronecker.h:134
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.

1299  {
1300  printf("\n----------------------------------------------------------------------\n");
1301  printf("Fitting graph on %d nodes, %d edges\n", Graph->GetNodes(), Graph->GetEdges());
1302  printf("Kron iters: %d (== %d nodes)\n\n", KronIters(), ProbMtx.GetNodes(KronIters()));
1303  TExeTm IterTm, TotalTm;
1304  double OldLL=-1e10, CurLL=0;
1305  const double EZero = pow((double) Graph->GetEdges(), 1.0/double(KronIters));
1306  TFltV CurGradV, LearnRateV(GetParams()), LastStep(GetParams());
1307  LearnRateV.PutAll(LrnRate);
1308  TKronMtx NewProbMtx = ProbMtx;
1309 
1310  if(DebugMode) {
1311  LLV.Gen(NIter, 0);
1312  MtxV.Gen(NIter, 0);
1313  }
1314 
1315  for (int Iter = 0; Iter < NIter; Iter++) {
1316  printf("%03d] ", Iter);
1317  SampleGradient(WarmUp, NSamples, CurLL, CurGradV);
1318  for (int p = 0; p < GetParams(); p++) {
1319  LearnRateV[p] *= 0.95;
1320  if (Iter < 1) {
1321  while (fabs(LearnRateV[p]*CurGradV[p]) > MxStep) { LearnRateV[p] *= 0.95; }
1322  while (fabs(LearnRateV[p]*CurGradV[p]) < 0.02) { LearnRateV[p] *= (1.0/0.95); } // move more
1323  } else {
1324  // set learn rate so that move for each parameter is inside the [MnStep, MxStep]
1325  while (fabs(LearnRateV[p]*CurGradV[p]) > MxStep) { LearnRateV[p] *= 0.95; printf(".");}
1326  while (fabs(LearnRateV[p]*CurGradV[p]) < MnStep) { LearnRateV[p] *= (1.0/0.95); printf("*");}
1327  if (MxStep > 3*MnStep) { MxStep *= 0.95; }
1328  }
1329  NewProbMtx.At(p) = ProbMtx.At(p) + LearnRateV[p]*CurGradV[p];
1330  if (NewProbMtx.At(p) > 0.9999) { NewProbMtx.At(p)=0.9999; }
1331  if (NewProbMtx.At(p) < 0.0001) { NewProbMtx.At(p)=0.0001; }
1332  }
1333  printf(" trueE0: %.2f (%d), estE0: %.2f (%d), ERR: %f\n", EZero, Graph->GetEdges(),
1335  printf(" currLL: %.4f, deltaLL: %.4f\n", CurLL, CurLL-OldLL); // positive is good
1336  for (int p = 0; p < GetParams(); p++) {
1337  printf(" %d] %f <-- %f + %9f Grad: %9.1f Rate: %g\n", p, NewProbMtx.At(p),
1338  ProbMtx.At(p), (double)(LearnRateV[p]*CurGradV[p]), CurGradV[p](), LearnRateV[p]());
1339  }
1340  if (Iter+1 < NIter) { // skip last update
1341  ProbMtx = NewProbMtx; ProbMtx.GetLLMtx(LLMtx); }
1342  OldLL=CurLL;
1343  printf("\n"); fflush(stdout);
1344 
1345  if(DebugMode) {
1346  LLV.Add(CurLL);
1347  MtxV.Add(NewProbMtx);
1348  }
1349  }
1350  printf("TotalExeTm: %s %g\n", TotalTm.GetStr(), TotalTm.GetSecs());
1351  ProbMtx.Dump("FITTED PARAMS", false);
1352  return CurLL;
1353 }
int GetParams() const
Definition: kronecker.h:164
int GetEdges(const int &NIter) const
Definition: kronecker.cpp:123
Definition: tm.h:355
double GetMtxSum() const
Definition: kronecker.cpp:140
int GetEdges() const
Returns the number of edges in the graph.
Definition: graph.cpp:313
void Dump(const TStr &MtxNm=TStr(), const bool &Sort=false) const
Definition: kronecker.cpp:636
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:499
const double & At(const int &Row, const int &Col) const
Definition: kronecker.h:46
TVec< TKronMtx > MtxV
Definition: kronecker.h:143
void SampleGradient(const int &WarmUp, const int &NSamples, double &AvgLL, TFltV &GradV)
Definition: kronecker.cpp:1271
TBool DebugMode
Definition: kronecker.h:141
void GetLLMtx(TKronMtx &LLMtx)
Definition: kronecker.cpp:98
TInt KronIters
Definition: kronecker.h:121
TKronMtx ProbMtx
Definition: kronecker.h:134
TKronMtx LLMtx
Definition: kronecker.h:134
PNGraph Graph
Definition: kronecker.h:120
int GetNodes(const int &NIter) const
Definition: kronecker.cpp:119
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
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.

1355  {
1356  printf("\n----------------------------------------------------------------------\n");
1357  printf("GradDescent2\n");
1358  printf("Fitting graph on %d nodes, %d edges\n", Graph->GetNodes(), Graph->GetEdges());
1359  printf("Skip moves that make likelihood smaller\n");
1360  printf("Kron iters: %d (== %d nodes)\n\n", KronIters(), ProbMtx.GetNodes(KronIters()));
1361  TExeTm IterTm, TotalTm;
1362  double CurLL=0, NewLL=0;
1363  const double EZero = pow((double) Graph->GetEdges(), 1.0/double(KronIters));
1364  TFltV CurGradV, NewGradV, LearnRateV(GetParams()), LastStep(GetParams());
1365  LearnRateV.PutAll(LrnRate);
1366  TKronMtx NewProbMtx=ProbMtx, CurProbMtx=ProbMtx;
1367  bool GoodMove = false;
1368  // Start
1369  for (int Iter = 0; Iter < NIter; Iter++) {
1370  printf("%03d] ", Iter);
1371  if (! GoodMove) { SampleGradient(WarmUp, NSamples, CurLL, CurGradV); }
1372  CurProbMtx = ProbMtx;
1373  // update parameters
1374  for (int p = 0; p < GetParams(); p++) {
1375  while (fabs(LearnRateV[p]*CurGradV[p]) > MxStep) { LearnRateV[p] *= 0.95; printf(".");}
1376  while (fabs(LearnRateV[p]*CurGradV[p]) < MnStep) { LearnRateV[p] *= (1.0/0.95); printf("*");}
1377  NewProbMtx.At(p) = CurProbMtx.At(p) + LearnRateV[p]*CurGradV[p];
1378  if (NewProbMtx.At(p) > 0.9999) { NewProbMtx.At(p)=0.9999; }
1379  if (NewProbMtx.At(p) < 0.0001) { NewProbMtx.At(p)=0.0001; }
1380  LearnRateV[p] *= 0.95;
1381  }
1382  printf(" ");
1383  ProbMtx=NewProbMtx; ProbMtx.GetLLMtx(LLMtx);
1384  SampleGradient(WarmUp, NSamples, NewLL, NewGradV);
1385  if (NewLL > CurLL) { // accept the move
1386  printf("== Good move:\n");
1387  printf(" trueE0: %.2f (%d), estE0: %.2f (%d), ERR: %f\n", EZero, Graph->GetEdges(),
1389  printf(" currLL: %.4f deltaLL: %.4f\n", CurLL, NewLL-CurLL); // positive is good
1390  for (int p = 0; p < GetParams(); p++) {
1391  printf(" %d] %f <-- %f + %9f Grad: %9.1f Rate: %g\n", p, NewProbMtx.At(p),
1392  CurProbMtx.At(p), (double)(LearnRateV[p]*CurGradV[p]), CurGradV[p](), LearnRateV[p]()); }
1393  CurLL = NewLL;
1394  CurGradV = NewGradV;
1395  GoodMove = true;
1396  } else {
1397  printf("** BAD move:\n");
1398  printf(" *trueE0: %.2f (%d), estE0: %.2f (%d), ERR: %f\n", EZero, Graph->GetEdges(),
1400  printf(" *curLL: %.4f deltaLL: %.4f\n", CurLL, NewLL-CurLL); // positive is good
1401  for (int p = 0; p < GetParams(); p++) {
1402  printf(" b%d] %f <-- %f + %9f Grad: %9.1f Rate: %g\n", p, NewProbMtx.At(p),
1403  CurProbMtx.At(p), (double)(LearnRateV[p]*CurGradV[p]), CurGradV[p](), LearnRateV[p]()); }
1404  // move to old position
1405  ProbMtx = CurProbMtx; ProbMtx.GetLLMtx(LLMtx);
1406  GoodMove = false;
1407  }
1408  printf("\n"); fflush(stdout);
1409  }
1410  printf("TotalExeTm: %s %g\n", TotalTm.GetStr(), TotalTm.GetSecs());
1411  ProbMtx.Dump("FITTED PARAMS\n", false);
1412  return CurLL;
1413 }
int GetParams() const
Definition: kronecker.h:164
int GetEdges(const int &NIter) const
Definition: kronecker.cpp:123
Definition: tm.h:355
double GetMtxSum() const
Definition: kronecker.cpp:140
int GetEdges() const
Returns the number of edges in the graph.
Definition: graph.cpp:313
void Dump(const TStr &MtxNm=TStr(), const bool &Sort=false) const
Definition: kronecker.cpp:636
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:499
const double & At(const int &Row, const int &Col) const
Definition: kronecker.h:46
void SampleGradient(const int &WarmUp, const int &NSamples, double &AvgLL, TFltV &GradV)
Definition: kronecker.cpp:1271
void GetLLMtx(TKronMtx &LLMtx)
Definition: kronecker.cpp:98
TInt KronIters
Definition: kronecker.h:121
TKronMtx ProbMtx
Definition: kronecker.h:134
TKronMtx LLMtx
Definition: kronecker.h:134
PNGraph Graph
Definition: kronecker.h:120
int GetNodes(const int &NIter) const
Definition: kronecker.cpp:119
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.

2018  {
2019  TExeTm IterTm;
2020  int Iter;
2021  double OldLL=0, MyLL=0, AvgAbsErr=0, AbsSumErr=0;
2022  TFltV MyGradV, SDevV;
2023  TFltV LearnRateV(GetParams()); LearnRateV.PutAll(LearnRate);
2024  TFltPrV EZeroV, DiamV, Lambda1V, Lambda2V, AvgAbsErrV, AvgLLV;
2025  TFltPrV TrueEZeroV, TrueDiamV, TrueLambda1V, TrueLambda2V, TrueLLV;
2026  TFltV SngValV; TSnap::GetSngVals(Graph, 2, SngValV); SngValV.Sort(false);
2027  const double TrueEZero = pow((double) Graph->GetEdges(), 1.0/double(KronIters));
2028  const double TrueEffDiam = TSnap::GetAnfEffDiam(Graph, false, 10);
2029  const double TrueLambda1 = SngValV[0];
2030  const double TrueLambda2 = SngValV[1];
2031  if (! TrueParam.Empty()) {
2032  const TKronMtx CurParam = ProbMtx; ProbMtx.Dump();
2033  InitLL(TrueParam); SetOrderPerm(); CalcApxGraphLL(); printf("TrueLL: %f\n", LogLike());
2034  OldLL = LogLike; InitLL(CurParam);
2035  }
2036  const double TrueLL = OldLL;
2037  if (! SamplePerm) { SetOrderPerm(); } else { SetDegPerm(); }
2038  for (Iter = 0; Iter < NIters; Iter++) {
2039  if (! SamplePerm) {
2040  // don't sample over permutations
2041  CalcApxGraphDLL(); CalcApxGraphLL(); // fast
2042  MyLL = LogLike; MyGradV = GradV;
2043  } else {
2044  // sample over permutations (approximate calculations)
2045  SampleGradient(WarmUp, NSamples, MyLL, MyGradV);
2046  }
2047  double SumDiam=0, SumSngVal1=0, SumSngVal2=0;
2048  for (int trial = 0; trial < AvgKGraphs; trial++) {
2049  // generate kronecker graph
2050  PNGraph KronGraph = TKronMtx::GenFastKronecker(ProbMtx, KronIters, true, 0); // approx
2051  //PNGraph KronGraph = TKronMtx::GenKronecker(ProbMtx, KronIters, true, 0); // true
2052  SngValV.Clr(true); TSnap::GetSngVals(KronGraph, 2, SngValV); SngValV.Sort(false);
2053  SumDiam += TSnap::GetAnfEffDiam(KronGraph, false, 10);
2054  SumSngVal1 += SngValV[0]; SumSngVal2 += SngValV[1];
2055  }
2056  // how good is the current fit
2057  AvgLLV.Add(TFltPr(Iter, MyLL));
2058  EZeroV.Add(TFltPr(Iter, ProbMtx.GetMtxSum()));
2059  DiamV.Add(TFltPr(Iter, SumDiam/double(AvgKGraphs)));
2060  Lambda1V.Add(TFltPr(Iter, SumSngVal1/double(AvgKGraphs)));
2061  Lambda2V.Add(TFltPr(Iter, SumSngVal2/double(AvgKGraphs)));
2062  TrueLLV.Add(TFltPr(Iter, TrueLL));
2063  TrueEZeroV.Add(TFltPr(Iter, TrueEZero));
2064  TrueDiamV.Add(TFltPr(Iter, TrueEffDiam));
2065  TrueLambda1V.Add(TFltPr(Iter, TrueLambda1));
2066  TrueLambda2V.Add(TFltPr(Iter, TrueLambda2));
2067  if (Iter % 10 == 0) {
2068  const TStr Desc = TStr::Fmt("%s. Iter: %d, G(%d, %d) K(%d, %d)", Desc1.Empty()?OutFNm.CStr():Desc1.CStr(),
2070  PlotTrueAndEst("LL."+OutFNm, Desc, "Average LL", AvgLLV, TrueLLV);
2071  PlotTrueAndEst("E0."+OutFNm, Desc, "E0 (expected number of edges)", EZeroV, TrueEZeroV);
2072  PlotTrueAndEst("Diam."+OutFNm+"-Diam", Desc, "Effective diameter", DiamV, TrueDiamV);
2073  PlotTrueAndEst("Lambda1."+OutFNm, Desc, "Lambda 1", Lambda1V, TrueLambda1V);
2074  PlotTrueAndEst("Lambda2."+OutFNm, Desc, "Lambda 2", Lambda2V, TrueLambda2V);
2075  if (! TrueParam.Empty()) {
2076  PlotTrueAndEst("AbsErr."+OutFNm, Desc, "Average Absolute Error", AvgAbsErrV, TFltPrV()); }
2077  }
2078  if (! TrueParam.Empty()) {
2079  AvgAbsErr = TKronMtx::GetAvgAbsErr(ProbMtx, TrueParam);
2080  AvgAbsErrV.Add(TFltPr(Iter, AvgAbsErr));
2081  } else { AvgAbsErr = 1.0; }
2082  // update parameters
2083  AbsSumErr = fabs(ProbMtx.GetMtxSum() - TrueEZero);
2084  // update parameters
2085  for (int p = 0; p < GetParams(); p++) {
2086  LearnRateV[p] *= 0.99;
2087  while (fabs(LearnRateV[p]*MyGradV[p]) > 0.1) { LearnRateV[p] *= 0.99; printf(".");}
2088  while (fabs(LearnRateV[p]*MyGradV[p]) < 0.002) { LearnRateV[p] *= (1.0/0.95); printf("*");}
2089  printf(" %d] %f <-- %f + %9f Grad: %9.1f, Rate:%g\n", p, ProbMtx.At(p) + LearnRateV[p]*MyGradV[p],
2090  ProbMtx.At(p), (double)(LearnRateV[p]*MyGradV[p]), MyGradV[p](), LearnRateV[p]());
2091  ProbMtx.At(p) = ProbMtx.At(p) + LearnRateV[p]*MyGradV[p];
2092  // box constraints
2093  if (ProbMtx.At(p) > 1.0) { ProbMtx.At(p)=1.0; }
2094  if (ProbMtx.At(p) < 0.001) { ProbMtx.At(p)=0.001; }
2095  }
2096  printf("%d] LL: %g, ", Iter, MyLL);
2097  printf(" avgAbsErr: %.4f, absSumErr: %.4f, newLL: %.2f, deltaLL: %.2f\n", AvgAbsErr, AbsSumErr, MyLL, OldLL-MyLL);
2098  if (AvgAbsErr < 0.001) { printf("***CONVERGED!\n"); break; }
2099  printf("\n"); fflush(stdout);
2100  ProbMtx.GetLLMtx(LLMtx); OldLL = MyLL;
2101  }
2102  TrueParam.Dump("True Thetas", true);
2103  ProbMtx.Dump("Final Thetas", true);
2104  printf(" AvgAbsErr: %f\n AbsSumErr: %f\n Iterations: %d\n", AvgAbsErr, AbsSumErr, Iter);
2105  printf("Iteration run time: %s, sec: %g\n\n", IterTm.GetTmStr(), IterTm.GetSecs());
2106 }
int GetParams() const
Definition: kronecker.h:164
int GetEdges(const int &NIter) const
Definition: kronecker.cpp:123
Definition: tm.h:355
double GetMtxSum() const
Definition: kronecker.cpp:140
void SetOrderPerm()
Definition: kronecker.cpp:813
int GetEdges() const
Returns the number of edges in the graph.
Definition: graph.cpp:313
void Dump(const TStr &MtxNm=TStr(), const bool &Sort=false) const
Definition: kronecker.cpp:636
double GetAnfEffDiam(const PGraph &Graph, const bool &IsDir, const double &Percentile, const int &NApprox)
Definition: anf.h:216
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:499
TVec< TFltPr > TFltPrV
Definition: ds.h:1604
TFlt LogLike
Definition: kronecker.h:135
const double & At(const int &Row, const int &Col) const
Definition: kronecker.h:46
double CalcApxGraphLL()
Definition: kronecker.cpp:1037
const char * GetTmStr() const
Definition: tm.h:370
void SetDegPerm()
Definition: kronecker.cpp:828
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:1022
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1318
void SampleGradient(const int &WarmUp, const int &NSamples, double &AvgLL, TFltV &GradV)
Definition: kronecker.cpp:1271
bool Empty() const
Definition: kronecker.h:32
void InitLL(const TFltV &ParamV)
Definition: kronecker.cpp:996
TPair< TFlt, TFlt > TFltPr
Definition: ds.h:99
void GetLLMtx(TKronMtx &LLMtx)
Definition: kronecker.cpp:98
void GetSngVals(const PNGraph &Graph, const int &SngVals, TFltV &SngValV)
Computes largest SngVals singular values of the adjacency matrix representing a directed Graph...
Definition: gsvd.cpp:175
TInt KronIters
Definition: kronecker.h:121
TKronMtx ProbMtx
Definition: kronecker.h:134
void PlotTrueAndEst(const TStr &OutFNm, const TStr &Desc, const TStr &YLabel, const TFltPrV &EstV, const TFltPrV &TrueV)
Definition: kronecker.cpp:2009
const TFltV & CalcApxGraphDLL()
Definition: kronecker.cpp:1194
Definition: dt.h:412
bool Empty() const
Definition: dt.h:488
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
TKronMtx LLMtx
Definition: kronecker.h:134
PNGraph Graph
Definition: kronecker.h:120
double GetSecs() const
Definition: tm.h:366
TFltV GradV
Definition: kronecker.h:136
int GetNodes(const int &NIter) const
Definition: kronecker.cpp:119
char * CStr()
Definition: dt.h:476
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
static double GetAvgAbsErr(const TKronMtx &Kron1, const TKronMtx &Kron2)
Definition: kronecker.cpp:655
static PNGraph GenFastKronecker(const TKronMtx &SeedMtx, const int &NIter, const bool &IsDir, const int &Seed=0)
Definition: kronecker.cpp:349
void TKroneckerLL::InitLL ( const TFltV ParamV)

Definition at line 996 of file kronecker.cpp.

996  {
997  InitLL(TKronMtx(ParamV));
998 }
void InitLL(const TFltV &ParamV)
Definition: kronecker.cpp:996
void TKroneckerLL::InitLL ( const TKronMtx ParamMtx)

Definition at line 1000 of file kronecker.cpp.

1000  {
1001  IAssert(ParamMtx.IsProbMtx());
1002  ProbMtx = ParamMtx;
1003  ProbMtx.GetLLMtx(LLMtx);
1005  if (GradV.Len() != ProbMtx.Len()) {
1006  GradV.Gen(ProbMtx.Len()); }
1007  GradV.PutAll(0.0);
1008 }
#define IAssert(Cond)
Definition: bd.h:262
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
static const double NInf
Definition: kronecker.h:13
TFlt LogLike
Definition: kronecker.h:135
bool IsProbMtx() const
Definition: kronecker.cpp:33
void PutAll(const TVal &Val)
Sets all elements of the vector to value Val.
Definition: ds.h:1229
void GetLLMtx(TKronMtx &LLMtx)
Definition: kronecker.cpp:98
TKronMtx ProbMtx
Definition: kronecker.h:134
TKronMtx LLMtx
Definition: kronecker.h:134
TFltV GradV
Definition: kronecker.h:136
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
void TKroneckerLL::InitLL ( const PNGraph GraphPt,
const TKronMtx ParamMtx 
)

Definition at line 1010 of file kronecker.cpp.

1010  {
1011  IAssert(ParamMtx.IsProbMtx());
1012  ProbMtx = ParamMtx;
1013  ProbMtx.GetLLMtx(LLMtx);
1014  SetGraph(GraphPt);
1016  if (GradV.Len() != ProbMtx.Len()) {
1017  GradV.Gen(ProbMtx.Len()); }
1018  GradV.PutAll(0.0);
1019 }
#define IAssert(Cond)
Definition: bd.h:262
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
static const double NInf
Definition: kronecker.h:13
TFlt LogLike
Definition: kronecker.h:135
bool IsProbMtx() const
Definition: kronecker.cpp:33
void PutAll(const TVal &Val)
Sets all elements of the vector to value Val.
Definition: ds.h:1229
void GetLLMtx(TKronMtx &LLMtx)
Definition: kronecker.cpp:98
TKronMtx ProbMtx
Definition: kronecker.h:134
TKronMtx LLMtx
Definition: kronecker.h:134
TFltV GradV
Definition: kronecker.h:136
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
void SetGraph(const PNGraph &GraphPt)
Definition: kronecker.cpp:882
bool TKroneckerLL::IsLatentEdge ( const int &  NId1,
const int &  NId2 
) const
inline

Definition at line 175 of file kronecker.h.

175 { return !IsObsEdge(NId1, NId2); }
bool IsObsEdge(const int &NId1, const int &NId2) const
Definition: kronecker.h:173
bool TKroneckerLL::IsLatentNode ( const int &  NId) const
inline

Definition at line 174 of file kronecker.h.

174 { return !IsObsNode(NId); }
bool IsObsNode(const int &NId) const
Definition: kronecker.h:172
bool TKroneckerLL::IsObsEdge ( const int &  NId1,
const int &  NId2 
) const
inline

Definition at line 173 of file kronecker.h.

173 { IAssert(RealNodes > 0); return ((NId1 < RealNodes) && (NId2 < RealNodes)); }
#define IAssert(Cond)
Definition: bd.h:262
TInt RealNodes
Definition: kronecker.h:131
bool TKroneckerLL::IsObsNode ( const int &  NId) const
inline

Definition at line 172 of file kronecker.h.

172 { IAssert(RealNodes > 0); return (NId < RealNodes); }
#define IAssert(Cond)
Definition: bd.h:262
TInt RealNodes
Definition: kronecker.h:131
void TKroneckerLL::MetroGibbsSampleNext ( const int &  WarmUp,
const bool  DLLUpdate = false 
)

Definition at line 1503 of file kronecker.cpp.

1503  {
1504  int NId1 = 0, NId2 = 0, hit = 0, GId = 0;
1505  TIntTr EdgeToRemove, NewEdge;
1506  double RndAccept;
1507 
1508  if(LEdgeV.Len()) {
1509  for(int i = 0; i < WarmUp; i++) {
1511 
1512  NId1 = LEdgeV[hit].Val1; NId2 = LEdgeV[hit].Val2;
1513  GId = LEdgeV[hit].Val3;
1514  SetRandomEdges(1, true);
1515  NewEdge = LEdgeV.Last();
1516 
1517  RndAccept = (1.0 - exp(LLMtx.GetEdgeLL(NewEdge.Val1, NewEdge.Val2, KronIters))) / (1.0 - exp(LLMtx.GetEdgeLL(NId1, NId2, KronIters)));
1518  RndAccept = (RndAccept > 1.0) ? 1.0 : RndAccept;
1519 
1520  if(TKronMtx::Rnd.GetUniDev() > RndAccept) { // reject
1521  Graph->DelEdge(NewEdge.Val1, NewEdge.Val2);
1522  if(NewEdge.Val1 != NewEdge.Val2) { GEdgeV.DelLast(); }
1523  else { LSelfEdge--; }
1524  LEdgeV.DelLast();
1525  } else { // accept
1526  Graph->DelEdge(NId1, NId2);
1527  LEdgeV[hit] = LEdgeV.Last();
1528  LEdgeV.DelLast();
1529  if(NId1 == NId2) {
1530  LSelfEdge--;
1531  if(NewEdge.Val1 != NewEdge.Val2) {
1532  GEdgeV[GEdgeV.Len()-1].Val3 = hit;
1533  }
1534  } else {
1535  IAssertR(GEdgeV.Last().Val3 >= 0, "Invalid indexing");
1536 
1537  GEdgeV[GId] = GEdgeV.Last();
1538  if(NewEdge.Val1 != NewEdge.Val2) {
1539  GEdgeV[GId].Val3 = hit;
1540  }
1541  LEdgeV[GEdgeV[GId].Val3].Val3 = GId;
1542  GEdgeV.DelLast();
1543  }
1544 
1545  LogLike += LLMtx.GetApxNoEdgeLL(EdgeToRemove.Val1, EdgeToRemove.Val2, KronIters) - LLMtx.GetEdgeLL(EdgeToRemove.Val1, EdgeToRemove.Val2, KronIters);
1546  LogLike += -LLMtx.GetApxNoEdgeLL(NewEdge.Val1, NewEdge.Val2, KronIters) + LLMtx.GetEdgeLL(NewEdge.Val1, NewEdge.Val2, KronIters);
1547 
1548  if(DLLUpdate) {
1549  for (int p = 0; p < LLMtx.Len(); p++) {
1550  GradV[p] += LLMtx.GetApxNoEdgeDLL(p, EdgeToRemove.Val1, EdgeToRemove.Val2, KronIters) - LLMtx.GetEdgeDLL(p, EdgeToRemove.Val1, EdgeToRemove.Val2, KronIters);
1551  GradV[p] += -LLMtx.GetApxNoEdgeDLL(p, NewEdge.Val1, NewEdge.Val2, KronIters) + LLMtx.GetEdgeDLL(p, NewEdge.Val1, NewEdge.Val2, KronIters);
1552  }
1553  }
1554  }
1555  }
1556  }
1557 
1558 // CalcApxGraphLL();
1559  for (int s = 0; s < WarmUp; s++) {
1560  if(SampleNextPerm(NId1, NId2)) {
1561  if(DLLUpdate) UpdateGraphDLL(NId1, NId2);
1562  }
1563  }
1564 }
#define IAssertR(Cond, Reason)
Definition: bd.h:265
static TRnd Rnd
Definition: kronecker.h:14
void SetRandomEdges(const int &NEdges, const bool isDir=true)
!!!!! MYUNGHWAN, CHECK!
Definition: kronecker.cpp:1417
Definition: ds.h:130
void UpdateGraphDLL(const int &SwapNId1, const int &SwapNId2)
Definition: kronecker.cpp:1241
double GetApxNoEdgeLL(int NId1, int NId2, const int &NKronIters) const
Definition: kronecker.cpp:191
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
int Len() const
Definition: kronecker.h:31
double GetEdgeLL(int NId1, int NId2, const int &NKronIters) const
Definition: kronecker.cpp:175
TVal1 Val1
Definition: ds.h:132
bool SampleNextPerm(int &NId1, int &NId2)
Definition: kronecker.cpp:1111
TFlt LogLike
Definition: kronecker.h:135
double GetEdgeDLL(const int &ParamId, int NId1, int NId2, const int &NKronIters) const
Definition: kronecker.cpp:207
TVal2 Val2
Definition: ds.h:133
double GetApxNoEdgeDLL(const int &ParamId, int NId1, int NId2, const int &NKronIters) const
Definition: kronecker.cpp:240
void DelEdge(const int &SrcNId, const int &DstNId, const bool &IsDir=true)
Deletes an edge from node IDs SrcNId to DstNId from the graph.
Definition: graph.cpp:345
const TVal & Last() const
Returns a reference to the last element of the vector.
Definition: ds.h:579
TIntTrV GEdgeV
Definition: kronecker.h:125
TInt LSelfEdge
Definition: kronecker.h:127
TIntTrV LEdgeV
Definition: kronecker.h:126
TInt KronIters
Definition: kronecker.h:121
TKronMtx LLMtx
Definition: kronecker.h:134
PNGraph Graph
Definition: kronecker.h:120
TFltV GradV
Definition: kronecker.h:136
int GetUniDevInt(const int &Range=0)
Definition: dt.cpp:39
void DelLast()
Removes the last element of the vector.
Definition: ds.h:665
TVal3 Val3
Definition: ds.h:134
void TKroneckerLL::MetroGibbsSampleSetup ( const int &  WarmUp)

Definition at line 1476 of file kronecker.cpp.

1476  {
1477  double alpha = log(ProbMtx.GetMtxSum()) / log(double(ProbMtx.GetDim()));
1478  int NId1 = 0, NId2 = 0;
1479  int NMissing;
1480 
1481  RestoreGraph(false);
1482  if(EMType == kronEdgeMiss) {
1483  CalcApxGraphLL();
1484  for (int s = 0; s < WarmUp; s++) SampleNextPerm(NId1, NId2);
1485  }
1486 
1487  if(EMType == kronFutureLink) {
1488  NMissing = (int) (pow(ProbMtx.GetMtxSum(), KronIters) - pow(double(RealNodes), alpha));
1489  } else if(EMType == kronEdgeMiss) {
1490  NMissing = MissEdges;
1491  } else {
1492  NMissing = (int) (pow(ProbMtx.GetMtxSum(), KronIters) * (1.0 - pow(double(RealNodes) / double(Nodes), 2)));
1493  }
1494  NMissing = (NMissing < 1) ? 1 : NMissing;
1495 
1496  SetRandomEdges(NMissing, true);
1497 
1498  CalcApxGraphLL();
1499  for (int s = 0; s < WarmUp; s++) SampleNextPerm(NId1, NId2);
1500 }
double GetMtxSum() const
Definition: kronecker.cpp:140
void SetRandomEdges(const int &NEdges, const bool isDir=true)
!!!!! MYUNGHWAN, CHECK!
Definition: kronecker.cpp:1417
bool SampleNextPerm(int &NId1, int &NId2)
Definition: kronecker.cpp:1111
void RestoreGraph(const bool RestoreNodes=true)
!!!!! MYUNGHWAN, CHECK!
Definition: kronecker.cpp:923
double CalcApxGraphLL()
Definition: kronecker.cpp:1037
TInt KronIters
Definition: kronecker.h:121
TKronMtx ProbMtx
Definition: kronecker.h:134
TInt MissEdges
Definition: kronecker.h:139
int GetDim() const
Definition: kronecker.h:30
TInt RealNodes
Definition: kronecker.h:131
TKronEMType EMType
Definition: kronecker.h:138
static PKroneckerLL TKroneckerLL::New ( )
inlinestatic

Definition at line 154 of file kronecker.h.

154 { return new TKroneckerLL(); }
PKroneckerLL TKroneckerLL::New ( const PNGraph GraphPt,
const TKronMtx ParamMtx,
const double &  PermPSwapNd = 0.1 
)
static

Definition at line 797 of file kronecker.cpp.

797  {
798  return new TKroneckerLL(GraphPt, ParamMtx, PermPSwapNd);
799 }
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.

801  {
802  return new TKroneckerLL(GraphPt, ParamMtx, NodeIdPermV, PermPSwapNd);
803 }
double TKroneckerLL::NodeDLLDelta ( const int  ParamId,
const int &  NId 
) const

Definition at line 1214 of file kronecker.cpp.

1214  {
1215  if (! Graph->IsNode(NId)) { return 0.0; } // zero degree node
1216  double Delta = 0.0;
1217  const TNGraph::TNodeI Node = Graph->GetNI(NId);
1218  const int SrcRow = NodePerm[NId];
1219  for (int e = 0; e < Node.GetOutDeg(); e++) {
1220  const int DstCol = NodePerm[Node.GetOutNId(e)];
1221  Delta += - LLMtx.GetApxNoEdgeDLL(ParamId, SrcRow, DstCol, KronIters)
1222  + LLMtx.GetEdgeDLL(ParamId, SrcRow, DstCol, KronIters);
1223  }
1224  const int SrcCol = NodePerm[NId];
1225  for (int e = 0; e < Node.GetInDeg(); e++) {
1226  const int DstRow = NodePerm[Node.GetInNId(e)];
1227  Delta += - LLMtx.GetApxNoEdgeDLL(ParamId, DstRow, SrcCol, KronIters)
1228  + LLMtx.GetEdgeDLL(ParamId, DstRow, SrcCol, KronIters);
1229  }
1230  // double counter self-edge
1231  if (Graph->IsEdge(NId, NId)) {
1232  Delta += + LLMtx.GetApxNoEdgeDLL(ParamId, SrcRow, SrcCol, KronIters)
1233  - LLMtx.GetEdgeDLL(ParamId, SrcRow, SrcCol, KronIters);
1234  IAssert(SrcRow == SrcCol);
1235  }
1236  return Delta;
1237 }
#define IAssert(Cond)
Definition: bd.h:262
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:548
double GetEdgeDLL(const int &ParamId, int NId1, int NId2, const int &NKronIters) const
Definition: kronecker.cpp:207
TIntV NodePerm
Definition: kronecker.h:128
double GetApxNoEdgeDLL(const int &ParamId, int NId1, int NId2, const int &NKronIters) const
Definition: kronecker.cpp:240
bool IsEdge(const int &SrcNId, const int &DstNId, const bool &IsDir=true) const
Tests whether an edge from node IDs SrcNId to DstNId exists in the graph.
Definition: graph.cpp:363
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:542
TInt KronIters
Definition: kronecker.h:121
int GetOutDeg() const
Returns out-degree of the current node.
Definition: graph.h:402
TKronMtx LLMtx
Definition: kronecker.h:134
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:379
PNGraph Graph
Definition: kronecker.h:120
int GetInDeg() const
Returns in-degree of the current node.
Definition: graph.h:400
int GetInNId(const int &NodeN) const
Returns ID of NodeN-th in-node (the node pointing to the current node).
Definition: graph.h:408
int GetOutNId(const int &NodeN) const
Returns ID of NodeN-th out-node (the node the current node points to).
Definition: graph.h:412
double TKroneckerLL::NodeLLDelta ( const int &  NId) const

Definition at line 1055 of file kronecker.cpp.

1055  {
1056  if (! Graph->IsNode(NId)) { return 0.0; } // zero degree node
1057  double Delta = 0.0;
1058  const TNGraph::TNodeI Node = Graph->GetNI(NId);
1059  // out-edges
1060  const int SrcRow = NodePerm[NId];
1061  for (int e = 0; e < Node.GetOutDeg(); e++) {
1062  const int DstCol = NodePerm[Node.GetOutNId(e)];
1063  Delta += - LLMtx.GetApxNoEdgeLL(SrcRow, DstCol, KronIters)
1064  + LLMtx.GetEdgeLL(SrcRow, DstCol, KronIters);
1065  }
1066  //in-edges
1067  const int SrcCol = NodePerm[NId];
1068  for (int e = 0; e < Node.GetInDeg(); e++) {
1069  const int DstRow = NodePerm[Node.GetInNId(e)];
1070  Delta += - LLMtx.GetApxNoEdgeLL(DstRow, SrcCol, KronIters)
1071  + LLMtx.GetEdgeLL(DstRow, SrcCol, KronIters);
1072  }
1073  // double counted self-edge
1074  if (Graph->IsEdge(NId, NId)) {
1075  Delta += + LLMtx.GetApxNoEdgeLL(SrcRow, SrcCol, KronIters)
1076  - LLMtx.GetEdgeLL(SrcRow, SrcCol, KronIters);
1077  IAssert(SrcRow == SrcCol);
1078  }
1079  return Delta;
1080 }
#define IAssert(Cond)
Definition: bd.h:262
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:548
double GetApxNoEdgeLL(int NId1, int NId2, const int &NKronIters) const
Definition: kronecker.cpp:191
double GetEdgeLL(int NId1, int NId2, const int &NKronIters) const
Definition: kronecker.cpp:175
TIntV NodePerm
Definition: kronecker.h:128
bool IsEdge(const int &SrcNId, const int &DstNId, const bool &IsDir=true) const
Tests whether an edge from node IDs SrcNId to DstNId exists in the graph.
Definition: graph.cpp:363
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:542
TInt KronIters
Definition: kronecker.h:121
int GetOutDeg() const
Returns out-degree of the current node.
Definition: graph.h:402
TKronMtx LLMtx
Definition: kronecker.h:134
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:379
PNGraph Graph
Definition: kronecker.h:120
int GetInDeg() const
Returns in-degree of the current node.
Definition: graph.h:400
int GetInNId(const int &NodeN) const
Returns ID of NodeN-th in-node (the node pointing to the current node).
Definition: graph.h:408
int GetOutNId(const int &NodeN) const
Returns ID of NodeN-th out-node (the node the current node points to).
Definition: graph.h:412
void TKroneckerLL::RestoreGraph ( const bool  RestoreNodes = true)

!!!!! MYUNGHWAN, CHECK!

Definition at line 923 of file kronecker.cpp.

923  {
924  // remove from Graph
925  int NId1, NId2;
926  for (int e = 0; e < LEdgeV.Len(); e++) {
927  NId1 = LEdgeV[e].Val1; NId2 = LEdgeV[e].Val2;
928  Graph->DelEdge(NId1, NId2);
929 // GEdgeV.DelIfIn(LEdgeV[e]);
930  }
931  if(LEdgeV.Len() - LSelfEdge)
932  GEdgeV.Del(GEdgeV.Len() - LEdgeV.Len() + LSelfEdge, GEdgeV.Len() - 1);
933  LEdgeV.Clr();
934  LSelfEdge = 0;
935 
936  if(RestoreNodes) {
937  for(int i = Graph->GetNodes()-1; i >= RealNodes; i--) {
938  Graph->DelNode(i);
939  }
940  }
941 }
void Del(const TSizeTy &ValN)
Removes the element at position ValN.
Definition: ds.h:1189
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:499
void DelNode(const int &NId)
Deletes node of ID NId from the graph.
Definition: graph.cpp:294
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:1022
void DelEdge(const int &SrcNId, const int &DstNId, const bool &IsDir=true)
Deletes an edge from node IDs SrcNId to DstNId from the graph.
Definition: graph.cpp:345
TIntTrV GEdgeV
Definition: kronecker.h:125
TInt LSelfEdge
Definition: kronecker.h:127
TIntTrV LEdgeV
Definition: kronecker.h:126
TInt RealNodes
Definition: kronecker.h:131
PNGraph Graph
Definition: kronecker.h:120
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.

1567  {
1568  TExeTm ExeTm, TotalTm;
1569  LLV.Gen(NSamples, 0);
1570  DLLV.Gen(NSamples, 0);
1571 
1572  ExeTm.Tick();
1573  for(int i = 0; i < 2; i++) MetroGibbsSampleSetup(WarmUp);
1574  printf(" Warm-Up [%u] : %s\n", WarmUp, ExeTm.GetTmStr());
1575  CalcApxGraphLL();
1576  for(int i = 0; i < GibbsWarmUp; i++) MetroGibbsSampleNext(10, false);
1577  printf(" Gibbs Warm-Up [%u] : %s\n", GibbsWarmUp, ExeTm.GetTmStr());
1578 
1579  ExeTm.Tick();
1580  CalcApxGraphLL();
1581  CalcApxGraphDLL();
1582  for(int i = 0; i < NSamples; i++) {
1583  MetroGibbsSampleNext(50, false);
1584 
1585  LLV.Add(LogLike);
1586  DLLV.Add(GradV);
1587 
1588  int OnePercent = (i+1) % (NSamples / 10);
1589  if(OnePercent == 0) {
1590  int TenPercent = ((i+1) / (NSamples / 10)) * 10;
1591  printf(" %3u%% done : %s\n", TenPercent, ExeTm.GetTmStr());
1592  }
1593  }
1594 }
Definition: tm.h:355
TFlt LogLike
Definition: kronecker.h:135
double CalcApxGraphLL()
Definition: kronecker.cpp:1037
const char * GetTmStr() const
Definition: tm.h:370
void Tick()
Definition: tm.h:364
void MetroGibbsSampleSetup(const int &WarmUp)
Definition: kronecker.cpp:1476
void MetroGibbsSampleNext(const int &WarmUp, const bool DLLUpdate=false)
Definition: kronecker.cpp:1503
const TFltV & CalcApxGraphDLL()
Definition: kronecker.cpp:1194
TFltV GradV
Definition: kronecker.h:136
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
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.

1692  {
1693  printf("\n----------------------------------------------------------------------\n");
1694  printf("Fitting graph on %d nodes, %d edges\n", int(RealNodes), int(RealEdges));
1695  printf("Kron iters: %d (== %d nodes)\n\n", KronIters(), ProbMtx.GetNodes(KronIters()));
1696 
1697  TFltV LLV(NSamples);
1698  TVec<TFltV> DLLV(NSamples);
1699  //int count = 0;
1700 
1701  EMType = Type;
1702  MissEdges = NMissing;
1703  AppendIsoNodes();
1704  SetRndPerm();
1705 
1706  if(DebugMode) {
1707  LLV.Gen(EMIter, 0);
1708  MtxV.Gen(EMIter, 0);
1709  }
1710 
1711  for(int i = 0; i < EMIter; i++) {
1712  printf("\n----------------------------------------------------------------------\n");
1713  printf("%03d EM-iter] E-Step\n", i+1);
1714  RunEStep(GibbsWarmUp, WarmUp, NSamples, LLV, DLLV);
1715  printf("\n\n");
1716 
1717  printf("%03d EM-iter] M-Step\n", i+1);
1718  double CurLL = RunMStep(LLV, DLLV, GradIter, LrnRate, MnStep, MxStep);
1719  printf("\n\n");
1720 
1721  if(DebugMode) {
1722  LLV.Add(CurLL);
1723  MtxV.Add(ProbMtx);
1724  }
1725  }
1726 
1727  RestoreGraph();
1728 }
void RunEStep(const int &GibbsWarmUp, const int &WarmUp, const int &NSamples, TFltV &LLV, TVec< TFltV > &DLLV)
Definition: kronecker.cpp:1567
void RestoreGraph(const bool RestoreNodes=true)
!!!!! MYUNGHWAN, CHECK!
Definition: kronecker.cpp:923
TVec< TKronMtx > MtxV
Definition: kronecker.h:143
void SetRndPerm()
Definition: kronecker.cpp:820
double RunMStep(const TFltV &LLV, const TVec< TFltV > &DLLV, const int &GradIter, const double &LrnRate, double MnStep, double MxStep)
Definition: kronecker.cpp:1597
TBool DebugMode
Definition: kronecker.h:141
TInt RealEdges
Definition: kronecker.h:132
void AppendIsoNodes()
Definition: kronecker.cpp:914
TInt KronIters
Definition: kronecker.h:121
TKronMtx ProbMtx
Definition: kronecker.h:134
TInt MissEdges
Definition: kronecker.h:139
TInt RealNodes
Definition: kronecker.h:131
int GetNodes(const int &NIter) const
Definition: kronecker.cpp:119
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
TKronEMType EMType
Definition: kronecker.h:138
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
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.

1597  {
1598  TExeTm IterTm, TotalTm;
1599  double OldLL=LogLike, CurLL=0;
1600  const double alpha = log(double(RealEdges)) / log(double(RealNodes));
1601  const double EZero = pow(double(ProbMtx.GetDim()), alpha);
1602 
1603  TFltV CurGradV(GetParams()), LearnRateV(GetParams()), LastStep(GetParams());
1604  LearnRateV.PutAll(LrnRate);
1605 
1606  TKronMtx NewProbMtx = ProbMtx;
1607  const int NSamples = LLV.Len();
1608  const int ReCalcLen = NSamples / 10;
1609 
1610  for (int s = 0; s < LLV.Len(); s++) {
1611  CurLL += LLV[s];
1612  for(int p = 0; p < GetParams(); p++) { CurGradV[p] += DLLV[s][p]; }
1613  }
1614  CurLL /= NSamples;
1615  for(int p = 0; p < GetParams(); p++) { CurGradV[p] /= NSamples; }
1616 
1617  double MaxLL = CurLL;
1618  TKronMtx MaxProbMtx = ProbMtx;
1619  TKronMtx OldProbMtx = ProbMtx;
1620 
1621  for (int Iter = 0; Iter < GradIter; Iter++) {
1622  printf(" %03d] ", Iter+1);
1623  IterTm.Tick();
1624 
1625  for (int p = 0; p < GetParams(); p++) {
1626  if (Iter < 1) {
1627  while (fabs(LearnRateV[p]*CurGradV[p]) > MxStep) { LearnRateV[p] *= 0.95; }
1628  while (fabs(LearnRateV[p]*CurGradV[p]) < 5 * MnStep) { LearnRateV[p] *= (1.0/0.95); } // move more
1629  } else {
1630  // set learn rate so that move for each parameter is inside the [MnStep, MxStep]
1631  while (fabs(LearnRateV[p]*CurGradV[p]) > MxStep) { LearnRateV[p] *= 0.95; printf(".");}
1632  while (fabs(LearnRateV[p]*CurGradV[p]) < MnStep) { LearnRateV[p] *= (1.0/0.95); printf("*");}
1633  if (MxStep > 3*MnStep) { MxStep *= 0.95; }
1634  }
1635  NewProbMtx.At(p) = ProbMtx.At(p) + LearnRateV[p]*CurGradV[p];
1636  if (NewProbMtx.At(p) > 0.9999) { NewProbMtx.At(p)=0.9999; }
1637  if (NewProbMtx.At(p) < 0.0001) { NewProbMtx.At(p)=0.0001; }
1638  LearnRateV[p] *= 0.95;
1639  }
1640  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()));
1641  printf(" currLL: %.4f, deltaLL: %.4f\n", CurLL, CurLL-OldLL); // positive is good
1642  for (int p = 0; p < GetParams(); p++) {
1643  printf(" %d] %f <-- %f + %9f Grad: %9.1f Rate: %g\n", p, NewProbMtx.At(p),
1644  ProbMtx.At(p), (double)(LearnRateV[p]*CurGradV[p]), CurGradV[p](), LearnRateV[p]());
1645  }
1646 
1647  OldLL=CurLL;
1648  if(Iter == GradIter - 1) {
1649  break;
1650  }
1651 
1652  CurLL = 0;
1653  CurGradV.PutAll(0.0);
1654  TFltV OneDLL;
1655 
1656  CalcApxGraphLL();
1657  CalcApxGraphDLL();
1658 
1659  for(int s = 0; s < NSamples; s++) {
1660  ProbMtx = OldProbMtx; ProbMtx.GetLLMtx(LLMtx);
1661  MetroGibbsSampleNext(10, true);
1662  ProbMtx = NewProbMtx; ProbMtx.GetLLMtx(LLMtx);
1663  if(s % ReCalcLen == ReCalcLen/2) {
1664  CurLL += CalcApxGraphLL();
1665  OneDLL = CalcApxGraphDLL();
1666  } else {
1667  CurLL += LogLike;
1668  OneDLL = GradV;
1669  }
1670  for(int p = 0; p < GetParams(); p++) {
1671  CurGradV[p] += OneDLL[p];
1672  }
1673  }
1674  CurLL /= NSamples;
1675 
1676  if(MaxLL < CurLL) {
1677  MaxLL = CurLL; MaxProbMtx = ProbMtx;
1678  }
1679 
1680  printf(" Time: %s\n", IterTm.GetTmStr());
1681  printf("\n"); fflush(stdout);
1682  }
1683  ProbMtx = MaxProbMtx; ProbMtx.GetLLMtx(LLMtx);
1684 
1685  printf(" FinalLL : %f, TotalExeTm: %s\n", MaxLL, TotalTm.GetTmStr());
1686  ProbMtx.Dump(" FITTED PARAMS", false);
1687 
1688  return MaxLL;
1689 }
int GetParams() const
Definition: kronecker.h:164
Definition: tm.h:355
double GetMtxSum() const
Definition: kronecker.cpp:140
int GetEdges() const
Returns the number of edges in the graph.
Definition: graph.cpp:313
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
void Dump(const TStr &MtxNm=TStr(), const bool &Sort=false) const
Definition: kronecker.cpp:636
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:499
TFlt LogLike
Definition: kronecker.h:135
const double & At(const int &Row, const int &Col) const
Definition: kronecker.h:46
double CalcApxGraphLL()
Definition: kronecker.cpp:1037
const char * GetTmStr() const
Definition: tm.h:370
TInt RealEdges
Definition: kronecker.h:132
void Tick()
Definition: tm.h:364
void GetLLMtx(TKronMtx &LLMtx)
Definition: kronecker.cpp:98
void MetroGibbsSampleNext(const int &WarmUp, const bool DLLUpdate=false)
Definition: kronecker.cpp:1503
TKronMtx ProbMtx
Definition: kronecker.h:134
int GetDim() const
Definition: kronecker.h:30
const TFltV & CalcApxGraphDLL()
Definition: kronecker.cpp:1194
TKronMtx LLMtx
Definition: kronecker.h:134
TInt RealNodes
Definition: kronecker.h:131
PNGraph Graph
Definition: kronecker.h:120
TFltV GradV
Definition: kronecker.h:136
void TKroneckerLL::SampleGradient ( const int &  WarmUp,
const int &  NSamples,
double &  AvgLL,
TFltV GradV 
)

Definition at line 1271 of file kronecker.cpp.

1271  {
1272  printf("SampleGradient: %s (%s warm-up):", TInt::GetMegaStr(NSamples).CStr(), TInt::GetMegaStr(WarmUp).CStr());
1273  int NId1=0, NId2=0, NAccept=0;
1274  TExeTm ExeTm1;
1275  if (WarmUp > 0) {
1276  CalcApxGraphLL();
1277  for (int s = 0; s < WarmUp; s++) { SampleNextPerm(NId1, NId2); }
1278  printf(" warm-up:%s,", ExeTm1.GetTmStr()); ExeTm1.Tick();
1279  }
1280  CalcApxGraphLL(); // re-calculate LL (due to numerical errors)
1281  CalcApxGraphDLL();
1282  AvgLL = 0;
1283  AvgGradV.Gen(LLMtx.Len()); AvgGradV.PutAll(0.0);
1284  printf(" sampl");
1285  for (int s = 0; s < NSamples; s++) {
1286  if (SampleNextPerm(NId1, NId2)) { // new permutation
1287  UpdateGraphDLL(NId1, NId2); NAccept++; }
1288  for (int m = 0; m < LLMtx.Len(); m++) { AvgGradV[m] += GradV[m]; }
1289  AvgLL += GetLL();
1290  }
1291  printf("ing");
1292  AvgLL = AvgLL / double(NSamples);
1293  for (int m = 0; m < LLMtx.Len(); m++) {
1294  AvgGradV[m] = AvgGradV[m] / double(NSamples); }
1295  printf(":%s (%.0f/s), accept %.1f%%\n", ExeTm1.GetTmStr(), double(NSamples)/ExeTm1.GetSecs(),
1296  double(100*NAccept)/double(NSamples));
1297 }
Definition: tm.h:355
static TStr GetMegaStr(const int &Val)
Definition: dt.h:1223
void UpdateGraphDLL(const int &SwapNId1, const int &SwapNId2)
Definition: kronecker.cpp:1241
int Len() const
Definition: kronecker.h:31
bool SampleNextPerm(int &NId1, int &NId2)
Definition: kronecker.cpp:1111
double CalcApxGraphLL()
Definition: kronecker.cpp:1037
const char * GetTmStr() const
Definition: tm.h:370
void Tick()
Definition: tm.h:364
const TFltV & CalcApxGraphDLL()
Definition: kronecker.cpp:1194
TKronMtx LLMtx
Definition: kronecker.h:134
double GetSecs() const
Definition: tm.h:366
double GetLL() const
Definition: kronecker.h:204
bool TKroneckerLL::SampleNextPerm ( int &  NId1,
int &  NId2 
)

Definition at line 1111 of file kronecker.cpp.

1111  {
1112  // pick 2 uniform nodes and swap
1113  if (TKronMtx::Rnd.GetUniDev() < PermSwapNodeProb) {
1116  while (NId2 == NId1) { NId2 = TKronMtx::Rnd.GetUniDevInt(Nodes); }
1117  } else {
1118  // pick uniform edge and swap endpoints (slow as it moves around high degree nodes)
1119  const int e = TKronMtx::Rnd.GetUniDevInt(GEdgeV.Len());
1120  NId1 = GEdgeV[e].Val1; NId2 = GEdgeV[e].Val2;
1121  }
1122  const double U = TKronMtx::Rnd.GetUniDev();
1123  const double OldLL = LogLike;
1124  const double NewLL = SwapNodesLL(NId1, NId2);
1125  const double LogU = log(U);
1126  if (LogU > NewLL - OldLL) { // reject
1127  LogLike = OldLL;
1128  NodePerm.Swap(NId2, NId1); //swap back
1129  InvertPerm.Swap(NodePerm[NId2], NodePerm[NId1]); // swap back
1130  return false;
1131  }
1132  return true; // accept new sample
1133 }
static TRnd Rnd
Definition: kronecker.h:14
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TFlt LogLike
Definition: kronecker.h:135
TFlt PermSwapNodeProb
Definition: kronecker.h:123
TIntV NodePerm
Definition: kronecker.h:128
void Swap(TVec< TVal, TSizeTy > &Vec)
Swaps the contents of the vector with Vec.
Definition: ds.h:1101
TIntTrV GEdgeV
Definition: kronecker.h:125
double SwapNodesLL(const int &NId1, const int &NId2)
Definition: kronecker.cpp:1083
double GetUniDev()
Definition: dt.h:30
int GetUniDevInt(const int &Range=0)
Definition: dt.cpp:39
TIntV InvertPerm
Definition: kronecker.h:129
void TKroneckerLL::SetBestDegPerm ( )

!!!!! MYUNGHWAN, CHECK!

Definition at line 842 of file kronecker.cpp.

842  {
843  NodePerm.Gen(Nodes);
844  const int NZero = ProbMtx.GetDim();
845  TFltIntPrV DegV(Nodes), CDegV(Nodes);
846  TFltV Row(NZero);
847  TFltV Col(NZero);
848  for(int i = 0; i < NZero; i++) {
849  for(int j = 0; j < NZero; j++) {
850  Row[i] += ProbMtx.At(i, j);
851  Col[i] += ProbMtx.At(j, i);
852  }
853  }
854 
855  for(int i = 0; i < Nodes; i++) {
856  TNGraph::TNodeI NodeI = Graph->GetNI(i);
857  int NId = i;
858  double RowP = 1.0, ColP = 1.0;
859  for(int j = 0; j < KronIters; j++) {
860  int Bit = NId % NZero;
861  RowP *= Row[Bit]; ColP *= Col[Bit];
862  NId /= NZero;
863  }
864  CDegV[i] = TFltIntPr(RowP + ColP, i);
865  DegV[i] = TFltIntPr(NodeI.GetDeg(), i);
866  }
867  DegV.Sort(false); CDegV.Sort(false);
868  for(int i = 0; i < Nodes; i++) {
869  NodePerm[DegV[i].Val2] = CDegV[i].Val2;
870  }
872 }
TPair< TFlt, TInt > TFltIntPr
Definition: ds.h:97
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:548
void SetIPerm(const TIntV &Perm)
!!!!! MYUNGHWAN, CHECK!
Definition: kronecker.cpp:875
const double & At(const int &Row, const int &Col) const
Definition: kronecker.h:46
TIntV NodePerm
Definition: kronecker.h:128
int GetDeg() const
Returns degree of the current node, the sum of in-degree and out-degree.
Definition: graph.h:398
TInt KronIters
Definition: kronecker.h:121
TKronMtx ProbMtx
Definition: kronecker.h:134
int GetDim() const
Definition: kronecker.h:30
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:379
PNGraph Graph
Definition: kronecker.h:120
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:430
void TKroneckerLL::SetDebug ( const bool  Debug)
inline

Definition at line 167 of file kronecker.h.

167 { DebugMode = Debug; }
TBool DebugMode
Definition: kronecker.h:141
void TKroneckerLL::SetDegPerm ( )

Definition at line 828 of file kronecker.cpp.

828  {
829  TIntPrV DegNIdV;
830  for (TNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
831  DegNIdV.Add(TIntPr(NI.GetDeg(), NI.GetId()));
832  }
833  DegNIdV.Sort(false);
834  NodePerm.Gen(DegNIdV.Len(), 0);
835  for (int i = 0; i < DegNIdV.Len(); i++) {
836  NodePerm.Add(DegNIdV[i].Val2);
837  }
839 }
TPair< TInt, TInt > TIntPr
Definition: ds.h:83
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:544
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
void SetIPerm(const TIntV &Perm)
!!!!! MYUNGHWAN, CHECK!
Definition: kronecker.cpp:875
TIntV NodePerm
Definition: kronecker.h:128
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1318
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:546
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:379
PNGraph Graph
Definition: kronecker.h:120
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
void TKroneckerLL::SetGraph ( const PNGraph GraphPt)

Definition at line 882 of file kronecker.cpp.

882  {
883  Graph = GraphPt;
884  bool NodesOk = true;
885  // check that nodes IDs are {0,1,..,Nodes-1}
886  for (int nid = 0; nid < Graph->GetNodes(); nid++) {
887  if (! Graph->IsNode(nid)) { NodesOk=false; break; } }
888  if (! NodesOk) {
889  TIntV NIdV; GraphPt->GetNIdV(NIdV);
890  Graph = TSnap::GetSubGraph(GraphPt, NIdV, true);
891  for (int nid = 0; nid < Graph->GetNodes(); nid++) {
892  IAssert(Graph->IsNode(nid)); }
893  }
894  Nodes = Graph->GetNodes();
895  IAssert(LLMtx.GetDim() > 1 && LLMtx.Len() == ProbMtx.Len());
896  KronIters = (int) ceil(log(double(Nodes)) / log(double(ProbMtx.GetDim())));
897  // edge vector (for swap-edge permutation proposal)
898 // if (PermSwapNodeProb < 1.0) { /// !!!!! MYUNGHWAN, CHECK! WHY IS THIS COMMENTED OUT
899  GEdgeV.Gen(Graph->GetEdges(), 0);
900  for (TNGraph::TEdgeI EI = Graph->BegEI(); EI < Graph->EndEI(); EI++) {
901  if (EI.GetSrcNId() != EI.GetDstNId()) {
902  GEdgeV.Add(TIntTr(EI.GetSrcNId(), EI.GetDstNId(), -1));
903  }
904  }
905 // }
906 
907  RealNodes = Nodes;
908  RealEdges = Graph->GetEdges();
909  LEdgeV = TIntTrV();
910  LSelfEdge = 0;
911 }
#define IAssert(Cond)
Definition: bd.h:262
void GetNIdV(TIntV &NIdV) const
Gets a vector IDs of all nodes in the graph.
Definition: graph.cpp:376
TEdgeI EndEI() const
Returns an iterator referring to the past-the-end edge in the graph.
Definition: graph.h:588
int GetEdges() const
Returns the number of edges in the graph.
Definition: graph.cpp:313
int Len() const
Definition: kronecker.h:31
TEdgeI BegEI() const
Returns an iterator referring to the first edge in the graph.
Definition: graph.h:586
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:499
TVec< TIntTr > TIntTrV
Definition: ds.h:1602
Edge iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:426
PUNGraph GetSubGraph(const PUNGraph &Graph, const TIntV &NIdV, const bool &RenumberNodes)
Returns an induced subgraph of an undirected graph Graph with NIdV nodes with an optional node renumb...
Definition: subgraph.cpp:7
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:542
TInt RealEdges
Definition: kronecker.h:132
TIntTrV GEdgeV
Definition: kronecker.h:125
TInt LSelfEdge
Definition: kronecker.h:127
TIntTrV LEdgeV
Definition: kronecker.h:126
TInt KronIters
Definition: kronecker.h:121
TKronMtx ProbMtx
Definition: kronecker.h:134
int GetDim() const
Definition: kronecker.h:30
TKronMtx LLMtx
Definition: kronecker.h:134
TInt RealNodes
Definition: kronecker.h:131
PNGraph Graph
Definition: kronecker.h:120
TTriple< TInt, TInt, TInt > TIntTr
Definition: ds.h:171
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
void TKroneckerLL::SetIPerm ( const TIntV Perm)

!!!!! MYUNGHWAN, CHECK!

Definition at line 875 of file kronecker.cpp.

875  {
876  InvertPerm.Gen(Perm.Len());
877  for (int i = 0; i < Perm.Len(); i++) {
878  InvertPerm[Perm[i]] = i;
879  }
880 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
TIntV InvertPerm
Definition: kronecker.h:129
void TKroneckerLL::SetOrderPerm ( )

Definition at line 813 of file kronecker.cpp.

813  {
814  NodePerm.Gen(Nodes, 0);
815  for (int i = 0; i < Graph->GetNodes(); i++) {
816  NodePerm.Add(i); }
818 }
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:499
void SetIPerm(const TIntV &Perm)
!!!!! MYUNGHWAN, CHECK!
Definition: kronecker.cpp:875
TIntV NodePerm
Definition: kronecker.h:128
PNGraph Graph
Definition: kronecker.h:120
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
void TKroneckerLL::SetPerm ( const char &  PermId)

Definition at line 805 of file kronecker.cpp.

805  {
806  if (PermId == 'o') { SetOrderPerm(); }
807  else if (PermId == 'd') { SetDegPerm(); }
808  else if (PermId == 'r') { SetRndPerm(); }
809  else if (PermId == 'b') { SetBestDegPerm(); }
810  else FailR("Unknown permutation type (o,d,r)");
811 }
void SetOrderPerm()
Definition: kronecker.cpp:813
void SetBestDegPerm()
!!!!! MYUNGHWAN, CHECK!
Definition: kronecker.cpp:842
void SetDegPerm()
Definition: kronecker.cpp:828
void SetRndPerm()
Definition: kronecker.cpp:820
#define FailR(Reason)
Definition: bd.h:240
void TKroneckerLL::SetPerm ( const TIntV NodePermV)
inline

Definition at line 183 of file kronecker.h.

183 { NodePerm = NodePermV; SetIPerm(NodePerm); }
void SetIPerm(const TIntV &Perm)
!!!!! MYUNGHWAN, CHECK!
Definition: kronecker.cpp:875
TIntV NodePerm
Definition: kronecker.h:128
void TKroneckerLL::SetRandomEdges ( const int &  NEdges,
const bool  isDir = true 
)

!!!!! MYUNGHWAN, CHECK!

Definition at line 1417 of file kronecker.cpp.

1417  {
1418  int count = 0, added = 0, collision = 0;
1419  const int MtxDim = ProbMtx.GetDim();
1420  const double MtxSum = ProbMtx.GetMtxSum();
1421  TVec<TFltIntIntTr> ProbToRCPosV; // row, col position
1422  double CumProb = 0.0;
1423 
1424  for(int r = 0; r < MtxDim; r++) {
1425  for(int c = 0; c < MtxDim; c++) {
1426  const double Prob = ProbMtx.At(r, c);
1427  if (Prob > 0.0) {
1428  CumProb += Prob;
1429  ProbToRCPosV.Add(TFltIntIntTr(CumProb/MtxSum, r, c));
1430  }
1431  }
1432  }
1433 
1434  int Rng, Row, Col, n, NId1, NId2;
1435  while(added < NEdges) {
1436  Rng = Nodes; Row = 0; Col = 0;
1437  for (int iter = 0; iter < KronIters; iter++) {
1438  const double& Prob = TKronMtx::Rnd.GetUniDev();
1439  n = 0; while(Prob > ProbToRCPosV[n].Val1) { n++; }
1440  const int MtxRow = ProbToRCPosV[n].Val2;
1441  const int MtxCol = ProbToRCPosV[n].Val3;
1442  Rng /= MtxDim;
1443  Row += MtxRow * Rng;
1444  Col += MtxCol * Rng;
1445  }
1446 
1447  count++;
1448 
1449  NId1 = InvertPerm[Row]; NId2 = InvertPerm[Col];
1450 
1451  // Check conflicts
1452  if(EMType != kronEdgeMiss && IsObsEdge(NId1, NId2)) {
1453  continue;
1454  }
1455 
1456  if (! Graph->IsEdge(NId1, NId2)) {
1457  Graph->AddEdge(NId1, NId2);
1458  if(NId1 != NId2) { GEdgeV.Add(TIntTr(NId1, NId2, LEdgeV.Len())); }
1459  else { LSelfEdge++; }
1460  LEdgeV.Add(TIntTr(NId1, NId2, GEdgeV.Len()-1));
1461  added++;
1462  if (! isDir) {
1463  if (NId1 != NId2) {
1464  Graph->AddEdge(NId2, NId1);
1465  GEdgeV.Add(TIntTr(NId2, NId1, LEdgeV.Len()));
1466  LEdgeV.Add(TIntTr(NId2, NId1, GEdgeV.Len()-1));
1467  added++;
1468  }
1469  }
1470  } else { collision ++; }
1471  }
1472 // printf("total = %d / added = %d / collision = %d\n", count, added, collision);
1473 }
static TRnd Rnd
Definition: kronecker.h:14
double GetMtxSum() const
Definition: kronecker.cpp:140
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
const double & At(const int &Row, const int &Col) const
Definition: kronecker.h:46
bool IsObsEdge(const int &NId1, const int &NId2) const
Definition: kronecker.h:173
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge from node SrcNId to node DstNId to the graph.
Definition: graph.cpp:321
bool IsEdge(const int &SrcNId, const int &DstNId, const bool &IsDir=true) const
Tests whether an edge from node IDs SrcNId to DstNId exists in the graph.
Definition: graph.cpp:363
TIntTrV GEdgeV
Definition: kronecker.h:125
TInt LSelfEdge
Definition: kronecker.h:127
TIntTrV LEdgeV
Definition: kronecker.h:126
TInt KronIters
Definition: kronecker.h:121
TKronMtx ProbMtx
Definition: kronecker.h:134
int GetDim() const
Definition: kronecker.h:30
PNGraph Graph
Definition: kronecker.h:120
double GetUniDev()
Definition: dt.h:30
TTriple< TInt, TInt, TInt > TIntTr
Definition: ds.h:171
TKronEMType EMType
Definition: kronecker.h:138
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
TIntV InvertPerm
Definition: kronecker.h:129
TTriple< TFlt, TInt, TInt > TFltIntIntTr
Definition: ds.h:182
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:430
void TKroneckerLL::SetRndPerm ( )

Definition at line 820 of file kronecker.cpp.

820  {
821  NodePerm.Gen(Nodes, 0);
822  for (int i = 0; i < Graph->GetNodes(); i++) {
823  NodePerm.Add(i); }
826 }
static TRnd Rnd
Definition: kronecker.h:14
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:499
void SetIPerm(const TIntV &Perm)
!!!!! MYUNGHWAN, CHECK!
Definition: kronecker.cpp:875
TIntV NodePerm
Definition: kronecker.h:128
void Shuffle(TRnd &Rnd)
Randomly shuffles the elements of the vector.
Definition: ds.h:1335
PNGraph Graph
Definition: kronecker.h:120
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
double TKroneckerLL::SwapNodesLL ( const int &  NId1,
const int &  NId2 
)

Definition at line 1083 of file kronecker.cpp.

1083  {
1084  // subtract old LL (remove nodes)
1085  LogLike = LogLike - NodeLLDelta(NId1) - NodeLLDelta(NId2);
1086  const int PrevId1 = NodePerm[NId1], PrevId2 = NodePerm[NId2];
1087  // double-counted edges
1088  if (Graph->IsEdge(NId1, NId2)) {
1089  LogLike += - LLMtx.GetApxNoEdgeLL(PrevId1, PrevId2, KronIters)
1090  + LLMtx.GetEdgeLL(PrevId1, PrevId2, KronIters); }
1091  if (Graph->IsEdge(NId2, NId1)) {
1092  LogLike += - LLMtx.GetApxNoEdgeLL(PrevId2, PrevId1, KronIters)
1093  + LLMtx.GetEdgeLL(PrevId2, PrevId1, KronIters); }
1094  // swap
1095  NodePerm.Swap(NId1, NId2);
1096  InvertPerm.Swap(NodePerm[NId1], NodePerm[NId2]);
1097  // add new LL (add nodes)
1098  LogLike = LogLike + NodeLLDelta(NId1) + NodeLLDelta(NId2);
1099  const int NewId1 = NodePerm[NId1], NewId2 = NodePerm[NId2];
1100  // correct for double-counted edges
1101  if (Graph->IsEdge(NId1, NId2)) {
1102  LogLike += + LLMtx.GetApxNoEdgeLL(NewId1, NewId2, KronIters)
1103  - LLMtx.GetEdgeLL(NewId1, NewId2, KronIters); }
1104  if (Graph->IsEdge(NId2, NId1)) {
1105  LogLike += + LLMtx.GetApxNoEdgeLL(NewId2, NewId1, KronIters)
1106  - LLMtx.GetEdgeLL(NewId2, NewId1, KronIters); }
1107  return LogLike;
1108 }
double GetApxNoEdgeLL(int NId1, int NId2, const int &NKronIters) const
Definition: kronecker.cpp:191
double GetEdgeLL(int NId1, int NId2, const int &NKronIters) const
Definition: kronecker.cpp:175
TFlt LogLike
Definition: kronecker.h:135
TIntV NodePerm
Definition: kronecker.h:128
void Swap(TVec< TVal, TSizeTy > &Vec)
Swaps the contents of the vector with Vec.
Definition: ds.h:1101
double NodeLLDelta(const int &NId) const
Definition: kronecker.cpp:1055
bool IsEdge(const int &SrcNId, const int &DstNId, const bool &IsDir=true) const
Tests whether an edge from node IDs SrcNId to DstNId exists in the graph.
Definition: graph.cpp:363
TInt KronIters
Definition: kronecker.h:121
TKronMtx LLMtx
Definition: kronecker.h:134
PNGraph Graph
Definition: kronecker.h:120
TIntV InvertPerm
Definition: kronecker.h:129
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.

2110  {
2111  TFltPrV BicV, MdlV, LLV;
2112  const double rndGP = G->GetEdges()/TMath::Sqr(double(G->GetNodes()));
2113  const double RndGLL = G->GetEdges()*log(rndGP )+ (TMath::Sqr(double(G->GetNodes()))-G->GetEdges())*log(1-rndGP);
2114  LLV.Add(TFltPr(1, RndGLL));
2115  BicV.Add(TFltPr(1, -RndGLL + 0.5*TMath::Sqr(1)*log(TMath::Sqr(G->GetNodes()))));
2116  MdlV.Add(TFltPr(1, -RndGLL + 32*TMath::Sqr(1)+2*(log((double)1)+log((double)G->GetNodes()))));
2117  for (int NZero = 2; NZero < 10; NZero++) {
2118  const TKronMtx InitKronMtx = TKronMtx::GetInitMtx(NZero, G->GetNodes(), G->GetEdges());
2119  InitKronMtx.Dump("INIT PARAM", true);
2120  TKroneckerLL KronLL(G, InitKronMtx);
2121  KronLL.SetPerm('d'); // degree perm
2122  const double LastLL = KronLL.GradDescent(GradIters, LearnRate, 0.001, 0.01, WarmUp, NSamples);
2123  LLV.Add(TFltPr(NZero, LastLL));
2124  BicV.Add(TFltPr(NZero, -LastLL + 0.5*TMath::Sqr(NZero)*log(TMath::Sqr(G->GetNodes()))));
2125  MdlV.Add(TFltPr(NZero, -LastLL + 32*TMath::Sqr(NZero)+2*(log((double)NZero)+log((double)KronLL.GetKronIters()))));
2126  { TGnuPlot GP("LL-"+OutFNm, Desc1);
2127  GP.AddPlot(LLV, gpwLinesPoints, "Log-likelihood", "linewidth 1 pointtype 6 pointsize 2");
2128  GP.SetXYLabel("NZero", "Log-Likelihood"); GP.SavePng(); }
2129  { TGnuPlot GP("BIC-"+OutFNm, Desc1);
2130  GP.AddPlot(BicV, gpwLinesPoints, "BIC", "linewidth 1 pointtype 6 pointsize 2");
2131  GP.SetXYLabel("NZero", "BIC"); GP.SavePng(); }
2132  { TGnuPlot GP("MDL-"+OutFNm, Desc1);
2133  GP.AddPlot(MdlV, gpwLinesPoints, "MDL", "linewidth 1 pointtype 6 pointsize 2");
2134  GP.SetXYLabel("NZero", "MDL"); GP.SavePng(); }
2135  }
2136 }
int GetEdges() const
Returns the number of edges in the graph.
Definition: graph.cpp:313
void Dump(const TStr &MtxNm=TStr(), const bool &Sort=false) const
Definition: kronecker.cpp:636
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:499
static TKronMtx GetInitMtx(const int &Dim, const int &Nodes, const int &Edges)
Definition: kronecker.cpp:705
static double Sqr(const double &x)
Definition: xmath.h:12
!!!!! MYUNGHWAN, CHECK!
Definition: kronecker.h:116
TPair< TFlt, TFlt > TFltPr
Definition: ds.h:99
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:430
void TKroneckerLL::TestGradDescent ( const int &  KronIters,
const int &  KiloSamples,
const TStr Permutation 
)
static

Definition at line 2138 of file kronecker.cpp.

2138  {
2139  const TStr OutFNm = TStr::Fmt("grad-%s%d-%dk", Permutation.CStr(), KronIters, KiloSamples);
2140  TKronMtx KronParam = TKronMtx::GetMtx("0.8 0.6; 0.6 0.4");
2141  PNGraph Graph = TKronMtx::GenFastKronecker(KronParam, KronIters, true, 0);
2142  TKroneckerLL KronLL(Graph, KronParam);
2143  TVec<TFltV> GradVV(4), SDevVV(4); TFltV XValV;
2144  int NId1 = 0, NId2 = 0, NAccept = 0;
2145  TVec<TMom> GradMomV(4);
2146  TExeTm ExeTm;
2147  if (Permutation == "r") KronLL.SetRndPerm();
2148  else if (Permutation == "d") KronLL.SetDegPerm();
2149  else if (Permutation == "o") KronLL.SetOrderPerm();
2150  else FailR("Unknown permutation (r,d,o)");
2151  KronLL.CalcApxGraphLL();
2152  KronLL.CalcApxGraphDLL();
2153  for (int s = 0; s < 1000*KiloSamples; s++) {
2154  if (KronLL.SampleNextPerm(NId1, NId2)) { // new permutation
2155  KronLL.UpdateGraphDLL(NId1, NId2); NAccept++; }
2156  if (s > 50000) { //warm up period
2157  for (int m = 0; m < 4; m++) { GradVV[m].Add(KronLL.GradV[m]); }
2158  if ((s+1) % 1000 == 0) {
2159  printf(".");
2160  for (int m = 0; m < 4; m++) { GradVV[m].Add(KronLL.GradV[m]); }
2161  XValV.Add((s+1));
2162  if ((s+1) % 100000 == 0) {
2163  TGnuPlot GP(OutFNm, TStr::Fmt("Gradient vs. samples. %d nodes, %d edges", Graph->GetNodes(), Graph->GetEdges()), true);
2164  for (int g = 0; g < GradVV.Len(); g++) {
2165  GP.AddPlot(XValV, GradVV[g], gpwLines, TStr::Fmt("grad %d", g)); }
2166  GP.SetXYLabel("sample index","log Gradient");
2167  GP.SavePng();
2168  }
2169  }
2170  }
2171  }
2172  printf("\n");
2173  for (int m = 0; m < 4; m++) {
2174  GradMomV[m].Def();
2175  printf("grad %d: mean: %12f sDev: %12f median: %12f\n", m,
2176  GradMomV[m].GetMean(), GradMomV[m].GetSDev(), GradMomV[m].GetMedian());
2177  }
2178 }
Definition: tm.h:355
TFltV & GetMtx()
Definition: kronecker.h:35
int GetEdges() const
Returns the number of edges in the graph.
Definition: graph.cpp:313
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:499
!!!!! MYUNGHWAN, CHECK!
Definition: kronecker.h:116
#define FailR(Reason)
Definition: bd.h:240
TInt KronIters
Definition: kronecker.h:121
Definition: dt.h:412
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
PNGraph Graph
Definition: kronecker.h:120
char * CStr()
Definition: dt.h:476
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:430
static PNGraph GenFastKronecker(const TKronMtx &SeedMtx, const int &NIter, const bool &IsDir, const int &Seed=0)
Definition: kronecker.cpp:349
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.

1942  {
1943  printf("Test gradient descent on a synthetic kronecker graphs:\n");
1944  if (DoExact) { printf(" -- Exact gradient calculations\n"); }
1945  else { printf(" -- Approximate gradient calculations\n"); }
1946  if (TruePerm) { printf(" -- No permutation sampling (use true permutation)\n"); }
1947  else { printf(" -- Sample permutations (start with degree permutation)\n"); }
1948  TExeTm IterTm;
1949  int Iter;
1950  double OldLL=0, MyLL=0, AvgAbsErr, AbsSumErr;
1951  TFltV MyGradV, SDevV;
1952  TFltV LearnRateV(GetParams()); LearnRateV.PutAll(LearnRate);
1953  if (TruePerm) {
1954  SetOrderPerm();
1955  }
1956  else {
1957  /*printf("SET EIGEN VECTOR PERMUTATIONS\n");
1958  TFltV LeftSV, RightSV;
1959  TGSvd::GetSngVec(Graph, LeftSV, RightSV);
1960  TFltIntPrV V;
1961  for (int v=0; v<LeftSV.Len();v++) { V.Add(TFltIntPr(LeftSV[v], v)); }
1962  V.Sort(false);
1963  NodePerm.Gen(Nodes, 0);
1964  for (int v=0; v < V.Len();v++) { NodePerm.Add(V[v].Val2); } //*/
1965  //printf("RANDOM PERMUTATION\n"); SetRndPerm();
1966  printf("DEGREE PERMUTATION\n"); SetDegPerm();
1967  }
1968  for (Iter = 0; Iter < 100; Iter++) {
1969  if (TruePerm) {
1970  // don't sample over permutations
1971  if (DoExact) { CalcGraphDLL(); CalcGraphLL(); } // slow, O(N^2)
1972  else { CalcApxGraphDLL(); CalcApxGraphLL(); } // fast
1973  MyLL = LogLike; MyGradV = GradV;
1974  } else {
1975  printf(".");
1976  // sample over permutations (approximate calculations)
1977  SampleGradient(WarmUp, NSamples, MyLL, MyGradV);
1978  }
1979  printf("%d] LL: %g, ", Iter, MyLL);
1980  AvgAbsErr = TKronMtx::GetAvgAbsErr(ProbMtx, TrueParam);
1981  AbsSumErr = fabs(ProbMtx.GetMtxSum() - TrueParam.GetMtxSum());
1982  printf(" avgAbsErr: %.4f, absSumErr: %.4f, newLL: %.2f, deltaLL: %.2f\n", AvgAbsErr, AbsSumErr, MyLL, OldLL-MyLL);
1983  for (int p = 0; p < GetParams(); p++) {
1984  // set learn rate so that move for each parameter is inside the [0.01, 0.1]
1985  LearnRateV[p] *= 0.9;
1986  //printf("%d: rate: %f delta:%f\n", p, LearnRateV[p], fabs(LearnRateV[p]*MyGradV[p]));
1987  while (fabs(LearnRateV[p]*MyGradV[p]) > 0.1) { LearnRateV[p] *= 0.9; }
1988  //printf(" rate: %f delta:%f\n", LearnRateV[p], fabs(LearnRateV[p]*MyGradV[p]));
1989  while (fabs(LearnRateV[p]*MyGradV[p]) < 0.001) { LearnRateV[p] *= (1.0/0.9); }
1990  //printf(" rate: %f delta:%f\n", LearnRateV[p], fabs(LearnRateV[p]*MyGradV[p]));
1991  printf(" %d] %f <-- %f + %f lrnRate:%g\n", p, ProbMtx.At(p) + LearnRateV[p]*MyGradV[p],
1992  ProbMtx.At(p), (double)(LearnRateV[p]*MyGradV[p]), LearnRateV[p]());
1993  ProbMtx.At(p) = ProbMtx.At(p) + LearnRateV[p]*MyGradV[p];
1994  // box constraints
1995  if (ProbMtx.At(p) > 0.99) { ProbMtx.At(p)=0.99; }
1996  if (ProbMtx.At(p) < 0.01) { ProbMtx.At(p)=0.01; }
1997  }
1998  ProbMtx.GetLLMtx(LLMtx); OldLL = MyLL;
1999  if (AvgAbsErr < 0.01) { printf("***CONVERGED!\n"); break; }
2000  printf("\n"); fflush(stdout);
2001  }
2002  TrueParam.Dump("True Thetas", true);
2003  ProbMtx.Dump("Final Thetas", true);
2004  printf(" AvgAbsErr: %f\n AbsSumErr: %f\n Iterations: %d\n", AvgAbsErr, AbsSumErr, Iter);
2005  printf("Iteration run time: %s, sec: %g\n\n", IterTm.GetTmStr(), IterTm.GetSecs());
2006  return TFltQu(AvgAbsErr, AbsSumErr, Iter, IterTm.GetSecs());
2007 }
int GetParams() const
Definition: kronecker.h:164
Definition: tm.h:355
double GetMtxSum() const
Definition: kronecker.cpp:140
void SetOrderPerm()
Definition: kronecker.cpp:813
void Dump(const TStr &MtxNm=TStr(), const bool &Sort=false) const
Definition: kronecker.cpp:636
TFlt LogLike
Definition: kronecker.h:135
const double & At(const int &Row, const int &Col) const
Definition: kronecker.h:46
double CalcGraphLL()
Definition: kronecker.cpp:1022
double CalcApxGraphLL()
Definition: kronecker.cpp:1037
const char * GetTmStr() const
Definition: tm.h:370
void SetDegPerm()
Definition: kronecker.cpp:828
void SampleGradient(const int &WarmUp, const int &NSamples, double &AvgLL, TFltV &GradV)
Definition: kronecker.cpp:1271
TQuad< TFlt, TFlt, TFlt, TFlt > TFltQu
Definition: ds.h:264
void GetLLMtx(TKronMtx &LLMtx)
Definition: kronecker.cpp:98
const TFltV & CalcGraphDLL()
Definition: kronecker.cpp:1158
TKronMtx ProbMtx
Definition: kronecker.h:134
const TFltV & CalcApxGraphDLL()
Definition: kronecker.cpp:1194
TKronMtx LLMtx
Definition: kronecker.h:134
double GetSecs() const
Definition: tm.h:366
TFltV GradV
Definition: kronecker.h:136
static double GetAvgAbsErr(const TKronMtx &Kron1, const TKronMtx &Kron2)
Definition: kronecker.cpp:655
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.

1795  {
1796  printf("Sample permutations: %s (warm-up: %s)\n", TInt::GetMegaStr(NSamples).CStr(), TInt::GetMegaStr(WarmUp).CStr());
1797  int NId1=0, NId2=0, NAccept=0;
1798  TExeTm ExeTm;
1799  const int PlotLen = NSamples/1000+1;
1800  double TrueLL=-1, AvgLL=0.0;
1801  TFltV AvgGradV(GetParams());
1802  TFltPrV TrueLLV(PlotLen, 0); // true log-likelihood (under the correct permutation)
1803  TFltPrV EstLLV(PlotLen, 0); // estiamted log-likelihood (averaged over last 1k permutation)
1804  TFltPrV AcceptV; // sample acceptance ratio
1805  TFltV SampleLLV(NSamples, 0);
1806  TVec<TFltPrV> GradVV(GetParams());
1807  for (int g = 0; g < GetParams(); g++) {
1808  GradVV[g].Gen(PlotLen, 0); }
1809  if (! TrueMtx.Empty()) {
1810  TIntV PermV=NodePerm; TKronMtx CurMtx=ProbMtx; ProbMtx.Dump();
1811  InitLL(TrueMtx); SetOrderPerm(); CalcApxGraphLL(); printf("TrueLL: %f\n", LogLike());
1812  TrueLL=LogLike; InitLL(CurMtx); NodePerm=PermV;
1813  }
1814  CalcApxGraphLL();
1815  printf("LogLike at start: %f\n", LogLike());
1816  if (WarmUp > 0) {
1817  EstLLV.Add(TFltPr(0, LogLike));
1818  if (TrueLL != -1) { TrueLLV.Add(TFltPr(0, TrueLL)); }
1819  for (int s = 0; s < WarmUp; s++) { SampleNextPerm(NId1, NId2); }
1820  printf(" warm-up:%s,", ExeTm.GetTmStr()); ExeTm.Tick();
1821  }
1822  printf("LogLike afterm warm-up: %f\n", LogLike());
1823  CalcApxGraphLL(); // re-calculate LL (due to numerical errors)
1824  CalcApxGraphDLL();
1825  EstLLV.Add(TFltPr(WarmUp, LogLike));
1826  if (TrueLL != -1) { TrueLLV.Add(TFltPr(WarmUp, TrueLL)); }
1827  printf(" recalculated: %f\n", LogLike());
1828  // start sampling
1829  printf(" sampling (average per 1000 samples)\n");
1830  TVec<TFltV> SamplVV(5);
1831  for (int s = 0; s < NSamples; s++) {
1832  if (SampleNextPerm(NId1, NId2)) { // new permutation
1833  UpdateGraphDLL(NId1, NId2); NAccept++; }
1834  for (int m = 0; m < AvgGradV.Len(); m++) { AvgGradV[m] += GradV[m]; }
1835  AvgLL += GetLL();
1836  SampleLLV.Add(GetLL());
1837  /*SamplVV[0].Add(GetLL()); // gives worse autocoreelation than the avg below
1838  SamplVV[1].Add(GradV[0]);
1839  SamplVV[2].Add(GradV[1]);
1840  SamplVV[3].Add(GradV[2]);
1841  SamplVV[4].Add(GradV[3]);*/
1842  if (s > 0 && s % 1000 == 0) {
1843  printf(".");
1844  for (int g = 0; g < AvgGradV.Len(); g++) {
1845  GradVV[g].Add(TFltPr(WarmUp+s, AvgGradV[g] / 1000.0)); }
1846  EstLLV.Add(TFltPr(WarmUp+s, AvgLL / 1000.0));
1847  if (TrueLL != -1) { TrueLLV.Add(TFltPr(WarmUp+s, TrueLL)); }
1848  AcceptV.Add(TFltPr(WarmUp+s, NAccept/1000.0));
1849  // better (faster decaying) autocorrelation when one takes avg. of 1000 consecutive samples
1850  /*SamplVV[0].Add(AvgLL);
1851  SamplVV[1].Add(AvgGradV[0]);
1852  SamplVV[2].Add(AvgGradV[1]);
1853  SamplVV[3].Add(AvgGradV[2]);
1854  SamplVV[4].Add(AvgGradV[3]); //*/
1855  if (s % 100000 == 0 && DoPlot) {
1856  const TStr Desc = TStr::Fmt("P(NodeSwap)=%g. Nodes: %d, Edges: %d, Params: %d, WarmUp: %s, Samples: %s", PermSwapNodeProb(),
1857  Graph->GetNodes(), Graph->GetEdges(), GetParams(), TInt::GetMegaStr(WarmUp).CStr(), TInt::GetMegaStr(NSamples).CStr());
1858  PlotGrad(EstLLV, TrueLLV, GradVV, AcceptV, OutFNm, Desc);
1859  for (int n = 0; n < SamplVV.Len(); n++) {
1860  PlotAutoCorrelation(SamplVV[n], 1000, TStr::Fmt("%s-n%d", OutFNm.CStr(), n), Desc); }
1861  printf(" samples: %d, time: %s, samples/s: %.1f\n", s, ExeTm.GetTmStr(), double(s+1)/ExeTm.GetSecs());
1862  }
1863  AvgLL = 0; AvgGradV.PutAll(0); NAccept=0;
1864  }
1865  }
1866  if (DoPlot) {
1867  const TStr Desc = TStr::Fmt("P(NodeSwap)=%g. Nodes: %d, Edges: %d, Params: %d, WarmUp: %s, Samples: %s", PermSwapNodeProb(),
1868  Graph->GetNodes(), Graph->GetEdges(), GetParams(), TInt::GetMegaStr(WarmUp).CStr(), TInt::GetMegaStr(NSamples).CStr());
1869  PlotGrad(EstLLV, TrueLLV, GradVV, AcceptV, OutFNm, Desc);
1870  for (int n = 0; n < SamplVV.Len(); n++) {
1871  PlotAutoCorrelation(SamplVV[n], 1000, TStr::Fmt("%s-n%d", OutFNm.CStr(), n), Desc); }
1872  }
1873  return SampleLLV; // seems to work better for potential scale reduction plot
1874 }
int GetParams() const
Definition: kronecker.h:164
Definition: tm.h:355
static TStr GetMegaStr(const int &Val)
Definition: dt.h:1223
void UpdateGraphDLL(const int &SwapNId1, const int &SwapNId2)
Definition: kronecker.cpp:1241
void SetOrderPerm()
Definition: kronecker.cpp:813
int GetEdges() const
Returns the number of edges in the graph.
Definition: graph.cpp:313
void Dump(const TStr &MtxNm=TStr(), const bool &Sort=false) const
Definition: kronecker.cpp:636
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:499
bool SampleNextPerm(int &NId1, int &NId2)
Definition: kronecker.cpp:1111
TFlt LogLike
Definition: kronecker.h:135
TFlt PermSwapNodeProb
Definition: kronecker.h:123
TIntV NodePerm
Definition: kronecker.h:128
double CalcApxGraphLL()
Definition: kronecker.cpp:1037
const char * GetTmStr() const
Definition: tm.h:370
void PlotGrad(const TFltPrV &EstLLV, const TFltPrV &TrueLLV, const TVec< TFltPrV > &GradVV, const TFltPrV &AcceptV, const TStr &OutFNm, const TStr &Desc)
Definition: kronecker.cpp:1740
void PlotAutoCorrelation(const TFltV &ValV, const int &MaxK, const TStr &OutFNm, const TStr &Desc)
Definition: kronecker.cpp:1773
bool Empty() const
Definition: kronecker.h:32
void Tick()
Definition: tm.h:364
void InitLL(const TFltV &ParamV)
Definition: kronecker.cpp:996
TPair< TFlt, TFlt > TFltPr
Definition: ds.h:99
TKronMtx ProbMtx
Definition: kronecker.h:134
const TFltV & CalcApxGraphDLL()
Definition: kronecker.cpp:1194
Definition: dt.h:412
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
PNGraph Graph
Definition: kronecker.h:120
double GetSecs() const
Definition: tm.h:366
TFltV GradV
Definition: kronecker.h:136
char * CStr()
Definition: dt.h:476
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
double GetLL() const
Definition: kronecker.h:204
void TKroneckerLL::UpdateGraphDLL ( const int &  SwapNId1,
const int &  SwapNId2 
)

Definition at line 1241 of file kronecker.cpp.

1241  {
1242  for (int ParamId = 0; ParamId < LLMtx.Len(); ParamId++) {
1243  // permutation before the swap (swap back to previous position)
1244  NodePerm.Swap(SwapNId1, SwapNId2);
1245  // subtract old DLL
1246  TFlt& DLL = GradV[ParamId];
1247  DLL = DLL - NodeDLLDelta(ParamId, SwapNId1) - NodeDLLDelta(ParamId, SwapNId2);
1248  // double-counted edges
1249  const int PrevId1 = NodePerm[SwapNId1], PrevId2 = NodePerm[SwapNId2];
1250  if (Graph->IsEdge(SwapNId1, SwapNId2)) {
1251  DLL += - LLMtx.GetApxNoEdgeDLL(ParamId, PrevId1, PrevId2, KronIters)
1252  + LLMtx.GetEdgeDLL(ParamId, PrevId1, PrevId2, KronIters); }
1253  if (Graph->IsEdge(SwapNId2, SwapNId1)) {
1254  DLL += - LLMtx.GetApxNoEdgeDLL(ParamId, PrevId2, PrevId1, KronIters)
1255  + LLMtx.GetEdgeDLL(ParamId, PrevId2, PrevId1, KronIters); }
1256  // permutation after the swap (restore the swap)
1257  NodePerm.Swap(SwapNId1, SwapNId2);
1258  // add new DLL
1259  DLL = DLL + NodeDLLDelta(ParamId, SwapNId1) + NodeDLLDelta(ParamId, SwapNId2);
1260  const int NewId1 = NodePerm[SwapNId1], NewId2 = NodePerm[SwapNId2];
1261  // double-counted edges
1262  if (Graph->IsEdge(SwapNId1, SwapNId2)) {
1263  DLL += + LLMtx.GetApxNoEdgeDLL(ParamId, NewId1, NewId2, KronIters)
1264  - LLMtx.GetEdgeDLL(ParamId, NewId1, NewId2, KronIters); }
1265  if (Graph->IsEdge(SwapNId2, SwapNId1)) {
1266  DLL += + LLMtx.GetApxNoEdgeDLL(ParamId, NewId2, NewId1, KronIters)
1267  - LLMtx.GetEdgeDLL(ParamId, NewId2, NewId1, KronIters); }
1268  }
1269 }
int Len() const
Definition: kronecker.h:31
double NodeDLLDelta(const int ParamId, const int &NId) const
Definition: kronecker.cpp:1214
double GetEdgeDLL(const int &ParamId, int NId1, int NId2, const int &NKronIters) const
Definition: kronecker.cpp:207
Definition: dt.h:1383
TIntV NodePerm
Definition: kronecker.h:128
void Swap(TVec< TVal, TSizeTy > &Vec)
Swaps the contents of the vector with Vec.
Definition: ds.h:1101
double GetApxNoEdgeDLL(const int &ParamId, int NId1, int NId2, const int &NKronIters) const
Definition: kronecker.cpp:240
bool IsEdge(const int &SrcNId, const int &DstNId, const bool &IsDir=true) const
Tests whether an edge from node IDs SrcNId to DstNId exists in the graph.
Definition: graph.cpp:363
TInt KronIters
Definition: kronecker.h:121
TKronMtx LLMtx
Definition: kronecker.h:134
PNGraph Graph
Definition: kronecker.h:120
TFltV GradV
Definition: kronecker.h:136

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.

TKronEMType TKroneckerLL::EMType
private

Definition at line 138 of file kronecker.h.

TIntTrV TKroneckerLL::GEdgeV
private

Definition at line 125 of file kronecker.h.

TFltV TKroneckerLL::GradV
private

Definition at line 136 of file kronecker.h.

PNGraph TKroneckerLL::Graph
private

Definition at line 120 of file kronecker.h.

TIntV TKroneckerLL::InvertPerm
private

Definition at line 129 of file kronecker.h.

TInt TKroneckerLL::KronIters
private

Definition at line 121 of file kronecker.h.

TIntTrV TKroneckerLL::LEdgeV
private

Definition at line 126 of file kronecker.h.

TKronMtx TKroneckerLL::LLMtx
private

Definition at line 134 of file kronecker.h.

TFltV TKroneckerLL::LLV
private

Definition at line 142 of file kronecker.h.

TFlt TKroneckerLL::LogLike
private

Definition at line 135 of file kronecker.h.

TInt TKroneckerLL::LSelfEdge
private

Definition at line 127 of file kronecker.h.

TInt TKroneckerLL::MissEdges
private

Definition at line 139 of file kronecker.h.

TVec<TKronMtx> TKroneckerLL::MtxV
private

Definition at line 143 of file kronecker.h.

TIntV TKroneckerLL::NodePerm
private

Definition at line 128 of file kronecker.h.

TInt TKroneckerLL::Nodes
private

Definition at line 121 of file kronecker.h.

TFlt TKroneckerLL::PermSwapNodeProb
private

Definition at line 123 of file kronecker.h.

TKronMtx TKroneckerLL::ProbMtx
private

Definition at line 134 of file kronecker.h.

TInt TKroneckerLL::RealEdges
private

Definition at line 132 of file kronecker.h.

TInt TKroneckerLL::RealNodes
private

Definition at line 131 of file kronecker.h.


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