Deep Lifetime Clustering
Authors: S Chandra Mouli
Leonardo Teixeira
Jennifer Neville
Bruno Ribeiro
Venue:  (2020)
Keywords: Lifetime Clustering
Deep Learning
Survival Distributions
Kuiper two-sample test

Abstract: The goal of lifetime clustering is to develop an inductive model that maps subjects into $K$ clusters according to their underlying (unobserved) lifetime distribution. We introduce a neural-network based lifetime clustering model that can find cluster assignments by directly maximizing the divergence between the empirical lifetime distributions of the clusters. Accordingly, we define a novel clustering loss function over the lifetime distributions (of entire clusters) based on a tight upper bound of the two-sample Kuiper test p-value. The resultant model is robust to the modeling issues associated with the unobservability of termination signals, and does not assume proportional hazards. Our results in real and synthetic datasets show significantly better lifetime clusters (as evaluated by C-index, Brier Score, Logrank score and adjusted Rand index) as compared to competing approaches.

Under review as a conference paper at ICLR 2020
DEEP LIFETIME CLUSTERING
Anonymous authors Paper under double-blind review
ABSTRACT
The goal of lifetime clustering is to develop an inductive model that maps subjects into clusters according to their underlying (unobserved) lifetime distribution. We introduce neural-network based lifetime clustering model that can find cluster assignments by directly maximizing the divergence between the empirical lifetime distributions of the clusters. Accordingly, we define novel clustering loss function over the lifetime distributions (of entire clusters) based on a tight upper bound of the two-sample Kuiper test p-value. The resultant model is robust to the modeling issues associated with the unobservability of termination signals, and does not assume proportional hazards. Our results in real and synthetic datasets show significantly better lifetime clusters (as evaluated by C-index, Brier Score, Logrank score and adjusted Rand index) as compared to competing approaches.
INTRODUCTION
Survival analysis is widely used to model the relationship between subject covariates and the time until particular terminal event of interest (e.g.. death, quitting of social media) that marks the end of all activities (or measurements) of that subject (known as the liferime of the subject). For instance, subject's logins a social network are her activities and the time until she quits the social network permanently is her lifetime.
The lifetime of a subject can be unobserved for two possible reasons: (a) the terminal event was nightccessore. i.e., the subject did not have a terminal event within the finite data-collection period, or (b) the terminal events are inherently unobservable. Right-censoring happens for instance when patient is still alive at the time of data-collection. Unobservability happens for instance, in social networks, when a subject simply stops using the service but does not provide a clear termination signal by deleting her account. In such scenario, the terminal events remain unobserved for most if not all subjects, even if the subjects quit the service within the data-collection period.
Numerous survival methods have been proposed (Witten and Tibshirani 2010a; Hothorn al. 2006, Ishwaran et al., 2008) to predict the lifetime subject given her covariates and her activi- ties/measurements for brief initial period of time, while also accounting for right-censoring. More recent deep learning models for lifetime prediction (Lee et al., 2018; |Ren et al. 2018 Chapfuwa al., 2018) have achieved much success due to their flexibility model complex relationships, and by avoiding limiting assumptions like parametric lifetime distributions (Ranganath et al.) 2016) and proportional hazards (Katzman et al.) 2018). In scenarios where terminal events are never observed (unobservability). it is a standard practice to introduce artificial termination signals through a predefined "timeout" for the period of inactivity, i.e., social network user inactive for m months has her last observed activity declared a terminal event. Such specification is typically arbitrary and can adversely affect the analysis depending on the "timeout" value used.
Notwithstanding the fact that lifetimes are hard to predict without termination signals in the training data, we are generally interested clustering subjects based on their underlying lifetime distribution to improve decision-male making. Applications include identifying disease subtypes (Gan al. 2018). understanding the implications of distinct manufacturing processes on machine parts, and qualitatively analyzing different survival groups in social network. Although accurately predicting time-to- terminal-even for an individual important in a variety of applications, lifetime clustering plays a complementary role and provides more holistic picture.
Lifetime clustering remains a relatively unexplored topic despite being an important tool. Although traditional unsupervised clustering methods such as k-means and hierarchical clustering are popular

---

Under review as a conference paper at ICLR 2020
for this task (Bhattacharjee et al. 2001: Sorlie et al. 2001 Bullinger et al. 2004). they may produce
clusters that are entirely uncorrelated with lifetimes (Gaynor and Bair 2013). Semi-supervised
clustering (Bair and Tibshirani 2004) and supervised sparse clustering (Witten and Tibshirami (0100)) employ a two-stage lifetime clustering process: (i) identify covariates associated with lifetime using Cox scores (Cox 1992), and (ii) treat these covariates differently while performing k-means clustering. They assume proportional hazards (i.c., constant hazard ratios over time) and require the presence of termination signals. Furthermore, a decoupled two-stage process such the above is not guaranteed to obtain clusters with maximally distinct lifetime distributions; rather, we require an end-to-end learning framework that prescribes a loss function specifically over the lifetime distributions of different clusters.
In this work we tackle the important task of inductive lifetime clustering without assuming propor- tional hazards, while also smoothly handling the unobservability of termination signals.
Contributions. (i) We introduce DeepCLife, an inductive neural-network based lifetime cluster- ing model that finds cluster assignments by maximizing the divergence between empirical (non- parametric) lifetime distributions of different clusters. Whereas the subjects of different clusters have distinct lifetime distributions, within cluster all subjects share the same lifetime distribution even if they have different lifetimes. Our model is robust to the modeling issues associated with the unobservability of termination signals and does not assume proportional hazards.
(ii) We define a novel clustering loss function over empirical lifetime distributions (of entire clusters) based the Kuiper two-sample test. We provide tight upper bound of the Kuiper p-value with casy-to-compute gradients facilitating its use as a loss function, which until now was prohibitively expensive due the test's infinite sum.
(iii) Finally, our results on real and synthetic datasets show that the proposed lifetime clustering approach produces significantly better clusters with distinct lifetime distributions (as evaluated by Logrank score, C-index, Brier Score and Rand index) as compared to competing approaches.
2 FORMAL FRAMEWORK
In this section, formally define the statistical framework underlying the clustering approach introduced later in the paper. Notation remark: We use superscript (u) to refer to variables indexed by a subject u and use subscript k to refer to random variables indexed by a random subject of cluster k. See Table for a complete list of all the variables and their meanings.
We assume that there are distinct underlying clusters with different event processes describing the activity events of random subject (e.g., logins to a social network, measurements of a patient) in the respective clusters. To make these notions more formal, we introduce our event process.
Definition 1 (Abstract Event Process). Consider the k-th cluster. The Random Marked Point Process (RMPP) for the activity events is 42 {Xk, (AA,s, MR,3, YK.i)enN, θ&} over discrete times = 0....... where X₃ is the random variable representing the covariates of a random subject in cluster k, O2 is the time to the zeroth activity event (joining), MR.s represent covariates of event i, YK, is the inter-event time between the i-th and the (i 1)-st activity events (e.g., logins), and A indicates an event with a termination signal (death), otherwise As. O. All these variables may be arbitrarily dependent. This definition is model-free, i.e., we will not prescribe model for Qk-
We observe the RMPP over a time window [0, tm]. Using the above formalism, we define the true lifetime of subject in cluster as the sum of all inter-event times until termination signal A = is observed.
Definition 2 (True lifetime). The random variable that defines the true lifetime until the terminal event of a subject in cluster k is Tk- = max; (Ergi Yo. Ie Ak.tr)
The true lifetime Tj is unobserved if: (a) the terminal event Ag.s 1 does not occur within the observation time period [0, tm]. or (b) the termination signals are inherently unobservable. Now, the true lifetime distribution of a subject in cluster & is defined as the probability that the subject has at least one more activity event after time i, and is given by (t) = P(T > 1] = 1 - Ft()), t NU [0), where Fi (t) is the underlying cumulative distribution function (CDF) of Tk. Note again that all the subjects of a cluster share the same lifetime distribution.
2

---

