Method and apparatus for inferring logical dependencies between random processes

Certain aspects of the present disclosure relate to methods and apparatus for inferring causal relationship between random processes using a temporal learning algorithm. The temporal learning algorithm determines structure of a causal graph with a set of nodes. Input to the nodes may be binary time series (e.g., random processes). The output of the temporal learning algorithm may be a labeled directed graph in which the direction of the connection between each two node indicates causal direction and the strength of connectivity between the nodes indicates intensity of the causal influence. The temporal learning algorithm may iteratively update strength of connections between nodes to track variations in real time.

TECHNICAL FIELD

Certain aspects of the present disclosure generally relate to random processes and, more particularly, to a method and apparatus for inferring logical dependencies between random processes.

BACKGROUND

Humans can understand causality intuitively and apply their causal knowledge to everyday problems rather effortlessly. Computationally, causal inference can be a powerful tool for many practical applications. However, despite its long historical context, the process which causal inference is built upon has been relatively underdeveloped in the computational sense and is limited to philosophical discussion. In comparison to related topics in statistical learning, there is a deficiency in the understanding of how a causal model is built computationally. This gap needs to be closed as the accuracy and efficacy of causal inference is largely dependent on the causal model that it relies on. For example, it may be very straightforward to make inference about or diagnose a patient's symptoms given a causal model that defines the cause and effect relationship between diseases with symptoms, but almost always, such causal models so valuable for automatic patient diagnosis are handcrafted by human experts (e.g., doctors).

SUMMARY

Certain aspects of the present disclosure provide a method for inferring logical dependencies. The method generally includes identifying one or more nodes in a causal graph, wherein each node is connected to one or more other nodes with directional connections, and direction of a connection between a first node and a second node indicates a causal influence from the first node on the second node, and strength of connectivity of the connection between the first node and the second node indicates intensity of the causal influence, determining strength of connectivity of each connection in the causal graph using a temporal learning algorithm based on one or more binary time series inputs, wherein the temporal learning algorithm comprises a probabilistic model based on a Gradient descent algorithm, and inferring a first set of one or more nodes as causes of occurrence of the second node, wherein each node in the first set has a causal influence on the second node with strength of connectivity equal to or greater than a threshold.

Certain aspects of the present disclosure provide an apparatus for inferring logical dependencies. The apparatus generally includes means for identifying one or more nodes in a causal graph, wherein each node is connected to one or more other nodes with directional connections, and direction of a connection between a first node and a second node indicates a causal influence from the first node on the second node, and strength of connectivity of the connection between the first node and the second node indicates intensity of the causal influence, means for determining strength of connectivity of each connection in the causal graph using a temporal learning algorithm based on one or more binary time series inputs, wherein the temporal learning algorithm comprises a probabilistic model based on a Gradient descent algorithm, and means for inferring a first set of one or more nodes as causes of occurrence of the second node, wherein each node in the first set has a causal influence on the second node with strength of connectivity equal to or greater than a threshold.

Certain aspects provide a computer-program product for inferring logical dependencies, comprising a non-transitory computer-readable medium having instructions stored thereon, the instructions being executable by one or more processors. The instructions generally include instructions for identifying one or more nodes in a causal graph, wherein each node is connected to one or more other nodes with directional connections, and direction of a connection between a first node and a second node indicates a causal influence from the first node on the second node, and strength of connectivity of the connection between the first node and the second node indicates intensity of the causal influence, instructions for determining strength of connectivity of each connection in the causal graph using a temporal learning algorithm based on one or more binary time series inputs, wherein the temporal learning algorithm comprises a probabilistic model based on a Gradient descent algorithm, and instructions for inferring a first set of one or more nodes as causes of occurrence of the second node, wherein each node in the first set has a causal influence on the second node with strength of connectivity equal to or greater than a threshold.

