EXPLAINING POINT PROCESSES BY LEARNING INTERPRETABLE TEMPORAL LOGIC RULES
Year: 2021

Abstract:
We propose a principled method to learn a set of human-readable logic rules to explain temporal point processes. We assume that the generative mechanisms underlying the temporal point processes are governed by a set of first-order temporal logic rules, as a compact representation of domain knowledge. Our method formulates the rule discovery process from noisy event data as a maximum likelihood problem, and designs an efficient and tractable branch-and-price algorithm to progressively search for new rules and expand existing rules. The proposed algorithm alternates between the rule generation stage and the rule evaluation stage, and uncovers the most important collection of logic rules within a fixed time limit for both synthetic and real event data. In a real healthcare application, we also had human experts (i.e., doctors) verify the learned temporal logic rules and provide further improvements. These expert-revised interpretable rules lead to a point process model which outperforms previous state-of-the-arts for symptom prediction, both in their occurrence times and types.

heading: 1 INTRODUCTION
text: Event sequences with irregular time intervals are ubiquitous. The inter-event times usually convey rich information regarding the underlying dynamics such as disease progression (Liu et al., 2015). It is useful to understand events’ generating mechanisms, as well as the occurrence reason and time. In systems where domain knowledge is rich, events generating can usually be governed by a few first-order temporal logic rules, as a compact representation of knowledge. In healthcare, the knowledge “if a sudden fall in blood pressure is observed, vasopressors are required to be applied to patients immediately; and then the blood pressure may return to normal afterwards" may explain why the event “blood pressure returns to normal from the abnormally low level " is observed after the event “vasopressors are used". This domain knowledge can be summarized as a collection of logic rules with temporal relation constraints, such as “A happens before B”, “If A happens, and after 5 mins, B can happen”, and “If A and B happen simultaneously, then at the same time C can happen”. However, temporal logic alone is not an ideal temporal model, as hard constraints will be too strict to model the recurrent noisy event data. Meanwhile, a large amount of literature has been devoted to modeling event data, among which temporal point process (TPP) models provide an elegant framework without the need to discretize the time horizon into bins and to compute the count of events within each bin. TPP models treat the interevent time as random variables and directly model the intensity function (i.e., occurrence rate) of the events. However, most TPP models lack interpretability, and they can not represent domain knowledge in a human-readable form. Recently, Li et al. (2020) proposed a unified framework to marry point process intensity functions with temporal logic rules. This method employs a set of pre-specified temporal logic rules to design the intensity functions to incorporate domain knowledge. The resulting so-called temporal logic point process models are inherently interpretable and expressive. Using such logic-informed intensity functions, the model can capture nonlinear dependencies, interactions, and various temporal relations between events. It was also shown that, by specifying one or two simple temporal logic rules, many existing parametric models, e.g. the Hawkes process (i.e. self-exciting processes) (Hawkes, 1971a) and the self-correcting process (Isham & Westcott, 1979) are special cases of the proposed temporal logic point process. However, in (Li et al., 2020) the temporal logic rules are required to be specified by the model builder, but they may not be known beforehand. Models constructed in such a way may suffer from model misspecification when the pre-specified logic rules are incorrect or missing.
Can we automatically discover the temporal logic rules governing the event dy-
namics based on historical event data alone?
This is a challenging problem since the space of possible temporal logic formulas is huge, comprising of a combination of a large number of discrete logic variables and all kinds of temporal relations. Previous inductive logic programming approaches focused mostly on deriving the relations between discrete logic variables, but have largely ignored the crucial temporal information (Dash et al., 2018; Wei et al., 2019). A generalization of these methods by further considering temporal relations in logic variables is largely missing and is in pressing needs due to the increasing availability of event data. To address the aforementioned challenges, we propose the TEmporal Logic rule LearnER (TELLER) algorithm for learning temporal logic rules from event sequences. TELLER is inspired by the branch-and-price algorithm (Barnhart et al., 1998), a column generation (CG) algorithm for linear programming (LP) problems where the number of variables is too large to be considered explicitly. In the CG algorithm framework, the original LP problem is solved via two alternating procedures: the master problem and the subproblem, where the master problem is the original problem with only a subset of variables being considered and the subproblem is a new problem created to identify a new variable to be added. Similarly, TELLER also alternates between solving a master problem and a subproblem, where the master problem aims to evaluate the current rules by maximizing the likelihood and reweighting these rules as in (Li et al., 2020), and the subproblem is to search and construct a new temporal logic rule (by extending a current rule or adding a new short rule). It repeats until the likelihood can no longer be improved by adding new candidate rules. In this way, TELLER searches through the vast space of potential temporal logic rules and learns the importance weights of the discovered rules to hedge against noise in the data. Fig. 1 shows the flow.
Specifically, TELLER is computationally efficient and with guarantees. It includes the candidate rules one by one in a tractable and progressive fashion, and is able to find a near-optimal set of rules. The hypothesized logic rules are in disjunctive normal form (DNF, OR-of-ANDs) with temporal relation constraints, and can be of various lengths. Given the temporal logic point process modeling framework, we show that the resulting objective function, i.e. likelihood, is convex, which guarantees optimal performance for our search algorithm. A set of logic rules and their importance weights are jointly learned by maximizing the likelihood. The
most important collection of logic rules are guaranteed to be discovered within a fixed time limit. The uncovered rules by TELLER will not only shed light on when and what events would happen, but also why some events would happen at a specific time. Our method facilitates the human-readable knowledge exchange between experts and point process models. On one hand, the mined temporal logic rules may supplement or refine the existing knowledge; on the other hand, human experts can easily provide feedback to modify the learned models via logic rules, as a way to add the safety of using these models in high-stake tasks like healthcare and autonomous driving. In our real experiment related to medicine, TELLER is used to learn the explanatory temporal logic rules regarding the choice and arrangement of drugs in improving patients’ health status. Doctors were asked to justify the rules and they confirmed that these discovered logic rules are consistent with the pathogenesis and have captured the most important factors in affecting patients’ health status.

