Artificial Intelligence

In case of high dimensionality, many models would fail, and this is known as curse of dimensionality. For example, when the dimension is high, KNN need not to be close to the target point. In general, any method that attempts to produce local varying functions in small isotropic neighborhoods will run into problems in high dimensions.

It is one kind of Monte Carlo Markov Chain method, for sampling from posterior distribution. The key is to sample from variables' conditional distribution: for each variable, sample from the conditional distribution where all other variables are fixed to their previous value.

\[x^i_1 \sim p(X_1=x_1 | X_2 = x^{i-1}_2, X_3=.., X_4=.., ...)\]

The convergence is when the sample values have the same distribution as their posterior joint distribution. The theory of MCMC guarantees that the stationary distribution of the samples is the target joint posterior distribution.

• How do we know they converge?
• what do you mean by "sample from conditional distribution"?

Two causes for an effect, if we can confirm one cause, it will reduce the happen of the other.

However, one cause does not provide any evidence of the other cause, because they are independent (??). But in probability theory, it SHOULD reduce the other cause.

For example, you scored 100/100 out of a test, can have two causes:

• paper is too easy
• you are too smart

Given that the paper is too easy, I tend not to think you are too smart.

Using the example taken from Wikipedia

	A	B	C	D	total
White collar	90	60	104	95	349
Blue collar	30	50	51	20	151
No collar	30	40	45	35	150
Total	150	150	200	150	650

We basically use the 3x4 table cells. This is the observed number.

1. We first calculate a table for the expected number, for example for (A, white collar), we calculate it as (150 /650 * 349 = 80.54).
2. Then, we compute the difference in each cell, as the test statistics, for example (90 - 80.54) / 80.54 = 1.11
3. We sum up all these difference values in the table cells
4. calculate the Degree of Freedom (DF) as \((ncol-1)*(nrow-1)\)
5. Using the DF and the test statistics, we can look up table to see what is the probability of seen such a distribution if the data is independent (our null hypothesis)

We define the outcome space as the space of possible outcomes, denoted as \(\Omega\). We also define the events \(S\). Each event \(\alpha \in S\) is a subset of \(\Omega\). For example, for a dice throwing, \(\Omega=\{1,2,3,4,5,6\}\), \(\{1\}\) and \(\{2,4,6\}\) are events.

Then, we can formally define a probability distribution P over \((\Omega, S)\) as a mapping from events in \(S\) to real values that satisfies the following conditions:

• \(P(\alpha) \ge 0\) for all \(\alpha \in S\)
• \(P(\Omega)=1\)
• If \(\alpha,\beta \in S\) and \(\alpha \cap \beta = \emptyset\), then \(P(\alpha \cup \beta) = P(\alpha) + P(\beta)\)

This definition also implies several interesting properties:

• \(P(\emptyset) = 0\)
• \(P(\alpha \cup \beta) = P(\alpha) + P(\beta) - P(\alpha \cup \beta)\)

There are two views of probability distribution. The frequentist interpretation views it as the frequencies of events, and the subjective interpretation views it as the degrees of belief.

We define conditional probability distribution (CPD) as \(P(\beta | \alpha) = \frac{P(\alpha \cap \beta)}{P(\alpha)}\). From this, we can get:

• chain rule: \(P(\alpha_1 \cap ... \cap \alpha_k) = P(\alpha_1) P(\alpha_2 | \alpha_1) ... P(\alpha_k | \alpha_1 \cap ... \cap \alpha_{k-1})\)
• bayes' rule: \(P(\beta|\alpha) = \frac{P(\alpha|\beta)P(\beta)}{P(\alpha)}\)