Under review as a conference paper at ICLR 2020
Table I: Table of notations.
Notation
Description
Notation
Description
(u)
Variables indexed by subject Random variables indexed by random subject of cluster & Joining time of the subject
T
True lifetime of the subject (unobserved) Observed lifetime of the subject
H
X
Time elapsed since last observed ac- tivity event before im CDF of the true lifetime ''' True lifetime distribution (= CCDF of true lifetime 7)
X
Covariates of the subject
F
Y
Inter-event time between i-th and (i-1)-
1)-
S
activity events
M;
Covariates of event i
S
Empirical lifetime distribution
A
A; = 1 denotes whether i-th activity
S(t]
S indexed by E 1,,
event is terminal
Training data. Our training data D consists of subjects from K underlying (hidden) clusters with distinct lifetime distributions S₁. for {1..... K}. For a subject u E 'D we observe the following quantities (x("), {(M[W) (w) ((")) ) (t.) (("),, where x((), """,,"" and f(") are analogously
defined as in Definition but for a given subject u. Q(") is the number of observed activity events
of u after her joining and before time t. The training data may may not contain the termination signals, (A(")) Ji=1,
(*)
((a)(()) (fm) where A(n)) = 1 indicates that event i was a terminal event for subject
(e.g., death). Termination signals are typically available healthcare applications, whereas in the
case of social networks, we usually do not observe the termination signal (i.e., account deletion) for any subject.
We define the observed lifetime of subject as H(u) =- >g (tm) y(!e), i.e., the sum of all the inter-event times within the observation period [0, fm] In the absence of termination signals, we additionally define inactive period as the time elapsed since the last observed event of subject u, shows the true lifetime, the observed lifetime, and the inactive period for four users of two different clusters in the training data. The events are observed (denoted by solid circles) only till the time of measurement fm. whereas the rest of the events are right-censored (denoted by solid diamonds), The termination signal (denoted by dotted diamonds) may be unobserved even if occurs before tm (eg., Uz).
given by (*) fm ((w) H(") We use (()) and (()) only during training. Figure I
Test data. For new test subject, we can only observe her covariates and her activity events for a brief initial period of time T since her joining. Formally, we observe the following quantities (x("), ((M,")) (i("))))))))))))))) (()) (g())))))) _(a)). The goal of inductive lifetime clustering is to be able to assign a cluster for a new unseen subject within r time her joining. Note that since H()) and x (u)
are tied to fmm they cannot be computed for test subjects.
Lastly, we formally define our clustering problem.
Definition 3 (Clustering problem). Consider a datasel 'D with N subjects. Our goal is to find mapping k. (x("), {(M(") ,,("")) (( (B())) + (l....,KK) K), that inductively maps subject covariates and observed activity events for brief initial period of time 7 into clusters, such that the divergence between the empirical lifetime distributions of these clusters is maximized, i.e..
R
arg max REK
min (.E(L....K ifj
((5(()),
where KC is a set of all mappings, (k))) the empirical lifetime distribution of subjects in D mapped to cluster k through k, and A is an empirical distribution divergence measure.
n² optimized in this fashion guarantees that subjects in different clusters have different lifetime distributions
'eee Appendix A.5 for why wish to maximize the minimum divergence across all pairs instead of the sum of divergences all pairs.

---

Under review as a conference paper at ICLR 2020
I Fm
T
H
x
U1 (Xig)
26, X:n)
F)
1- Cluster (low-risk)
U2 (xix)
25, X
M)
U3 (xite
30,
X
grnde F)
Zeroth event (jining)
Observed events
P
U4 (xxip] = 35,
Unobserrved events
Last observed event
Termination signal (possibly unobservable)
Cluster (high-risk)
Observation period
Depicting two clusters (low-risk and high-risk; shown by the truc lifetime distributions) following different RMPPs, cach with two subjects. T(") is the true lifetime of subject (may be unohserved due to right censoring or due unobservability termination signals). H(") her observed lifetime, the period between the first and the last observed event. x(") is the time between the last observed event and fm. and ((*)(tm)) is the number of events of after her joining and before fm-
Figure I:
3 THE DEEPCLIFE MODEL
In this section, we propose a practical lifetime clustering approach using neural networks that optimizes Equation (T. Let 'D be the training data as defined in Section 2 Since we want to maximize divergence between empirical lifetime distributions, we assume discrete times (relative to subject joining). E 10.1..... ) where fmax = maX ((") the maximum observed lifetime of any subject u E D. Note that it is sufficient to define the empirical distribution till faax since we have not observed any subject with lifetime greater than mmxx.
3.1 CLUSTER ASSIGNMENTS : 0g ox (W1)
We define neural network that takes user covariates and the event data for a subject u during a brief initial period after her joining as input, and outputs her cluster assignment probabilities, k (W1) for all & E KL.
(oa +5), W1 a x("(()) = (x(x), (M y(()), 1 Fi=1
where W, are the weights of the neural network. The final layer of y is softmax layer with K units. Figure 2 depicts y as feedforward neural network with L. hidden layers, although our model not restricted to a feedforward architecture. In our experiments, we compute summary statistics over the observed events {M (w) Ji in order to make it compatible with the feedforward architecture.
3.2 PROBABILITY OF TERMINATION: g(4) (W₂)
During the training of our model, we require termination signals or probabilistic estimation of the termination signals in order to write the likelihood of the model. Given the model parameter W2, we define ((a) (W2) as the probability that the last observed event of u was terminal, i.c., u will have no future activity events after the last observed event.
If the termination signals A." are observed in the training data (e.g. healthcare), clearly ((w) (W2) ( (i.e., W2 is ignored).
When such termination signals are unobservable (e-g., social network), existing survival methods commonly use timeout window of predefined size W fixeed over the inactive period x (() to specify the probability of termination as ((w)(W (wnee)): 1 (4) > However, such specification is arbitrary and precludes any learning of the window size parameter W Wixee- Instead, we model the
latent termination probabilities 3(*) (W₂) using a smooth non decreasing function of (("), i.c., higher the period of inactivity, higher the probability that the last observed event was terminal.
4

---

Under review as a conference paper at ICLR 2020
1.00
Gode
Group Group
Emolrical Distribution Divergenoe Lose
0.75
P (CC37)
Empriior small surppl
0 0.50
Thm
Empirical
0.25
Distributions
Kaplan- Maier Estimator
1.00
Output Layer
(b) Overlapping life- time distributions in- validates proportional
(c)
True lifetime distributions (dashed)
(soft K clustors
empirical dis- tributions (solid)
Profubiilty
hazard assumption
termination
W4
Wi
Ixput
FT
X
Ma pe y,
Sggar Eoeit priple
user
Dri
(a) Model architecture
(d) Samples 100
(c) Samples 1000
Figure 2: (a) Feedforward neural network g(: W1) outputs the cluster assignments for a batch of users. The cluster assignments along with the probability of termination is used to obtain lifetime distributions of each cluster using Kaplan-Meier estimator. Finally, logarithm of Kuiper p-value upper hound is used as the divergence loss A. (b) Lifetime distributions can have different shapes and cross each other, violating proportional hazards assumptions. (c) Divergence metric must account for uncertainty in the distributions, otherwise divergence maximization leads to imbalanced clusters. (d-e) Upper and lower bounds of the logarithm of Kuiper p-value when varying the Kuiper statistic D) +7.
If the termination signals A, are unobservable in the training data D (e.g.. social network), we use ((w) (W₂) 1 (2 where W2 O.
3.3 EMPIRICAL LIFETIME DISTRIBUTION OF CLUSTER k SW1, W2; D)
Given the training data D and model parameters W1 and W2, we can obtain the soft cluster assign- ments 0k (W1) and the probability of termination g(v) (W2) for all subjects E and clusters k E (1... K} as shown in Section 3.1 and Section 3.2 In this subsection, we obtain the empirical lifetime distribution of all the clusters 1... K. using the Kaplan-Metts Meier estimates (Kaplan and Meier 1958). We do not assume parametric form for the lifetime distribution, and rather use empir- ical distributions our optimization allow lifetime curves of any shape (Figure 2b). Kaplan- MMier estimates are maximum likelihood estimate of the lifetime distribution of set of subjects assuming (a) hard memberships (each subject entirely belongs to the set) and (b) the presence of termination signals. We modify the estimates to account for partial memberships and probability of termination instead.
Proposition 1. Given the training data D. a cluster the cluster assignment probabilities {ar (w)) (Wi))weD, and the probabilities of termination (W2)) the maximum likelihood estimate of the empirical lifetime distribution of cluster k is given by,
81 (W; - (W,, W2;D)
S2W W:; W) =
(3)
3k. (wi;
1=0
for all t E {0, 1.....,tmaa? where, sx(W1; = EmED 1HH()) 2 5] ag (w) (W1), is the expected
number of subjects in cluster k who are at risk (of termination) at time j. and, dy We; D)[b]
(w) EvED 1[H(">) j] g(v) (Wa) ox (W1), is the expected number of subjects that are predicted to have had a terminal event at time
The proof is presented in the supplementary material.
5

---

Under review as a conference paper at ICLR 2020
3.4 EMPIRICAL DISTRIBUTION DIVERGENCE LOSS
A(Sa; Sc)
We rewrite the objective function of lifetime clustering from Definition 3 with respect to the model parameters W1 and W2 as follows,
arg max min A S.)
WT, W
(4)
W1.W2 (JE(1... K) (()
where S, is the empirical distribution, shorthand for the vector S, W2; D), and A is diver- gence measure between two empirical distributions.
We note the following essential requirements for the divergence measure A: (a) A defined over empirical distributions must take into account sample sizes, (b) A should have easy-to-comput gradients since it is used an objective function to train neural networks, and (c) A should not assume proportional hazards, and should allow for crossing lifetime curves (see Figure 2b)..
Divergence measures such Kullback-Leibhe et al. 2012) fulfill (b, c) but not (a), and will result in sample anomalies as depicted in Figure 2c (also seen our experiments: Figure 3d). Logrank test (Mantel 1966). commonly used for comparing
(Kullback and Leibler 1951) ) and MMD) (Gretton
lifetime distributions, fulfills (a. b). but has low statistical power when the proportional hazards
assumption not met (Peto and Peto 1972. Bland and Altman 2004) (e.g., Figure 26 Finally, p-value from two-sample tests such as the Kolmogorov-Smingg
(K-S) test (Massey Jr 1951) fulfill
(a, c), but not (b) as they require the computation of an infinite sum, resulting in an impractical objective function unless heuristic approximations are made.
We propose to use the Kuiper test (Kuiper 1960), a two-sample test closely related to the K-$ test with increased statistical power in distinguishing distribution tails (Tygert 2010). Specifically, we define (S... S,):= log KD(S St)), where KD is the p-value from the Kuiper test between S. and Sg. Our choice of the Kuiper test is because it is amenable to upper and lower bounds as shown next, thus avoiding the prohibitive heuristic approximations of infinite sums.
Proposition 2. (Bounds for Kuiper p-value.) Given two empirical lifetime distributions So and So with discrete support and sample sizes Tly and ny respectively, define the maximum positive and negative separations between them,
Di (o(.....foor.
($a[4 S,(1)),
DT,- tm))
($.(4) Sa(())
sup
sup
The Kuiper test p-value Kuiper 1960) gives the probability that A, the empirical deviation for n. and ng observations under the null hypothesis S. Sb exceeds the observed value V D. DT,6
KD(S So) PIA V1 2 Σ
(4j²>2, 1)e 1)e-21"X2 22
(5)
Aa.b Ma,b + 0.155 + 0.24 )V and Ma. nams is the effective sample size. Then, the tnt
MM.bb
upper bound for the Kuiper p-value is,
KD(S.: <min 1, 2- 11 a. 2 1] (w(rdb. w(1, da,0) + v(ril Aa,))
(1o)
(up) + (up) )a,b) - w(ra.b) b .dabb)
(up)
where (4-22)=44->2-
w(r, A)=-re 2² (10)
V2ha, -
and,
(up) rabb
V2ha,
The proof is presented in the supplementary material.
Figures 2d and 2e show empirical results of the upper and lower bounds as a function of V
D+ against the expensive heuristic computation where the infinite sum in Equation 5 is
approximated with 10s terms (Press al. 1996). We optimize Equation (4) with A(S., So
-log (S, Sb)) where (D denotes the Kuiper p-value upper bound in Equation 6 A
defined this way satisfies all three requirements we described in the beginning of Section 3.4 takes
sample sizes into account, has closed form expression with easy-to-compute gradients, and does not assume proportional hazards.
"hhe test is typically defined using CDFs but it is equivalent to use lifetime distributions (CCDFs) instead. II "Lwwer bound is presented the supplementary material.

---

Under review as a conference paper at ICLR 2020
Implementation. We implement our clustering procedure feedforward neural network in Pytorch (Paszke et al.) (017)) and use ADAM (Kingma and Ba 2014) to optimize Equation (4). Each iteration of the optimization takes as imput a batch of subjects, generates a single value for the set loss, calculates the gradients, and updates the parameters W1 and W2. We show in the supplementary material that the time and space complexity per iteration of the proposed approach OKKB- + maxx and size. For large values of K, we achieve tractability by sampling K random pairs of clusters every iteration instead of all (*) possible pairs.
respectively, where K' is the number of clusters and B is the batch
4 RELATED WORK
Majority of the work in survival analysis has dealt with the task of predicting the time to an observable terminal event (e.g., death), especially when the number of features is much larger than the number of subjects (Witten and Tibshirani [2010a] pre. Hothorn et al. 20066] Shivaswamy et al.
2007 Recently,
many deep learning approaches (Luck et al. 2017: Katzman al. 2018: Lee et al.
2018: Ren et al..
2018) have been proposed for predicting the lifetime distribution of a subject given her covariates, while effectively handling censored data that typically arise in survival tasks. DeepHit (Lee et al.)
2018) introduced novel architecture and a ranking loss function in addition to the log-likelihood loss for lifetime prediction in the presence of multiple competing risks. Using a log-likelihood loss similar to DeepHit, |Ren et al. (2018) propose recurrent architecture to predict the survival distribution that captures sequential dependencies between neighbouring time points. Finally, Chhaffuwa et al. (2018) introduce an ad versarial learning framework model the lifetime given the subject covariates. In contrast to these works on predicting lifetimes, our task is to cluster the subjects based on their underlying lifetime distributions.
There are relatively fewer works that perform lifetime clustering. Many unsupervised approaches have been proposed identify cancer subtypes in gene expression data but do not consider the lifetime (Eisen et al. 1998; Alizadeh et al.) 2000; (Bhattacharjee et al. 2001]] Sorlie et al. [200]] Bullinger al. 2004), and may produce clusters that entirely independent of the lifetimes. Semi-supervised clustering (Bair and Tibshirani 2004) and supervised sparse clustering (Witten and Tibshirami| (2010b)
use Cox scores (Cox 1992) to identify features associated with the lifetime and treat these features differently while using k- k-means to perform the final clustering. Unlike these lifetime clustering methods, DeepCLife does not assume proportional hazards, and can smoothly handle the absence of termination signals. Our supplementary material has more in-depth discussion of related work.
5 RESULTS
Baselines. We perform experiments on one synthetic dataset and two real-world datasets Friend- ster social network and MIMIC III healthcare dataset (Johnson et al. 2016).
We compare the following lifetime clustering approaches: (a) SSC-Bair, a semi-supervised clustering method (Bair and Tibshirani] 2004) that performs k-means clustering on selected covariates that have high Cox scores (Cox 1992); ; (b) SSC-Gaynor or supervised sparse clustering (Gaynor and Bair 2013), modification of sparse clustering (Witten and Tibshirani (2100b) that weights the covariates based on their Cox scores; (c) DeepHittGMM. a Gaussian mixture model applied over last layer embeddings learnt by DeepHit (Lee et al.] 2018); (d) DeepCLife-MMN
the DeepCL.fft model with Maximum Mean Discrepancy (Gretton et al. 2012) as the divergence measure; (e) DeepCL.ife KuiperUB, the DeepCLife model with the proposed divergence measure based on the Kuiper p-value upper bound (Equation (6))
Termination signals for evaluation and baselines. (Timcout.) The competing methods and most evaluation metrics for survival applications require clear termination signals. In scenarios where we do not observe termination signals (e.g., Friendster experiments), we specify termination signals artificially when training the baselines using a pre-defined "timeout", i.e., (Wisee)))))) = 1 > W.ooo] During evaluation, we use the same W Wixeed to specify the termination signals and compute the metrics. This helps the competing methods since they are trained and evaluated using termination signals with the same Wixeed, whereas our approach is not trained with these termination signals.
7

---

Under review as a conference paper at ICLR 2020
Table 2: (Synthetic) C-index (%) and Adjusted Rand index (%) for clusters with standard errors in parentheses for different methods
Deo,
D(G
Adj. Rand Index f (%)
Adj. Rand
Adj. Rand
Method
C-index 1 (5)
C-index (%)
C-index (%)
Index 1 (56)
Index f (%)
SSC-Buir
62.75 (0.35)
74.66 (0.48)
62.99 (0.26)
56.86 (0.63)
63.77 (0.24)
47.67 (0.24)
SSC-Gaynor
56.34 (0.50)
19.88 (0.51)
57.21 (0.43)
16,60 (0.56)
56.75 (0.32)
5.84 (0,11)
DeepHit-GMM
63.31 (0.32)
85.05 (1.01)
65.23 (0.21)
78.47 (0.94)
59.59 (1.98)
38.77 (7.16)
DeePCLife-MMD
64.35 (0.33)
98.47 (0.28)
67.25 (0.26)
99.68 (0.16)
62.17 (0.71)
36.75 (1.10)
DeepCLife- KuilpeUBBB
64.37 (0.32)
99.02 (0.14)
67.24 (0.26)
99.94 (0.06)
68.96 (0.38)
73.61 (0.62)
Table 3: (Friendster) C-index (%). Integrated Brier Score (%) and Logrank score with standard errors in parentheses for different methods and K=2, 4 clusters with number of training examples ~10==
==
K
Method
C-index (%)
LB.S (%)
Logrank Score
C-indes t (%)
I.B.S. J. (%)
Logrank Score t
SSC-Bair
64.42 (0.15)
22.18 (0.02)
5479.27 ( 38.06)
67.18 (0.13)
21.55 (0.03)
13013.86
182.07)
SSC-Gaynor
64.42 (0.18)
22.17 (0.02)
5557,41 38.43)
69.99 (0.28)
21.62 (0.01)
15204.81
41.29)
DeepHii+GMM
64.33 (1.80)
22.04 (0.23)
9207.46 (503148)
76.55 (0.12)
20.64 (0.02)
40703.01
477.25)
DeeDCLifo-MMD
67.49 (0.11)
22.07 (0.02)
27642.60 (1301.85)
70.93 (1.80)
22.40 (0.07)
33030.93 (4277.24)
DeepCLife-
KuiperUBB
75.58 (0.15)
20.13 (0.02)
47837.25 ( 297.63)
77.04 (0.88)
18.99 (0.20)
59236.36 (2126.55)
Metries. Given the cluster assigmments k((') E {l...., }} and the termination signals (possibly using a "timeout" window) for all the users u' in the test data, can obtain the empirical lifetime distribution of all the clusters SR, Vk E {I,...,K] }} using the Kaplan-Meier estimates (over the test data alone). Then, the empirical lifetime distribution of a user w' is given by that of her assigned cluster, i.e., 5(a") ;= Se(ar) We use the following metrics for evaluating the clusters obtained from the methods.
Logrank Score t. Logrank test (Mantel 1966) statistic is non- non-parametric test that outputs high values when it is unlikely for the K groups to have the same lifetime distribution.
Adjusted Rand index t. The Adjusted Rand index (Hubert and Arabie 1985) is a measurement of cluster agreement, compared the ground truth clustering (if available). ARI is 0.0 for random cluster assignments and 1.0 for perfect assignments.
C-Index 1. Concordance index (Harrell et al. 1982) is commonly used metric that calculates the fraction of pairs of subjects for which the model predicts the correct order of survival while also incorporating censoring. We use the expected lifetime obtained from the lifetime distribution S(u') as the predicted lifetime of user u'. C-index is 1.0 for perfect predictions and 0.5 for random predictions.
Integrated Brier Score J. Integrated Brier score (Brier 1950) Graf et al. 1999) computes mean squared difference between the survival probabilities and the actual outcome over [0, fmax] It ranges from 0.25 for random predictions to O for perfect predictions.
Although cluster evaluation metrics like Logrank score more suitable for the lifetime clustering task, we also use predictive measures like C-index and Brier Score to further validate the clusters.
Evaluation. We evaluate the models using 5-fold cross validation. We use the ith fold for testing and sample No subjects from the remaining 4 folds for training. We use 20% of the No subjects as validation for early stopping and hyperparameter tuning for the different approaches.
5.1 EXPERIMENTS
Synthetic experiment. We test our method with a synthetic datase for which we have the true clusters as ground truth. We generate clusters C1, C2 and C3 with different lifetime distributions such that C2 and C3 have proportional hazards, but lifetime distribution of Ci crosses the other two curves (shown in Figure 2b). We choose an arbitrary time of measurement, f. 150, to imitate right censoring. We sample 10t subjects for each cluster, their features drawn from mixture of Gaussians. The lifetime ((a) of a subject u is randomly sampled from the lifetime distribution of her ground truth cluster. Table 2 shows performance of the methods on three synthetic datasets: D ((C,. D ((C.
T
# indicates higher is better, J. indicates lower is better. Detailed description in the supplementary material. "The values in bold are statistically significant with p-value < 0.01 using paired t-test over validation folds.
Moor details about all the datasets and preprocessing steps can be found in the supplementary material.
8

---

Under review as a conference paper at ICLR 2020
Probabllity (CCDF)
1.0
& (ns 180028)
Probablitty (CCDA)
1.0
$ (n, 179794)
0.8
Sy (oy 32)
0.8
Sy (n, 38808)
0.6
(ny 8302)
0.6
8260)
0.4
0.4
6, (ny 62366)
$q (ny 974391
0.2
0.2
Sq (ns 67057)
0.0
0
10
20
30
40
50
0.0
0
10
20
30
40
50
Probability (CCDF)
1.0
Time
Time (in months)
0.8
(a) SSC-Bair
(b) SSC-Gaynor
0.6
Probability (CCDF
1.0
(n. 84253)
Probablitty (CCDF)
1.0
5, (nf 137003)
0.4
0.8
(n. - 54615)
0.8
$, (hg 0)
0.2
0.6
53 (n. 87994)
0.6
5y U/ 89859)
0.0
10
20
40
50
Time (in months)
0.4
0.2
(c) DeepCTiife-KuiperrU
0
10
20
30
40
50
0.0
50
Time (in months)
Time (in months)
(c) DeePHit+GMM
(d) DeepCLife-MMD
Figure 3: (Friendster) Empirical lifetime distributions of clusters obtained from different methods for K K (legend shows cluster sizes n1, R2, do not guarantee clusters with maximally different lifetime distributions. (d) DeepCLafe-MMMD suffers from sample anomalies (n2 = 0). (e) DeepCLife-Kal ffe--riieeU..B obtains clusters with significantly different lifetime distributions (best Logrank scores).
,2,)))) na).
Baseline methods (a-c) employ two-stage clustering process and
Probability (CCDF)
1.0
K
0.8
Method
C-index (9)
I.B.S. (%)
Lugrank Score
0.6
SSC-Bair
52.78 (0.76)
15.89 (0.20)
11.77 ( 4,20)
0.4
5, (ni 2957)
SSC-Gaynor
52.32 (0.96)
15.87 (0.15)
120,71 (59.33)
0.2
$2 (n2= 3955)
DeepHit-GMM
64.93 (0.54)
15.70 (0.15)
171.93 (11.15)
DMMD
58.85 (0.60)
15,03 (0.35)
157.84 (11.01)
0.0
5
10 15 20
25
30
SrepCLifeKKiierrUl
66.30 (1.09)
15.50 (0.23)
205.25 (11.45)
Time (in days)
(b)
(a)
Kuepprife-KuiperUBB
Figure 4: (MIMIC IIII (a) Empirical lifetime distributions obtained by DeepCLife- BeepCLife-KuiperUB for K 2. (b) C-index (%), Brier Score (%) and Logrank score with standard errors for different methods on healthcare data for K=2.
D(C,,Ca.Cg) DeepCLifeKKuipeUUB and DMDD were able to recover perfect ground truth cluster assignments on Dic,,Cs .Ca) and ((c,,Cs) whereas the baseline methods performed invariably worse. On the harder dataset Dic, D(C,,C,,C,) DeepCI.ife-Kupperr recovered the ground truth clusters almost twice as better than any other method.
Friendster experiment. Friendster dataset consists of 15 million users in the Friendster online social network along with the comments sent and received by the users. We consider a subset with 1.1 million users who had participated in least comment. We use each user's profile information (like age, gender, location, etc.) as covariates, and define activity events as the comments sent or received by the user. We compute summary statistics of the activity events within 5 months from joining such as number of comments sent/received, number of people interacted with, mean inter-event times, etc. The task is to cluster new test users using their covariates and the summary statistics computed over initial signals (i.c., account deletion) for any subject in the data. We use an arbitrary window of W fxxd = 10 months over the inactivity period to obtain termination signals (=s 65% assumed to have quit) for the competing methods and for computing the evaluation metrics; DeepCLife does not require such arbitrary specification but learns smooth timeout window during training.
5 months of activity. Note that we do not observe termination
Table 3 shows results for K=2, 4 clusters. We note that the proposed method obtains higher C-index values and Brier scores compared the baselines without termination signals. DeepCL.ife-

---

Under review as a conference paper at ICLR 2020
KuiperUB achieves a significant improvement in Logrank scores compared to the baselines because its loss specifically maximizes for differences in empirical distributions, while also taking sample sizes into account. DeepCLife-MMD
the other hand does not account for sample sizes, and hence performs worse. The empirical lifetime distributions of the clusters obtained from different methods for K=3 are shown in Figure 3 The clusters obtained from the baselines (a-c) are not substantially different from each other. Although DeepCLife-MMD obtains clusters with distinct lifetime distributions, it suffers from sample anomalies i.e., outputs clusters with very few or no subjects (e.g., S2 in Figure 3dp.
BeeeCLife-KuieeUUS outputs clusters that have significantly different lifetime distributions with the best Logrank scores. Corresponding plots of empirical lifetime distributions for K=2,4, 4, 4,5 are presented the supplementary material. For K=4, we observe that in the supplementary material). We present heuristic to select optimal K based on the validation performance of the clusters in Appendix A.4
finds crossing yet distinct lifetime distributions (see Figure 7
Friendster, we see that user in low-risk cluster has average 7.76 friends, sends 5.06 comments with an average response time of 20 days. On the other hand, a user in a high-risk cluster has just 1.56 friends on average and sends far fewer comments, around 1.07, but with fast response time of 1.32 days. Interestingly, users that stayed longer in the system had lower activity rate in the beginning.
Qualitative Analysis: the clusters found by ChepCLife-Kuipetti
MIMIC III experiment. MIMIC III dataset JJhnssn al., 2016) consists of around 46500 patients admitted to the Intensive Care Unit (ICU). The task is to cluster the patients based on their mortality within 30 days of admission
the ICU (Purushotham et al. 2017). Unlike Friendster experiments, we can observe terminal events. Lifetime of a patient is right-censored if she was discharged within the 30-day period (=x 84% right-censored). We use only the initial 7=24 hours of patient measurements (e.g. heart rate, respiratory rate, etc.) to perform the clustering. We compute summary statistics for each type of measurement, for example, number of heart rate measurements taken, mean heart rate, etc. to make the inputs compatible with the feedforward architecture in achieves significantly better
Figure [a Results for K== in Table|4]shhvv that C-index and Logrank scores, followed by DeepHiG The corresponding empirical lifetime distributions of the clusters are shown in Figure 4a
CONCLUSION
In this work we introduced Kuiper-based nonparametric loss function maximize the divergence between empirical distributions, and a corresponding upper bound with easy-to-compun gradients. The loss function then used train feedforward neural network inductively map subjects into K lifetime-based clusters without requiring termination signals. We show that this approach produces clusters with better C-index values and Logrank scores than competing methods.
REFERENCES
Charu C Aggarwal, Stephen C Gates, and Philip Yu. On using partial supervision for text categorization. TKDE, 2004.
Ahmed M Alaa and Mihaela van der Schaar. Deep multi-task gaussian processes for survival analysis with competing risks. In NIPS, 2017.
Ash A Alizadeh, Michael B Eisen, R Eric Davis, Chi Ma, Izidore S Lossos, Andreas Rosenwald, Jennifer C Boldrick, Hajeer Sabet, Truc Tran, Xin Yu, et al. Distinct types of diffuse large b-cell lymphoma identified by gene expression profiling. Nature, 403(6766):503-51, 2000.
Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein Generative Adversarial Networks. In ICML, 2017.
Eric Bair and Robert Tibshirani. Semi-supervised methods to predict patient survival from gene expression data. PL Biol, 2(4)xe108, 2004.
Sugato Basu, Arindam Banerjce, and Raymond Mooney, Semi-supervised clustering by seeding. In ICMI., 2002.
10

---

Under review as a conference paper at ICLR 2020
Sugato Basu, Mikhail Bilenko, and Raymond J Mooney. A probabilistic framework for semi- supervised clustering. In SIGKDD, 2004.
Arindam Bhattacharjee, William G Richards, Jane Staunton, Cheng Li, Stefano Monti, Priya Vasa, Christine Ladd, Javad Beheshti, Raphael Bueno, Michael Gillette, al. Classification of hu- man lung carcinomas by mrna expression profiling reveals distinct adenocarcinoma subclasses. Proceedings of the National Academy of Sciences, 98(24):13700-137995 2001.
J Martin Bland and Douglas Altman. The logrank test. Bmj, 328(7447):1073, 2004.
Glenn W Brier. Verification of forecasts expressed in terms of probability. Monthey Weather Review, 78(1):1-3, 1950.
Lars Bullinger, Konstanze Döhner, Eric Bair, Stefan Fröhling, Richard F Schlenk, Robert Tibshirani, Hartmut Döhner, and Jonathan R Pollack. Use cene-expression profiling to identify progmostic subclasses in adult acute myeloid leukemia. New England Journal of Medicine, 350(16);:005-1616 2004.
Paidamoyo Chapfuwa, Chenyang Tao, Chunyuan Li, Courtney Page, Benjamin Goldstein, Lawrence Carin, and Ricardo Henao. Adversarial time-to-event modeling. arXiv preprinl wrXiv:1804.03184 2018.
SK Chuang, Cai, CW Douglass, Wei, and TB Dodson. Frailty approach for the analysis of clustered failure time observations in dental research. Journal of dental research, 84(1):54-58, 2005.
David Cox. Regression models and life-tables. In Breakthroughs in statistics, pages 527-541. Springer, 1992.
Richard M Dudley, Real analysis and probability, volume 74. Cambridge University Press, 2002. ISBN 0521007542.
Michael B Eisen, Paul Spellman, Patrick O Brown, and David Botstein. Cluster analysis and display of gide expression patterns. PNAS, 1998.
K. Fukumizu, A. Gretton, X. Sun, and B. Schölkopf. Kernll Measures of Conditional Dependence. In NIPS, 2008.
Yanglan Gan, Ning Li, Guobing Zou, Yongehang Xin, and Jihong Guan. Identification of cancer subtypes from single-cell ma-seq data using consensus clustering method. BMC medical genomics, 11(6):1 11, 2018.
Sheila Gaynor and Eric Bair. Identification of biologically relevant subtypes via preweighted sparse clustering. Biostatistics, pages 1-33, 2013.
Erika Graf, Claudia Schmoor, Willi Sauerbrei. and Martin Schumacher. Assessment and comparison of prognostic classification schemes for survival data. Statistics in medicine, (8(17-18):222-22555 1999.
Arthur Gretton, Kenji Fukumizu, Zaid Harchaoui, and Bharath K. Sriperumbudur. A Fast, Consistent Kernl Two-Sample Test. In Advances in Neural Information Processing Systems, 2009.
Arthur Gretton, Karsten M Borgwardt, Malte J Rasch, Bernhard Schölkopf, and Alexander Smola. A kernel two-sample test. Journal of Machine Learning Research, 13(Mar):723-773, 2012.
Frank E Harrell, Robert M Califf, David B Pryor, Kerry Lee, and Robert A Rosati. Evaluating the yield of medical tests. Jama, 247(18):2543-255 2244.. 1982.
Torsten Hothor, Peter Bühlmann, Sandrine Dudoit, Annette Molinaro, and Mark Van Der Laan. Survival ensembles. Biostatistics, 7(3):355-377 -733, 2006.
Philip Hougaard. Frailty models for survival data. Lifetime data analysis, (3)):255-233 1995.
Xuelin Huang and Robert A Wolfe. frailty model for informative censoring. Biometrics, 58(3): 510-520, 2002.
11

---

Under review as a conference paper at ICLR 2020
Lawrence Hubert and Phipps Arabie. Comparing partitions. Journal of classification, 2(1):193-21 1985.
Hemant Ishwaran, Udaya Kogalur, Eugene Blackstone, Michael S Lauer, et al. Random survival forests. The annals of applied statistics, -3)6,,,-860, 2008.
Hemant Ishwaran, Udaya B Kogalur, Eiran Gorodeski, Andy J Minn, and Michael Lauer. High- dimensional variable selection for survival data. Journal of the American Statistical Association, 105(489):205-211 2010.
Alistair EW Johnson, Tom Pollard, Lu Shen, Lehman Li-wei, Mengling Feng, Mohammad Ghassemi, Benjamin Moody, Peter Szolovits, Leo Anthony Celi, and Roger G Mark. Mimic-iii, freely accessible critical care database. Scientific data, 3: 3:160035, 2016.
Edward L Kaplan and Paul Meier. Nonparametric estimation from incomplete observations. Journal of the American statistical association, 53(282):457-481 1958.
Jared L Katzman, Uri Shaham, Alexander Cloninger, Jonathan Bates, Tingting Jiang, and Yuval Kluger. Deepsurv: personalized treatment recommender system using a cox proportional hazards deep neural network. BMC medical research methodology. 18(1):24, 2018.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
Nicolaas H Kuiper. Tests concerning random points on circle. In Indagationes Mathematicae (Proceedings), 1960.
Solomon Kullback and Richard Leibler. On information and sufficiency. The annals of mathemati- cal statistics, 22(1):79-88 06.779666111 1951.
Vincenzo Lagani and Ioannis Tsamardinos. Structure-based variable selection for survival data. Bioinformatics, 26(15): 1887-1894, 2010.
Changhee Lee, William R Zame, Jinsung Yoon, and Mihaela van der Schaar. Deephit: A deep learning approach to survival analysis with competing risks. AAAI, 2018.
Huimin Li, Dong Han, Yawen Hou, Huilin Chen, and Zheng Chen. Statistical inference methods for two crossing survival curves: a comparison of methods. PLoS One, 10())ee0116774 2015a.
Yujia Li, Kevin Swersky, and Rich Zemel. Generative moment matching networks. In ICML, 2015b.
Margaux Luck, Tristan Sylvain, Héloïse Cardinal, Andrea Lodi, and Yoshua Bengio. Deep learning for patient-specific kidney graft survival analysis. arXiv preprint arXiv: 1705. 10245, 2017.
Nathan Mantel. Evaluation of survival data and two new rank order statistics arising in its considera- tion. Cancer Chemother Rep, 50: 10:166-170, 1966.
Frank J Massey Jr. The kolmogorov--mmiroy test for goodness of fit. Journal of the American statistical Association, 46(253):68-788 1951.
Kamal Nigam, Andrew McCallum, Sebastian Thrun, Tom Mitchell, et al. Learning to classify text from labeled and unlabeled documents. AAAI/IAAI, 792, 1998.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary Vito,o, Zeming Lin, Alban Desmaison, Luea Antiga, and Adam Lerer. Automatic differentiation in pytorch. 2017.
Richard Peto and Julian Peto. Asymptotically efficient rank invariant test procedures. Journal of the Royal Statistical Society. Series A (General), pages 185-207, 1972.
William H Press, Saul A Teukolsky, William T Vetterling, and Brian P Flannery. Numerical recipes in C, volume 2. Cambridge university press Cambridge, 1996.
Sanjay Purushotham, Chuizheng Meng, Zhengping Che, and Yan Liu. Benchmark of deep learning models large healthcare mimic datasets. arXiv preprint arXiv: 171.08531, 2017.
12

---

Under review as a conference paper at ICLR 2020
William M Rand. Objective criteria for the evaluation of clustering methods. Journal of the American Statistical association, 66(336):846-88) 8500, 1971.
Rajesh Ranganath, Adler Perotte, Noémie Elhadad, and David Blei. Deep survival analysis. arXiv preprint 160i 02158, 2016.
Kan Ren, Jiarui Qin, Lei Zheng, Zhengyu Yang, Weinan Zhang. Lin Qiu, and Yong Yu. Deep recurrent survival analysis. arXiv preprint arXiv:/809.024000 2018.
Bruno Ribeiro and Christos Faloutsos. Modeling website popularity competition in the attention- activity marketplace. In WSDM, 2015.
Pannagadatta Shivaswamy, Wei Chu, and Martin Jansche. A support vector approach to censored targets. In ICDM, 2007.
Therese Sorlie, Charles M Perou, Robert Tibshirani, Turid Aas, Stephanie Geisler, Hilde Johnsen, Trevor Hastie, Michael B Eisen, Matt Van De Rijn, Stefanie S Jeffrey, et al. Gene expression patterns of breast carcinomas distinguish tumor subclasses with clinical implications. Proceedings of the National Academy of Sciences, 98(19): 18899-00844 2001.
Yizhou Sun, Jiawei Han, Charu C Aggarwal, and Nitesh V Chawla. When will it happen?: relationship prediction in heterogeneous information networks. In WSDM, 2012.
Mark Tygert. Statistical tests for whether a given set of independent, identically distributed draws comes from specified probability density. PNAS, 2010.
Daniela Witten and Robert Tibshirani. Survival analysis with high-dimensional covariates. Statis- tical methods in medical research, 19(1):29-51, 2010a.
Daniela M Witten and Robert Tibshirani. A framework for feature selection in clustering. Journal of the American Statistical Association, 105(490):133-226, 2010b.
13

---

Under review as a conference paper at ICLR 2020
A APPENDIX
A.1 PROOF OF PROPOSITION
Proposition (Proposition Given the training data D, cluster k, the cluster assignment probabil- (w)) buED. and the probabilities of termination (W2)) the maximum likelihood estimate of the empirical lifetime distribution of cluster k is given by,
ities {aj
8& Wi D) - dR (Wi, W2;
(W, 22; DM4
II f=0
8k WW;
for all I. {0, 10,1,...,,matt mmar). where, 8& (W = 1 (H)
2 j| 0
(a) (W1), ) the expected
number of subjects in cluster l who are risk (of termination) time j. and, dw W2; D)Li]
(u) EnED 1(H(") = jl 3(x) (W2) okk (W1). the expected number of subjects that are predicted to have had termination event at time j.
Proof. For subject u, let e(u) Bernoulli(3(w) (W2)) be the sampled termination signal, i.e.. e(w) 1 indicates that the subject's observed lifetime her true lifetime, H(M) T((), Let g(a) ~ Categorical(a, (Wi),.. aK
(u) )) be the sampled cluster assignment of the subject.
Finally, let the empirical lifetime PMF of cluster & 1.. K} be defined as P(T: 1) Au,t for E
). where T. is the true lifetime of a random subject in cluster k.
The likelihood of the training data DD for a particular cluster lt given the sampled termination signal ( JED be written using Kaplan and Meier
(e(w) DED and the sampled cluster assignments {1((4) (1958) as,
II P ( P(T > (10))a (((0))-e"")
L
LEED
Next, we take expectation over the cluster assignments and termination signals to get,
La = EE )
(e(0)) hu
II P(T. = 11 (w) P(T > (()))1= 1-e(")
(7)
LNED
Using mean-field approximation and proceeding as Kaplan and Meier (9588) to write Equation 7 as a product over time instead of subjects, we get,
La =
de (1) (1 Ae.
)x.)) debbl
(8)
1=
where, we have used P(Tk = 1) = Ak.j, sk is a shorthand for sk(W1, W2; D)
EVED 1(H(") 2 a (w) (W1), the expected number of subjects at risk time and, d& is shorthand for de W2; D)Li] EneD 1[/((") = j] ((w) a( (W1), the expected number subjects that are predicted to have had a termination event at time j.
Finally, maximizing the likelihood in Equation ( with respect to Au, for all k: E (1.... K} and t E {0, 1....fmax) m and computing the lifetime distributions (CCDF) S5 from the corresponding lifetime PMFs finishes the proof.
A.2 PROOF OF PROPOSITION 2
Proposition (Proposition D. Given two empirical lifetime distributions S, and So with discrete sup- port and sample sizes The and ny respectively, define the maximum positive and negative separations between them as.
D+ sup
($.
So(tt).
1E (E(0...Araa))
D= sup
($:(4) Sa(1).
OE (o
14

---

Under review as a conference paper at ICLR 2020
The Kuiper test p-value Kuiper (1960) gives the probability that A, the empirical deviation for na and mb observations under the null hypothesis Sa Sb. exceeds the observed value V = Dā, + D a.
KD(Sa,, P(A V = - (4) 1)e 1)e-22 22,
where Aa.b (MMus + 0.155
0.24
V and Ma,6 =
Datt is the effective sample size. natmo
VMa.b
Then, the lower and upper bounds for the Kuiper p-value are,
KD(Sa, Sp))
I[r 2 1] (wr(r a.. Aa,b)
2
2
u(rab )a,b)) + =((rlup) )a,b) + w(ratt))
(1))
(10)
(up)
(up) Aa,b)
and
KD(Sa: So)
S min
1
1/b [1)) 2 1] (1o(ragg)) (10)
a.b )a,s)
2
2
w(1, Aa,b) + u (10) )a,b))
+ v(ra. (up) Na.b) - w(r a.b )o,,))
(up)
(10)
where v(r, A) = (4r²>² 1)e- 2x with w(r, A) = -re -r==2x= 22 and (10)
rab =
V2h..0
r a,
(up)
V2ha,b
Proof. To prove these bounds, we first regard that the indefinite integral w(r, A) = f v(r, Ajdr = -re-2r"X + C. Then, for given X, v(r, A) is monotonically increasing w.r.t in the interval (0, v2x and monotonically decreasing w.r. in the interval </2 20).
Let (to) [ ((p) = { and (A) Σm e(r, A). Here, we assume that ((lo) * (up)) i.e., 22 is not an integer. The bounds can be easily modified for when y(tt)) r(up), Now, v(r, A) is decreasing w.t. (v(Mp), oo), and we have,
v(r, X)dr I (10) s S v(r, A)dr.
and adding v(r(up), A) throughout we get.
/ n(up)41 v(r, X)dr
((p)) A)
< J(twr) xo| (A) S ((r(1r),, X) frem v(r, A)dr
(11)
Similarly, since v(r, A) is increasing in (0, ((10)), we have, (t))
u(r, A)dr S -1
and adding v()( >) throughout get,
(10)
v(r, A)dr + ((o(()), A)
5 Jp, (A) < L v(r, A)dr + v(r(lo), X).
(12)
where assume that (1o) > 1, otherwise, (p) ) is trivially zero
15

---

Under review as a conference paper at ICLR 2020
Combining equations equation
11 and equation
12 get,
-1
1 [ (T0)
211-
vrr A)dr + e(r(l0)) ,2)
te(((upp) 2) + +10)++
o(r:A)dt
$ 1|rll0) 2 . - ( (2) + (/plem)
(1o)
1 2 211-
v(r, d)rr + o(pilo),
v(((up) 2) fo v(r; A)dr.
(13)
(riup
We use the fact that KD(S., So)) = 2 (aa)))) (A) = 1/r(10) 2 1| (1 (A)
Jrew oeg and w(r, >) = o(r, d)d and that KD(S,, Sp) I 1 to complete the proof.
A.3 ADDITIONAL RESULTS
A.3.1 FRIENDSTER EXPERIMENT
Results on the Friendster experiments for K 3, 5 shown in Table We observe that DeepCLife outperforms all baselines by large margins, particularly in the Logrank score. Figures 5 to g show empirical lifetime distributions of the clusters found by the methods on the Friendster dataset for K = 2, 3, 4, 5 respectively. Baseline methods SSC-Bair, SSC-Gaynor and DecPHit+GMMM employ a two-stage clustering process and do not guarantee clusters with maximally different lifetime distributions. DeepCLiffe-MMD does not account for sample sizes of empirical distributions and suffers from sample anomalies, i.e., outputs clusters containing almost no subjects. DeepCLife- KuiperUB obtains clusters with the best Logrank scores. Interestingly, DeepCLife finds clusters with crossing yet distinct lifetime distributions for K (see Figure
Probability (CCDF)
1.0
1068531
Probability (CCDF)
1.0
S, 185640)
0.8
Iny 40009)
0.8
5, 0% 402221
0.6
0.6
0.4-
0.4
0.2
0.2
Probability (CCDF)
1.0
5, (ny 95840)
0.0
0.0
0.8
(n. 1310221
0
10
20
30
40
50
0
10
20
30
40
50
Time
Time (in months)
0.6
(a) SSC-Bair
(b) SSC-Gaynor
0.4
Probability (CCDF)
1.0
In 1513311
Probability (CCDF)
1.0
0.2
0.8
Ing 75531)
0.8
0
10
20
30
40
50
0.6
0.6
(in months)
0.4
0.4
(c) DeepCLife-KuiperUU
0.2
0.2
0
10
20
30
40
50
0
10
20
30
40
50
Time (in months)
(in months)
(c)
DccpHit+GMM
(d) DeepCLife-MMD
Figure 5: (Friendster) Empirical lifetime distributions of clusters obtained from different methods for K=2 (legend shows cluster sizes ni, 12)).
16

---

Under review as a conference paper at ICLR 2020
Probablitty (CCDF)
$ (ns 180028)
Probablity (CCDA)
1.0
$ (n, 179794)
0.8
Sy (oy 32)
0.8
Sy (n, 38808)
0.6
(ny 8302)
0.6
8260)
0.4
0.4
6; (ny 62366)
$q (ny 97439)
0.2
0.2
Sq (ns 67057)
0.0
0
10
20
30
40
50
0
10
20
30
40
50
Probability (CCDF)
1.0
Time
Time (in months)
0.8
(a) SSC-Bair
(b) SSC-Gaynor
0.6
Probability (CCDF
(n. 84253)
Probability (CCDF)
1.0
5, (nf 137003)
0.4
0.8
(ng - 54615)
0.8
$g (hg 0)
0.2
53 (n. 87994)
5y U/ 89859)
0.0
0.6
10
20
40
50
Time (in months)
0.4
0.2
(c) DeepCT.ifc-KuiperrB
10 20
30
40
50
0.0
50
Time (in months)
Time (in months)
(c) DeMPHit+GMM
(d) DeepCLife-MMM) MMD
Figure 6: (Friendster) Empirical lifetime distributions of clusters obtained from different methods for K K
(legend shows cluster sizes 11,, 12, n1a).
1.0
1.0
Probability (CCDF)
Probablitty (CCDF)
S: (ft 167081
0.8
0.8
Ohu 8052)
0.6
0.6
0.4
0.4
0.2
0.2
1.0
5.0%
Probability (CCDF)
0.0
10
30
40
50
0.0
10
20
30
40
50
0.8
5. (h) - 49279)
(% 05789)
Time
Time (in months)
0.6
45450)
(a) SSC-Bair
(b)
SSC-Gaynor
0.4
1.0
5, -61771
1.0
0.2
Probabiitty (CCDF)
Probabiity (CCDF)
0.8
0 - 437271
828221
0.8
0.0
10
30
40
50
0.6
35112)
0.6
Time (in months)
0.4
0.4
(c) KuepperfeK
0.2
0.2
0.0
0.0
0
10
20
30
40
50
10
20
30
40
50
Time (in months)
Time (in months)
(c) DeepHit+GMM
(d) DeepCLife-MMMD
Figure 7: (Friendster) Empirical lifetime distributions clusters obtained from different methods K=4 (legend shows cluster sizes).
A.3.2 MIMIC III EXPERIMENT
Figure shows the empirical lifetime distributions of the clusters found by DeepCLiiteKuupprrU in MIMIC III dataset for K 2.
A.4
OPTIMAL NUMBER CLUSTERS: K
Similar to standard clustering algorithms, choice of K is subjective and depends the downstream application of the clusters. Here we discuss a heuristic to use Logrank scores as a useful guide to choose the optimal number of clusters. For the Friendster experiments, Figure T0 shows the Logrank
17

---

Under review as a conference paper at ICLR 2020
Table 4: (Friendster) C-index (%). Integrated Brier Score (%) and Logrank score with standard errors in
parentheses for different methods' and K K,3, clusters with number of training examples N 10..
K
Method
C-index 1 (9)
4 (8)
Logrank Score f
C-index (%)
J. (8)
Logrank Score
SSC: Bair
64.23 (0.24)
22.19 (0.02)
5277.82
43.63)
75,80 (0.16)
20.26 (0.02)
43605.161
91.39)
SSC-Gaynor
64.13 (0.21)
22.18 (0.02)
$400.75
39.59)
75.66 (0.20)
20.48 (0.01)
41824.28 151 85)
DeepHit+GMM
20.97 (0.06)
33880.55
426.74)
76.17 (0.27)
(0.11)
39254.67
(1721.56)
DeepC1 MMc
72.75 (1.24)
18.94 (0.65)
50173.94
(4809.80)
63.08 (2.69)
21.55 (0.54)
14308.90 (9149.41)
DeepCLife-
KuiperUB
78.48 (0.32)
19.70 (0.55)
54191.28
436.72)
76.51 (1.25)
18.99 (0.16)
56130.21 (4036.02)
Probability (CCDF)
Probability (CCDF)
Csy 118101)
5,
& 157551
(4 505621
0.4
0.2
0.2
Probability (CCDF)
5, 314291
8, 41574)
0.0
30
40
50
0.0
30
40
50
0.8
8, (n 201741
Time
Time (in months)
0.6
5, (% 395601
9, 851151
SSC-Bair
(b)
SSC-Gaynor
0.4
1.0
0.2
Probablity (CCDF)
Probablity (CCIF)
0.0
10
20
0.6
0.5
Time (in months)
0.4
0.4
(e) Deepprife-KuiperUUB
0.2
0.2
0.0
0.0
50
50
Time (in months)
Time (in months)
(c) DeepHlit-GMM
(d) DeepCLife-MMD
Figure 8: (Friendster) Empirical lifetime distributions of clusters obtained from different methods for K=5 (legend shows cluster sizes).
scores on a held-out validation set for clusters obtained from DeepCLife-KuuperUUR with K = 2...7. We observe that K gives the best mean Logrank score and K 5 close behind. However, for K > 5. the Logrank scores drop drastically indicating that there are no more clusters that have distinct lifetime distributions from the ones already found.
Similarly for the MIMIC III experiments, Figure 11 shows the Logrank scores on held-out validation set for clusters obtained from Kuupeei with K 2...8 We see that choosing K gives the highest Logrank score. However, we also observe that from K = 2 to K = 5 the scores do not increase significantly; a practitioner might decide to use K for this reason.
A.5 CHOICE MINIMUM VS SUM IN EQUATIONS AND
We define the clustering problem in Definition as finding mapping x such that,
(,(1())
R arg max KEK
min KJ, 1y.
where IC is set all mappings, (1:) is the empirical lifetime distribution of subjects in the training data D mapped to cluster through and A is an empirical distribution divergence measure.
In this section, we discuss the issues that arise when one chooses to optimize the sum of divergences over all pairs of clusters rather than the minimum.
18

---

Sa- Under review as a conference paper at ICLR 2020
1.0
5 io; = 3580]
1.0
6 In 3767)
Probabiltty (CCDF)
Probability (CCDF)
0.8
53322
0.8
(nz 1911)
0.6
0.6
0.4
0
10
15
20
25
30
5
10
15
20
25
30
Time
days)
Time (in days)
(a)
(b) K =
1.0
1.0
Probability (CCDF)
in 1511
Probability (CCDF)
In, 1464)
0.8
0.8
5, 10831
5. Inu 1831)
5, (i 24477
In.- 6331
0.0
0.0
0
10
15
20
25
30
5
10
15
20
25
30
Time (in days)
Time (in days)
(c)
(d) K
5
5, in; 11933
Probabiity (CCDF)
5, (i) 843)
0.6
(n, 1986]
905)
0.4
5, Ins 14301
0.2
0.0
20 Time (in days)
10
(e) K
Figure 9: (MIMIC III) Empirical lifetime distributions of clusters obtained from DeepCLife-KuiperUB with
K= 6 (legend shows cluster sizes).
22000
Logrank score
20000
18000
16000
14000
12000
2
5 6 Number of clusters (K)
7
Figure 10: (Friendster) Logrank scores (error bars denote standard errors) on held-out validation set for the clusters obtained from DeepCLite-KuiperUU with different values of K. K = 4 seems to give the best mean performance, while K close behind; increasing K further drastically reduces the Logrank score.
Let K = 4 and consider balanced clusters with lifetime distributions S = S2 * S.
Note that such clustering is not desirable since there are virtually only clusters found (as $i and Š2 are the same, etc). But for such assignment, the sum of divergences is relatively high Eizy A(S., 4. (S,, Sz). The could be further maximized by simply increasing
19

---

Under review as a conference paper at ICLR 2020
300
275
250
225
t 200
175
99 150
125
100
2
3
4
7
Number of clusters (K)
Figure 11: (MIMIC III) Logrank scores (error hars denote standard errors) held-out validation set for the clusters obtained from DeepCl.ifeKuuiprruu with different values of K. K 6 gives the best Logrank performance. However, Logrank scores for K 2 to K 5 do not increase
significantly; suggesting K = could be a good choice as well.
1.0
Lifetime distribution of clusters (K 4)
&, (ny 36153)
Probability (CCDF)
& (ng 49279)
0.8
$, (ny 95780)
Probabiiity (CCOF)
Cluster
0.6
3 (ne 45650)
Cluster
Cluster
0.4
0.2
0.0
0
10
20
30
40
50
Time (in months)
Time
(a) Maximizing min.yy A(S:,
(b) Maximizing Σij, A(S., S,)
Figure 12: (Friendster) Clusters found by the proposed approach with K when maximizing the minimum divergence (left) vs maximizing the sum of divergences (right).
divergence between S1 and S3 while keeping $2 Sn and S33 S4. On the other hand, since min;yj ASS,, 5,) = 0, the model should maximize the divergence between Š, and $2 first.
Figure 12 shows the clusters found by the proposed approach while maximizing the minimum divergence vs maximizing the sum of divergences in the Friendster dataset with =4. 4. We observe that the clusters obtained using the sum of divergences the loss exhibit the property discussed above (i.e., clusters 2 and Figure are almost the same).
A.6 ALGORITHM
For ease of use, we present Algorithm to compute the proposed divergence measure log(KD) (S,,
A.7 TIME/SPACE COMPLEXITY OF DEEPCLIFF- KUIPERUR
Here we discuss the time and space complexity of the proposed algorithm. We only discuss the complexity of computation of the proposed loss function for one iteration assuming minibatch of size B, number of clusters K and discrete times with 1.... First, we can compute the empirical lifetime distributions of all the K clusters in O(K KB) time using O O(Klmax) space. Computing upper bound of the Kuiper p-value for two lifetime distributions using Algorithm requires (4max) time and O (max) space. Since we compute the upper bound for all (K) pairs, the time complexity then becomes O O t whereas the space complexity remains (fmmax) The total time and space complexity of the proposed algorithm O(K B + (max) and O (K1mmx) respectively.
20

---

Under review as a conference paper at ICLR 2020
Algorithm 1 Kuiper Divergence Upper Bound (Log)
Require: Two empirical lifetime distributions Sa and Si with sample sizes na and na respectively
1: function KUIPERU B(S Sb, Ra, 1b6)
2:
D t max(6 (Sa Sb)
Sa So are vectors of length fmax +1
3:
D + max (8p- Sa)
4:
V f- D + D
P. Kuiper statistic Effective sample size
5:
M + nant
tut
6:
A (VM M + 0.155 + 0.24 V
VM
7:
p(0b + V2X-
8:
(up) + 72X
9:
if (1o) 2 then
10:
KD-UB + W(r A) W(1, + V(rilo), A) V(HOp), - W((ruu)), A)
11: else
KD-UB ((r(up) A) W(r1op),
13:
return log KD-UB
function V(r, A)
return (4r )2 12
function W(r, return -re 22
A.7.1 TRACTABILITY THROUGH SAMPLING
Each iteration of optimization involves computing the Kuiper upper bound for all (K) pairs of clusters, hence can be prohibitively expensive for large values of K. Rather, we propose to sample randomly p O(K) pairs without replacement from the (K) possible pairs of clusters. The time and space complexity reduces to O(KB B + K mmax and O(Ktmas respectively.
A.8 ADDITIONAL DETAILS ABOUT DATASETS
1.00
Cluster
Cluster
Cluster
0.75
CCDF
0.50
0.25
0.00
50
100
150
200
Time
Figure 13: (Toy) True lifetime distributions of simulated clusters (with fm 150).
Synthetic dataset. We also test our method with synthetic dataset for which we have the true clustering as ground truth. We generate 3 clusters C1 C2 and C3 with different lifetime distributions, as depicted in Figure[33 [3] Note that while the lifetime distributions C2 and C33 follow proportional hazards assumption, the lifetime distribution of C₁ violates this assumption by crossing the other survival curves.
We simulate 10 subjects for each cluster k. and generate 20 random features for each sampled subject. The lifetime (1)) of subject in a cluster randomly sampled from the corresponding
21

---

Under review as a conference paper at ICLR 2020
lifetime distribution of the cluster. We also choose an arbitrary time of measurement, f. 150, to imitate right censoring.
We generate covariates (x) of each subject a as two sets of 10 attributes. Each attribute is simulated
(3) (2) and Pk,s for = 1.... 20 and k = 1, 2, 3. For the first set of 10 features, these means are uniformly selected from the range [0,30] and variance of 1 is used. For the second set of features, the three means are uniformly selected from the range [0, 30) and variance of 10 is used. Now that the modes of each Gaussian of each feature are defined, we generate the features as follows: for each feature i of user u of cluster k, we uniformly choose one of the three modes m E {1,2.3} Once the mode is selected, we generate a value from N N(uk
from mixture of three Gaussians with means Mk.s Mk.s
(())m)) o²) (where o² is for i E [1, 10] and 10 for i E [11, 20)). We decided to have these two sets of features as the first one (with lower variance) represents more relevant features which can help identify the clusters, while the second set (with higher variance) represents less meaningful features that may be similar for all clusters.
We create three separate datasets ,c), (i,,,, and PiC,,C,.Cs such that De is union of all the clusters in the set C. We report the C-index and Adjusted Rand index for the proposed method and the baselines on these simulated datasets in Table
Friendster dataset. Friendster dataset consists of around 15 million users with 335 million friend- ship links in the Friendster online social network. Each user has profile information such as age, gender, marital status, occupation, and interests. Additionally, there are user comments on each other's profile pages with timestamps that indicate activity in the site.
In our experiments, we only use data from March 2002 to March 2008, as after March 2008 Friendster's monthly active users have been significantly affected with the introduction of "new Facebook wall" (Ribeiro and Faloutsos| 2015). From this, we only consider a subset of 1.1 million users who had participated at least one comment, and had specified their basic profile information like age and gender. We will make our processed data available to the public at location (anonymized), We use each user's profile information (like age. gender, relationship status, occupation and location) as features. We convert the nominal attributes to one-hot encoded features. We compute the summary statisties of the user's activity over the initial 7=5 months such as the number of comments sent and received, number of individuals interacted with, etc. In total, we construct 60 numeric features that are used for each of the models in our experiments.
MIMIC III dataset. MIMIC III dataset consists of patients compiled from two ICU databases: Vue and Metavision. The dataset consist of 50,000 patients with a total of 330 million different measurements recorded. We mainly use three tables the dataset: PATIENTS, ADMI SSIONS, CHART_EVENTS. PATIENTS table consists of demographic information about every patient such as gender, date of birth, and ethnicity. ADMISSI SSTONS ONS table consists of the admission and discharge times of the patients. A patient can have multiple admissions; in our experiments, their longest stay. Finally, CHART_ EVENTS table records all the measurements of the patients taken during their stay such as daily weight, heart rate and respiratory rate. The measurements of the patients are shifted by an unknown offset (consistent across measurements for a single patient) for anonymity, hence all times are relative to the patient.
only consider
HEART_EVENTSS
Each entry in the CHART_ EVENTS table has column for item identifier that specifies the measured item (like heart rate). Since the dataset is compiled from different databases, same item can have multiple identifiers. We use the following time series for features: 'Peak Insp. Pressure", 'Platcau Pressure', 'Respiratory Rate'. 'Heart Rate". 'Mean Airway Pressure'. 'Arterial Base Excess', 'BUN', "Creatinine", 'Magnesium', 'WBC' and 'Hemoglobin', We observe each of these time series for = 24 hours from the patient's 'ss admission to the ICU, and compute summary statistics such as number of observations, mean, variance, mean inter-arrival times, etc. Complete processing script is provided in the supplementary material.
CHART_EVENTS
A.9 METRICS
Here describe the metrics used for evaluating the clusters obtained from the methods.
22

---

Under review as a conference paper at ICLR 2020
Concordance Index. Concordance index C-index (Harrell et al. 1982) is commonly used metric in survival applications (Alaa and van der Schaar 2017 Luck et al. 2017) to quantify a model's 's abilitt discriminate between subjects with different lifetimes. It calculates the fraction of pairs of subjects for which the model predicts the correct order of survival while also incorporating censoring. Concordance index and can be interpreted in a similar fashion, i.c., a C-index score of 1 denotes perfect predictions as compared a C-index score of 0.5 for random predictions.
be
generalization of AUROC (Area Under ROC curve)
Integrated Brier Score. Brier score (Brier
1950
Graf et al. 1999) is quadratic scoring rule,
computed as follows for survival applications,
B
(1[T()) t] 5((
(14)
max
where for a given subject u, T' is her true lifetime and Ş(u) is her empirical lifetime CCDF, Brier score is 0 for perfect predictions and 0.25 for random predictions.
Logrank Test Score. Logrank test Mantel 1966) is con-maraetrric hypothesis test that is used to compare survival distributions. The null hypothesis for the test is defined as Ho (i() ft((), i.e., the K groups have the same survival distribution. It is most appropriate when the observations are censored and the censoring is independent of the events. High values of the logrank statistic denote that it is unlikely that the K groups have the same survival distribution.
Adjusted Rand index. The Rand index (Rand 1971) is a measurement of cluster agreement, compared the ground truth clustering (if available). The adjusted version (Hubert and Arabie 1985) is a corrected-for-chance version of the Rand index, which assigns score of 0 for the expected Rand index, obtained by random cluster assignment. The maximum value of the Adjusted Rand index is 1. We use this metric only for the toy dataset where we have the ground truth cluster assignments available.
A. NEURAL NETWORK HYPERPARAMETERS
Parameter
Values
aHiddenLayers
2,
UliiddenUnits
[128, 256]
Minibatch Size
[128, 256, 1024]
Learning Rate
[10-3 10
Activation
[Tanh, ReLU]
Batch normalization
(True False]
L2 Regularization
[10- 0]
Table 5: Different neural network hyperparameters for the proposed approach used in our experiments. The best set of hyperparameters was chosen based on validation performance.
B RELATED WORK
Traditional survival analysis models. The Cox regression model (Cox, 1992) is widely used
method survival analysis to estimate the hazard function A (1) (t) = stw)(r) where dF(") the
dr (t)
probability density of F(,), The hazard function is then estimated using the covariates, ( of subject The hazard function has the form, (()]x()))= Ao {(("x(()) where Ao (t) is a base hazard function common for all subjects, and 3 are the regression coefficients. The model assumes that the ratio of hazard functions of any two subjects is constant over time. This assumption is violated frequently in real-world datasets (Li et al., 2015a). near-extreme case when this assumption does not hold is shown in Figure 2b where the survival curves of two groups of subjects cross each other.
Majority of the work in survival analysis has dealt with the task of predicting the survival outcome especially when the number of features is much higher than the number of subjects (Witten and
23

---

Under review as a conference paper at ICLR 2020
Tibshirani 2010a pre: Hothorn al. 2006: Shivaswamy et al. 2007). A number of approaches
have also been proposed to perform feature selection in survival data (Isharan et al.. 2010 Lagani and Tsamardinos 2010). In the social network scenario, [unn al. (2012) predicts the re relationship building time, that is, the time until a particular link is formed the network. [Alaa and van der
Schaar (2017) proposed nonparametric Bayesian approach for survival analysis in the case of more than one competing events (multiple diseases). They not only assume the presence of termination signals but also the type of event that caused the termination.
Survival (or lifetime) clustering. There have been relatively fewer works that perform lifetime clustering. Many unsupervised upproaches have been proposed identify cancer subtypes in gene expression data without considering the survival outcome (Eisen et al., 1998; Alizadeh et al. 2000).
Traditional semi-supervised clustering methods (Aggarwal et al.] 2004] Basu et al.] 2002 2004
Nigam et al., 1998) do not perform well in this scenario since they do not provide way to handle the issues with right censoring. |Birr and Tibshirani (2004) proposed semi-supervised method
for clustering survival data in which they assign Cox scores (Cox 1992) for each feature in their dataset and considered only the features with scores above a predetermined threshold. Then, an unsupervised clustering algorithm, like k-means, is used to group the individuals using only the selected features. Such an approach can miss out on clusters when the features are weakly associated with the survival outcome since such features discarded immediately after the initial screening. In order to overcome this issue, Gaynor and Bair (2013) proposes supervised sparse clustering as a modification to the sparse clustering algorithm of Witten and Tibshirani (2010b). The sparse clustering algorithm has a modified k-means score that uses distinct weights in the feature set; it initializes these feature weights using Cox scores (Cox
1992) and optimizes the same objective.
Bair and Tibshirani (2004) and Gaynor and Bair (013) assume the presence of termination signals. Additionally, there is disconnect between the use of survival outcomes and the clustering step in these algorithms. In this paper, we provide loss function that quantifies the divergence between lifetime distributions of the clusters, and we minimize said loss function using a neural network in order to obtain the optimal clusters.
Divergence measures. Since we need to optimize the divergence between two distributions using finite sample of training data, this problem is related to two-sample tests in statistics. Recently, there is growing interest in loss functions for comparing two distributions, including the Wasserstein distance (Dudley) 2002 p. 420) and the Maximum Mean Discrepancy (MMD) (Gretton et al. 2009 Fukumizu et al.| 2008). specifically in the context of training generative adversarial networks (GANs) (Arjovsky al. 2017 Li et al. 20155).
Traditional two-sample tests, such as the Balmogorov-Smimon (KS) test, are generally disregarded in learning tasks due to their alternating infinite series that makes gradient computations computationally expensive. The alternative state-of-the-art divergence approach that seems most suited to our problem is MMD Gretton et al. (2009), unfortunately, as seeing in our results, they can be less resilient to small sample sizes in empirical distributions.
Deep survival methods. Many deep learning approaches Luck al. (2017); Katzman al. (2018); Lee et al. (2018); Ren et al. (2018) have been proposed for predicting the lifetime distribution of a subject given her covariates. while effectively handling censored data that typically arise in survival tasks. DeepHit Lee et al.] 2018) introduced novel architecture and ranking loss function in addition to the log-likelihowe loss for lifetime prediction in the presence of multiple competing risks. Using a log-likelihoos loss similar to DeepHit, Ren et al. al. (2018) propose a recurrent architecture to predict the survival distribution that captures sequential dependencies between neighbouring time points. To the best of our knowledge, there hasn't 't been a work on using neural networks for a lifetime clustering task.
Frailty analysis. Extensive research has been done on what is known frailty analysis, for predicting survival outcomes in the presence of clustered observations (Hougaard 1995; Chuang et al. 2005 Huang and Wolfe 2002). Although frailty models provide more flexibility in the presence of clustered observations, they do not provide a mechanism for obtaining the clusters themselves, which is our primary goal.
24


Reviews:
[{"review_id": "S1lAJysb9r", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors propose an approach to cluster subjects into K clusters according to their underlying, often unknown, life distribution. The loss function to the neural-network-based approach is based on a tight upper bound to the two-sample Kuiper test. Experiments are conducted on artificial and two real life datasets.\n\nI enjoyed reading the paper, the authors propose an approach to address an important yet relatively under-explored problem in survival analysis.\n\nIt is not entirely clear how to handle the case when after the model is trained, H^(u) for a new subject u is larger than t_max when the model is trained. In such case, \\Chi^(u) will be negative, thus what happens with \\beta^(u)(W_2)?\n\nWhen the termination signals are not available (friendster data) termination signals are set artificially when training and evaluation, thus, is the model learning artificially set termination signals and thus artificial survival functions? what is the point of doing this? Moreover, if the termination signals are artificial, what is the point of calculating C-Index and Integrated Brier score? I understand the motivation to compare to existing methods, it is really not clear how meaningful they are at evaluating performance.\n\nIn general, using C-Index and Brier scores in the context of the presented application may be misleading (or non-applicable) because these metrics are usually applied to survival analysis scenarios where one seeks to estimate likelihood of survival or time to event (over a usually infinite time horizon). Here, \\beta^(u)(W_2) is a function of \\Chi^(u) which is known (also not comparable to survival analysis), artificially tied to a pre-specified time-horizon t_max, and not dependent on covariates as in survival analysis. Further, SSC-Bair and SSC-Gaynor are clustering models, how are survival estimates obtained for these?\n\nIn practice, how is K selected? based on the friendster results for K=2,3,4,5 they all seem to produce distinct clusters, so which one should be used? This raises a question: how are the clusters, their members or the number of clusters informing the use case? In the MIMIC III experiment, where events are observed, the model finds two clusters without strikingly different survival functions (relative to friendster). Can one really consider S_2 as the high-risk group? Can one get higher risk clusters with larger K?\n\nMinor:\n- A_i^(u) is missing from the definition in the training data.\n- In Section 3.2, if \\xi^(u) is shared, why the superscript indicating that is subject specific?", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "H1gI2HOCYB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a method to cluster subjects based on the latent lifetime distribution. The proposed model clusters by maximizing the empirical divergence between different clusters. \n\nThe problem setting of this paper is not clear to me. I am not sure which variables are observed and which are not.  For example, in the Friendster experiment, the data of 5 months from joining is used for clustering. However, the termination windows are chosen to be 10 months. Therefore, it is clear that the observed data will not contain the termination signals, and I do not believe the training of the model is possible, without observing any termination signals.  In the paper, do we consider only one type or multiple types of events? Is $M_{k, i}$ a vector that represents the attributes or properties of an event?\n\nSome details of the model are not clear to me. In Equation (2), the input of the neural network differs in length across different subject $u$, because the number of observed events for each subject is different. \nHow does the proposed neural network take inputs of different lengths?\nHow the non-decreasing function $\\xi^{(u)}$ is defined in Section 3.2? Is it a function of the observed data for each subject?  \n\nHow the empirical distribution $\\hat{S}_i$ in Equation (4) is computed is also not clear to me. How $\\hat{S}_i$ is a vector? Is it constructed by concatenating $\\hat{S}_k(W_1, W_2; D)[t] $ with different $t$? How to normalize $\\hat{S}_i$ such that it is a valid probabilistic distribution? Since $\\hat{S}_i$ is high dimensional, it looks very challenging to estimate the joint distribution.\n\nThe overall objective function is given by Equation (4), is it correct? In Equation (4), why should we compute the minimum values across all possible pairs of clusters rather than the summation of all pairs? If Equation (4) is the overall objective function, then it looks like the model does not contain a component that maximizes a likelihood function. How is it guaranteed that the model will fit the data? It looks like the model will converge to a trivial solution that $\\beta$ is a constant such that $\\beta = 1$ for one cluster and $\\beta = 0$ for another cluster, if the likelihood function is not involved. This will give a maximum divergence between distributions. \n\nIn summary, it seems that numerous technical details are missing and the paper might contain technical flaws. I do not suggest the acceptance of this paper.\n\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "B1l4mKqqFS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a deep learning method for clustering subjects (patients, users of social networks) into clusters of different lifetime (survival time) distributions. Inputs for a subject include covariates (age, gender, etc) and an event sequence. A key difficulty in the problem is that the lifetime of a subject is often unobserved. The proposed method is to learn a termination function that is non-decreasing with time, which essentially treats prolonged inactivity as termination in a probabilistic way. Clustering is done in a discriminative manner where the objective function considers cluster sizes besides between-cluster differences in lifetime distribution. (The inclusion of cluster size information in the objective function avoids degenerate clustering results.)\nThe paper is strong in technical contents. The objective function is well-motivated and placed on solid theoretical foundation. Empirically, the proposed method performed significantly better than baselines.\nThe weakness of the paper is that the utility of the work has not been demonstrated. For example, the Friendster dataset (1.1 million social network users) is partitioned into 2-5 clusters. However, are there clusters that a service provider can use to improve their service? It is doubtful whether such “useful” clusters can be found using the proposed algorithm. One might need to obtain a fairly large number of clusters, via conditioning perhaps, before finding some really useful ones. \n•\tThe paper is strong in technical contents. The objective function is well-motivated and placed on solid theoretical foundation.\n•\tEmpirically, the proposed method performed significantly better than baselines. \n•\tThe utility of the work has not been demonstrated. Potential impact is an outstanding issue here because the proposed method is very special-purpose. \n\nQuestion to the authors: It is observed that the numbers of friends and comments are strongly correlated with the clustering. Were those two covariates included in the analysis? If not, why?\n\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors propose a clustering algorithm for users in a system based on their lifetime distribution. The reviewers acknowledge the novelty of the proposed clustering algorithm, but one concern left unresolved is how the results of the analysis can be of use in the real world examples used. 
Decision: Reject