Explaining Point Processes by Learning Interpretable Temporal Logic Rules
Authors: Shuang Li
Mingquan Feng
Lu Wang
Abdelmajid Essofi
Yufeng Cao
Junchi Yan
Le Song
Venue: ICLR 2022 Poster (2022)
Keywords: Temporal Point Process
Temporal Logic Rules
Explainable Models

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. 

Published as a conference paper at ICLR 2022
EXPLAINING POINT PROCESSES BY LEARNING INTERPRETABLE TEMPORAL LOGIC RULES
Shuang Li -1, Mingquan Feng? +1, Lu Wang", Abdelmajid Essofi',
Yufeng Cao² 5, Junchi Yan 5, Le Song
*CUHK, Shenzhen "Shanghai Jiao Tong University *Microsoft Research MBZUAI
BBioMap
1 lishuangécuhk. wwwpaangecuuukeuu..... cn, {fengmingquan, yufeng. cao, yanjunchi jsjtu. atu..ddu.co wlu@microsoft. com, [Abdelmajjdd.Esoof.. le. song @mbzuai aacaaaa.cc...... ac.ac
ABSTRACT
We propose principled method to learn set of human-readable logic rules explain temporal point processes. We assume that the generative mechanisms underlying the temporal point processes are governed by a set of first-order tem- poral logic rules, as a compact representation of domain knowledge. Our method formulates the rule discovery process from noisy event data as a maximum likeli- hood problem, and designs efficient and tractable branch-and-pric 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 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 a point process model which outperforms previous state-of-ther th-thhr-rts for symptom prediction, both in their occurrence times and types.
INTRODUCTION
Event sequences with irregular time intervals are ubiquitous. The inter-event times usually convey rich information regarding the underlying dynamics such as discase progression (Liu et al., 2015). It is useful to understand events' generating mechanisms, time. In systems where domain knowledge is rich, events generating can usually be governed by a few first-order temporal logic rules, as compact representation of knowledge. In healthcare, the knowledge "if a sudden fall in blood pressure is observed, vasopressors are required to be applied patients immediately; and then the blood pressure may return 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 rules with temporal relation constraints, such as "A happens before B", "If A happens, and after mins, 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.
well as the occurrence reason and
collection of logic
Meanwhile, large amount of literature has been devoted 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 compute the count of events within each bin. TPP models treat the inter- event time as random variables and directly model the intensity function (i.c., 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
"quual contribution.
"Shanng Li is with the School of Data Science, The Chinese University of Hong Kong, Shenzhen, Shenzhen 51 518172, China, and the Shenzhen Institute of Artificial Intelligence and Robotics for Society, Shenzhen 518129,
China (corresponding author, e-mail: lishuang @ cuhk.edu.en).
Mingguan Feng and Junchi Yan are with Dept. of CSE, MoF Key Lab of Artificial Intelligence, and
SJTU-Yal Yale Joint Center for Biostatisties and Data Science, National Center for Translational Medicine, SJTU.
8 Yufeng Cao is with the Antai College Economics and Management the Data-Driven Management Decision Making Lab, SJTU.
Cooe available http:///ghhu....ooooooogggggggug Point Processes ICLR ICLR

---

Published as a conference paper at ICLR 2022
process intensity functions with temporal logic rules. This method employs 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, c.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 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 dynamics based on historical event data alone? It is challenging as the space of possible temporal logic formulas is huge, comprising of combinations of massive 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 inspired by the branch-and 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 IP problem is solved via two alternating procedures: the master problem and the subproblem, where the master problem is the original problem with only subset of variables being considered and the subproblem is new problem created to identifyy new variable to be added. Similarly, TELLER also alternates between solving a master problem and 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 new temporal logic rule (by extending current rule adding 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. I shows the flow.
Specifically, TELLER is computationally efficient and with guar- antees. 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 mod- eling framework, we show that the resulting objective function, Le. 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.
TELLER
Subproblem: search nule that potentially most increase the ikeliood
Master problem: reweight maximize the likelhood
Figure I: alternates between a rule evaluation stage (master problem) and a rule proposal stage (subproblem).
The flow of TELLER. It
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.
2 BACKGROUND
2.1 FIRST-ORDER TEMPORAL LOGIC RULES
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.
2

---

Published as a conference paper at ICLR 2022
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 set of static predicates X' (Xi,...., Xa). where each static predicate (((c) is a logic random variable that defines the property or relation of entities, such as Smokes(c) or Friend(c, c'). where e and c' are the entities. By adding a temporal dimension to predicate X,, we obtain temporal predicate (X.(e, 12 which can be viewed as continuous-timg 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 [NormalBlooPPressuree referring to the patient, will take value I or O at any time to indicate whether the patient's 's blood pressure is normal or not, with stochastic state transition time (see Fig. 2).
hr20 where entity is
To simplify the notation, we will temporally drop the depen- dency of predicates on entities. We will write ((c, t) as (t) instead and the grounded temporal predicate as {a(t)
Given repeated events
time
2.2 TEMPORAL LOGIC POINT PROCESS
(X2(1))20
Temporal Point Process (TPP) provides an elegant tool to cap- ture the dynamics of the event sequences. It is characterized by conditional intensity function, denoted by X(4)H)), where his-
('()))ra
Feature: (t) = Σ X
Σ 4 ( ext lege2
tory H4 is the knowledge of times of all events. By definition, we have H(t )dt [[ ([t, t dt)) (Ht), where []t ++dt)) denotes the number of points falling in an interval [t. t + di). Here aim to use TPP to model these 0-1 events and use the intensity function to capture the 0-1 transition rate.
6vvald combinations
Feature constructions of TLPP using simple logic formula f:Y + AAB, as a template to gather combinations of the hody predicate his- tory events. A has 2 events and B has 3 events, leading 6 valid combinations.
Figure 2:
Temporal relation. We will use the interval-basedd temporal relations originally introduced in Allen's '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 relations, 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 LA, the temporal predicate (Xx())
takes state IA = 0 or 1, we define 1,, = (4A, AAg] lA E (LA1: (.a). as time interval where LA, is the transition time that this predicate enters the state ZA and AA, is the transition time that this predicate leaves the state A- For any two temporal predicates, given their time intervals, Les +tu, and Th = (tB, LBgg) their temporal relation function, denoted as RA type B (Te,, Teg) ) E RR is a logic function defined over the time intervals and can be evaluated by plugging in the specific time intervals.
RAtype
For example, RA Before B = l > } and RA Equals = l(tA, = La 3lttA = (. 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:
(I) where each temporal predicate and the temporal relations can be evaluated at ty. tu and t, along with their corresponding intervals It, and It, In the above formula, negation (-) means the head predicate Y can take a negative sign; X, = X U UX,, is the set of predicates defined in f. where X7 is the set of predicates as negation in the formula f. and X7 = X2 \ X 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 t,, 2 t,,. ty.
f Y-)Y (ty)) + Ax.ex; Xu(tw) Ax.Ex, -X.(t.)) Ax..x.ex, Ru tupe v (Iew, Je,))
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 He 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 x²())= == X(1)H))) as the transition intensity for (Y))) transit from 0 to
3

---