So far, we use events. The use of events are cumbersome in some case. For example, we need to use GradeA, GradeB, GradeC, etc to represent the events for different grades. Thus, we introduce random variables (RV) as a way of reporting an attribute of the outcome. Formally, a random variable is defined by a function that associates with each outcome in \(\Omega\) a value. We use \(Val(X)\) to denote the set of values a random variable \(X\) can take. We use upper case \(X\) to denote the random variables, use lower case \(x\) to denote a generic value of \(X\), and use \(x^1, ..., x^k\) to denote the possible values. We use bold typeface X to denote a set of random variables, and lowercase bold typeface x to denote an assignment to all variables in the set. A distribution over random variables with \(k\) values are called Multinomial Distribution, one over binary random variables are called Bernoulli Distribution.

Once we define the random variables, we can define marginal distribution over X as the distribution over events that can be described using X, denoted by \(P(X)\). We may also be interested in the distribution over multiple random variables. In general, a joint distribution over a set \(X = \{X_1, ..., X_n\}\), denoted as \(P(X_1, ..., X_n)\), is the distribution that assigns probabilities to events that can be described using these random variables. We use \(\xi\) to refer to a full assignment to the variables in \(X\). The conditional probability in terms of random variables are intuitive.

For continuous random variables, probability density function (PDF) is used for continuous random variables, because the vector is infinite. I record some distributions here:

Uniform distribution over [a,b], denoted as \(X \sim Unif[a,b]\), if \(p(x) = \frac{1}{b-1}\) in [a,b] otherwise 0.

Gaussian distribution with mean \(\mu\) and variance \(\sigma^2\), denoted as \(X \sim N(\mu; \sigma^2)(x)\), if

\[p(X)=\frac{1}{\sqrt{2\pi} \sigma} e^{-\frac{(x-\mu)^2}{2 \sigma^2}}\]

Multivariate normal distribution:

\[N(x|\mu, \Sigma) = \frac{1}{(2\pi)^{D/2}} \frac{1}{|\Sigma|^{1/2}} exp\{-\frac{1}{2}(x-\mu)^T \Sigma^-1 (x-\mu)\} \]

Expectation is \(E_x[f]=\sum_x p(x)f(x)\). Variance is

\begin{align} var[f] & = E[(f(x) - E[f(x)])^2]\\ & = E[f(x)^2] - E[f(x)]^2 \end{align}

The square root of variance is called standard deviation.

Specially for x, it is

\[var[x] = E[x^2] - E[x]^2\]

The covariate of two random variables x and y is defined as

\begin{align} cov[x,y] & = E_{x,y}[(x-E[x])(y-E[y])]\\ & = E_{x,y}[xy] - E[x]E[y] \end{align}

The entropy is from information theory. We want to calculate how much information we gain after seeing an observation from a probability distribution \(p(x)\). Intuitively, if we see a highly improbable event, we received a lot of information. If we observe a very likely event, we gain less information. The extreme case, if we observe an event that is certain to happen, we would receive no information. How can we quantify this?

The straightforward thinking is that, the information gain of two independent observations \(x\) and \(y\) should be the sum of the gain of the two, i.e. \(h(x,y) = h(x) + h(y)\). And we have \(p(x,y) = p(x)p(y)\), thus, we need to take the logarithm of \(p(x)\) to define \(h(x)\), i.e.

\[h(x) = -log_2 p(x)\]

The basis 2 is arbitrary. We also want to define information gain for a distribution. To that end, we define entropy as

\[H(x) = - \sum_x p(x) log_2 p(x)\]

The conditional entropy is

\[H[y|x] = - \int \int p(y,x)ln p(y|x) dy dx\]

and we can see

\[H[x,y] = H[y|x] + H[x]\]

Consider some unknown distribution p(x), and we use q(x) to approximate it. If we use q(x) to transmit the information about p(x), how much additional information is required to correct the mistake? We model that by relative entropy, or Kullback-Leibler (KL) divergence, defined as:

\begin{align} KL(p||q) & = - \int p(x) ln q(x) dx - (- \int p(x) ln p(x) dx)\\ & = - \int p(x) ln \frac{q(x)}{p(x)} dx \end{align}

Note that this is not a symmetrical quantity. We can show that \(KL(p||q) \ge 0\) with equality if and only if \(p(x) = q(x)\).