Certain aspects of the present disclosure provide an apparatus for inferring logical dependencies. The apparatus generally includes at least one processor and a memory coupled to the at least one processor. The at least one processor configured to identify one or more nodes in a causal graph, wherein each node is connected to one or more other nodes with directional connections, and direction of a connection between a first node and a second node indicates a causal influence from the first node on the second node, and strength of connectivity of the connection between the first node and the second node indicates intensity of the causal influence, determine strength of connectivity of each connection in the causal graph using a temporal learning algorithm based on one or more binary time series inputs, wherein the temporal learning algorithm comprises a probabilistic model based on a Gradient descent algorithm, and infer a first set of one or more nodes as causes of occurrence of the second node, wherein each node in the first set has a causal influence on the second node with strength of connectivity equal to or greater than a threshold.

DETAILED DESCRIPTION

Causal inference is a powerful tool for many practical applications. However, despite its long historical context, the process which causal inference is built upon is relatively underdeveloped computationally which is mostly limited to philosophical discussion. Accuracy and efficacy of causal inference is largely dependent on the causal model that it relies on. Certain aspects of the present disclosure present methods for modeling causal inference.

Causal understanding of events and objects are crucial in all scientific settings so it will come as no surprise that a lot of philosophic discourse has been collected on this subject. In an abstract and philosophic sense, causality can only be determined by counter-factual interventions. In other words, the causal element that connects two events X and Y (e.g., smoking and lung cancer) can only be determined if one could perform the following steps. Upon observing Y in the present (e.g., somebody is suffering from lung cancer), one may go back in time and change event X (e.g., prevent smoking). Everything else should remain unchanged. A new outcome Z is observed at the present time. If the new outcome Z is similar to Y, then X is not a cause for Y. If Z is different from Y, then X is considered to be a cause for Y. For example, if the patient did not smoke and he is still suffering from lung cancer, then smoking is not considered to be a cause for lung cancer. On the other hand, if the patient did not smoke in the past and he is no longer suffering from lung cancer at the counterfactual present, one may determine that smoking directly causes lung cancer. It should be noted that it would be a luxury to be able to conduct these perfectly controlled experiments in real life. In short, controlled intervention in the system is the best way to determine causal relations between things.

Inferring causality without intervention, purely based on observation may be possible depending on the definition of causality. Several approaches exist in the art for causal inference. The most relevant prior art is summarized here. For example, a causal inference method may use contingency data to output acyclic graphs. This method works best when the available data is in the form of a contingency table.

Granger causality (GC) performs causal inference with real-valued data that are expressed over time. Granger causality is determined by fitting a linear model between the input and output variables. The principle of causality that was first proposed by Norbert Wiener, but popularized by Clive Granger says that: Given two random processes X and Y, the random process X is considered causal to Y if the amount of uncertainty in predicting y(t) at time t given all of the past values of Y and X is less than that in predicting y(t) given only the past history of Y itself. Several extensions of the GC can be used to handle temporal data that takes on real values. In addition, a conditional GC approach may deal with problems involving multiple variables.

An information-theoretic generalization of Granger causality may use general temporal data and can handle general processes. However, this method is computationally complex and requires fitting models of high complexity. A very recent causal inference approach uses temporal logic and is based on a simple idea of what it means for a cause to create an effect. However, this approach does not yield strength of cause-effect relationships, and therefore does not have predictive ability.

Conventional Classification of Causes

A given cause can influence an effect in one of several ways, such as a sufficient cause, a necessary cause or a preventive cause. A cause is sufficient if the presence of an event C is sufficient to cause the event E. The sufficient cause may be captured in a logical relationship, as follows:

A cause is necessary if the presence of the event C is necessary for the effect E to occur. The necessary cause may be captured in a logical relationship, as follows:

A cause is preventive if the presence of the event C prevents the occurrence of the event E. The preventive cause may be captured in a logical relationship, as follows:

The relationships in the above statements are the standard logical relationships. These relationships may also be formulated probabilistically. For example, the event C can cause the event E with a probability a (e.g., 0.6). Then, the event C may be called a sufficient cause with strength of a for the event E.