Published as a conference paper at ICLR 2022
1, given history up to t; and μ (t) ((t))()) vice versa. Assume the generating process of the 0-1 events are governed by the set of temporal logic rules F= = {fi, 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 evidence to reason about the transition rate of the head predicate. To ease the notation, define the predicate index set of 2 as U. then the formula effect of f is computed as 8y (f (ut),, { (fw), Jt, Jueu E Hi) == f (1 v(t), (tu( Tt JuEu) f (v((t), (fu(tu), J.,, )uEU) (2)
where y(t) is the observed head predicate state at t, 1 ytt) is its counterfactual state, (zu((a)) It, Juet E He 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 V X. FE, which essentially difference between the what-if scenario and the true scenario, answers the question such as "should (() transit its state given logic formula f is true".
One can check that the sign of FE can only be 1. -11 or O, which can be interpreted as: sign = 1 indicates positive effect for the head to transit, -1 indicates negative effect, and 0 means no effect. Only the non-zero FE will refer to an effective combination. Let Hi be the historical trajectory specific to predicate up to f, 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.,
(t) = Σ (t.) 6,(t (t), { (fw), Jt,, Jweu).
(3)
where (f) is the feature informed by logic formula f. One can refer to Fig. for an illustration.
For each f E F. one can build the rule-informed and eestory-dependent features (t( as above, and assumes the rules are connected in disjunctive normal form (fR-of-ANDo) to deduce Y. Then the transition of {Y [t) are modeled monotonically increasing and non-negative functions of the weighted sum of the features:
(4) where w = [wy]reF 2 O are the weight parameters associated with each rule E F, and bo. b are the spontaneous intensity, which are distinet for the dual intensities. Weight parameters will be shared by the dual intensities, but the calculated features Øy through (2) and (3) will always have opposite signs. One can think of the formula weight wy 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 TI.PP 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.
(1))) exp bo + "1er Wy (,)))))
(²()) = ex))=exp(p (b: + Σ "y
JEF "y +)(())
THE PROPOSED METHOD: TELLER
Likelihood function and its convexity, Given (He JosTeTT one can
Temponal lagle nale leaming problem (6)
write out the likelihood w.r.t. the intensity (t) and (²(()) (1). Suppose
realization of (oocer = (Y(0) 0, (th) = 1,-.-. (t..)
In < < 1. ). the (log) likelihood are (see proof in Appendix C): f(w, by, b1) = log L(w, by, 61), where:
(RMP) (Fa,77)
L(w, bo. b1) =A exp (-
(-f-" ("x(s)dss .H (42(
current
exp (-1,0 1 (s)ds) ...eepppppp (-f" (w)dds))
Construct Subprobrem from dual ($.0
to RMP
Note that - is convex w.r.t w. bo and bj. This 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.
Solve Subpeotiem
Von
the Inoreased gale regadiee?
No
End (Rule found)
TELLER uses TLPP as the backbone to evaluate the likelihood of the grounded 0-1 temporal predicate sequences. The likelihood will be maxi- mized 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.
Figure 3: TELLER
4

---

Published as a conference paper at ICLR 2022
3.1 TEMPORAL LOGIC RULE LEARNING PROBLEM (MASTER PROBLEM)
We aim to uncover the set of temporal logic rules F based via optimizing: Muster w", Dg. bj = argmin - E(w, bo. b1) + Ào E1e CfWs; s.t. 2y fEF (6)
10,bo.01
where F 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 X,. X and x 2) the important temporal relations defined over the involved predicates in f: and 3) the weight parameter W 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 of can be the rule length if we want to learn both the sparse and short rules. Any affine function e.g. Ào SE Cywy with of 2 0, Ao 2 0 should work here and will not change the convexity. One can further tune Ao to balance the negative likelihood and the complexity penalty via tross-validation. The sparsity of w" will indicate the collection of rules learned and these non-zero weight rules will compose F.
Although we can write the rule learning problem as a regularized convex optimization above, the set of variables (wy) is exponentially large and can not be optimized simultaneously in tractable way. The idea of TELLER is to start from a restricted master problem (RMP). where the search space is smaller and the solution 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.
Key Idea:
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.
3.2 CRITERION TO ADD RULES
Restricted master problem (RMP). TELLER first replaces the original rule set F by a small subset Fo FF and gradually expands this subset to produce nested sequence of subsets Fo Fi c C. Fx C .... It does so by adding candidate rules identified by subproblems (we will elaborate on this later). Note that the initial rule set Fo can be empty set any pre-defined small set.
For each Fs. h = 0, 1,..., TELLER solves the restricted master problem by replacing F with Fe: PRestricted w(x) (k)))) (i)) argmin
l (w, bu b2) +
cywy; s.t. wy 0, E FR. (7) FEF.
Σ
w.bn.b,
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 ex- tended to a feasible solution to the original problem by setting the weights of all missing f E F Fx 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, bo. b.. 1) -é (w, by. b,) + EEeF C - - W. where Vy 2 0 is the Lagrange multiplier associated with the non -egaatiity constraints of wy. Being convex problem, strong duality holds under mild conditions. Suppose un", bū bj is primal optimal, and v" dual optimal, then- - [(w", bg. bj) = inf inf bo. Lww, bo, bj. =²). 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): Ol (ur, by, b,)
V',(1)) =
Cff
(8)
Owy
where subscript (k) means the price depends on the current optimal solution of the RMP, and subscript I refers to the constraint wy 2 0. The optimality condition says: if the extended solution of w()) is
optimal to the original problem, it must satisfy the following condition:
w²,0))
= (f)(k)) = 0: w5,0k) 0 = VF.(M) 2 0 Vf
where Vy.(k) is computed via (8). For the missing rules, we have Wy((k) 0 automatically, and if
they are the optimal solution to the original problem, the computed (A) 2 0 must hold. A more
detailed description of complementary slackness and optimality condition is given in Appendix D.
5

---

Published as a conference paper at ICLR 2022
Therefore, the rule adding criterion is to search over the missing rules and find the rule that most violates the condition, i.c., leads to the most negative V by (8). Adding it to Fk+1 will most reduce the objective value. Assuming the computed minimal Vy 2 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 new rule, as will be discussed next.
3.3 PROPOSE A NEW TEMPORAL LOGIC RULE
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 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 wik) (.)) 5f for the restricted master problem (7), a subproblem is con- structed by taking the partial derivative w.r.t the weights. The log likelihood can be regarded as a
). function of the dual conditional intensities: E(X*, 1²"). By the chain rule, the subproblem optimizes:
min /((r|ten(e) (6.(k) ((,))) = ④e (X",H) Ox" DE (E(""H") 8p² 0,
cff (10)
0x- Owy
Ow, w "6.6))
where dy E & is the rule-based feature, X and μ= are functions of σy. 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 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 FR+1; if the optimal value of the above problem is non-negative, we have proven that the current solution 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 oy requires evaluating all valid combinations of predicate events from history.
Speedup subproblem. To make the subproblem tractable, we adopt a couple of principles. I) Theoretically, the optimality of the subproblem can be sacrificed. In fact, any solution to (I0) 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 'ss 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 way like depth-first search (DFS) or breadth-fire first search (BFS). In our setting, they are named as rule- (RAFS), respectively. REFS will always
extension-first first-scarch (REFS) and tule-addition-ffrtt-eaaa 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 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 onc. 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 (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-whithted 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.

---

Published as a conference paper at ICLR 2022
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 "symptoms <- drugs A symptoms". 3.4 DISCUSSION ON SCALABILITY OF THE ALGORITHM
In addition,
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 se- quences and hundreds of predicates, this type of progressive algorithm tends to be hard to termi- nate and obtaining the optimality condition is al- most impossible; this is the so-called tailliggoff effect (Lübbecke & Desrosiers, 2005; Savels- bergh, 2002). Therefore, we need other tech- niques to make the TELLER scale with the data and the predicates. For example, we may con- dition an early termination to the algorithm if a fixed time limit is exceeded. ting the time limit is proven to work well and the most important rules are likely to be discov- ered. 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,, 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, parameters for consecutive RMPs, i.e. we initialize W(K+1), (0) bj (1+(++1) using the optimal solution W/k (0) (i.(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.
Rotoecbiess Beanch
New
Cyerke
the Tuiter FaghtS
Randiie
Rite
rdes
New tule
Outer Logo
fu Fa facs
My
10 cs de 4000 opp 0,00 Mi-4
Uperts
practice, set-
www.thhhhioooooro.....ooooo 449 900
Figure 4: Overall flow of TELLER. It alternates be- tween rule evaluation stage and rule proposal stage. The logic rules and their weights are jointly learned.
can warm-start the model
When the domain knowledge is not accessible, a rule of thumb to initialize Fo is to start with an "empty" set, which refers to there being only a base term in the intensity function, i.c., X (²())= = exp (bo) and the initial estimate can be learned by MLE (i.e., restricted master problem).
4
EXPERIMENTS
We evaluate TELLER on synthetic and real event data. For real data, we consider healthcare treatment understanding and crime pattern learning (crime results are in Appendix H & 1).
4.1 BASELINES
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 Recurrent Neural Network (RNN); 2) Neural Hawkes Process (NHP) (Mei & Eisner, 2016), an improved variant of RMTPP by constructing a continuous-timg LSTM; 3) Transformer Hawkes Process (THP) (Zuo et al., 2020), an NPP model with self-attention mechanism; 4) Treu-Regulrrized GRU (TR-GRU) (Wu et al., 2018a), a deep time-series model with a designed tree regularizer 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/noppaaamett TPPs: 1) Hawkes Process with an exponential kernel (HExp) (Lewis & Mohler, 2011): 1): 8) Inhomogeneous Poisson Process (IPP), where the intensity is a sum of & weighted Gaussian kernels: A(t) = E as (2ma?) -1/2 exp (- (t cx)? /af), where c; and d, are fixed center and standard deviation, and a is the weight for kernel i.
Table 1: Model properties and interpretability comparison of all baselines and TELLER
Model
RMTPP
NHF
TR-GRU
RPPN
CAUSE
HEXP
IPF
TELLER
Interpeetalle
L'exible
Passimnntus
Interaction
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
7

---

Published as a conference paper at ICLR 2022
D Jaccard 1.00
Dutaset: Jaccard 0.75
Dataset-3 Jaccard 1.00
Dataset Jaccard 0.60
Dutaset Jaccard 0.30
Dataset Jaccard 0.75
Learred
Learred
Leamed
Lammedd
Thath
Thth
Thath
Thun
That
Trath
MAE i 0.36
MAE = 0.11
MAE = 0.07
MAE = 0.32
MAG = 0.08
MAG 0.07
Two
Ratn Weight
Saln Weiget
Rate Weight
Ratn Weight
Bale Velget
Rute Weight
Figure 5: Rule discovery and weight leamnnng results of TELLER
SEE.-ERREEFS REFS on 6 synthetic datasets (2.4K seqs).
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 subset of events to another event.
4.2 SYNTHETIC DATA
We verify TELLER's rule discovery ability on synthetic datasets with ground truth. The syn- thetic events are generated from TLPPs with known set of rules and weights. We prepared 12 synthetic datasets with various rule lengths, weights, and temporal relations. See Appendix G for details. Both the REFS and RAFS subproblem search schemes are tested on all 12 datasets. Consistent results show an accurate performance of our algorithm in terms of both the rule discovery and param- eter learning. We list all the discovered rules based on 1ataset-1 using 2400 and 600 sequences respectively in Tab. 2, where the correct rules are marked in blue. For 1ataset-1, the body predicate set is (A, [A,B,C 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 ground truth rules without any noise rules. The results indicate TELLER is capable of mining rules from noisy event data, and that performance improves with more samples.
Table 2: Learned Rules on Synthetic Datasct
True Rules (4 va. Learned Rules (RETS)
2400 Sequences:
E+AA Before B)
ELRACA (R Refore RJ A Refore F)
E (C Before DJ ( Equal B)
600 Sequences:
E+AA Before
R RAAADA (A Equal DJ A (A Bafore F)
E AA 8A (A Before
1 Before A)
RACA (R Refore RJ
Refore F)]
E B BABAAAA (8 Before E) A (C Before B)
E- AAAACA Before E)
Before E)
6 CAAA JA Equal C) A (A Bafora E)
S AAA (A Before -C) 1-2 Before
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 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 1 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 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 the brute-force methods.
C-
Bun time (sscond)
Figure 6: Training process.
evident jumps whenever true rule is discovered. As comparison, the
4.3 REAL DATA: TREATMENT ON MIMIC-III
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 well as their importance weights.
8

---

Published as a conference paper at ICLR 2022
Predicates and dataset statisties. 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). We define two 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 I 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 can be found in Appendix H.2. Evaluation metries and results. We use two evaluation metrics: 1)
Table 3:
MIMIC-II:
LowÜrine is evaluated by predicting the time of transitions from state O to state 1, 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 Accuracy(ACC). Comparison results are in Tab. 3.
Event prediction results.
Lawtrin (MAE)
Survival
Method
(ACC)
RMIPF
1.983
0.796
NHP
1.684
0.802
THP
Discovered temporal logic rules. Tab. 4 shows the uncovered explanatory temporal logic rules and weights learned by TELLER. We use LowUrine as the head predicate and Norma 1Urine as its negation. For each discov-
TR
RPPN
2,666
1.640
0.767
0.811
CAUSE
1.712
0.740
HEsp
2.578
0.882
IPP
0.784
ered rule, the sign of the head predicate will be automatically determined by the algorithm. Human experts confirmed that these discovered logic rules are consistent with
TELLER
1.266
0.930
the pathogenesis of sepsis, and have captured the most important factors in affecting real-time urine output and survival. Experts found that Rule 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 (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 drug selection. For example, in Rule 7, using Crystalloid and Phenylephrine (vasopressors) together will play an evident role in triggering the urine to a normal level. In Rules 6, 8, and 9, using Crystalloid yields 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.
Expert-Model interaction. Experts are involved in TELLER's learning loop: 1) Experts can provide predicate set, their interested head predicates, an initial rule set, and desired rule templates to the model; 2) Run TELLER to obtain pre- liminary results for experts to check. Ex- perts can delete unreasonable or noise rules and give the refined rule set to the model before continuing learning. Ex- perts provided advice for predicates def- inition 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 + HighSpp2; LowUrine + No Normall 1 Sod i um; LowUrine < Normal 1 1Sodium A 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. Then TELLER is re-implemented to refine the result, as in Tab. 4.
Table 4: Learned Rules with LowUr ine the head predicate.
Woight
Rule
1.07
0.89
Rule 2:LowUrine LowSodin A :LowSodin Bodore Lowtrina)
1.16
Rule 3: 35Sowtiring Ine Fighhreetinin
Kepual (llighhhewet in, Lostri inw)
1.48
Rule 4:5ow0Fine e BEGABUN A (FIGEBUN Before Sowteines
Rule Siiowtieinee- RighRUM A Grystellold
1.10
A (iiighu Refore Tealtrine)
A (Eryatal loid nefore lovirine)
Role 61Roona10FF16 e- LoviELne A Orystallold
4.14
(oowbrine Zoual NornalUrine)
A iCrystalloid Beual RoznalUring]
Rule 7:torns [1e
Lowirr Pheenylaporine
3.13
LLombrinw Zqual Norns (irmmlUrion
Wiinylepher ine Equal Nornaluriow)
Rule 8: inrine e- lovürine Orystalloid & colletd
1.83
(Crystallois Equal Noons10eiacc]
(colloid Equal MermalUrine).
(towbrine Squal Norne10rine)
$1hoznel0E.om
Collord
Egual coallaid Equa)
(0rine)
5 CONCLUSION
In this paper, we have proposed 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.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
This work was in part supported by Shanghai Municipal Science and Technology Major Project (2021S2DDZX0100 (2), Neil Shen's SJTU Medical Research Fund and NSFC (61972250, U19B2035).
Shuang Li's research was part supported by the Start-up Fund UDF01002191 of The Chinese University of Hong Kong, Shenzhen, Shenzhen Institute of Artificial Intelligence and Robotics for Society, and Shenzhen Science and Technology Program JCY1200200324400001010000
REFERENCES
James F Allen. Maintaining knowledge about temporal intervals. In Readings in qualitative reasoning aboul physical systems, pp. 361-372. Elsevier, 1990.
Cynthia Barnhart, Ellis L Johnson, George L Nemhauser, Martin WP Savelsbergh, and Pamela H Vance. sauuchhand-rrice Column generation for solving huge integer programs. Operations research, 46(3):316-329 1998.
William Brendel, Alan Fern, and Sinisa Todorovic. Probabilistic event logic for interval-based event recognition. In CVPR 20/1, pp. 3329-3336. IEEE, 2011.
William W Cohen, Tensorlog: A differentiable deductive database. arXiv preprint arXiv:1605.0652; 2016.
Sanjeeb Dash, Oktay Gunluk, and Dennis Wei. Boolean decision rules via column generation. Advances in Neural Information Processing Systems, 31:4655-4665 2018.
N. Du, H. Dai, R. Trivedi, U. Upadhyay, M. Gomez-Rodriguez,, and L. Song. Recurrent marked temporal point processes: Embedding event history to vector. In KDD, 2016a.
Nan Du, Hanjun Dai, Rakshit Trivedi, Utkarsh Upadhyay, Manuel Rodriiuzz and Le Song. Recurrent marked temporal point processes; Embedding event history to vector. In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, pp- 1555-1564) 2016b.
Richard Evans and Edward Grefenstette. Learning explanatory rules from noisy data. Journal of Artificial Intelligence Research, 61:1-64, 2018.
Ludwig Fahrmeir and Gerhard Tutz. Multivariate statistical modelling based on generalized linear models. Springer Science & Business Media, 2013.
Bernd Finkbeiner. Christopher Hahn, Markus N Rabe, and Frederik Schmitt. Teaching temporal logics neural networks. arXiv preprint arXiv:2003.04216 2020.
Valentin Goranko and Antje Rumberg. Temporal Logic. In Edward N. Zalta (ed.), The Stanford Encyclopedia Philosophy. Metaphysics Research Lab, Stanford University, Fall 2021 edition, 2021.
A. Hawkes. Point spectra of some mutually exciting point processes. Journal of the Royal Statistical Soccity. Series B (Methodological), pp. 438-443, 1971a.
Alan G Hawkes. Spectra of some self-exciting and mutually exciting point processes. Biometrika, 58 (1):83-90, 1971b.
V. Isham and M. Westcott. A self-correcting point process. Stochastic Processes and Their Applica- tions, 833:335--347, 1979.
Alistair EW Johnson, Tom J Pollard, Lu Shen, H Lehman Wi-Wei, Mengling Feng, Mohammad Ghassemi, Benjamin Moody, Peter Szolovits, Leo Anthony Celi, and Roger Mark. Mimic-iii, a freely accessible eritical care database. Scientific data, 3(1):1-9, 2016.
E. Lewis and E. Mohler. A nonparametric em algorithm for multiscale hawkes processes. Journal of Nomparametric Statisties, 2011.
10

---

Published as a conference paper at ICLR 2022
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.
Xin Liu, Junchi Yan, Shuai Xiao, Xiangfeng Wang, Hongyuan Zha, and Stephen Chu. On predic- tive patent valuation: Forecasting patent citations and their types. In Proceedings of the AAAI Conference Artificial Intelligence, volume 31, 2017.
Yu- YunYing Liu, Shuang Li, Fuxin Li, Le Song, and James M Rehg. Efficient learning of continuous-time hidden markov models for disease progression. Advances in neural information processing systems, 28:3599, 2015.
Marco E. Lübbecke and Jacques Desrosiers. Selected topics in column generation. Operations research, 53(6): 1007)11077-102, 2005.
Hongyuan Mei and Jason Eisner. The neural hawkes process: neurally self modulaodul multivariate point process. arXiv preprint arXiv: 2016.
Boston Department of Innovation and Technology.
Crime
Incident Reports.
https://data. www.:laaaabostooggoooooooo http:///......ooooooov/aaa/////e new-system, 2015. [Online; accessed 03-May-2021].
Tivadar Papai, Henry Kautz, and Daniel Stefankovic. Slice normalized dynamic markov logic networks. Advances in Neural Information Processing Systems, 25: 19:79-9-19 2012.
Xuefeng Peng, Yi Ding, David Wihl, Omer Gottesman, Matthieu Komorowski, Li-wei H Lehman, Andrew Ross, Aldo Faisal, and Finale Doshi-Veler Improving sepsis treatment strategies by com- bining deep and kernel-based reinforcement learning. AMIA Annual Symposium Proceedings, volume 2018, pp. 887, American Medical Informatics Association, 2018.
Aniruddh Raghu, Matthieu Komorowski, Imran Ahmed, Leo Celi, Peter Szolovits, and Marzyeh Ghassemi. Deep reinforcement learning for sepsis treatment. arXiv preprinl arXiv: 11171.009600. 2017.
Matthew Richardson and Pedro Domingos. Markov logic networks. Machine learning, 62(1-2): 107-136, 2006.
Ali Sadeghian, Mohammadreza Armandpour, Patrick Ding, and Daisy Zhe Wang. Drum: End-to-end differentiable rule mining on knowledge graphs. arXiv preprint 1rXiv:1911.0000 2019.
Suchi Saria. Individualized sepsis treatment using reinforcement learning. Nature medicine, 24(11):
1641-1642, 2018
Martin WP Savelsbergh. sunch-andd-rices Integer programming with column generation, bp. 2002.
Parag Singla and Pedro M Domingos. Lifted first-order belief propagation. In AAAI, volume 8, pp. 1099, 2008.
Son D Tran and Larry S Davis. Event modeling and recognition using markov logic networks. In European Conference on Computer Vision, pp. 610-623. Springer, 2008
Po-Wei Wang, Priya Donti, Bryan Wilder, and Zico Kolter. Satnet: Bridging deep learning and logical reasoning using differentiable satisfiability solver. In International Conference Machine Learning, pp. 6545-6554. PMLR, 2019a.
Po-Wei Wang, Daria Stepanova, Csaba Domokos, and Zico Kolter. Differentiable learning of numerical rules in knowledge graphs. In International Conference on Learning Representations, 2019b.
Tong Wang, Cynthia Rudin, Finale Doshi Velez, Yimin Liu, Erica Klampfl, and Perry MacNeille. A bayesian framework for learning rule for interpretable classification. The Journal of Machine Learning Research, 18(1 18(1)23357-393, 2017.
Dennis Wei, Sanjeeb Dash, Tian Gao, and Oktay Gunluk. Generalized linear rule models. In International Conference Machine Learning, pp. 6687-6696. PMLR, 2019.

---

Published as a conference paper at ICLR 2022
Mike Wu, Michael Hughes, Sonali Parbhoo, Maurizio Zazzi, Volker Roth, and Finale Doshi- Velez. Beyond sparsity: Tree regularization of deep models for interpretability. Proceedings of the AAAI Conference Artificial Intelligence, volume 32, 2018a.
Weichang Wu, Junchi Yan, Xiaokang Yang, and Hongyuan Zha. Decoupled learning for factorial marked temporal point processes. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery Data Mining. pp. 2516-2525, 2018b.
Shuai Xiao, Junchi Yan, Mehrdad Farajtabar, Song, Xiaokang Yang, and Hongyuan Zha. Learning time series associated event sequences with recurrent point process networks. IEEE transactions on neural networks and learning systems,
2019.
Junchi Yan, Shuai Xiao, Changsheng Li, Bo Jin, Xiangfeng Wang, Bin Ke, Xiaokang Yang, and Hongyuan Zha. Modeling contagious merger and acquisition via point processes with profile regression prior. In IJCAI, pp. 2690-2696, 2016.
Junchi Yan, Hongteng Xu, and Liangda Li. Modeling and applications for temporal point processes. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & 2019.
Data Mining, pp.
Fan Yang. Zhilin Yang, and William W Cohen. Diffcrentiable learning of logical rules for knowledge base reasoning. arXiv preprint arXiv:1702.08S6: 2017.
Yuan Yang and Le Song. Learn to explain efficiently via neural logic inductive learning. In International Conference Learning Reprexentations, 2019.
Qiang Zhang, Aldo Lipani, Omer Kimnp, and Emine Yilmaz. Self-attentive hawkes process. In International Conference on Machine Learning. pp. 11 1118--11933 PMLR, 2020a.
Qiang Zhang, Aldo Lipani, and Emine Yilmaz. Learning neural point processes with latent graphs. In Proceedings of the Web Conference 2021, pp. 1495-1505, 2021.
Wei Zhang, Thomas Panum, Somesh Jha, Prasad Chalasani, and David Page. Cause: Learning granger causality from event sequences using attribution methods. In International Conference Machine Learning, pp. 1135--1225, PMLR, 2020b.
Simiao Zuo, Haoming Jiang, Zichong Li, Tuo Zhao, and Hongyuan Zha. Transformer hawkes process. In International Conference on Machine Learning, pp.
PMLR, 2020.
12

---

Published as a conference paper at ICLR 2022
A RELATED WORK
Our work adds the interpretability to temporal point process models and extends the logic learning method.
Temporal point process models have been an elegant tool for event data learning, either for future prediction (quasi-) causality discovery (Yan et al., 2019; 2016; Liu et al., 2017; Wu et al., 2018b). Traditional parametric models such as Hawkes process (Hawkes, 1971b) are built on simple assumptions such that past events will boost the occurrence of future events. To capture more complicated dynamics, Du et al. (2016a) proposed the first neural point process (NPP) model, where the intensity function is modeled by a Recurrent Neural Network (RNN). Mei & Eisner (2016) improved RMTPP by constructing a continuous tantinuuus-tmme RNN. Zuo et al. (2020); Zhang et al. (2020a) further leveraged the self-attention mechanism capture the long-term dependencies of events and meanwhile enhance the computational efficiency. While these neural-based point process models are flexible and excel at event prediction, they are hard to interpret. To add transparency to the black-box models, recently Zhang et al. (2021) introduced Granger causality as latent graph to explain point processes and the structures are jointly learned via gradient descent. However, Granger causality is still limited to the mutual triggering patterns of events. To incorporate more sophisticated and interpretable event patterns Li et al. (2020) proposed a Temporal Logic Point Process (TLPP), which constructs intensity function by pre-specified temporal logie rules. In fact, such temporal logic rule guided symbolic reasoning process will require highly expressive models such as Transformer to have good approximate their solutions (Finkbeiner et al., 2020). However, TLPP can not automatically discover rules and our TELLER overcomes this major drawback.
Probabilistic logic model dates back Markov Logic Networks (MLN) (Richardson & Domingos, 2006; Singla & Domingos, 2008), where Markov random field is used to model the first-order logic rules and their weights will be learned. Enhanced methods (Papai et al., 2012; Tran & Davis, 2008; Brendel et al., 2011) 1) are generally based on probabilistic graphical models, which allow for partial and noisy observations yet at the cost of intensive computation for inference. TLPP (Li et al., 2020) and our TELLER simplify their setting with two assumptions, i.e. causal direction and fully observed states, and then the temporal logic model can be formulated as a continuous-time point process, which bridges the first-order temporal logic rules to point process.
Logic learning methods include SATNet (Wang et al., 2019a), which transforms rule mining into an SDP-relaxed MaxSAT problem, and attention based methods (Yang & Song, 2019). Some works (Wang et al., 2017; Evans& & Grefenstette, 2018; Wei et al., 2019) formulated logic learning as learning an explanatory binary classifier. For example, Evans & Grefenstette (2018) constructed differentiable model that predicts the conditional probability of the outcome label for ground atom. Neural-LP (Yang et al., 2017) provided the first fully differentiable rule mining method based on TensorLog (Cohen, 2016), and Wang et al. (2019b) extended Neural-LP to learn rules with numerical values via dynamic programming and cumulative sum operations. In addition, DRUM (Sadeghian et al., 2019) connected learning rule confidence scores with low-rank tensor approximation. Among all these methods, Dash al. (2018) and Wei et al. (2019) first introduced the Column Generation algorithm in logic learning, which is the closest to our learning framework. However, all these methods are restricted to the static setting and cannot be directly implemented on event sequences.
B ALLEN'S S THIRTEEN TEMPORAL RELATION
Allen's 's original paper (Allen, 1990) defined 13 types of temporal relations between two time intervals. Specifically, define the time intervals for predicate FA and predicate FB as I,, = (t. tA, and Ita (tB,, tB,]] respectively, where tA, and f, are the transition times that the predicate enters the state, and and (A2 and LB2 are the time that the predicate leaves the state. The temporal relation, denoted as A type ( leg)) ), is logic function defined over the time intervals.
See below Table 5 for an illustration. As shown in this table, the temporal relation can be mathemati- cally evaluated by step function
g(s) = 1 (s 2 0)
and indicator function
<(8) = 1 0).
Considering the inverses of the listed relations plus the symmetric relation "Equal", there are a total of 13 relations.
In practice, to tolerate noise, i.e., the imprecisely recorded time information, it makes sense to introduce softened approximation functions for the step function g(s) and the delta function x(s) in
13