Recall that for two random variables x and y, if they are independent, the joint distribution can factorize into the product of their marginals, i.e. \(p(x,y) = p(x)p(y)\). If they are not independent, how close they are from being independent? We can quantify this by mutual information between \(x\) and \(y\), defined as:

\begin{align} I[x,y] & = KL[p(x,y)||p(x)p(y)]\\ & = - \int \int p(x,y) ln \frac{p(x)p(y)}{p(x,y)} dx dy \end{align}

Finally, we can see

\[I[x,y] = H[x] - H[x|y] = H[y] - H[y|x]\]

The linearity of expectation property states that \(E[X+y]=E[X]+E[Y]\). There is no general product form, but if X and Y are independent, we have \(E[X*y]=E[X]*E[Y]\). The variance is defined as \(Var_P[X] = E_P[(X-E_P[X])^2]\), or \(Var[X] = E[X^2] - (E[X])^2\). We don't have even the linear property, but if X and Y are independent, then \(Var[X+Y]=Var[X]+Var[Y]\). The variance generally scales as a quadratic function of X: \(Var[aX+b]=a^2Var[X]\). The standard deviation is \(\sigma_X=\sqrt{Var[X]}\).

Next, we introduce independence. First in events notation, we say that

an event \(\alpha\) is independent of event \(\beta\) in P, denoted as \(P \models (\alpha \bot \beta)\), if \(P(\alpha | \beta) = P(\alpha)\) or if \(P(\beta) = 0\)

An alternative definition

\(P \models (\alpha \bot \beta)\) iff \(P(\alpha \cap \beta) = P(\alpha) P(\beta)\)

For conditional independence, we say that

an event \(\alpha\) is conditionally independent of event \(\beta\) given event \(\gamma\) in P, denoted as \(P \models (\alpha \bot \beta | \gamma)\), if \(P(\alpha | \beta \cap \gamma) = P(\alpha | \gamma)\) or if \(P(\beta \cap \gamma) = 0\)

And the alternative definition as well:

\(P \models (\alpha \bot \beta | \gamma)\) iff \(P(\alpha \cap \beta | \gamma) = P(\alpha | \gamma) P(\beta | \gamma)\)

Of course, we want to define in terms of random variables as well:

Let X, Y, Z be sets of random variables. We say X is conditional independent of Y given Z, if \(P \models (X=x \bot Y=y | Z=z)\) for all values x,y,z. When \(Z=\emptyset\), we simply write \((X \bot Y)\), and say X and Y are marginally independent.

The alternative for this:

\(P \models (X \bot Y | Z)\) iff \(P(X,Y | Z) = P(X|Z) P(Y|Z)\)

The conditional independence says that, learning the value of Y does not provide additional information about X, once we know Z. We have some properties hold in general:

• Symmetry: \((X \bot Y | Z) \Rightarrow (Y \bot X | Z)\)
• Decomposition: \((X\bot Y,W | Z) \Rightarrow (X \bot Y | Z)\)
• Weak union: \((X \bot Y,W |Z) \Rightarrow (X\bot Y | Z,W)\)
• Contraction: \((X \bot W | Z, Y) \& (X \bot Y|Z) \Rightarrow (X\bot Y,W|Z)\)

There is one more property, intersection, that holds in positive distribution, where \(P(\alpha) > 0\) for non-empty events. The property says, for mutually disjoint sets X,Y,Z,W, we have:

• intersection: \(X\bot Y|Z,W \& (X\bot W|Z,Y) \Rightarrow (X \bot Y,W|Z)\).

All these properties are called graphoid axioms.

After defining probability distribution, we are interested in answering probability queries. We have evidence variables E and query variables Y, and we aims to compute \(P(Y|E=e)\), and this is called the Posterior/, also called conditional probability or posterior probability. It seems also to be called probabilistic inference, referring to the computation of posterior probabilities given evidence.

A second type of query is MAP query, also called Most Probable Explanation (MPE). It aims to find a high-probable joint assignment to some subset of variables. The MAP assignment is the most likely assignment to all of the non-evidence variables. Formally, let \(W=X-E\), our task is to find \(MAP(W|e) = argmax_w P(w,e)\)