heading: 2 BACKGROUND

heading: 2.1 FIRST-ORDER TEMPORAL LOGIC RULES
text: First-order temporal logic is a form of symbolized reasoning in which each statement is a composition of temporal predicates and their relations. We formally define the interval-based temporal logic below. This type of temporal logic rule is often suitable for reasoning about events with duration, which are better modeled if the underlying temporal ontology uses time intervals. It fits well with the temporal point process models for event sequences, where the time intervals of events are explicitly modeled. Refer to (Goranko & Rumberg, 2021) for a comprehensive survey of various temporal logic models. Temporal predicate. First define a set of static predicates X = {X1, . . . , Xd}, where each static predicate Xi(c) is a logic random variable that defines the property or relation of entities, such as Smokes(c) or Friend(c, c0), where c and c0 are the entities. By adding a temporal dimension to predicate Xi, we obtain a temporal predicate {Xi(c, t)}t 0, which can be viewed as a continuous-time stochastic process. Given observations, each temporal predicate will be grounded as a list of ordered
0-1 events, which take True (1) and False (0) in an alternating way with the state transition times recorded. For example, a temporal predicate {NormalBloodPressure(c, t)}t 0, where entity c is referring to the patient, will take value 1 or 0 at any time t to indicate whether the patient’s blood pressure is normal or not, with stochastic state transition time (see Fig. 2).
To simplify the notation, we will temporally drop the dependency of predicates on entities. We will write X(c, t) as X(t) instead and the grounded temporal predicate as {x(t)}t 0.