---

Published as a conference paper at ICLR 2022
Table 5: Interval-based temporal relations. Logic Function RA type B LEA Ita)
Temporal Relation
Illustration
Before B
g(tB, tAa
Cxr
Eap
Evp
A Meets B
n(tA, tB,)
Cu
A Overlaps B
g(tB, (A,) g(tB, [Aa)) .g(B3> t(g)
R4 fa. Aa)
toz
Starts B
n(lA, - -BB)) 9((B; - 1A22)
CA. To, Fa,
Fas
A Contains B
g(tB, - -A,)) )- g(tA2 - tB2)
t4.
A Finished-by B
g(L,, - -AA)) =((AA2 (B2)
Fu fay
Fay ly
Equals B
<((A, - LB,)) -x(1A2 -BB))
farm fa; Ka. fx.
replacement those used in the definitions of temporal relations in Table Step function g(8) can be softened as, e.g., a triangular function or a logistic function, i.c., ( min(1, max(0. 3s 4)),
9(8)
(11)
exp(-3s)
Delta function n(s) can be softened as triangular function Laplace density function, i.e., (()) max(0, min( + + - +
<<s) exp(-1sl/7)
(12)
Decaying parameters and y 2 can be pre-specified or treated as unknown parameters, which can be learned from data by maximizing the likelihood. In this paper, pre-specify these decaying parameters and make them frozen in the learning process (i.e., both the master and the subproblem).
C PROOF OF THE LIKELIHOOD
Given realization of all predicates {H(t))oCTETT one can write out the likelihood function in terms of the intensity function as follows.
For the head predicate Y. denote the dual conditional intensity function as X (t) and μ²" (t). Let p(tn+1/ HH,,, vff.) = 0) and p(tn-a/7He,, v(t,) 1) be the conditional density function of the next event time fn+1 given history and y(m,) 0, y(t,.. 1, respectively. Let Ft ytt,,.))nn = and F( (t,,) = 1) be the corresponding cumulative distribution function for any t > tn. Based the definition of the conditional transition intensity (or called hazard function), we have (t) p(U Hr,, ((,.) 0)
F(t He, ytn,) = =0) and H (²(1)= p(t (tm)) = =1)
(13)
(1 vtt..) 1).
From (13), we have
(t) dt log(1 FL v(l..) = 0)),
n² (t) = dt log(1 (t y(t.) = 1)). Integrating both sides, we can get the conditional density and the cumulative distribution function,
p(t)He,, 0) (t) exp
F(t v(t,) 0) = exp
X (s)ds
= =1) = =+ 1 exp
P (s)ds
F(tHH,,,
exp
1r (s)dss
14

---

Published as a conference paper at ICLR 2022
Let = 0. Given the transition times (42, 12....,,..) In), and suppose y(la) 0. y(tn) and the head
predicate is still in state at time T, the likelihood function can be factorized into all the conditional densities of each points given all points before it, i.e. the likelihood function is F(t) v(tx) 1)).
C p(tilp(ee [7te, v(to) = ()p(ta//4 He, v(t1)= 11. 1962 = 0)(1 ((nn),)((tnn
Plugging in the conditional density function and the cumulative distribution function, the likelihood expressed as,
C (xt) (- 10 X((s)ss) 1 (12) exp (- S 1 (s)ds)
(tn) exp ( -- (*()dss exp (- Sr 1² (s)ds).
which completes the proof.
D OPTIMALITY CONDITION AND COMPLEMENTARY SLACKNESS
We will provide more descriptions on the optimality condition and the complementary slackness, which provides sound guarantee to our learning algorithm.
Given the original restricted convex problem,
Master
w", ,,6, bj
argmin -( bo. b1) + ESEr cruf s.t. wy 20 fEF (14)
ar,hg.b
where parameter ef depends the complexity of rule f. such the number of predicates involved in f (i.e., rule length).
The Lagrangian of the original master problem is L(w, bo. b,, v) = - (w, b1. + Ecgu
FEF Σ Viwh
(15)
FEF
where vy 2 0 is the Lagrange multiplier associated with the non-negativity constraints of wy- As it a convex problem and strong duality holds under mild conditions. Define un", 1b by as the primal optimal, and v² as the dual optimal, then: -((w" by bi)
inf L(w bo (b.b)1.)) w,bo,b
(strong duality)
( -e le(u,bb.bi
inf w. w.bobb
Σ Cews E Eijws
fet
let
(16)
S - -ww", bī) + Σ Apuz - Σ
VING
FEF
S - (ww (b) + Σ Apw
JEF
Therefore, Σ uu3 = 0, for f F. This implies the complementary slackness, i.e., wj > 0 = V = Given the Marush-Kuhi Maahn-Tucker (KKT) conditions, gradient of Lagrangian L(w", by, bj. v*) w.r.t. w², bb, bj vanishes, i.e.,
W = 0 - vn 2 0,
(17)
v af(w, bu. b1)
+ Cj-
(18)
ows In summary, combining conditions (17) and (18), we obtain the optimalitiy condition, 1. if w > 0, then 2/ = O; 2. if w 0, then vi 2 O, where the gradient 1/ can be computed via (18).
w 66.00
15

---

Published as a conference paper at ICLR 2022
E ALGORITHM BOX
Our TELLER alternates between solving a restricted master problem and a subproblem. We summa- rize the algorithm in Algorithm and Algorithm 2. RMP indicates the Restricted Master Problem used to update model parameters. SP refers to the Sub-Problem used to construct new rule. Here we use RAFS as our search scheme.
Algorithm 1: TELLER (RAFS)
Input:
Timt MaxRuleL.en Output: ruleSet
stack
empty stack;
ruleSet < empty set;
w t O;
w RMP(b, w, ruleSet); // Initialize weights and bases. while RunTimeS TimeLimit do stack. Emppy(( then NewRule +- SP(b, w, ruleSet, None); // Search simple rule with length
1. if NewRule is None then
10
break; // If simple rule does not exist, algorithm ends.
11
else
12
RuleToExtend stack.top(;
NewRule t- SP(b, w, ruleSet, Rule/ToExtend):// Try to extend this rule. if NewRule None then stack f- empty stack:// If this rule can not be extended, do not revisit it.
14
16
fflentNeeruulsssMaakullleenn then
stack + empty stack:// If this rule reaches the maximum rule length, stop extending it.
18
NewRule then nuleSet.add(NewwRuee... stack.push(NewRulee
20
b. w < RMP(b, w, ruleSet):// After adding new rule, update weights and bases
22 return ruleSet
16

---

Published as a conference paper at ICLR 2022
Algorithm 2: SubProblem (SP)
Input: w, ruleSet, RoEteeEx
Output: NewRule
TempRelSet < (Ree Rey: Rme:..., Null); // Thirteen types of temporal
relation and Null (i.e., no temporal relation constraint).
bodyPredSet, Y defined by dataset;
candRuleSet + empty set;
RuleToExtend None then
// Search simple rule with length 1. for sYg in [+.-] do for X in bodyPredSet and (ign(X) in {+: -} do
for Rx,y in TempRelSet do
candRuleSet.add( (-)Y (-) Rx,y);
else
// Try to extend input rule.
for X in bodyyeeeSSt.
TeaffrrenneeRueeTTEeeeeee and for sign(X) in {+, -} do for X' in Rule'ToExtend do for Rx,x' y in TempRelSet do SandRuleSettadd(())))
11
RuleTooExtend A (-)X (Ax'in ToEeend Xx ));
14 Value, optRule +- Evaluate the subproblem objective and choose the smallest one from the candRuleSet; is if optaalu < then
// This rule is valid rule, i.e. it can improve RMP.
16
NewRule + optRule;
17 else
18
NewRule + None;
19
return NewRule
F SEARCH SCHEME FOR SUBPROBLEM: RULE-ADDITION-FRS SEARCH
The search scheme also be the mule-Addition-Fiss Search (RAFS). For the RAFS, the algorithm starts with an empty rule set and first focuses on discovering all rules with only one body predicate. Then assign each of them score that equals the objective function of the subproblem (pricing problem) applied to the rule. To expand the rules from length / to / / 1, we do the following: we process all generated rules that have predicates in increasing order of their score (since we to find a negative reduced cost), and for each such rule, we create new rules by appending an additional predicate together with the associated temporal relations. Whenever we find rule with a negative reduced cost, we add it to the current rule list. When our enumeration terminates, we return the best rules generated by the heuristic before proceeding to the next value When none of the rules with length can be extended to ( + we proceed to expand rule from length / + 1 to + 2. We may also pre-specify maximum rule length and set a time limit to the algorithm.
17

---

Published as a conference paper at ICLR 2022
G SYNTHETIC EXPERIMENT RESULTS
Dataset description: For synthetic experiment, we systematically considered 12 settings, where settings-(1, 7, 10, 11, 12] are reported as dataset- 2, 4,5, 63 in main text Section 4.2. Each setting corresponds to different rule weights, rule length and number, type of temporal relation, and intensity of free predicates.
To verify the similarity between the ground truth rules and the generated rules, we further utilize the Jaccard coefficient to measure the degree consistency between the generated rules and the truth rules. For the i-th ground truth rule data, let Ug be the set of rules in the i-th ground truth rule and Uj be the i-th rules generated by our method. The Jaccard is defined [0:0ü]
[0,00;1"
The Jaccard similarities (range from 0 to 1) are reported in Table 6 and Fig. 7. We explore how the sample size (600, 1200, 2400) and the search method (REFS and RAFS) will impact the performance. We plot the Jaccard of our method in different sample sizes and search methods on 12 settings (see Table for descriptions). The results are summarized Fig. 7. We find that the performance gradually improves with the increase of sample size, which verifies that sufficient data can benefit the learning performance.
As mentioned in Section 3.3, REFS will always extend the longest existing rule, and RAFS is always extending the shortest existing rule. As shown in Fig. 7, REFS achieves similar performance with RAFS on most settings.
Table Synthetic Data: Jaccard similarity with the Ground Truth Rules.
Setting
REFS-600
REFS-1200
REFS-2400
RAFS-600
RAFS-1200
RAFS-2400
Setting1
0.222
0.972
1,000
0.200
1.000
0.500
Setting2
0.059
0.000
0.250
0.200
0.200
0.222
Setting-3
0.182
0.286
0.750
0.286
0.375
0.750
Sctting-4
0.111
0.429
0.600
0.117
0.428
0.600
Setting-5 5
0.200)
0.571
1,000
0.125
0.500
1.000)
Setting-6
0,250
0.667
0.750
0.222
0,333
0.600
Setting-7
0,250
0.750
0.750
0.090
0.750
0.600
Setting-8
0.167
0.000
0.286
0.071
0.00
0.200
Setting
0.750
0.600
1,000
0.600
0.750
1.000
Setting-10
0.059
0.231
0,600
0.111
0.154
0.750
Setting-11
0.444
0.571
0,800
0.364
0.444
0.800
Setting-
0.375
0.429
0.750
0.091
0.429
1.000
Setting3
REFS
18F5
NAPS
RAFS
REFS
RAPS
R1875
+
RAPS
Setting:
Setting55
3449
Setting-7
3000
Setting 4
0.03
300
RETS
RIES RAYS
RGTS RAPS
RE15
RATS
2508
600
-106
255
12/5
2000
240
Figure 7: Jaccard similarity Synthetic Data: with REFS Results in Blue and RAFS Results in Red.
18

---

Published as a conference paper at ICLR 2022
Table 7: Synthetic Data Setting and Observations.
Observation
Setting-1: 1: Same body predicate intensity
Hard scenario since all body predicates have the same occurrence rate. TELLER can still recover the rules (Tahle 2) and their weights.
8
1.
1,
Setting-2: Low important weights
Lowering the important weights enhances the challenges in learning.
0..5
1,11
Setting-3: High important weights
relatively high rule weights. TELLER accurately recover the rules and their weights.
L.5.
= 1,1
Setting-4: Add rule length
Adding rule length enhances the challenges in learning.
1.1,2]
[1.1.1.1]
Setting-S: Add rule 1.1]
Adding one rule does not harm the rule recovery and learning performance.
A
1.1.1.1
Setting-6: Add one dummy predicate
Adding dummy predicates enhances the challenges learning.
w
1,1,
1,0..)
Setting-7: Different body predicate intensities
Body predicates have different occurrence rates. The MAE results outperform Setting-1
11
0..6
Setting-8: Different intensities and low weights
Lowering the important weights enhances the challenges in learning. but different intensities lower the challenges.
0.5.
=
[0.6, 0.8, 1.2, 1.4]
Setting-9: Different intensities and high weights
Both high weights and different intensities lower the challenges.
w 1.5, 1.5, 1.5]
0..6.0.8. 1.2,111
Setting-10: Different intensities and add rule length
Both adding rule length and different intensitics enhance the challenges.
1.
A 1.2 1.4]
Setting-11: 11: Different intensities and add one rule
Both adding rule and different intensities lower the challenges.
w = 1,, 1,
0..6, 1.2,
Setting- 12: Different intensities and add one dummy predicate
Adding dummy predicate enhances the challenges learning. but different intensitics lower the challenges.
1,
0.6. L.2, 1.4,0.2
19

---

Published as a conference paper at ICLR 2022
H REAL EXPERIMENT: MIMIC
H.1 SUPPLEMENTAL INFORMATION
MIMIC-II is dataset released under PhysioNet Credentialed Health Data License 1.5.0². was approved by the Institutional Review Boards of Beth Israel Deaconess Medical Center (Boston, MA) and the Massachusetts Institute of Technology (Cambridge, MA). The requirement for individual patient consent was waived because all the patient health information was deidentified. We manually checked that this data do not contain personally identifiable information or offensive content.
H.2 EYPERPARAMETER AND EXPERIMENT ENVIRONMENT
For the MIMIC dataset, we limit the maximum rule length to be 3, and the maximum #rules to be 20. The learning rate in solving the restricted master problem is x x10-4 The master problem is optimized by the SGD type algorithm and we choose to use the projected gradient descent to take care of the weight constraints. The batch size is 64. Each time we solve the subproblem, randomly selected 50% of the training data (i.e., patient sequences) to evaluate the subproblem objective. To exclude noisy and irrelevant rules, we clip the learned weights and discard these rules with weights smaller than is 10-2 in solving the restricted master problem. To further reduce the number of candidate rules, we threshold the subproblem gain as 10-3 i.e., we only include the candidate rules with negative cost smaller than -5 x 10-3, Our model is trained and evaluated using 16 processes parallel, server with a Xeon W-3175X CPU.
For the neural- neural-based baselines, we set: 1) TR-GRU with 4 hidden states and 4009 trainable weights, 2) RPPN with 64 hidden states, 64 embedding dimensions, and 33277 trainable weights, 3) CAUSE with 16 hidden states and 19312 trainable weights, 4) NHP with 8 hidden states, 814 trainable weights, 5)THP with 8 hidden states, 3608 trainable weights, 6) RMTPP with 32 hidden states, 5440 trainable weights, and 7) IPP with Gaussian kernels, = [1, 1, 11. [1, 0.8, 0.5].
H.3 PREDICATE DEFINITION IN MIMIC
H.4 DISCOVERED TEMPORAL LOGIC RULES
The discovered rules to explain the real-time urine have been reported in Section 4 Table 4. We list the discovered rules relate to the survival condition here Table
20

---

Published as a conference paper at ICLR 2022
Table 8: Defined Predicates in Our MIMIC-III Experiment.
Lab Measurements
Low/Noormal/HLigh-Syyya
Iow/Hoomaal/Higg-pp0222000
Low/NoormallHighhccVV
Low//Wormaal/H.hh-vvV
Loww/hoommal//iighhPoooassiiii
Low//Nozmaal/Hihh--SSddium
Low//loormaa//iigb-hhllooiil
Low//Normal/Htghh-BBU0
Low//Noziall/High-00PP
Lov//Normaal//iigh-BBCCCCoo
Loo///orraaa//igghh-HCCCooot
Low//Wormal///iill-attttiaaaaa
Lov//Worrmal//ighh##03333
Lot//Normaa//Hga00550220000
Output
LowUrine
Input
Colloid, Crystallid, Water
Drugs
Norepinephrine, Spinephrine, Dobutamine, Dopamine, Phenylephrine
Suvival Condition
Survival
Temporal Relation Type
Before, Equal
Table
Learned Rules with Survival head predicate for Sepsis Patients in MIMIC-III
Weight
Rule
Rule S:vvvvurvvivll + NormalsvR A Epinephrine
0.95
A (Epinephrine Before NotSurvival)
A (NormalsVR Before NotSurvival)
Rule 2:NotSurvival + HighAtteriale -
0.91
A (HighhrterialBe Before NotSurvival)
Rule 3:NorSurvival A
0. 82
A (Phenylephrine Before Not.Survival)
A (HighBUN Before NotSurvival)
Rule o
0.51
A (HighSodium Before NotSurvival)
+ Rule 5:NotSurvival http://wwwwaaagoioooooooooooooaa Nereppippppeeeeeeeeeeeeiee
0.53 A (HighSodium Before NotSurvival)
A (Norepinephrinn Refore NotSurvival)
Rule 4 Nomaalttriiaa
0.89
A (NormalAteriaalH Before Survivall
Rule h
0.55
A (HighPotassium Before NotSurvival)
Rule
Colliooottaaiiinnoooooooooo Colloid
1.19
(Highhotassiim Before NotSurvival)
A (Colloid Before NotSurvival)
Rule hrteruuuwwaaaaiiigggaaaeeeaaaaaa
1.00
A (HighlAterialPH Before NotSurvival)
A (HighläterialPi Before NotSurvival)
6.61
Rule 10:NotSurvival HighHC03 (HighHC03 Before Survival)
21

---

Published as a conference paper at ICLR 2022
1
REAL EXPERIMENT: CRIME
Crime Incident Reports are provided by Boston Police Department to document the type of each incident as well when and where it occurred (of Innovation & Technology, 2015).
1.1 SUPPLEMENTAL INFORMATION
This dataset is released by the Boston Department of Innovation and Technology under Open Data Commons Public Domain Dedication and License (PDDL). The publisher does not discuss how the data was collected and whether consent was obtained. We manually checked that this data does not contain personally identifiable information or offensive content.
Predicate Definition and Dataset statistics. We are interested in the top four most frequent crime types: vandalism, theft from motor vehicles, assault, and shoplifting. Another ten predicates are defined describe the occurrence time properties, such whether it is in the morning the afternoon, on weekdays or weekends, in spring or winter, etc. The set of defined predicates is displayed in Table 10. We consider all the crime reports from June 2015 May 2021 and split the data into 1879 sequences according to days. We randomly choose 80% of these sequences training data and the remaining as testing data. On average, each sequence contains 46.03 events.
Table 10: Defined Predicates for Crime.
Period of Crime
Spring, Summer, Aut umn, Winter, Weekday, Weekend, Morning, Afternoon, Evening, Night
Crime Types
Vandalism, Theft
Assault, Shopliftinng
Temporal Relation Type
Before, Equal
1.2 HYPERPARAMETERS AND EXPERIMENT ENVIRONMENT.
Our model is trained and evaluated using 16 processes in parallel, on a server with a Xeon W-3175X CPU. For this Crime dataset, limit the maximum rule length to be 2, and the maximum #rules to be 20. The learning rate used in updating model parameters in the restricted master problem 10-1 The master problem optimized by SGD with a batch size of 64. The subproblem objective function is evaluated on the entire training data. To exclude noisy and irrelevant rules, we clip the learned weights and discard these rules with weights smaller than is 10-2 in solving the restricted master problem. To further reduce the number of candidate rules, we set a threshold to the subproblem gain as x10 i.e., we only include the candidate rules with negative cost smaller than x 10-2
For the non-parametric baselines, we set: 1) TR-GRU with 4 hidden states and 1129 trainable weights, 2) RPPN with 64 hidden states, 64 embedding dimensions, and 27037 trainable weights, 3) CAUSE with 16 hidden states and 5872 trainable weights, 4) NHP with 8 hidden states, 382 trainable weights, 5YTHP with 8 hidden states, 2408 trainable weights, 6)MTPP with 32 hidden states, 2240 trainable weights, and P)I with 3 Gaussian kernels, [1, 1),
[1, 0.8, 0.5].
1.3 PREDICTION ACCURACY
Table 11: Crime: MAE of Event Time Prediction.
Larceny TheftFromMV
Larceny Shoplifting
Method
Vandalism
Assault
RPPN
0.881
1.137
1.185
0.777
HExp
0.761
0.949
1,912
0.704
TR-GRU
0.759
1.351
1,400
1.092
CAUSE
0.962
1.127
1.206
0.892
NHP
0.613
1.300
1.887
1.269
THP
0.973
1.043
0.957
0.939
RMTPP
0.874
1.021
1,059
0.763
IPP
0.908
1.274
1,508
1.179
TELLER
0.770
0.826
1,465
0.710
22