Non-parametric models essentially exploit the locality of data.

Histogram density model simply partitions the input into bins of width \(\delta_i\), and calculate the density inside each bin by normalization, i.e. \(\int p(x) dx = 1\), resulting in \(p_i = \frac{n_i}{N \delta_i}\).

The downsides:

1. it is discontinuous
2. it does not scale with dimensionality

Two other models, kernel method and KNN, are highly related. Specifically, with some D-dimentional distance model like Euclidean, we can define a region \(R\) of volume \(V\) around a data point containing \(K\) data points. The density estimator is \(p(x) = \frac{K}{NV}\). Importantly, if we fix K and determine the value of V from the data, it is called K-Nearest-Neighbor; if we fix V and determine K from the data, it is called Kernel Method. The kernel function is the function that define the shape of the region. The kernel method has one problem: since \(V\) is fixed, if the data points are dense at some points while sparse at others, it will lead to precision problem.

We typically denote undirected graph as H, directed graph as G, and a general graph as K.

• For two nodes connected by any edge, we have neighbor (Nb) relation
• A graph in which every pair of nodes is connected by an edge is called complete

For directed graph:

• For a direct edge, we have parent (Pa) and child (Ch) relation
• The boundary of X, denoted as \(Boundary_X\), is \(Pa_X \cup Nb_X\)
• A family in a graph is a node and its all parents
• A node is root if no parent
• A node is sink if it has no children
• A connected DAG in which every node has at most one parent is called a tree
• A connected DAG in which every node has at most one child is called a chain

For undirected graph, two nodes are adjacent if there is an edge joining them, denoted as \(X \sim Y\). A path is a set of vertices that are adjacent sequentially. A complete graph is a graph where every pair of vertices is joined by an edge. A subgraph is a subset of vertices together with their edges. A clique is a complete subgraph. It is called maximal if it is a clique and no other vertices can be added to it and still yield a clique.

For directed graph, a path can follow any edge, but must not reverse direction. However, a trail can follow either direction. Some defines the path as a trail, i.e. can go either along or against the arrows, and define the directed path for those that go along arrows. If there exists a path between two vertices, they are said to be connected, otherwise disconnected.

An acyclic graph containing both directed and undirected edges is called a partially directed acyclic graph (PDAG). Such a PDAG can be cecomposed into chain components, where the edges between components must be directed. The hybrid network is the one that has both continuous and discrete probabilities.

The skeleton of G is the corresponding undirected graph, i.e. strip away all arrowheads.

We have two views of the graphical model. On one hand, we view it as a representation of a set of independence that holds in the distribution. On the other, the graph defines a skeleton for factorizing a distribution: rather than represent the entire joint distribution, we break up the distribution into smaller factors locally, and the overall joint distribution can be represented as the product of these factors. This two perspectives of graphical model are equivalent in a deep sense.

Undirected graphical model is also called Markov random field or Markov network. Directed graphical model is called Bayesian network. They differ in the set of independence they can encode, and in the factorization of the distribution they can induce.

The general model is the Naive Bayes Model, or Idiot Bayes Model, where we assume the naive Bayes Assumption that all features are conditionally independent given its class. Thus we have the factorization \(P(C,X_1,...,X_n) = P(C) \prod_{i=1}^n P(X_i|C)\).

The naive Bayes model has too strong assumption. The Bayesian Network can encode the conditional independence relationship in a finer granularity. It can be viewed in two different ways, representing a joint distribution, and a compact representation of a set of conditional independence assumptions. Both views are equivalent.

The Bayesian network has two components: a graph encode the relation, and its Conditional Probability Distribution (CPD).