Certain aspects of the present disclosure propose a method for inferring logical dependencies (e.g., causal relationship) between random processes using a temporal learning algorithm. The temporal learning algorithm determines structure of a causal graph with a set of nodes. Input to the nodes may be binary time series (e.g., random processes). The output of the temporal learning algorithm may be a labeled directed graph in which the direction of the connection between two nodes (e.g., A and B) indicates causal direction and the strength of connectivity between the nodes indicates intensity of the causal influence. The temporal learning algorithm may iteratively update strength of connections between nodes to track variations in real time.

Temporal Causal Learning

Several challenges may be addressed in producing a causal graph. For example, if an event A causes both events B and C as shown inFIG. 1A, a pair-wise analysis between the nodes may wrongly result in a relationship between the events B and C (e.g., B causes C or vice-versa). This ambiguity should be avoided in modeling causality between events.

FIGS. 1A and 1Billustrate two example causal graphs, in accordance with certain aspects of the present disclosure.FIG. 1Aillustrates a causal graph in which the event A causes both events B and C.FIG. 1Billustrates another causal graph in which the event A causes the event B, and the event B causes the event C. For the graph shown inFIG. 1B, upon considering only the events A and C, it is possible to wrongly conclude that there is an arrow between events A and C. In addition, a node may have spontaneous activity which is not due to any external variable in the system. This may cause the algorithm to infer wrong edges between other events (e.g., graph nodes) and the event A.

It should also be noted that connectivity of the graph may initially be unknown and is learned as evidence becomes available. This uncertainty can add tremendous computational complexity to the problem. In addition, when several causes have potential impact on one node, these causes may interact in a non-trivial manner.

In order to solve the causal inference problem, the following assumptions may be made in the temporal learning algorithm: i) An event can influence another event only in the future. ii) The influence of an event on the occurrence of other events occurs within a time scale, which is known a priori. iii) If multiple causes influence an effect, the causes interact in a pre-specified manner (e.g., OR, AND, or NOT relationship) to produce the effect.

For certain aspects, in order to infer causality, a network of cause-effect relationships may be used such that the edges are labeled according to the strength of causality. The incoming edges may influence the state of a node using a certain probabilistic model. The problem of causality inference may thus be reduced to a problem of reverse engineering the network parameters given the data (also called inference).

For certain aspects, probabilistic machinery may be used to deal with the inference problem, by writing out the Logarithmic Likelihood (called log-likelihood) and using a gradient descent algorithm to update the parameters in such a way that the log-likelihood of the data is increased. A set of all nodes that wield non-trivial influence on a given node in the reverse-engineered model may be inferred as causes of occurrence of the given node.

The proposed temporal learning algorithm has a low complexity, can be updated iteratively, can track changes in causality, may work with latent variables, and can infer causality for a general family of functions. A latent variable (as opposed to an observable variable), is a variable that is not directly observed but is rather inferred (through a mathematical model) from other variables that are observed (or directly measured). These advantages may give the proposed algorithm a significant advantage compared to the existing algorithms in the literature for causal learning.

FIG. 2illustrates example operations200for inferring logical dependencies, in accordance with certain aspects of the present disclosure. At202, one or more nodes may be identified in a causal graph. Each node may be connected to one or more other nodes with directional connections. At204, strength of connectivity of each connection in the graph may be determined using a temporal learning algorithm based on one or more binary time series inputs. Direction of a connection between a first node and a second node may indicate a causal influence from the first node on the second node, and strength of connectivity of the connection between the first node and the second node may indicate intensity of the causal influence. At206, a first set of one or more nodes may be inferred as causes of occurrence of the second node. Each node in the first set may have a causal influence on the second node with strength of connectivity equal to or greater than a threshold.

Modeling the Causal Inference

First, a single effect E=Cn+1may be considered. Multiple potential causes C, may affect the effect E. Each cause may not only influence the effect in the immediate time instant following the event, but it can also influence the effect in a time window after occurrence of the cause. This characteristic may be captured explicitly by an exponential decay function.