heading: 2.2 TEMPORAL LOGIC POINT PROCESS
text: Temporal Point Process (TPP) provides an elegant tool to capture the dynamics of the event sequences. It is characterized by conditional intensity function, denoted by (t|Ht), where history Ht is the knowledge of times of all events. By definition, we have (t|Ht)dt = E[N([t, t+dt])|Ht], where N([t, t+dt]) denotes the number of points falling in an interval [t, t + dt]. Here we aim to use TPP to model these 0-1 events and use the intensity function to capture the 0-1 transition rate. Temporal relation. We will use the interval-based temporal relations originally introduced in Allen’s seminal paper (Allen, 1990) to describe the temporal relations that can exist in any two temporal predicates. There are 13 types of possible temporal re-
lations, including Before, Meets, Overlap and so on (see Appendix B for a comprehensive illustration), and we denote this set by R. To evaluate these temporal relations, we need to define the time interval using the state transit in/out times. For example, at time tA, the temporal predicate {XA(t)}t 0 takes state xA = 0 or 1, we define ItA = (tA1 , tA2 ], tA 2 (tA1 , tA2 ], as a time interval where tA1 is the transition time that this predicate enters the state xA and tA2 is the transition time that this predicate leaves the state xA. For any two temporal predicates, given their time intervals, ItA = (tA1 , tA2 ] and ItB = (tB1 , tB2 ], their temporal relation function, denoted as RA typeB(ItA , ItB ) 2 R, is a logic function defined over the time intervals and can be evaluated by plugging in the specific time intervals. For example, RA BeforeB = {tB1 > tA2} and RA EqualsB = {tA1 = tB1} {tA2 = tB2}. All these definitions of temporal relations are also given in Appendix B. Temporal logic formula. A first-order temporal logic rule f is defined as logical connectives of temporal predicates and their temporal relations. The generic form is:
f : (¬)Y (ty) ^
Xu2X+f Xu(tu) ^ Xv2X f ¬Xv(tv) ^ Xu,Xv2Xf Ru type v(Itu , Itv ) (1)
where each temporal predicate and the temporal relations can be evaluated at ty, tu and tv along with their corresponding intervals Itu and Itv . In the above formula, negation (¬) means the head predicate Y can take a negative sign; Xf = X+f [ X
f is the set of predicates defined in f , where X
f is the set of predicates as negation in the formula f , and X + f = Xf \ X f . We assume has a causal direction, and the body part of the formula indicate the evidence to be gathered from history to deduce the state of the head predicate. By this assumption, it is only valid to consider ty tu, tv . Given observed sequences of data, each predicate in X will be grounded as a list of ordered 0-1 events. The main idea of temporal logic point process (TLPP) (Li et al., 2020) is to use the temporal logic rules (1) as templates to selectively choose combinations of events from history as evidence to infer the transition rate of these 0-1 events. In this way, the structure of the intensity function will be informed by the pre-specified temporal logic rules. Below we provide more details. Logic-informed intensity function. Let Ht include all the historical trajectories of the grounded predicates in X up to t. TLPP leverages the rule set to model the state transition dynamics of the head predicates. Define ⇤(t) := (t|Ht) as the transition intensity for {Y (t)}t 0 to transit from 0 to 1, given history up to t; and µ⇤(t) := µ(t|Ht) vice versa. Assume the generating process of the 0-1 events are governed by the set of temporal logic rules F = {f1, f2, . . . }. First consider one formula f , to incorporate its knowledge in intensity construction, we define a formula effect (FE), which aims to gather only the effective combinations of the historical predicate events defined by f as evidence to reason about the transition rate of the head predicate. To ease the notation, define the predicate index set of Xf as U , then the formula effect of f is computed as
f (t | y(t), {xu(tu), Itu}u2U 2 Ht) := f (1 y(t), {xu(tu), Itu}u2U ) f (y(t), {xu(tu), Itu}u2U ) (2) where y(t) is the observed head predicate state at t, 1 y(t) is its counterfactual state, {xu(tu), Itu}u2U 2 Ht is one historical combination of the body predicates (including their states
and time intervals) in f , and f(·) is the clausal form of (1), which is an alternative expression to ease the evaluation of the rule. For example, Y X is logically equivalent to its clausal form ¬Y _X . FE, which is essentially a difference between the what-if scenario and the true scenario, answers the question such as “should Y (t) transit its state given logic formula f is true". One can check that the sign of FE can only be 1, -1 or 0, which can be interpreted as: sign(FE) = 1 indicates a positive effect for the head to transit, -1 indicates a negative effect, and 0 means no effect. Only the non-zero FE will refer to an effective combination. Let Hut be the historical trajectory specific to predicate u up to t, and one can aggregate all the valid (i.e., non-zero) FEs from history by a summation over all combinations of the temporal predicate states and their intervals, i.e.,
f (t) = X
{(xu(tu),Itu )2H u t }u2U f (t | y(t), {xu(tu), Itu}u2U ), (3) where f (t) is the feature informed by logic formula f . One can refer to Fig. 2 for an illustration. For each f 2 F , one can build the rule-informed and history-dependent features f (t) as above, and assumes the rules are connected in disjunctive normal form (OR-of-ANDs) to deduce Y . Then the transition of {Y (t)}t 0 are modeled as monotonically increasing and non-negative functions of the weighted sum of the features:
⇤(t) = exp ⇣ b0 + X f2F wf · f (t) ⌘ , µ⇤(t) = exp ⇣ b1 + X f2F wf · f (t) ⌘
(4)
where w = [wf ]f2F 0 are the weight parameters associated with each rule f 2 F , and b0, b1 are the spontaneous intensity, which are distinct for the dual intensities. Weight parameters will be shared by the dual intensities, but the calculated features f through (2) and (3) will always have opposite signs. One can think of the formula weight wf as the confidence level put on f . The higher the weight, the more influence that the formula will have on the intensity. The rationale of TLPP is that the intensity functions are constructed in a way that the yielding 0-1 event sequences will enable the set of logic rules to be more satisfied. 3 THE PROPOSED METHOD: TELLER
Likelihood function and its convexity. Given {Ht}0<t<T , one can write out the likelihood w.r.t. the intensity ⇤(t) and µ⇤(t). Suppose a realization of {Y (t)}0<t<T = {Y (0) = 0, Y (t1) = 1, . . . , Y (tn) = 1, tn < T < tn+1}, the (log) likelihood are (see proof in Appendix C): `(w, b0, b1) = logL(w, b0, b1), where:
L(w, b0, b1) = ⇤(t1) exp
✓ Z t1
0
⇤(s)ds ◆ · µ⇤(t2) (5)
exp
✓ Z t2
t1
µ⇤(s)ds ◆ · · · exp ✓ Z T
tn
µ⇤(s)ds ◆ ,
Note that ` is convex w.r.t w, b0 and b1. This is true as the intensity function has a functional form of Eq. (4), and this turns the log-likelihood function into a generalized linear model (GLM) with Poisson observations and log link (Fahrmeir & Tutz, 2013). It is well-known that the negative log-likelihood of a GLM is convex w.r.t the model parameters. This convexity property leads to a convergence guarantee for TELLER. We will design our TELLER with the backgrounds detailed in the previous section. TELLER uses TLPP as the backbone to evaluate the likelihood
of the grounded 0-1 temporal predicate sequences. The likelihood will be maximized to jointly learn the set of temporal logic formulas and their weights. The problem is essentially combinatorial and requires enumerating an exponentially large set of combinations of the predicates and their signs. Our problem is even more challenging compared to traditional inductive logic programming due to the sequential properties of data with temporal information. TELLER solves this problem using the procedures as shown in Fig. 3. We will start our exposition with the formulation of the original, or the master rule learning problem.

heading: 3.1 TEMPORAL LOGIC RULE LEARNING PROBLEM (MASTER PROBLEM)
text: We aim to uncover the set of temporal logic rules F based via optimizing:
PMaster : w⇤, b⇤0, b ⇤ 1 = argmin w,b0,b1
`(w, b0, b1) + 0 X
f2F̄ cfwf ; s.t. wf 0, f 2 F̄ (6)
where F̄ is the complete and exponentially large collection of all possible temporal logic formulas that can be created by the set of the pre-specified temporal predicates and their temporal relations. The algorithm needs to determine: 1) the assignment Xf , X+f , and X
f ; 2) the important temporal relations defined over the involved predicates in f ; and 3) the weight parameter wf as in (4). The
regularization penalties related to the rule complexity are incorporated into the objective to force sparsity and to trade off accuracy against rule simplicity. Rule complexity coefficient cf can be the rule length if we want to learn both the sparse and short rules. Any affine function e.g. 0 P f2F̄ cfwf with cf 0, 0 0 should work here and will not change the convexity. One can further tune 0 to balance the negative likelihood and the complexity penalty via cross-validation. The sparsity of w⇤ will indicate the collection of rules learned and these non-zero weight rules will compose F . Key Idea: Although we can write the rule learning problem as a regularized convex optimization above, the set of variables (wf ) is exponentially large and can not be optimized simultaneously in a tractable way. The idea of TELLER is to start from a restricted master problem (RMP), where the search space is smaller and the solution is tractable but suboptimal. TELLER will gradually improve this solution by iteratively expanding the search space until the solution approximates the optimum. The idea is inspired by the fact that most of the candidate rules in F̄ will not be in F and will lead to a zero value weight in the optimal solution. We do not want to waste resources by including these redundant rules when we expand the search space to optimize (6). TELLER will always generate the rule that has the potential to improve the objective function, which is an any-time algorithm with the guarantee that the most important rules have been considered. Our progressive algorithm gives rise to two questions: 1) the criterion to determine the new rule to add; 2) How to construct new candidate temporal logic rules, as will be tackled in the following.

heading: 3.2 CRITERION TO ADD RULES
text: Restricted master problem (RMP). TELLER first replaces the original rule set F̄ by a small subset F0 ⇢ F̄ and gradually expands this subset to produce a nested sequence of subsets F0 ⇢ F1 ⇢ · · · ⇢ Fk ⇢ · · · . It does so by adding candidate rules identified by subproblems (we will elaborate on this later). Note that the initial rule set F0 can be an empty set or any pre-defined small set. For each Fk, k = 0, 1, . . . , TELLER solves the restricted master problem by replacing F̄ with Fk:
PRestricted : w⇤(k), b ⇤ 0,(k), b ⇤ 1,(k) = argmin w,b0,b1
` (w, b0, b1) + X
f2Fk
cfwf ; s.t. wf 0, f 2 Fk. (7)
This can be regarded as the rule evaluation stage, where all rules in the current set will be reweighed. Note that an optimal solution to the restricted master problem above can be extended to a feasible solution to the original problem by setting the weights of all missing f 2 F̄ \ Fk to zero. The optimality of this extended solution can be verified by leveraging the convexity property of the original problem (6). Let the Lagrangian of the original problem be L(w, b0, b1,⌫) = ` (w, b0, b1) + P f2F̄ cfwf P f2F̄ ⌫fwf , where ⌫f 0 is the Lagrange multiplier associated with the non-negativity constraints of wf . Being a convex problem, strong duality holds under mild conditions. Suppose w⇤, b⇤0, b⇤1 is primal optimal, and ⌫⇤ is dual optimal, then `(w⇤, b⇤0, b⇤1) = infw,b0,b1 L(w, b0, b1,⌫⇤). This implies the complementary slackness, which will lead to the following condition. Evaluate current dual price. Obtain the dual price for each constraint in the original problem (6):
⌫f,(k) = @` (w, b0, b1)
@wf
w⇤ (k) ,b⇤ 0,(k) ,b⇤ 1,(k)
+ cf , (8)
where subscript (k) means the price depends on the current optimal solution of the RMP, and subscript f refers to the constraint wf 0. The optimality condition says: if the extended solution of w⇤(k) is optimal to the original problem, it must satisfy the following condition:
w ⇤ f,(k) > 0 ) ⌫f,(k) = 0; w⇤f,(k) = 0 ) ⌫f,(k) 0 8f 2 F̄ , (9) where ⌫f,(k) is computed via (8). For the missing rules, we have wf,(k) = 0 automatically, and if they are the optimal solution to the original problem, the computed ⌫f,(k) 0 must hold. A more detailed description of complementary slackness and optimality condition is given in Appendix D. So, the rule adding criterion is to search over the missing rules and find the rule that most violates the condition, i.e., leads to the most negative ⌫f by (8). Adding it to Fk+1 will most reduce the objective value. Assuming the computed minimal ⌫f 0, it is guaranteed that the current solution to the restricted problem is also optimal to the original one. A subproblem is constructed and optimized to identify a new rule, as will be discussed next.

heading: 3.3 PROPOSE A NEW TEMPORAL LOGIC RULE
text: Construct a subproblem from the current dual price. A subproblem is formulated to propose a new (or missing) temporal logic rule which can potentially improve the optimal value of the RMP, i.e. having a negative increased gain. The increased gain of a missing rule is defined as the possible change in the objective per unit when it is included in the rule set, and it is computed by taking
the partial derivative of the objective function w.r.t the rule weight. Note the subproblem itself is a minimization, to find the most negative increased gain. Given the solution w⇤(k), b ⇤ 0,(k), b ⇤
1,(k) for the restricted master problem (7), a subproblem is constructed by taking the partial derivative w.r.t the weights. The log likelihood can be regarded as a function of the dual conditional intensities: `( ⇤, µ⇤). By the chain rule, the subproblem optimizes:
min f2
⌫( f |w ⇤ (k), b ⇤ 0,(k), b ⇤ 1,(k)) =
✓ @` ( ⇤, µ⇤)
@ ⇤ @ ⇤ @wf + @` ( ⇤, µ⇤) @µ⇤ @µ⇤ @wf ◆ w⇤
(k) ,b⇤ 0,(k) ,b⇤ 1,(k)
+ cf , (10)
where f 2 is the rule-based feature, ⇤ and µ⇤ are functions of f , and the conditional intensities are time and history-dependent (see Eq. (4)). In our formulation, this subproblem objective happens to be the current dual price. The objective can be hard to express in a closed-form but will be easily evaluated numerically. Minimizing over the feature space is essentially searching through a combinatorial space of the temporal predicates and their temporal relations to determine a rule f , so that its yielding feature will minimize the objective function. Solve subproblem to identify a new rule. As discussed above, if the optimal value of the subproblem is negative, we have identified a feature (i.e., rule) to enter the rule set to construct Fk+1; if the optimal value of the above problem is non-negative, we have proven that the current solution to the RMP is also optimal to the original problem. Note that the subproblem would not generate the same feature or rule more than once, since the optimal Lagrangian multipliers in the RMP are non-negative. However, explicitly solving subproblem (10) requires enumerating all possible conjunctions of the input predicates, their signs, and all possible pairwise temporal relations. The construction of feature f requires evaluating all valid combinations of predicate events from history. Speedup subproblem. To make the subproblem tractable, we adopt a couple of principles. 1) Theoretically, the optimality of the subproblem can be sacrificed. In fact, any solution to (10) that has a negative objective will generate a rule with negative increased gain and can be added to the rule set. This provides a performance guarantee for speedup. 2) Practically, prior knowledge in rule structures can be leveraged. Our prior knowledge has 3 parts: sparsity, heredity, and expert’s preference in rule templates. sparsity means the uncovered rule set is small and the rule lengths are generally short. In our algorithm, the maximal rule length is pre-specified as H . It means we do not need to consider rules with lengths exceeding H . By heredity, we mean if the conjunction of the input predicates is important, at least one of the involved input predicates will show some significance. Heredity justifies that we can gradually grow rules from the existing short segments in the current set. Search algorithms. With the prior knowledge above, we can design search algorithms in a way like depth-first search (DFS) or breadth-first search (BFS). In our setting, they are named as ruleextension-first-search (REFS) and rule-addition-first-search (RAFS), respectively. REFS will always extend the existing rules until the length reaches H , while RAFS will first add all possible rules with length 1, and then consider the rules with length 2 and so on. Here we describe details of REFS, and leave RAFS for Appendix F. In Fig. 4, a REFS is used to construct a new temporal logic rule. Specifically, it starts by constructing a rule with length one (i.e., one body predicate). This is achieved by scanning the predicate set X and temporal relation set R, then enumerating the signs and possible temporal relations with the head predicate. The subproblem objective is used to score these segments and select the most negative one. The process continues to extend current segments in the same way, until the rule length reaches H , or the minimal subproblem objective becomes positive. In this way, the complexity of our subproblem is O(d), where d is the number of predicates. Once new rules are added to the rule set, the model will be re-fitted and the model parameters will be re-weighted according to Eq. (7). Longer rules might outweigh their short segments after the rule evaluation stage and thus the length of an important rule can be determined. In addition, we can use expert’s preference in rule templates to solve the subproblems. Human experts provide preferred rule templates (rather than a rule set), which reduce the rule searching space, since it masks out many irrelevant predicates and their combinations. For example, doctors are interested in how a treatment affects the evolution of patient health status. To reflect the doctor’s conjectures, the rule template can be defined as “symptoms drugs ^ symptoms”.