The Bayesian network is parameterized by a CPD, representing the distribution over one node given others. However, this does not make sense in an undirected model, in which we want a symmetric parameterization, and the probability should capture the degree to which A and B agree or disagree. We define a factor \(\phi\) to be a function from \(Val(D)\) to IR, where D is a set of random variables. As with Bayesian network, we want to represent the distribution by products of local probability, thus we want to compute \(P(a,b,c,d)\) as \(\phi_1(a,b) \phi_2(b,c) \phi_3(c,d) \phi_4(d,a)\). However, it is by no means to be normalized, thus we need to normalize it. The normalization is not a constant obviously, but a function. In particular, \(P(a,b,c,d) = \frac{1}{Z} \phi_1(a,b) \phi_2(b,c) \phi_3(c,d) \phi_4(d,a)\), where \(Z=\sum_{a,b,c,d} \phi_1(a,b) \phi_2(b,c) \phi_3(c,d) \phi_4(d,a)\) is called partition function. The factors product \(\phi_1 (X,Y) \phi_2(Y,Z)\) is defined such that the common parts in Y are matched, similar to database joins. A factor is only one contribution to the overall joint distribution, the full joint distribution must take into consideration of all factors involved. A concept called pairwise Markov Network is one where all the factors are over single variables or pairs of variables. In visual, it is structured as a grid.

When we want to make some assignment to some variables \(U=u\), it is called condition a distribution, or factor reduction, and the operation is to remove the entries that are inconsistent with the event \(U=u\), and re-normalize the factors. Using the same idea, given \(U=u\) as a context, the reduced Markov Network \(H[u]\) of the Markov Network \(H\) is the one over nodes \(W=X-U\), and keeps the same edges, i.e. we have an edge X-Y if there is an edge X-Y in H.

Inference refers to answering probabilistic queries, the computation of marginal vertex probabilities and expectations from their joint distribution. In particular, we study the computing of posterior probability of some variables given evidence on others.

Learning refers to the estimation of edge parameters from data, and learning the structure skeleton. Fundamental assumptions in learning is the Independent and Identical Distribution (IID), meaning that the data samples are sampled independently from the same distribution.

The central idea of learning is the likelihood of the data, given the model, denoted as \(P(D: M)\). The log of it is the log-likelihood \(l(D: M) = log P(D: M)\). The negated forms are called the loss and log-loss, reflecting the cost per instance of using the model. The hamming loss counts the number of variables in which the model differs from the ground truth.

Generally the amount of data required to estimate parameters grows linearly with the number of parameters. And since the network connectivity can be exponential to the number of variables, the amount of data can grow exponentially with the variables, or the network connectivity. The bias-variance trade-off also applies here obviously. Restricting our model class is one way to reduce overfitting, it prevents us from selecting a model that precisely captures the training data. However, we are giving more bias. The less restricted ones generally cause large variance.

Different types of objectives defines different kind of training. If we use P(Y,X) as the objective, it is called generative training, because we train the model to generate all the variables, both the predict variable and the feature variable. Alternatively, the discriminative training uses \(P(Y|X)\) as the objective, thus only model the result. Generally speaking, generative models have a higher bias, because they make more assumptions about the form of the distribution, but obviously this training works better on limited data. The generative models offer a more natural interpretation of a domain, and are better able to deal with missing values and unlabeled data.

The training will contain three axes of problems, namely whether the output is Bayesian or Markov network, the constraints we know about the model prior to learning, and whether the data are fully observable.

The basic representation of causal model is the causal Bayesian network. We can devise the Bayesian network by quite simple steps. First, by the chain rule, the joint probability is \(P(x_1, ..., x_N) = \prod_j P(x_j | x_1, ..., x_{j-1})\). Then, suppose that \(X_j\) is only sensitive to some of the a small subset \(PA_j\) of those predecessors, we have \(P(x_j | x_1, ..., x_{j-1}) = P(x_j | pa_j)\). A minimal set \(PA_j\) satisfying this is called the Markovian parents of \(X_j\). It is shown by Pearl in 1988 that such \(PA_j\) is unique if P is strictly positive. Then, combine these two equations, we have \(P(x_1, ..., x_n) = \prod_i P(x_i | pa_i)\). Note that, although the chain rule is order specific, this equation is no longer order-specific. A distribution P is said to be Markov compatible with a DAG G, or P is Markov relative to G, if P can be factorized by this equation. The Markov compatibility is a necessary and sufficient condition for a DAG G to explain a body of data represented by P.

