We present two online causal structure learning algorithms which can track changes in a causal structure and process data in a dynamic real-time manner. Standard causal structure learning algorithms assume that causal structure does not change during the data collection process, but in real-world scenarios, it does often change. Therefore, it is inappropriate to handle such changes with existing batch-learning approaches, and instead, a structure should be learned in an online manner. The online causal structure learning algorithms we present here can revise correlation values without reprocessing the entire dataset and use an existing model to avoid relearning the causal links in the prior model, which still fit data. Proposed algorithms are tested on synthetic and real-world datasets, the latter being a seasonally adjusted commodity price index dataset for the U.S. The online causal structure learning algorithms outperformed standard FCI by a large margin in learning the changed causal structure correctly and efficiently when latent variables were present.
The standard TDL algorithm provides a dynamic estimate of a univariate random variable using a simple update rule. In this update, the error in the current estimate is updated with a learning rate coefficient. Therefore, the static learning rate plays an important role and controls how quickly or slowly a model learns a problem. If it is chosen too small, the TDL algorithm converges slowly. If it is chosen too large, the algorithm will be so sensitive even when the environment is stable. TDL algorithm can detect slow change but not high stability or dramatic changes. That feature is essential for causal structure learning as causal structures often have non-deterministic connections. In contrast, CPD algorithms are useful for dramatic changes that indicate breaks between periods of stability @cite_15 . CPD algorithms must store large parts of input data. These algorithms assume that the model only has a dramatically changing environment separated by periods of stability. Both algorithm types have not been applied to tracking causal structure. To do so, they need the necessary modifications.
@cite_15
2072931156
We introduce two new temporal difference (TD) algorithms based on the theory of linear least-squares function approximation. We define an algorithm we call Least-Squares TD (LS TD) for which we prove probability-one convergence when it is used with a function approximator linear in the adjustable parameters. We then define a recursive version of this algorithm, Recursive Least-Square TD (RLS TD). Although these new TD algorithms require more computation per time-step than do Sutton‘s TD(λ) algorithms, they are more efficient in a statistical sense because they extract more information from training experiences. We describe a simulation experiment showing the substantial improvement in learning rate achieved by RLS TD in an example Markov prediction problem. To quantify this improvement, we introduce the TD error variance of a Markov chain, σTD, and experimentally conclude that the convergence rate of a TD algorithm depends linearly on σTD. In addition to converging more rapidly, LS TD and RLS TD do not have control parameters, such as a learning rate parameter, thus eliminating the possibility of achieving poor performance by an unlucky choice of parameters.