heading: 3.4 DISCUSSION ON SCALABILITY OF THE ALGORITHM
text: The previous discussion provides a theoretical framework to find an (near-) optimal temporal logic rule set based on the point process model. For large problems with thousands of event sequences and hundreds of predicates, this type of progressive algorithm tends to be hard to terminate, and obtaining
the optimality condition is almost impossible; this is the so-called tailing-off effect (Lübbecke & Desrosiers, 2005; Savelsbergh, 2002). Therefore, we need other techniques to make the TELLER scale with the data and the predicates. For example, we may condition an early termination to the algorithm if a fixed time limit is exceeded. In practice, setting the time limit is proven to work well and the most important rules are likely to be discovered. For large problems, we may also choose to take a random subset of sequences and a random subset of predicates for evaluation. When solving for the RMP, we can use a stochastic gradient descent-type of optimization to approximate the gradient using a batch of sequences. By doing so, we enable the RMP to scale with the data (sequences). Furthermore, we can warm-start the model parameters for consecutive RMPs, i.e. we initialize w(k+1), b0,(k+1), b1,(k+1) using the optimal solution w⇤(k), b ⇤ 0,(k), b ⇤
1,(k). When solving the subproblems, besides the efficient search scheme, we may also choose to take a subset of the predicates in searching for further speedup.
When the domain knowledge is not accessible, a rule of thumb to initialize F0 is to start with an "empty" set, which refers to there being only a base term in the intensity function, i.e., ⇤(t) = exp (b0) and the initial estimate can be learned by MLE (i.e., restricted master problem).