The action \(do(X=x)\) means, on the graph, to delete the ingoing links to X, and set the value of X to x, and nothing else. This results in a new distribution, \(P_x(v)\), rather than simply the original distribution conditioned on \(X=x\). We have some intuitive properties for this new intervention distribution:

• \(P(v_i | pa_i) = P_{pa_i}(v_i)\)
• \(P_{pa_i, s}(v_i) = P_{pa_i}(v_i)\) for all S that is disjoint of \(\{V_i, PA_i\}\).

To test whether a variable \(X_i\) has a causal influence on \(X_j\), we simply compute the marginal distribution of \(X_j\) under the action \(do(X_i=x_i)\), i.e. \(P_{x_i}(x_j)\) for all values \(x_i \in Val(X_i)\), and test whether the distribution is sensitive to \(x_i\).

A functional causal model is another representation of the causal model, consisting of a set of equations of the form \(x_i = f_i(pa_i, u_i)\), where \(pa_i\) means parents, i.e. the immediate causes of \(X_i\), \(U_i\) represents the errors, i.e. the disturbances, or correlations. This general form is nonlinear, nonparametric. The linear Structural Equation Models (SEMs) are more specific: \(x_i = \sum_{k\ne i} \alpha_{ik} x_k + u_i\).

Given a functional causal model, we can draw a graph, with arrows from each member of PA toward \(X_i\). The resulting graph is called a causal diagram. If the causal diagram is acyclic, then the model is called semi-Markovian. If, in addition to acyclicity, the error terms are mutually independent (i.e. each variable is independent of all its non-descendants, conditional on its parents, this is also called the Markovian assumption), the model is called Markovian.

The functional causal model can also represent the intervention, by alternating a subset of functions, and most of the time, this modification is simpler, e.g. change \(x_3 = f_3(x_1, u_3)\) to be \(x_3 = on\). The functional model's representation of interventions offers greater flexibility and generality than that of a stochastic model:

• the analysis of intervention can be extended to cyclic model
• The interventions involving the modification of equational parameters are more readily comprehended
• The analysis of causal effects in non-Markovian models (again cyclic) will be greatly simplified
• permits the analysis of context-specific actions and policies

Actually, the biggest shine part of functional models comes at the analysis of couterfactuals. The difficulty of counterfactual queries in stochastic models lies in that given no data, it is impossible to predict non-treatment case. But, the true insights of importance of counterfactual queries rely in "integrating substantive knowledge with statistical data so as to refine the former and interpret the latter". To see that we can answer counterfactual queries, an example is given by Pearl:

Most people would agree that President Clinton's place in history would be different had he not met Monica Lewinsky, but only a few would assert that his place in history would change had he not eaten breakfast yesterday

The stochastic causal models are insufficient for computing probabilities of counterfactuals. But, a functional causal model constitutes a mathematical object sufficient for the computation and definition of such probabilities. Generally to answer a counterfactual query, three steps are generalized to any causal models:

1. abduction: update the probability \(P(u)\) to obtain \(P(u|e)\)
2. action: do(X=x)
3. prediction: use the modified model to compute the probability of \(Y=y\)

The real reason why stochastic causal models are insufficient is the U variables do not appear explicitly in stochastic models, thus we cannot apply abduction step to update \(P(u)\) with evidence \(e\).

For two disjoint set X and Y, the causal effect of X on Y is defined as P(y | do(x)), a function from X to the space of probability distribution on Y. The causal effect identifiability is defined, such that the causal effect of X on Y is identifiable from a graph G if the quantity \(P(y | do(x))\) can be computed uniquely from any positive distribution of the observed variables. It is well known that, the causal effect is identifiable if X,Y and all parents of X are observed. Thus, for Markovian model, the causal effects are identifiable.