---

Published as a conference paper at ICLR 2022
Table 12:
Temporal Logic Rules Discovered for Four Types of Crime Events.
Weight
Rule
Rule 1:Vandalimm Shoplifting
3.84
A(Shoplifting Before Vandalism)
Rule 2:Vandalism TheftFromMy
1.83
A(IheftFromMV Before Vandalism)
Rule
A Shoplifting
0.43
AShoplifting Before Vandalism)
A A(TheftFromM/ Before Vandalism)
Rule 4:TheffFromMV Shoplifting hffh
2.46
(Shoplifting Before TheftFromMV)
Rule F:TheftFromM < The A Summer
1.42
A A(TheftFroMMV Equal Summer)
A (TheftFFooM/ Before TheftFromM))
Rule 6 Assault Weekend
0.40
A (Weekend Equal Assault)
(Assault Equal Assault)
Rule 7:Assault < Sholliffiinggggggggn Assault
3.62
A (Shoplifting Before Assault.)
(Assault Before Assault)
Rule 8:Shoplifting Theffrrroor
1.67
A A(TeeftFromWV
BeetoooMMeeeeoreeeee Before Shoplifting)
Rule 9:Shoplifting Stgpgliiitttttnggooooooooggnggn Vandalism
1.14
A (Vandalism Before Shoplifting)
(Shoplift Before Shoplifting)
Rule 10: 10 +
A Weekday
1.30
(Shoplifting Before Shoplifting)
A (Weekday Equal Shoplifting)
The mean absolute error (MAE) the predicted event times are displayed in Table Our model outperforms other models in predicting TheftFromMV. It has comparable performance with the Hawkes baseline on the remaining three tasks. We can think of Hawkes process as a special case of our model and this is especially true if we restrict our model to learn short rules.
1.4 DISCOVERED RULES
We displayed the discovered important rules in Table 12, from which one can observe the following crime patterns. Shoplifting and The may trigger Vandalism. One explanatory reason that larceny may involve break-in and destruction of security devices (Rule 1, 2, and 3). Shoplifting triggers TomM.. These two events are special types larceny, and thus they may exhibit similar crime patterns (Rule 4). TVe exhibits self-exciting (i.e., clustering) patterns in summer. This may due to that winter is extremely cold in Boston, and summer, however, nice period of the year for outdoor activities and thus motor vehicles may pour into the area, which potentially increases the likelihood of theft (Rule 5). Assault shows a self-cxeiting pattern on weekends. People tend have more social activities weekends, which increases the possibility of domestic violence and affray (Rule 6). Shoplifting triggers Assault. This might be explained by the fact that if shoplifting spotted the scene, the thief may have a physical conflict with the security guard (Rule 7). TheftFromMV and Vandalism will work together to trigger Shoplifting, which is consistent with our previous observations and 2 (Rule 8 and 9). Shoplifting is self-exiting on weekdays. Stores are busier on weekends than on weekdays, and thus weekdays might be better choice for shoplifters (Rule 10).
23