heading: 4 EXPERIMENTS
text: We evaluate the rule discovery ability and prediction accuracy of TELLER on synthetic and real event data. For synthetic data, with groundtruth temporal logic rules, the accuracy can be evaluated by comparing the uncovered results to the ground truth. For real data, we consider a healthcare treatment understanding problem and a crime pattern learning problem (crime results are in Appendix H & I).

heading: 4.1 BASELINES
text: We considered the following SOTA baselines: 1) Recurrent Marked Temporal Point Processes (RMTPP) (Du et al., 2016b), the first neural point process (NPP) model, where the intensity function is modeled by a Recurrent Neural Network (RNN); 2) Neural Hawkes Process (NHP) (Mei & Eisner, 2016), an improved variant of RMTPP by constructing a continuous-time LSTM; 3) Transformer Hawkes Process (THP) (Zuo et al., 2020), an NPP model with a self-attention mechanism; 4) Tree-Regularized GRU (TR-GRU) (Wu et al., 2018a), a deep time-series model with a designed tree regularizer to add model interpretability; 5) Recurrent Point Process Network (RPPN) (Xiao et al., 2019), where the intensity is modeled by two interleaved RNNs with attention mechanism; 6) CAUSE (Zhang et al., 2020b), an NPP model with Granger causality statistic learned. We also considered other widely used parametric/nonparametric TPPs: 1) Hawkes Process with an exponential kernel (HExp) (Lewis & Mohler, 2011); 8) Inhomogeneous Poisson Process (IPP), where the intensity is a sum of k weighted Gaussian kernels: ̂(t) = Pk
i=1 ↵i 2⇡ 2i 1/2 exp (t ci) 2 / 2i , where ci and i are fixed center and standard deviation,
and ↵i is the weight for kernel i.
In Tab. 1, we compared TELLER with these baselines by the model properties: 1) Interpretable: model parameters and prediction are understandable to humans; 2) Flexible: model is expressive to capture sophisticated non-linear dependencies; 3) Parsimonious: model parameters are of small or medium size; 4) Pairwise interaction: can identify the mutual influence of the events; 5) Higher-order interaction: can identify the composite effect of a subset of events to another event.