For semi-Markovian model, there exists some graphical test to decide whether a set Z of observed variables is sufficient for identifying \(P(y | do(x))\). The first one being the back-door criterion:

(Back-door) A set of variables Z satisfies the back-door criterion, relative to an ordered pair (\(X_i\), \(X_j\)) in DAG G if

1. no node in Z is descendant of \(X_i\), and
2. Z blocks every path between \(X_i\) and \(X_j\) that contains an arrow into \(X_i\)

For the disjoint sets X and Y, the set Z is said to satisfy the back-door criterion relative to (X,Y) if it satisfies the criterion for any pairs \((X_i,Y_i) \in (X,Y)\)

If Z satisfies back-door criterion relative to (X,Y), the causal effect of X on Y is identifiable, as \(P(y|do(x)) = \sum_z P(y | x, z) P(z)\).

The second one being the front-door criterion:

(Front-door) A set of variables Z satisfies the font-door criterion, relative to an ordered pair of variables (X,Y) if

1. Z intercepts all directed paths from X to Y
2. there is no back-door path from X to Z
3. all back-door paths from Z to Y are blocked by X

If Z satisfies the front-door criterion relative to (X,Y) and if \(P(x,z)>0\), then the causal effect of X on Y is identifiable as: \(P(y|do(x)) = \sum_z P(z | x) \sum_{x'} P(y|x',z)P(x')\).

Typically we use do-calculus to transform the intervention from one form to another, thus it can syntactically solve intervention queries. The do-calculus is a set of inference rules.

Some more graphical notation: \(G_{\bar{X}}\) is the graph obtained by deleting from G all arrows pointing to nodes in X, \(G_{\underline{x}}\) the graph obtained by deleting from G all arrows emerging from nodes in X. \(P(y | \hat{x}, z) = P(y, z | \hat{x}) / P(z | \hat{x})\) is the probability of Y=y given X is held constant at x, and that under this condition Z=z is observed.

• Insertion/deletion of observations: \(P(y | \hat{x}, z, w) = P(y | \hat{x}, w)\) if \((Y \bot Z | X, W)_{G_{\hat{x}}}\). This rule reaffirms d-separation.
• Action/observation exchange: \(P(y | \hat{x}, \hat{z}, w) = P(y | \hat{x}, z, w)\) if \((Y \bot Z | X, W)_{G_{\hat{x}\underline{Z}}}\). This rule provides a condition for an external intervention \(do(Z=z)\) to have the same effect on Y as the passive observation \(Z=z\)
• Insertion/deletion of actions: \(P(y|\hat{x}, \hat{z}, w) = P(y | \hat{x}, w)\) if \((Y \bot Z | X, W)_{G_{\hat{X}, \hat{Z(W)}}}\) where Z(W) is the set of Z-nodes that are not ancestors of any W-node in \(G_{\hat{X}}\). This rule introduces or deletes an external intervention \(do(Z=z)\)

A causal effect is identifiable if there exists a finite sequence of transformations in the rules to reduce it to a standard probability expressions involving observed quantities.

The \(P(y|do(x))\) models the total effect of X on Y. The direct effect of X on Y is given by \(P(y|do(x), do(s_{XY}))\), where \(S_{XY}\) is the set of all observed variables except X and Y. This effect is meant to quantify the effect that is not mediated by other variables in the model, or more accurately, the sensitivity of Y to change X while all other factors in the analysis are held fixed (to any value??).

If a third variable Z can influence both X and Y, then X and Y are said to be confounded, and Z is called a confounder of X and Y, or covariates, concomitants.

There is a Simpson's Paradox for confounders. Basically, it is that an event C increases the probability of E in a given population p, and at the same time, decreases the probability of E in every subpopulation of p. In equation, it says:

• \(P(E|C) > P(E|\not C)\): increase the probability
• \(P(E|C,F) < P(E| \not C, F)\): decrease the probability whenever condition on F
• \(P(E|C,\not F) < P(E | \not C, \not F)\), or condition on \(\not F\)

This essentially capture the misunderstanding between action and observation. A real world example from HackerNews: every bug you fix in your code increases your chances of shipping on time, but provides evidence that you won't. In this case, E is the event of deliver on time, C is the event of bug fix.

The problem is the first statement \(P(E|C) > P(E|\not C)\). C is not an evidence for E, but rather a positive causal factor for E. So proper statement should be written as \(P(E | do(C)) > P(E | do(\not C))\).

The paradox is resolved, and we result in a Sure-Thing Principle: an action C that increases the probability of an event E in each sub-population must also increase the probability of E in the population as a whole, provided that the action does not change the distribution of the sub-populations.

Finally, a formal causal definition of confounding comes that, X and Y are not confounded in causal model M iff \(P(y|do(x)) = P(y|x)\).

Two books for reference

• Causation, prediction, and search 2000-Book-Spirtes-Causation
• Causality 2009-Book-Pearl-Causality

The problem is to minimize a function f(x) of variables \(x_1,...,x_n\) over a region of feasible solutions S.

\[min_{x\in S} f(x)\]

The solutions state space S is formed as a rooted tree. The key to this algorithm is the efficient estimation of lower or upper bound. The problem is NP-hard.

f(x) is called objective function. a function g(x) is the lower bound, defines on S with the property that g(x) ≤ f(x) for all x ∈ S.

The algorithm:

1. use a heuristic, find a solution x_h. Store its value B ← f(x_h). B is the global best solution so far. If no solution found, init B to ∞
2. init a queue with the root ??
3. loop until the queue is empty
   1. take a node N off the queue
   2. if N represents a single candidate solution x (N is a leaf?) and f(x) < B, then B = f(x).
   3. Else, branch on N to produce new nodes \(N_1,...,N_i\). For each new node:
      1. if g(N_i) > B, do nothing.
      2. else store N_i onto the queue

Intuitively in natural language description, the problem is to minimize (or maximize) the objective function f(x) over \(x_1,..,x_n\). The feasible solution search state space is a tree. The initial best known value is B=f(x_h) or ∞ if no solution x_h found by heuristic. From the root, everytime branch into two or more branches. For those branches, compute the lower bound. If the lower bound is larger than current best, then do not need to go into these branch. Thus we can eliminate the computation of this branch.

The assumption is the lower (or upper) bound is efficient to compute. Every time branch may or may not overlap, as long as the optimal solution is inside at least one branch.

The problem is, from an initial node, find the least-cost path to one goal node (out of one or more possible goals).

\[f(n) = g(n) + h(n)\]

where n is current node.

• f(n) is the cost function.
• g(n) is the known cost of getting from initial node to n.
• h(n) is a heuristic esitimate of the cost to get from n to any goal node.
• h(n) must be admissible, i.e. it never overestimates the actual cost, i.e. it is always less then or equal to the actual cost.

The algorithm: from initial node, it maintains a priority queue of nodes. The lower \(f(n)\), the higher its priority. At each step, the node with lowest \(f(x)\) is removed, and \(f\) and \(g\) of its neighbors are updated. Add these neighbors into the queue. The algorithm terminates when one goal node has a lower \(f\) value than any node in the queue.

Intuitively, from the start point, try all neighbors, and remember both the actual cost from the initial node, and the estimate from this node to one goal. Repeat trying neighbors until reach goal nodes. Stop when the goal nodes has the lowest cost function value.

Concepts:

• plateau: a large set of neighbors having the same score

Searches

• first-ascent hill climbing: once it finds one that leads to a better score, it applies it without considering other directions

Overcome local maxima:

• basin flooding: keep track of all previous results, and consider any operator leading to result that has not been visited
• tabu search: keep a list or recent operators applied, and in each subsequent step, do not consider operators that reverse the effect of recently applied operators.
• data-perturbation: similar to random restarts. Perturb the search in a way that will allow it to overcome local obstacles and make progress toward the global maxima. Different from random restart where perturbation change the network, the data-perturbation changes the training data.