A process Ai(t), i=1, . . . , n may be defined as follows:
Ai(t)=1 if Cioccurred at timet, for alli, for allt.

From the process Ai(t) a process fi(t) may be obtained which incorporates the persistence of the process Ciin producing the output at time t (e.g., temporal persistence). One way of obtaining fi(t) from Ai(t) may be prolonging every effect for a certain amount of time with certain intensity. As an example, the temporal persistence may be modeled using a standard function g(.) that is convolved with Ai(t,. An example of g(t) may be an exponential decay function with time constant τ as shown inFIG. 3.

FIG. 3illustrates an example effect of an event, in accordance with certain aspects of the present disclosure. As illustrated, when the event occurs, it can affect other events for a certain time as shown with an exponential decay function. Effect of the event may decrease exponentially as time passes.

In general, among multiple potential causes for an effect E, some of the causes are true causes. A true cause should be able to produce the effect, irrespective of the absence or presence of other causes. For certain aspects, a true cause may be modeled as follows:
E(t)=β1A1(t)|β2A2(t)
where βiε{0,1}. If βi=1, Aihas an impact on E. Otherwise, Aidoes not have an impact on E.

To model the fact that Aimay not always cause E, noise may be added to the system, which results in a noisy OR model, as follows:
E(t)=R(β1Ai(t))|R(β2A2(t))
where βiis the probability that Aiinfluences E and R(p) indicates a spiking function that produces a spike with probability p at the time it happens. The temporal persistence may be included into the model by convolving Ai(t) with g(t), as follows:
E(t)=R(β1f1(t))|R(β2f2(t)),
fi(t)=g(t)*Ai(t)
where g(t) can be an exponential decay function, and * represents a convolve operation.

In the above model, in the absence of any of the causes, the effect cannot occur. Since all the possible causes are not modeled, there may still be a chance that the effect can occur in the absence of any of the known or modeled causes. This can be modeled by including a spontaneous occurrence probability R(γ) in the model, as follows:
E(t)=R(β1f1(t))|R(β2f2(t))|R(γ)

The spontaneous occurrence probability R(γ) may be treated as unknown. As an example, the spontaneous occurrence probability may be modeled as a third cause with f3=1, and β3=γ, as follows:
E(t)=R(β1f1(t))|R(β2f2(t))|R(β3f3(t))
The problem of causal modeling is now reduced to the following problem: Given the processes Ai(t), what are the values of βi, i=1, . . . . , 3.
Solution

In order to find parameters of the causal model, certain aspects may assume initial values for βiall i (e.g., one possible starting value is zero). For certain aspects, instead of encoding βiin the algorithm, another parameter bimay be calculated. The relationship between βiand bimay be defined as follows:

βi=exp⁡(bi)1+exp⁡(bi)
where exp(.) represents exponential function. Mapping between βiand biensures that when biranges from −∞ to +∞, βiwill range from 0 to 1. Therefore, the algorithm can operate without any constraint on bi. At any time t,

An example causal learning problem with two potential causes influencing the effect E is considered.FIGS. 4A-4Cillustrate example simulation results400A,400B and400C with different initial values. As shown inFIG. 4A, the solid curves402,404and406show the learnt value of the parameters β1, β2and λ, and the dotted curves410,408and412show the actual values of these parameters, respectively. It can be seen that the estimated values converge to the actual values. Another example with different (random) initial condition is shown inFIG. 4B. It can be seen that in bothFIGS. 4A and 4B, the estimated values converge to the actual values with different initial values for β1, β2and λ. TheFIG. 4Cshows an example where the value of β1is set to zero.

Sparsity in the Algorithm:

In several situations, the algorithm may need to return as few non-zero elements as possible. This can be modeled by setting up the maximum likelihood problem with a penalty for sparsity. For example, the sparsity constraint may be modeled as follows:
MaxP(data/β)−μ|β|0
where Max P(data/β) represents the maximum likelihood of the data given the parameter β, and |.|0shows the L0norm. The term |β|0captures the number of non-zero βis, and μ is a constant for the penalty. For certain aspects, the L0norm in the above equation may be relaxed and be replaced with the L1norm, as shown in the following equation.
MaxP(data/β)−μ|β|1

By writing out the maximum likelihood equations for the temporal learning problem, a modified gradient descent algorithm may be obtained, as follows:

For certain aspects, parameters in the above equations may be updated at every time step, or they may be updated once every few time steps (e.g., once in a block of time T). The convergence time may be shorter if parameters are updated once in a block of time T. In addition, updating the parameters is costly in terms of hardware implementation. Therefore, the value of the parameters may only be updated once in a block of time T to reduce complexity/cost. The update that is applied after time T may be equal to the sum of the updates generated at every time step by the algorithm, scaled reasonably as preferred.

Learning Causality Graphs in a Network of Cause-Effect Relationships

A set of n random processes that interact with each other may be considered. A network (as illustrated inFIG. 5) with certain structure of causal influence may be assumed in which the evolution of node i can depend only on nodes in C(i). Each process A may be generated according to the following rule:
Ai(t)=R(βj1fj1(t))|R(βj2fj2(t))| . . . |R(βjkfjk(t))
where C(i)={j1, j2, . . . , jk}

FIGS. 5A and 5Billustrate example networks500of cause-effect relationships, in accordance with certain aspects of the present disclosure. Structure of the network and its parameters may be inferred using the causal learning algorithm. In each iteration of the algorithm, structure of the network and its parameters may be estimated using the models described above. At first, it may be assumed that the network is a fully connected graph as shown inFIG. 5B.

At each node j, strength of each connection between node j and other nodes (e.g., β1j, β2j, . . . , βnjmay be estimated. The causal learning algorithm may be highly distributed and at the end of the algorithm, all of the n2parameters of the network can be estimated. If the estimated value of a parameter is less than or equal to a threshold, the parameter can be considered to be equal to zero. Therefore, a connection having strength of connectivity equal to zero (or smaller than the threshold) may be deleted. An example graph that is output of the causal learning algorithm is shown inFIG. 5A. In this graph only nonzero connections between nodes are shown.

FIG. 6illustrates an example table with original and estimated (inferred) values for the network inFIG. 5A, in accordance with certain aspects of the present disclosure. It can be seen that the values that are inferred using the temporal learning algorithm are very close to the original (actual) values of the network, with less than 10% error.

The temporal noisy OR model as described above is an instance of sufficient causation. The causal learning algorithm may be generalized to cover other types of causes such as necessary and preventive causation.

Preventive Causation

A preventive cause can effectively ensure that the outcome does not take place. The preventive cause may be modeled by the following logic: CĒ. Similar to the in the temporal noisy OR case, the event C can prevent the event E with a certain strength γ.

The mathematical model for multiple preventive causes may be written as follows:
E(t)=R(λ)R(1−γ1f1(t))R(1−γ2f2(t))
in which if γ1=1, f1Ē. Also, if γ1=0, there may not be any correlation between f1and E. Spontaneous excitation λ is also captured in the above formula. It should be noted that a non-temporal version of this problem is called the Noisy-And-Not in the literature.
Learning Rule for Preventive Causation:

The stochastic gradient descent on maximum likelihood estimate for the Noisy And Not may be derived. As described above, instead of encoding γiin the algorithm, gimay be encoded. The relationship between γiand gimay be written as follows:

This remapping ensures that as giranges from −∞ to +∞, γiwill range from 0 to 1, thus the algorithm can operate without any constraint on gi. The parameter μ is used to adjust the sparsity of the solution. Increasing μ tends to increase the sparsity of the solution. At any time t,

The right hand side of the above equations may be evaluated using the estimates of γiin the previous step, which are obtained using the previous estimate of gi. Δ is a learning parameter, which can be adjusted prior to learning, γTis the total preventive effect on E and γ\iis the total preventive effect on E other than node i, as follows:
1−γT=Πj(1−γjfj(t))
1−γ\i=Πj≠i(1−γjfj(t))
Necessary Causation

A cause is said to be a necessary cause, if absence of the cause implies absence of the effect. In other words, the cause is perceived to be necessary to create the effect ifCĒ. A necessary cause may operate on a process with strength α (e.g.,

The mathematical model for multiple necessary causes may be written as follows:
E(t)=R(λ)R(1−α1f1(t))R(1−α2f2(t))
in which, if α1=1. In addition, if α1=0, there is no correlation between f1and E. the parameter λ models the spontaneous excitation. It should be noted that a non-temporal version of the above equation is called the Noisy-And in the literature.
Learning Rule for Necessary Causation:

The stochastic gradient descent on maximum likelihood estimate for the Noisy And model may be derived. Similar to other cases, instead of encoding αiin the algorithm, αimay be encoded. The relationship between αiand αimay be written as follows:

αi⁢=exp⁡(ai)1+exp⁡(ai)
The remapping ensures that as airanges from −∞ to +∞, αiwill range from 0 to 1, thus the algorithm can operate without any constraints on ai. The parameter μ is used to adjust the sparsity of the solution. Increasing μ tends to increase the sparsity of the solution.

At any time t,

The right hand side is evaluated using the estimates of αiin the previous step, which are obtained using the previous estimates of ai. Δ may represent a learning parameter, which can be adjusted prior to learning. αTmay represent the total effect of necessary causes, and α\imay represent the total effect of necessary causes on the event E in the absence of αi, as follows:
1−αT=Πj(1−αjfj(t))
1−α\i=Πj≠i(1−αjfj(t))
Combinations of Various Types of Causation:

In general, a model may include a mixture of necessary and sufficient causes. For example, a necessary cause C1and a sufficient cause C2may jointly influence an effect. Such a relationship may cause conflict. For example, when the necessary cause is absent and the sufficient cause is present (e.g., C1=0, and C2=1), the output is indeterminate. To break the conflict, a priority may be set for the causes in case of a conflict. Thus, an OR logic table is consistent when sufficient causation is given priority, and an AND logic table is consistent when necessary causation is given priority.

FIG. 7illustrates an example table showing example combinations of necessary and sufficient causes, in accordance with certain aspects of the present disclosure. As illustrated in the table, for the case that a necessary cause C1is equal to zero and a sufficient cause C2is equal to one, if the necessary cause is given priority, the effect E would be equal to zero. If the sufficient cause is given priority, the effect E would be equal to one.

The inference algorithms may have two different types of outputs depending on which cause is given priority, The output for the case when the necessary cause is given preference may differ from the output for the case when sufficient cause is given preference. In both of these cases, a preventive cause (if any) may be given foremost preference.

The type of each edge between nodes may be unknown a priori. This may be captured in the model by replacing each edge with three possible edges, one for each type of causation. Thus for any edge i, the variables αi, βiand γimay be estimated for the necessary, sufficient and preventive causation, respectively. The following general model may be used to estimate all the parameters:
E(t)=[R(β1f1(t))| . . . |R(βnfn(t))]R(1−α1f1(t)) . . .R(1−αnfn(t))R(1−γ1f1(t)) . . .R(1−γnfn(t))

FIG. 8illustrates an example network with sufficient and necessary causes, in accordance with certain aspects of the present disclosure. For the effect E 802, each cause may be either sufficient (e.g., 804, 806, 808) or necessary (e.g., 810, 812, 814).

Inference Algorithm

For certain aspects, when the causal learning algorithm is performed on the above model, the variables corresponding to each type of causation may be compared to a threshold. If none of the three variables αi, βiand γicrosses the threshold (e.g., is higher than the threshold), i may not be a cause for the event E. If only one of the variables αi, βi, and γicrosses the threshold, then i may be declared as a cause of the corresponding type for the event E. If more than one of these variables crosses the threshold, the largest variable may be declared as the type of the cause. Here again ai, biand giare used in the iterative update instead of αi, βiand γi.

The right hand sides of the above equations may be evaluated using the previous estimates of ai, biand gi, from which the estimates of αi, βiand γiare obtained. The various quantities used in the updates may be defined, as follows:
1−αT=Πj(1−αjfj(t))
1−α\i=Πj≠i(1−αjfj(t))
βT=β1f1(t)|β2f2(t)| . . . |βnfn(t)
β\i=β1f1(t)|β2f2(t)| . . . |βi−1fi−1(t)|βi+1fi+1(t)| . . . |βnfn(t)
1−γT=Πj(1−γjfj(t))
1−γ\i=Πj≠i(1−γjfj(t))
p=(1−αT)βT(1−γT)

For certain aspects, the right hand side of the update of a certain type of causation may be forced to include no knowledge of the other types of causation from the same edge. For example, the update rule of aimay not depend on the values of biand gi. This type of knowledge constraint can be enforced on all or some of the causes in the network that includes varying combinations of different types of causes.

FIG. 9illustrates an example network with sufficient, necessary or preventive causes, in accordance with certain aspects of the present disclosure. In the network, arrows902and904denote preventive causes, arrows906and908denote sufficient causes, and arrows910and912denote necessary causes. The goal is to recover this network given the data. Simulation results show that the proposed temporal learning algorithm is able to recover all the parameters within 10% error.

Causal Inference Based on Neural Networks:

A standard artificial neural network (as shown inFIG. 11) may be considered where the state of each node is determined by the state of its incoming edges, this can be modeled as follows:

Ai⁡(t+1)=ψt⁡(∑j⁢wij⁢Aj⁡(t)-τi)
where Ai(t+1) denotes the state of node i (e.g., state of the neuron i). ψtmay represent a threshold function, as follows:
ψt(x)=1; x>0
ψt(x)=0; x≦0

It can be assumed that wij=0 for all edges other than the incoming edges. The variable τimay act as a threshold. Alternately, a node 0 may be created for which activity is ever-present input with w0j=−τiand A0(t)=1, which may result in more consistent notation, as follows:

The output at a given time in the above model may only depend on the inputs (causes consistent with our viewpoint) at any given time. With the persistence of A using f, the above model may be modified to include persistent of an input, as follows:

The above model may have two issues. First issue is how to model noise in the system. The second issue is that since ψtis a discontinuous function, it is not possible to derive gradient descent algorithms that can infer the values of wij.

For certain aspects, a probabilistic model may be used to overcome the above issues, as follows,:

Ai⁡(t+1)=R⁢{ψ⁡(∑j⁢wij⁢Aj⁡(t))}
where ψ is a continuous function approximating the threshold function ψt. For certain aspects, the function ψ can be implemented as a sigmoid function ψ(x), as follows:

FIG. 10illustrates an example sigmoid function, in accordance with certain aspects of the present disclosure. The sigmoid function has the following property:

ψ′⁡(x)ψ⁡(x)=1-ψ⁡(x)
Learning Rule

The learning rule for the causal inference based on neural networks may be written as follows: For each j,

If⁢⁢Aj⁡(t)=1,wij←wij+Δ⁡[ψ′⁡(∑j⁢wij⁢fj⁡(t))ψ⁡(∑j⁢wij⁢fj⁡(t))]⁢fi⁡(t)-sign⁡(wij)⁢μIf⁢⁢Aj⁡(t)=0,wij←wij-Δ⁡[ψ′⁡(∑j⁢wij⁢fj⁡(t))1-ψ⁡(∑j⁢wij⁢fj⁡(t))]⁢fi⁡(t)-sign⁡(wij)⁢μ
where sign(wij) represents sign of the wij, and ψ′(x) denotes derivative of ψ with respect to x. The term involving μ promotes sparsity.
Sparsity in the Algorithm:

In several situations, it may be preferred for the algorithm to return as few non-zero elements as possible. This can be done by setting up the maximum likelihood problem with a penalty for sparsity, as follows:
MaxP(data/w)−μ|w|0

The |w|0norm captures the total number of non-zero wij. For certain aspects, the l0norm may be replaced with the l1norm, as follows:
MaxP(data/w)−μ|w|1

The penalty term in this modified optimization introduces the term −sign(wij)μ into the algorithm so that there is a tendency for the value of wijto stay close to zero.

For the special choice of sigmoid function, the following update rule may be used:
If Aj(t)=1, wij←wij+Δ└1−ψ(Σjwijfj(t)┘fi(t)−sign(wij)μ
If Aj(t)=0, wij←wij−Δ└1−ψ(Σjwijfj(t)┘fi(t)−sign(wij)μ

At the end of the algorithm, values of the wijbe compared to a threshold to select the non-zero values which have influence on node j. These are declared to be the causal influences of node j. In addition, if the inferred value is positive, then it can be inferred that event j causes i to occur. If the inferred value is negative, it can be inferred that event j prevents i from occurring.

An Example Neural System

FIG. 11illustrates an example neural system1100with multiple levels of neurons in accordance with certain aspects of the present disclosure. The neural system1100may comprise a level of neurons1102connected to another level of neurons1106though a network of synaptic connections1104. For simplicity, only two levels of neurons are illustrated inFIG. 11, although fewer or more levels of neurons may exist in a typical neural system.

As illustrated inFIG. 11, each neuron in the level1102may receive an input signal118that may be generated by a plurality of neurons of a previous level (not shown inFIG. 11). The signal1108may represent an input current of the level1102neuron. This current may be accumulated on the neuron membrane to charge a membrane potential. When the membrane potential reaches its threshold value, the neuron may fire and generate an output spike to be transferred to the next level of neurons (e.g., the level1106).

The transfer of spikes from one level of neurons to another may be achieved through the network of synaptic connections (or simply “synapses”)1104, as illustrated inFIG. 11. The synapses1104may receive output signals (i.e., spikes) from the level1102neurons, scale those signals according to adjustable synaptic weights w1(i,i+1), . . . , wP(i,i+1)(where P is a total number of synaptic connections between the neurons of levels1102and1106), and combine the scaled signals as an input signal of each neuron in the level1106. Further, each of the synapses1104may be associated with a delay, i.e., a time for which an output spike of a neuron of level i reaches a soma of neuron of level i+1.

A neuron in the level1106may generate output spikes1110based on a corresponding combined input signal originating from one or more neurons of the level1102. The output spikes1110may be then transferred to another level of neurons using another network of synaptic connections (not shown inFIG. 11).

The neural system1100may be emulated by an electrical circuit and utilized in a large range of applications, such as image and pattern recognition, machine learning, motor control, and alike. Each neuron in the neural system1100may be implemented as a neuron circuit or a neural processor. The neuron membrane charged to the threshold value initiating the output spike may be implemented, for example, as a capacitor that integrates an electrical current flowing through it.

In an aspect, the capacitor may be eliminated as the electrical current integrating device of the neuron circuit, and a smaller memristor element may be used in its place. This approach may be applied in neuron circuits, as well as in various other applications where bulky capacitors are utilized as electrical current integrators. In addition, each of the synapses1104may be implemented based on a memristor element, wherein synaptic weight changes may relate to changes of the memristor resistance. With nanometer feature-sized memristors, the area of neuron circuit and synapses may be substantially reduced, which may make implementation of a very large-scale neural system hardware implementation practical.

The various operations of methods described above may be performed by any suitable means capable of performing the corresponding functions. The means may include various hardware and/or software component(s) and/or module(s), including, but not limited to a circuit, an application specific integrated circuit (ASIC), or processor. Generally, where there are operations illustrated in Figures, those operations may have corresponding counterpart means-plus-function components with similar numbering. For example, operations200illustrated inFIG. 2correspond to components200A illustrated inFIG. 2A.