heading: 4.2 SYNTHETIC DATA
text: We first verify TELLER’s rule discovery ability on synthetic datasets with ground truth. The synthetic events are generated from TLPPs with a known set of rules and weights. We prepared 12 synthetic
Consistent results show an accurate performance of our algorithm in terms of both the rule discovery and parameter learning. We list all the discovered rules based on dataset-1 using 2400 and 600 sequences respectively in Tab. 2, where the correct rules are marked in blue. For dataset-1, the body predicate set is {A,B,C,D}, and the head predicate is E. Given 600 sequences, TELLER successfully discovered 2 out of 3 truth rules along with several noise rules; whereas, given 2400 sequences, TELLER accurately uncovered all 3 ground truth rules without including any noise rules. The results indicate that TELLER is capable
of mining hidden rules from noisy event data. Given more samples, the learning performance will improve as a result. More datasests’ results are reported in Fig. 5, where 6 synthetic datasets with 2400 sequences are used for evaluation. Each plot in the top row uses a Venn diagram to show the true rule set and the learned rule set, from which the Jaccard similarity score (area of the intersection divided by the area of their union) is calculated. TELLER discovered almost all the true rules. Each plot in the bottom compares the true rule weights with the learned rule weights, with the Mean Absolute Error (MAE) reported. Almost all truth rule weights are accurately learned and the included noise rule weights are relatively small. In dataset-4, we crafted a long and complex rule with 3 body predicates to challenge TELLER. It is still able to correctly discover this rule, while the weight is slightly underestimated. The existence of long logic rules will require more data and stronger signals (i.e., higher rule weights) to have an accurate recovery. More information about the experiment settings can be found in Appendix G.
We also compared TELLER with the brute-force method, where we enumerated all possible temporal logic rules and built a full model to learn the rule weights. We showed the training process for dataset-1 in Fig. 6, where the evolving likelihood versus the run time is displayed. For TELLER, we also marked the time point when the true rule is discovered (gray dashed vertical lines). The key observations are: 1) For TELLER, the likelihood increases
very fast and we can see evident jumps whenever a true rule is discovered. As a comparison, the likelihood for the brute-force method increases slowly. 2) All the true rules can be discovered efficiently by TELLER and this verifies that we can set a time limit for early stopping. We can stop TELLER when the objective function seems to start centering around some level. This experiment verifies that our method is computationally efficient compared to the brute-force methods.