Reviews:
[{"review_id": "nEetOEhncPK", "reviewer": "Reviewer_AiEu", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\n1.\tStructure and presentation\n\nThe paper is not self-contained on the theoretical basis. It especially lacks necessary explanations on the relationship between interpretable temporal logic rules and temporal point processes. From the problem to the output (such as the derived rules in Table 2), the paper does not seem to show any strong dependencies on the temporal point process (TPP) model. Unfortunately, it neither fully demonstrates and constructs the complete problem background nor provides sufficient technical details on the critical process (rule generation, searching/expanding algorithm, expert knowledge templates). Instead, it took a lot of space to define a two-stage solution framework. For me, this is not the most valuable contribution.\n\nFigure 1 tries to convey too many technical details that are difficult for readers to understand, especially when reading Section 1, until it was cited in the discussion of “Search algorithms” in Section 3.1 to show the necessary details of designing the REFS algorithm. Therefore, figure 1 should focus on TELLER’s core idea rather than technical details in the paper’s introduction part.\n\nThe situation in Figure 2 is similar, where the author uses the concept of TLPP before its theoretical preliminaries are introduced in the main text. In the discussions of “Logic-informed intensity function”, the author may consider guiding readers to understand the concept and calculation method of intensity function using case studies designed in Figure 2, rather than directly referring to it without any explanation.\n\nThe position of Figure 3 is also problematic. It appears in Section 3.1 and is not quoted by any text until the end of Section 3.4.\n\n2.\tNovelty and contribution\n\nFor the concepts introduced in Section 2, the authors should clarify which are cited and new tools designed by TELLER. More importantly, it is necessary to reflect the differences between the related work built on TPP model and this study. \n\nTo my understanding, it is not an outstanding innovation to define rule discovery as a two-stage optimization problem. The most valuable contribution is in designing a sound rule generation or expanding algorithm in the sub-optimization problem (near-optimal).\n\nAlthough the paper claimed: “Our problem is even more challenging compared to traditional inductive logic programming cases due to the sequential properties of the data and the presence of temporal information.” However, we do not see any theoretical analysis to show how TELLER has reduced the calculation?\n\nSince the event sequences and values are discrete, is this problem challenging to solve in the case of a limited number of basic events (the number of variables considered in the case analysis is small in reality)? That is, how big is the size of the searching space of the $P_Master problem (Equation 4) in real practices?\n\nIn response to this issue, the paper skipped several key details when designing the search algorithms in Section 3.3: (1) Why the complexity is O(d)? In such a not-complex solution space, why should we resort to a complicated searching scheme instead of enumerating? (2) When extending the original rule, TELLER considers “the signs and possible temporal relations with the head predicate”. However, the paper did not show specific principles and rules to do this. Many detailed questions need to be explained: Is the extending process following any temporal sequential way? Can it support the negation pattern? Can it discover the loop structure? And logical branch structure? These factors will significantly affect the ability of the extending algorithm to find effective rules\n\nIn Section 3.4, the author mentioned that TELLER's scalability is an advantage over brute-force solving algorithms. Although there can be many event sequences in a complex example, what kind of problem will have so many predicates? For example, we see the cases in the experiment part are: \n1. Synthetic data: predicate set {A,B,C,D}, head {E}.\n2. MIMIC-III:  62 predicates as stated, head {LowUrine, Survival}.\n\nFinally, we can also see from Crime experiments that users still need to define promising predicates to guide the algorithm to discover rules. It seems the distance between reasonable predicates and truth rule is not far away, or we can say that in the case of limited predicates and temporal relations, the best results can be obtained through brute-force enumeration and evaluation. Therefore, the authors should clarify whether there are problem scenarios that need to deal with massive predicates to prove the necessity of designing TELLER.\n\n3.\tTechnical details\n\nThe authors can consider discussing why we need to introduce rule set weights in logic-informed intensity function.\n\nThe paper mentioned that “the initial rule set can be an empty set or any pre-defined small set”. Will an accurate pre-defined set contribute to the accuracy of the algorithm? Better to provide some experimental results and analysis.\n\nIn the analysis of TELLER’s scalability, the author mentioned: \"In practice, setting the time limit is proven to work well and the most important rules are likely to be discovered.\" This is a key observation in evaluating TELLER. Therefore, it is recommended to design different time window parameters to verify the effect of the algorithm.\n\n4.\tThe subjectivity of the experimental results\n\nIn Table 1, the author gives five properties but does not explain how to decide whether a method is of or not of these properties. Table 1 shows several arbitrary comparison results without seeing any justified process. It is recommended that the authors provide a detailed definition for several fundamental properties such as Parsimonious and Higher-order interaction and justify the results through a case study or statistical results.\n\n5.\tReproducibility\n\nThe author did not attach their codes, which affected the evaluation of the paper’s reproducibility. \n\n6.\tMiscellaneous and language problems\n\nThrough careful check, it is found that the font size of the paper is not consistent. Starting from the \"Logic-informed intensity function\" section on page 4, the font suddenly becomes smaller. I am not sure whether this meets the ICLR format requirements because the content from Page 4-8 may exceed the limit.\n\nThe first paragraph in Section 3.4 is a redundant summary that deserves to be simplified.\n\nSection 1, Paragraph (Para) 2, “These domain knowledge can be summarized as” -> This domain knowledge\n\nSection 1, Para 3, “without the need to discretize the time horizon into bins.” Not clear, what “bins” refers to ?\n\nPage 2, Para 5, “where the number of variables are too large to be considered explicitly.” -> is too large to\n\nPage 3, Para 6, “the body part of the formula indicate the evidence” -> indicates\n\nPage 4, Para 4, “-1 indicates negative effect,” -> a negative effect\n\nPage 4, the last line, “requires enumerating exponentially large set of combinations” -> an exponentially large set\n\nPage 5, Para 3, “the set of variables (the $w_f$s) we are optimizing on”. It is inappropriate to use plural “s” here.\n\nPage 6, Para 6, “This provides performance guarantee for speedup algorithms.” -> a performance guarantee\n\nPage 6, Para 6, “we do not need to consider rules with length exceeding $H$.” -> with a length exceeding $H$\n\nPage 6, Para 6, “we mean if the conjunctions of the input predicates is important” -> are important\n\nPage 8, the last paragraph, “Among all these predicates we are interested in reasoning about two predicates.” Ambiguous, should be separated by commas\n\nPage 9, Para 1, “is a important signal for septic shock” -> an important \n\nPage 9, the last paragraph, “We propose a promising TELLER algorithm to learn interpretale temporal logic rules” -> interpretable\n", "summary_of_the_paper": "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.", "summary_of_the_review": "In summary, although the paper presents a solid theoretical discussion and a comprehensive verification, it still has defects in the overall structure, the clarity of innovation, the challenges of the problem scene, and some method details. As a result, I do not recommend accepting the paper even though it shows many merits.\n\nRevision Notes (2021-11-26):\n\nMost of the problems have been appropriately resolved or explained in the revision. The quality of the paper has been significantly improved and exceeded the acceptance threshold. Therefore, I have raised my score to 6.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "cBPVHZlutky", "reviewer": "Reviewer_BWwC", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I find the paper quite interesting. Admittedly, the proposed optimization problem is a very difficult one due to the high dimensionality of the parameter space and it is almost hopeless to find the global optimum. The proposed TELLER algorithm is not perfect, but the authors explain the idea very well and the algorithm makes heuristic sense. The problem this paper aims at solving is an important one and I can see that it will make a difference in many applications. I especially like the fact that domain experts were brought into the real data analysis and the results look interesting. The only concern I have is about the stability of the algorithm, which may be of critical importance in practice. Specifically,\n\n1. In equation (6), how should the complexity $c_{f} $ be determined? I think they determine the sparsity of the solution $w$, hence is important. Simply saying that \"$c_f$ can be the rule length\" is a bit arbitrary. Wouldn't it make more sense if a tuning parameter, say $\\lambda$, is introduced to balance the negative likelihood and complexity penalty? In such case, the Master Probe would become minimizing $-\\ell(w,b_0,b_1)+\\lambda\\sum_{f\\in\\bar{\\mathcal{F}}}c_fw_f$ and $\\lambda$ can be chosen by some sort of cross-validation.\n\n2. How much impact does the initial subset $\\mathcal{F}_0$ have on the final solution? Can some simulations be conducted to show the impact of $\\mathcal{F}_0$？\n\n3. In synthetic data experiments, the number of true logic rules is at most 4. What would happen if this number continues to grow? In this case, the search space for the optimum will be much larger and how well would the algorithm work?\n", "summary_of_the_paper": "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.\n\n\n[1] Shuang Li, Lu Wang, Ruizhi Zhang, Xiaofu Chang, Xuqin Liu, Yao Xie, Yuan Qi, and Le Song. Temporal logic\npoint processes. In International Conference on Machine Learning, pp. 5990–6000. PMLR, 2020.", "summary_of_the_review": " The problem this paper aims at solving is an important one and I can see that it will make a difference in many applications.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "_1N6UJ2S4U_", "reviewer": "Reviewer_sdkz", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Intepretable models are increasingly relevant as ML models are applied to more and more domains where safety and fairness are important -- characteristics that are hard to judge for traditional black box models. The method presented is novel and gets good improvements on existing state of the art methods on synthetic and real data.", "summary_of_the_paper": "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.", "summary_of_the_review": "Novel method which gets improvements on SOTA", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "GT3Uv55WAL7", "reviewer": "Reviewer_GzHz", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength: \n* The problem of learning temporal logical rules is very important and interesting. \n* The key idea is novel and interesting. \n* The experiments are extensive, which are conducted on both synthetic data and real data. \n* There are many case studies and learned rules, which is interesting. \n\nWeakness:\n* It would be better if the authors can provide references for the temporal logic formula in the background section. \n* There is a number of works for learning logical rules (e.g., Neural-lp, DRUM). It would be better to claim that the key difference between temporal logical rules and ordinary logical rules, and how temporal logical rules generalize them.\n* The following paper is also relevant, please discuss this paper in the related work section. \n\nWang, Po-Wei, et al. \"Differentiable learning of numerical rules in knowledge graphs.\" International Conference on Learning Representations. 2019.\n\n", "summary_of_the_paper": "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.\nThe authors conduct extensive experiments on both synthetic data and real data. \n", "summary_of_the_review": "In summary, it seems that this is a novel and interesting paper for learning temporal logical rules with solid experiment results. I am familiar with logical rule learning but not the temporal point process, so I am not sure about my evaluation of the temporal process part. But in general, learning temporal logical rules is very interesting. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper has been independently evaluated by four expert reviewers. After discussion with authors, three of them set their recommendations at marginal acceptance, one at straight accept. Perhaps the key criticism involved limited rigor of theoretical justification for the proposed method, but it appears to be applicable in practice as the empirical results suggest. All things considered, I am leaning towards recommending that this paper is accepted for ICLR 2022.
Decision: Accept (Poster)