heading: 4.3 REAL DATA: TREATMENT ON MIMIC-III
text: MIMIC-III contains electronic health records of patients admitted to the intensive care unit (ICU) (Johnson et al., 2016). We focused on patients diagnosed with sepsis (Saria, 2018; Raghu et al., 2017; Peng et al., 2018), as one of the major causes of mortality in ICU. Evidence suggests that the treatment strategy remains uncertain – it is unclear how to use intravenous fluids and vasopressors to support the circulatory system. There also exists clinical controversy about when and how to use these two groups of drugs to reduce the side effect. TELLER is aimed to learn the explanatory temporal logic rules regarding these two groups of drugs as well as their importance weights. Predicates and dataset statistics. We define 62 predicates, including two groups of drugs (i.e., intravenous fluids and vasopressors) and lab measurements. The variables involved are similar to (Saria, 2018). Among all these predicates, we are interested in reasoning about two predicates. So we define them as head predicates: 1) LowUrine and 2) Survival. We treat real-time urine as a
head predicate since low urine is the direct indicator of bad circulatory systems and is an important signal for septic shock. A complete table of predicates can be found in Appendix H. In our experiment, lab measurement variables are converted to binary values (according to the normal range used in medicine) with the transition times recorded. For drug predicates, they are recorded as 1 when they were applied to the patient. We extracted 4298 patient sequences, and randomly chose 80% of them for training and the remaining for testing. The average time horizon is 392.69 hours and the average #events per sequence is 79.03. Detailed setup and hyperparameters can be found in Appendix H.2.
Evaluation metrics and results. We use different evaluation metrics for the two head predicates: 1) LowUrine is evaluated by predicting the time of transitions from state 0 to state 1 (this is related to the appearance of septic shock in medicine), for which the performance is measured by Mean Absolute Error (MAE). 2) Survival is evaluated by predicting whether the patient is survived at the end of treatment, for which the performance is measured by AUC. The performances of our model and all baselines are given in Tab. 3. Discovered temporal logic rules. Tab. 4 shows the uncovered explanatory temporal logic rules and their weights learned by TELLER. Here, we use LowUrine as the head predicate and NormalUrine
as its negation. For each discovered rule, the sign of the head predicate will be automatically determined by the algorithm. Human experts (i.e., doctors in ICU) confirmed that these discovered logic rules are consistent with the pathogenesis of sepsis, and have captured the most important factors in affecting real-time urine output and survival. Experts are also interested in interpreting the clinical meaning of the discovered rules. They found that Rule 1 to Rule 4 capture the major lab measurements that usually emerge together with extremely low urine. Rule 5 seemed hard to interpret in the beginning by experts, since they thought it was slightly counter-intuitive. They later concluded that, in some extreme cases, even after using Crystalloid (one type of intravenous fluids) as the treatment, the urine can remain low, and thus Rule 5 is still likely to be observed. Rules 6-9 shed light on drug selection. For example, reflected in Rule 7, using Crystalloid and Phenylephrine (a type of vasopressors) together will play an evident role in triggering the urine to a normal level. In Rules 6, 8, and 9, using Crystalloid yields a weight of 4.14, using Colloid (a type of intravenous fluids) yields a weight of 1.97, and using the combinations of the two yields a weight of 1.83, which can be regarded as an incremental contribution in addition to using them separately.
Expert-Model interaction. Experts are involved in TELLER’s learning loop: 1) Experts can provide a predicate set, their interested head predicates, an initial rule set, and desired rule templates to the model; 2) Run TELLER to obtain preliminary results for experts to check. Experts can delete unreasonable or noise rules and give the refined rule set to the model before continuing learning. Experts provided advice for predicates definition and the desired rule templates. We ran TELLER from an empty set and generated 12
rules. Experts verified the rules’ correctness and deleted the following ones: LowUrine HighSpO2; LowUrine NormalSodium; LowUrine NormalSodium ^ Water. We were informed that the first rule is contradictory with Pathophysiology common sense, while the other two rules are correct yet irrelevant to the treatment strategy. We deleted these 3 rules and re-implemented TELLER to refine the rule set and weights with final output in Tab. 4.

heading: 5 CONCLUSION
text: In this paper, we have proposed a new algorithm TELLER to learn interpretable temporal logic rules to explain point processes, with promising results on both synthetic and real-world data. To our best knowledge, this is the first work that automates the discovery of the temporal logic rules based on point process models. Our method adds transparency and interpretability to event models.

Review summaries:
This paper introduces TELLER, a framework with novel algorithms based on the temporal point process model to discover interpretable temporal logic rules. To this end, the authors designed a “rule generation - evaluation” two-stage way to solve the problem efficiently. The proposed method is evaluated using one synthetic and two real data sets. Experts have also verified that the learned temporal logic rules are interpretable and reflect many critical principles in real practices.

This paper builds upon the work of [1] and proposes an algorithm to simultaneously estimate the logic rules and the model parameters.  The estimation problem is formulated as the contained optimization problem (6), with both continuous and discrete parameters to optimize over. The proposed TELLER algorithm divided the original problem into a sequence of Restricted master problems and gradually expand the search space for a global optimum.  Subjective constraints and expert opinions can be incorporated into the search algorithm as well.   [1] Shuang Li, Lu Wang, Ruizhi Zhang, Xiaofu Chang, Xuqin Liu, Yao Xie, Yuan Qi, and Le Song. Temporal logic point processes. In International Conference on Machine Learning, pp. 5990–6000. PMLR, 2020.

The paper uses a method inspired by column generation to continuously add temporal logic rules to their model to maximize the likelihood of the data. The goal is to generate a model that is highly interpretable. They compare against state of the art baselines and get good improvements.

This paper proposed a model for learning temporal logical rules for the temporal point process. Specifically, the key idea is to formulate the rule learning as a restricted master problem and gradually optimize the objective function, which can significantly lower down the search space. The authors conduct extensive experiments on both synthetic data and real data.