Year: 2019

Abstract:
Convolutional neural network (CNN) for time series data implicitly assumes that the data are uniformly sampled, whereas many event-based and multi-modal data are nonuniform or have heterogeneous sampling rates. Directly applying regular CNN to nonuniform time series is ungrounded because it is unable to recognize and extract common patterns from the nonuniform input signals. Converting the nonuniform time series to uniform ones by interpolation preserves the pattern extraction capability of CNN, but the interpolation kernels are often preset and may be unsuitable for the data or tasks. In this paper, we propose the Continuous CNN (CCNN), which estimates the inherent continuous inputs by interpolation, and performs continuous convolution on the continuous input. The interpolation and convolution kernels are learned in an end-to-end manner, and are able to learn useful patterns despite the nonuniform sampling rate. Besides, CCNN is a strict generalization to CNN. Results of several experiments verify that CCNN achieves a better performance on nonuniform data, and learns meaningful continuous kernels.

heading: 1 INTRODUCTION
text: Convolutional neural network (CNN), together with recurrent neural network (RNN), is among the most popular deep learning architectures to process time series data. However, both CNN and RNN rest on the assumption that both the input and output data are sampled uniformly. However, many time-series data are event-based and thus not uniform in time, such as stock price (Gençay et al., 2001), social media data (Chang et al., 2016) and health care data (Johnson et al., 2016).
There are several easy solutions to adapt CNN to accommodate nonuniform time series. The first solution is to directly append the time stamps or time intervals to the input features, which are then fed into a regular CNN (Zhang et al., 2017). However, the problem is that, without the uniform sampling assumptions, the application of the regular CNN is ungrounded, and thus the performance is compromised. This is because one major justification of CNN is that the filters/kernels are able to extract useful patterns from input signals. But if the sampling rate varies, the traditional CNN will no longer be able to recognize the same pattern.
A second obvious solution is to transform the nonuniform time series to uniform by interpolation, and then feed the transformed signal to a regular CNN. This approach preserves CNN’s ability to extract signal patterns despite the nonuniform sampling. However, simple interpolation schemes require preset interpolation kernels, which are not flexible and may not fit the signal or the task well. To sum up, most existing CNN-based remedies for nonuniform time series either cannot reasonably capture the signal patterns or are too inflexible to maximize the performance in a data-driven manner.
Motivated by these challenges, we propose Continuous CNN (CCNN), a generalization to CNN for nonuniform time series. CCNN estimates the implicit continuous signal by interpolation, yet performs continuous convolution on the continuous signal. As a result, CCNN is capable of capturing the useful patterns in the implicit input signal, which is of nonuniform sampling rate or naturally has an uneven time interval. Furthermore, the interpolation and convolution kernel functions are not preset, but rather learned in an end-to-end manner, so that the interpolation is tailored for each task. Finally, we show that CCNN and CNN are equivalent in terms of representation power under a uniform sampling rate. As shown in section 5, CCNN can achieve much better performance than the state-of-the-art systems on non-uniform time series data.
The proposed CCNN can also be well-combined with the temporal point process (TPP). TPP is a random process of event occurrence, which is capable of modeling nonuniform time intervals. However, most existing TPPs require inflexible preset parameterization. CCNN is able to expand the power of TPP by replacing the modeling of the history contribution with a CCNN module.

heading: 2 RELATED WORKS
text: There are some research efforts of adapting RNN for nonuniform series. Some works (Pearlmutter, 2008; Funahashi & Nakamura, 1993; Cauwenberghs, 1996) use continuous-time dynamical system methods to design RNN structures. Phased-LSTM (Neil et al., 2016) and Time-LSTM (Zhu et al., 2017) introduce a time gate that passes the data at a certain frequency. Similar ideas can be found in Clockwork RNN (Koutnik et al., 2014) and DilatedRNN (Chang et al., 2017). (Mei & Eisner, 2017) and (Du et al., 2016) explicitly model the sequence as a temporal point process and utilize RNN structure to encode the sequence history.
For non-neural network-based approaches, the probabilistic generation process of both events and its timestamps is assumed. (Liu & Hauskrecht, 2016) deals with irregularly sampled time series by direct value interpolation and estimates the model via EM algorithm. (Wang et al., 2016; Du et al., 2015) base their model on the Hawkes process and estimate via conditional gradient algorithm.
The proposed CCNN is well supported by works on spiking neural networks (SNN) (Maass, 1997), which mimic how human brains process information. The inputs to SNNs are spike chains with nonuniform intervals that carry information. An important class SNNs (Eliasmith & Anderson, 2004; Tapson & van Schaik, 2013; Tapson et al., 2013) convolves the input with continuous kernel functions, which is similar to the key step of CCNN. However, CCNN differs from SNN in two aspects. First, for SNN, the input information resides in time intervals, not in the inputs values; the goal of the SNN convolution is to extract time interval information. In contrast, the input information for CCNN resides in input values, not time intervals; the goal of the continuous convolution is to remove the interference of nonuniform sampling. Second, CCNN learns the kernel functions in a data-driven manner, whereas SNN employs predefined kernel functions.
Nonuniform time series processing is related to the task of point set classification, where the input is a set of points nonuniformly distributed in the Rd space (d = 3 in most cases). Several existing methods directly work on the coordinates of the points (Qi et al., 2017a;b). Some alternative approaches turn the point sets into graphs by establishing edge connections among nearest neighbors (Shen et al., 2017; Wang et al., 2018). The graph approaches utilize distance information to some degree, but the distance information is quantized. CCNN, on the other hand, make full use of the time interval information.

heading: 3 THE CCNN ALGORITHM
text: Our problem is formulated as follows. Given a nonuniform input sequence x(t1), x(t2), · · · , x(tN ) ∈ Xin, where the input time stamps tn ∈ Tin can be distributed nonuniformly, our goal is to design a continuous convolutional layer that can produce output for any arbitrary output time t, y(t).
The proposed CCNN solves the problem via two steps:
(1) interpolation to recover the continuous signal x̂(t);
(2) continuous convolution on x̂(t).
Furthermore, rather than applying a preset interpolation, CCNN learns the interpolation kernel and the convolution kernel in an end-to-end manner. The following two subsections elaborate on the two steps respectively. The channel dimension and input dimension are set to one for simplification.

heading: 3.1 INTERPOLATION
text: CCNN reconstructs the underlying continuous input signal, x̂(t), by interpolating among nonuniform input samples.
x̂(t) = N∑ i=1 x(ti)I(t− ti;Tin,Xin) + ε(t;Tin,Xin) (1)
where the first term is the interpolation term, and I(·) is the interpolation kernel; the second term is the error correction term. For the first term, a form analogous to the Parzen window approach Parzen (1962) is used. Many interpolation algorithms can be expressed in this form (refer to Appendix A), illustrated in Fig. 6. Considering the versatility of I(·), the interpolation algorithms representable by Eq. (1) are vast. The error correction term, ε(·), are assumed to be determined by the input output time stamps and input values, hence its arguments include t, Tin and Xin.

heading: 3.2 CONTINUOUS CONVOLUTION
text: Analogous to a standard CNN layer, after the continuous input is estimated by interpolation, the CCNN layer performs a continuous convolution to produce the final output.
y(t) = x̂(t) ∗ C(t) + b (2)
where ∗ denotes continuous convolution, C(t) denotes the convolution kernel, and b denotes bias. Unfortunately, I(·), ε(·) and C(·) are not individually identifiable. To see this, we combine Eqs. (1) and (2).
y(t) = N∑ i=1 x(ti) [I(t− ti;Tin,Xin) ∗ C(t)]︸ ︷︷ ︸ collapsed kernel function + [ε(t;Tin,Xin) ∗ C(t) + b]︸ ︷︷ ︸ collapsed bias function
= N∑ i=1 x(ti)K(t− ti;Tin,Xin) + β(t;Tin,Xin)
(3)
whereK(t;Tin,Xin) is the collapsed kernel function, representing the combined effect of interpolation and convolution; β(t;Tin,Xin) is the collapsed bias function, representing the combined effect of error correction and convolution.
Eq. (3) shows that learning the interpolation and convolution kernels and errors is now simplified into learning the collapsed kernel and bias functions. Once these two functions are learned, the final output can be readily computed using Eq. (3). The next section will explain how CCNN is structured to learn these functions in an end-to-end manner.

heading: 4 THE CCNN STRUCTURE
text: Following the discussion in Sec. 3, a CCNN layer is divided into three parts: the kernel network learning the collapsed kernel function, the bias network learning the collapsed bias function, and the main network producing the final output using Eq. (3).

heading: 4.1 THE KERNEL NETWORK
text: The basic idea of the kernel network is to represent the kernel function using a neural network, based on the fact that a neural network can represent any function given enough layers and nodes (Hornik, 1991). In order to regularize the complexity, a few assumptions on K(·) are introduced:
Stationarity and Finite Dependency: The dependency of K(·) on Tin is relative to the output time t, and is constrained to among the adjacent time stamps, i.e.
K(t− ti;Tin,Xin) = K({t− ti±k, x(ti±k)}k=0:OK ) (4)
where {t − ti±k, x(ti±k)}k=0:OK denotes the set of t − ti±k and x(ti±k) where k runs from 0 to OK , and OK is the order of the kernel network. Notice that the examples in Eqs. (14)-(16) and many other interpolation kernels still satisfy this assumption.
Finite Kernel Length: The collapsed kernel function has finite length.
K(t− ti;Tin) = 0,∀|t− ti| > LK (5)
where LK is the kernel length. This assumption implies the interpolation and the convolutional kernels both have finite length. While many interpolation kernels do have finite length (e.g. Eqs. (14) and (15)), others do not (e.g. Eq. (16)). Nevertheless, most infinite-length interpolation kernels, including Eq. (16), have tapering tails, and thus truncation on both sides still provides good approximations. Regarding the convolutional kernel, the finite length assumption naturally extends from the standard CNN.
Fig. 2(a) shows the kernel network structure, which is a feedforward network. According to Eq. (4), the inputs are ({t−ti±k, x(ti±k)}k=0:OK ). The output represents the kernel function, which is forced to be zero when |t− ti| > LK . To reduce learning difficulties, the time differences are fed into an optional two-hot encoding layer, which will be discussed later in details.

heading: 4.2 THE BIAS NETWORK
text: For the bias network, a similar stationarity and finite dependency assumption is applied as follows.
β(t;Tin,Xin) = β({t− tj∗±k, x(tj∗±k)}k=0:OB ), (6)
where tj∗ is the closest input time stamp to output time t:
tj∗ = argmin tj∈Tin
|tj − t| (7)
and OB denotes the order of the bias network. The only difference from Eq. (4) is that the closest input time stamp, tj∗ , is chosen as a reference on which the time difference and the adjacent input time stamps are defined, because the major argument of the bias function is the output time itself, t, instead of the input-output time difference t− ti. Fig. 2(b) shows the bias network, which is also a feedforward network.

heading: 4.3 CAUSAL SETTING
text: For causal tasks, current output should not depend on future input, and therefore the t− ti±k terms that are greater than 0, as well as the corresponding x(ti±k), are removed from Eq. (4). Similarly, t− tj∗±k that are greater than 0, as well as the corresponding x(tj∗±k), are removed from Eq. (6). Also, the condition bound in Eq. (5) is replaced with t− ti > LK or t− ti < 0.

heading: 4.4 TWO-HOT ENCODING
text: The kernel and bias functions can be complicated functions of the input times, so model complexity and convergence can be serious concerns. Therefore, we introduce a two-hot encoding scheme for the input times, which is an extension to the one-hot scheme, but which does not lose information.
Denote the time difference value to be encoded as ∆t. Similar to one-hot, the two-hot encoding scheme partitions the range of ∆t into D − 1 intervals, whose edges are denoted as π1, π2, · · · , πd. However, rather than having a length-D − 1 vector representing the intervals, two-hot introduces a length-D vector representing the edges. When ∆t falls in an interval, the two elements corresponding to its two edges are lit. Formally, denote the encoded vector as g, and suppose ∆t falls in interval [πk, πk+1). Then
gk = πk+1 −∆t
δ , gk+1 = ∆t− πk δ ; gl = 0, ∀l /∈ {k, k + 1} (8)
where δ = πk − πk−1 denotes the interval width (all the intervals are set to have equal width); gk denotes the k-th element of g. Fig. 3 gives an intuitive visualization of the encoding process.
As an example explanation of why two-hot helps, it can be easily shown that a one-layer feed-forward network can only learn a linear function (a straight line) without any encoding, but a piecewise constant function with one-hot encoding, and yet a piecewise linear function with two-hot encoding.

heading: 4.5 COMBINING WITH TEMPORAL POINT PROCESSES
text: For tasks like predicting the time interval till the next event, the output of CCNN will be the predicted probability distribution of the time interval, which requires a good probabilistic model characterizing the likelihood of these intervals. Temporal point process (TPP) is a popular and general model for the timestamps of the random processes {x(ti), ti} whose time intervals are nonuniform. It turns out that CCNN can be well combined with TPPs in modeling the time interval prediction task, in a similar way to Du et al. (2016).
A TPP is parameterized by λ∗(t), which depicts the rate of the probability of the event occurrence. Formally
λ∗(t)dt = Pr ( Event i happens in [t, t+ dt) ∣∣∣∣∣⋃ j<i {x(tj), tj} ) (9)
It can be shown that the probability density function (PDF) of an event happening at time t conditional on the history of the events ⋃ j≤i−1{x(tj), tj} can be expressed as
f∗(t) = λ∗(t) exp ( − ∫ t ti−1 λ∗(τ)dτ ) . (10)
Rather than applying some preset functional form for λ∗(t) as in conventional TPPs, we propose to use a CCNN to model λ∗(t) as follows. First, we pass the historical time series to a CCNN to learn a history embedding
hi−1 = CCNN  ⋃ j≤i−1 {x(tj), tj}  , (11) where CCNN (·) is just a functional abstraction of CCNN. Then λ∗(t) is obtained by combining the history information and the current time information as follows
λ∗(t) = exp(vhi−1 + w(t− ti−1) + b), (12)
0 1 2 3 4 5 6 7 (a) t (Period=4)
2
1
0
1
K er
ne l W
ei gh
t K (
t)
T/2 = 2.0
0 1 2 3 4 5 6 7 (b) t (Period=5)
2
1
0
1
K er
ne l W
ei gh
t K (
t)
T/2 = 2.5
0 1 2 3 4 5 6 7 (c) t (Period=6)
2
1
0
1
K er
ne l W
ei gh
t K (
t)
T/2 = 3.0
0 1 2 3 4 5 6 7 (d) t (Period=7)
2
1
0
1
K er
ne l W
ei gh
t K (
t)
T/2 = 3.5
Figure 4: The learned continuous kernel function on the sine, as functions of ∆t = t− ti.
where v,w and b are trainable parameters. Combining Eqs. (10) and (12), we can obtain a closed-form expression for f∗(t)
f∗(t) = exp ( vhi−1 + w(t− ti−1) + b+ 1
w
( exp(vhj−1 + b)− exp(vhj−1 + w(t− tj−1) + b) )) .
(13) By maximizing this likelihood on the training data, we can estimate the conditional distribution of the time intervals. To obtain a point estimate of the time interval till the next event, we compute the expectation under Eq. (13) numerically.
Du et al. (2016) also applies the same approach, but the history embedding hi−1 is computing by a regular RNN. CCNN, with its improved processing of nonuniform data, is expected to produce a better history embedding, and thereby a better estimate of the time intervals.

heading: 4.6 SUMMARY AND GENERALIZATION
text: Fig. 2 illustrates the structure of a CCNN layer. To sum up, the kernel network and bias network learn the continuous kernel and bias as functions of t, Tin and Xin. The main network applies these functions to produce the output according to Eq. (3). The hyperparameters include OK (Eq. (4)), LK (Eq. (5)), OB (Eq.(6)) and δ (Eq. (8)).
It is worth highlighting that CCNN not only accommodates arbitrary input timestamps, it can also produce output at any output timestamps, by simply adjusting the value of t in Eqs. (3), (4) and (6). So a CCNN layer can accept input at a set of timestamps, and produces output at a different set of timestamps, which is very useful for resampling, interpolation, and continuous sequence prediction.
When the inputs x(ti) and output y(t) need to be multidimensional, according to Eq. (3), K(·) and β(·) become vectors or matrices with matching dimensions. Therefore, we simply need to adapt the output of the kernel and the bias networks from scalars to vectors or vectorized matrices. Also, a multi-layer CCNN can be constructed by stacking individual CCNN layers, with the input timestamps of a layer matching the output timestamps of its previous layer.

heading: 5 EVALUATION
text: In this section, CCNN is evaluated on a set of prediction tasks on both simulated and real-world data.

heading: 5.1 PREDICTING SIGNAL VALUE ON SIMULATED DATA
text: The prediction task predicts the next sample x(tN+1), given the previous nonuniform samples x(t1) · · ·x(tN ). Datasets The synthetic datasets are generated by unevenly sampling from three standard time series: Sine, Mackey-Glass(MG) and Lorenz. The details of the time series are introduced in Appendix C.1
Baselines The following algorithms are compared:
• CCNN: The proposed algorithm. The first layer is a CCNN layer which takes both the sampling time intervals and the signal sequence. After the CCNN layer, the sequence is resampled onto a
uniform time interval. For predicting future label, signal value, and interval, the CCNN is configured using only past value, i.e. CCNN kernel has non-zero value only when t′ − LK < ti < t′, shown in Fig. 1. The time information is either two-hot encoded (Adams et al., 2010) (CCNN-th) or not encoded (CCNN).
• CNN: data are directly fed into a regular CNN, with no special handling of nonuniform sampling. • CNNT: The sampling time intervals are appended to the input data, which are fed to a regular CNN. The time information is either two-hot encoded (CNNT-th), or not encoded (CNNT).
• ICNN: data are interpolated to be uniform before being fed to a regular CNN. Piecewise Constant (ICNN-P), linear (ICNN-L), quadratic (ICNN-Q), cubic spline (ICNN-C) and sinc (ICNN-S) interpolation algorithms are implemented.
• RNNT: the sampling time intervals are appended to the input data, then are fed into a vanilla RNN. The time information is either two-hot encoded (RNNT-th), or not encoded (RNNT).
All the networks have two layers with ReLU activations in the hidden layers and no activations in the output layer. For CNN, ICNN, and CNNT, the convolution kernel length of each layer is set to 7. For ICNN, the input signal is interpolated at timestamps tN+1 − k, k = 1, · · · , 13 to form a uniform sequence before feeding into two-layers regular CNN. For CCNN, the output time stamps of the first layer are tN+1 − k, k = 1, · · · , 13. The kernel length LK = 3. Since its input is uniform, the second layer of CCNN is a regular convolutional layer, with kernel length 7. These configurations ensure that all the neural networks have the same expected receptive field size of 13.
The rest of the hyperparameters are set such that all the networks have comparable number of parameters, as in Appendix C.2. All the networks are trained with Adam optimizer Kingma & Ba (2014) and mean squared error (MSE) loss. The training batch size is 20. The number of training steps is determined by validation. The validation set size is 10,000.
Results and Analysis Table 11 lists the MSEs. There are three observations. First, CCNN-th outperforms the other baselines in terms of prediction accuracy. Notice that the number of convolution channels of CCNN are significantly smaller than most of the other baselines, in order to match the number of parameters. Nevertheless, the advantage in properly dealing with the nonuniform sampling still offsets the reduction in channels in most tasks. Second, interpolation methods (ICNNs and CCNN) generally outperform the other baselines, particularly CNNT. This again shows that interpolation is more reasonable for dealing with nonuniform time series than simply appending the time intervals. Furthermore, preset interpolation algorithms (ICNNs) can rarely match CCNN that has the flexibility to learn its own interpolation kernel. Third, two-hot encoding usually improves performance. Again, there are fewer channels with two-hot encoding in order to match model complexity, but the advantage of two-hot encoding still stands out.
Kernel Analysis In order to visualize the learned continuous kernels K(t− ti;Tin,Xin), we set the CCNN network has the same configuration except CCNN filter number is 1, and is trained separately with nonuniformly sampled (λ = 1) sine signals with T = 4, 5, 6, 7. The learned continuous kernel function is quite interpretable. Each kernel is a sine-like function with estimated period equaling the underlying signal period shown in Fig. 4

heading: 5.2 PREDICTING TIME INTERVALS TO NEXT EVENT
text: We then evaluate CCNN on real-world data to to predict the time intervals to the next event.
Datasets and Configurations Four time series datasets with nonuniform time intervals are introduced, i.e. NYSE, Stackoverflow2, MIMIC ((Johnson et al., 2016)) and Retweet ((Zhao et al., 2015)). Detailed information are provided in Appendix C.3. The input sequence is the timestamps and the one-hot encoded types of a series of events. The task is to predict the time interval until the next event of a specific type, given the previous events. As mentioned in Sec. 4.5, following the design in (Du et al., 2016), the input sequence is assumed to be generated via an underlying marked TPP, where the time stamps follow a TPP, and the marker, i.e. the type of the event, is generated from a multinomial distribution conditioned on history. The output of the networks is a condition intensity function λ∗(t)
1Hereafter, in tables, the numbers in parentheses show standard deviation. 2https://archive.org/details/stackexchange
as in Eq. (12). The loss function is the log-likelihood of the training set as in (Du et al., 2016). As the model prediction, the expected duration is computed numerically from the estimated conditional distribution. The evaluation metric is the MSE of the expected duration and the actual duration to the next event. Configurations of all the models are the same as in previous experiments except that: the one-hot encoded event types, {x(ti)}, are first passed through an embedding layer, which is a 1× 1 convolutional layer with a channel dimension of 8, and the resulting embedded vectors are then fed into the networks.
This task is a causal task, where current output should not depend on future input. Therefore, the CCNN configuration is adapted to the causal setting, as discussed in section 4.3.
Baselines We benchmark with two baselines specialized for this type of tasks, Recurrent Marked Temporal Point Process (RMTPP) (Du et al., 2016) and N-SM-MPP (Mei & Eisner, 2017). N-SMMPP is the current state-of-the-art deep learning method. For NYSE, StackOverflow and MIMIC, we directly compare to the results (Mei & Eisner, 2017) reported, and re-implemented RMTPP to benchmark ReTweet. Configurations for CCNNs are provided in Appendix C.4.
Results and Analysis Fig. 5 shows the estimated event interval (expectation of Eq. (10)) and RMSEs. The upper plots show that the predicted interval aligns well with ground truth and result in smaller RMSE in the MIMIC and Retweet dataset. In NYSE and StackOverflow, though the groud truth shows extremely fluctuation on event intervals and CCNNs fail to predict accurately as in MIMIC and ReTweet, the predicted interval still tends to capture the increase and decrease trend. The lower plots compare the RMSE with the baselines. CCNN algorithms outperformed two baselines in all datasets. There is a slight advantage of CCNN-th over CCNN, which verifies the effectiveness of two-hot encoding.

heading: 5.3 ADDITIONAL EXPERIMENTS
text: Two additional experiments on real-world data, which are predictions on Data Market and interpolation on speech, are presented in Appendix D.

heading: 6 CONCLUSION
text: In this paper, we have introduced CCNN for nonuniform time series with two takeaways. First, interpolation before continuous convolution is shown to be a reasonable way for nonuniform time series. Second, learning task-specific kernels in a data-driven way significantly improves the performance. There are two promising directions. First, we have focused on 1D convolution, but this framework can be generalized to multi-dimensional nonuniform data. Second, while the computational complexity is similar for CCNN and CNN, the runtime of the former is much longer, because of the lack of parallelization. Fast implementation of CCNN is thus another research direction.

heading: B REPRESENTATION POWER ANALYSIS
text: In this section, we study how the proposed CCNN layer relates to and compares against two CNN baselines in terms of representation power. The first baseline is simply a regular convolutional layer, and the second baseline is a convolutional layer with input time intervals, ∆ti, appended to the input features, which we will call CNNT throughout.

heading: B.1 CASE 1: OUTPUT TIMESTAMPS SAME AS INPUT
text: This subsection intuitively explains why CCNN has a superior representation power to CNNT. Suppose the output timestamps are the same as input timestamps, i.e. t ∈ Tin. Then, combining Eq. (3) with Eqs. (4)-(6), we have
y(tj) = ∑ i x(ti)K(tj − ti;Tin,Xin)
+ β(0; {tj − tj±k, x(tj±k)}k=0:OB ). (17)
In contrast, for a CNNT layer, if we separate the convolution on time interval from the rest
y(tj) = ∑ i x(ti)Kj−i + [∑ i (tj − tj−1)K ′j−i + b ] . (18)
The second term of Eq. (17) represents a feed-forward network on {tj − tj±k, x(tj±k)}k=0:OB , whereas the second term of Eq. (18) can be regarded as a one-layer feed-forward network on
{tj − tj−1}, which is equivalent to a one-layer feedforward network on {tj − tj±k}k=1:OB . In other words, appending the time interval feature to the convolution layer is only a weak version of the CCNN bias network.
Yet a more fundamental disadvantage of CNNT lies in the first term, where the convolution kernel of CNNT, Kj−i, does not depend on the actual time difference, but the order in which the sample arrives. This makes CNNT very vulnerable to the sampling variations. CCNN, on the other hand, has a more robust kernel function for nonuniform data.

heading: B.2 CASE 2: UNIFORM TIMESTAMPS
text: Both CNNT and CCNN have the same representation power as CNN under uniform sampling rate, and thus both are strict generalizations to CNN. For CNNT this is trivial because the second term of Eq. (18) reduces to a constant. For CCNN, we have the following theorem.
Theorem 1. Let F be the set of all functions that can be represented by a CCNN layer, and G be the set of all functions that can be represented by a 1×W convolutional layer. Then F = G, if the following conditions hold:

heading: 1. the input and output timestamps are uniform and the same, i.e. ∆ti = ∆t, ∀i.

heading: 2. The two-hot encoding interval boundaries are at multiples of ∆t, i.e. πk = k∆t.

heading: 3. The dimension of the two-hot vector of CCNN is no smaller than the CNN kernel length, i.e.
text: D ≥W .

heading: 4. If the kernel network has hidden layers, the hidden node dimension is no smaller than W .
text: 5. CCNN and CNN have the same receptive field size, i.e. 2LK = W∆t.
6. The kernel and bias networks do not depend on Xin.
Proof to Theorem 1. We will only consider the 1D case. The generalization to multi-dimensional cases is straightforward. The regular 1×W CNN performs the following operation to generate the output sequence
y(τk) = k+(W−1)/2∑ i=k−(W−1)/2 x(ti)Kk−i + b (19)
where { K−(W−1)/2, · · · ,K(W−1)/2 } and b are trainable parameters. Here we implicitly assume that W is odd. We will prove the theorem by primarily utilizing the correspondence between Equations (17) and (19).
•F ⊂ G: ∀K({tj − tj+k}k=±0:±OK ) represented by the kernel network, and ∀β({tj − tj+k}k=1:OB ) represented by the bias network, and thereby ∀f ∈ F. By Eq. (4) and Cond. 1, the arguments of the kernel function K(·), namely the input to the kernel network, can only be a set of consecutive multiples of ∆t, i.e.
K({(w + k)∆t}k=±0:±OK ) (20)
where w is an integer.
Moreover, from Eq. (5) and Cond. 5, K(·) is non-zero iff w lies in the interval [−(W − 1)/2, (W − 1)/2].
Similarly, from Eq. (17) and Cond. 1, the arguments of the bias function β(·) can only take one set of values:
β({k∆t}k=±1:±OB ) (21)
Then, Eq. (19) can be made equivalent to Eq. (17) by setting
Kw = K({(w + k)∆t}k=±0:±OK ) b = β({k∆t}k=±1:±OB )
(22)
which means f ∈ G. Here concludes the proof that any CCNN layer can be matched by a CNN layer.
•G ⊂ F Here we would only prove the case where both the weight network and bias network of CCNN has only one layer, which is the most difficult case. If either network has more than one layers, the proof is easily generalizable by setting the bottom layers to identity, which is feasible because of Cond. 4. Also, we only consider the case where the kernel network order and the bias network order are both ones, i.e.
OK = 1, OB = 1 (23)
The proof can be generalized to larger orders by setting the additional weights to zero. In the special case defined above, the kernel network in Eq. (20) is further simplified to K(w∆t). The bias network in Eq. (21) is further simplified to β(0).
Further, notice that the w∆t, as the input to the kernel network, has to go through two-hot encoding. By Cond. 2 and 3, the two-hot encoding of w∆t is a one-hot vector, where only the w-th dimension is activated and the rest is zero. Since the kernel network is a one-layer feedforward network, denote the weight connected to the w-th dimension of the two-hot vector as Pw, then we have
K(w∆t) = Pw (24)
∀{Cw} and b that define a CNN layer, and thereby ∀g ∈ G, let
Pw =
{ Kw if− W−12 ≤ w ≤ W−1 2
0 otherwise (25)
Cond. 3 ensures that there are enough number of nontrivial Pws to cover all the w in the case specified in line 1 of the equation above; and let
β (0) = b (26)
which means the bias network learns a constant. Then the CCNN layer can be made equivalent to the CNN layer, i.e. g ∈ F. Here concludes the proof that any CNN layer can be matched by a CCNN layer.
Thm. 1 implies that in the uniform case where the increased model complexity of CCNN is not needed, it will not harm the performance either. Replacing CNN or CNNT with CCNN will not be worse off regardless of how the data are distributed in time.
As a final remark, readers may argue that the improved representation power of CCNN is merely a trivial result of increased model complexity, not because CCNN handles the time information more correctly. However, as will be shown in the next section, even with matching model complexity, CNN and CNNT are still unable to match the performance of CCNN. CCNN does not just increase the model complexity but increases the model complexity the right way.

heading: C EXPERIMENT SETTINGS

heading: C.1 PREDICT FUTURE SIGNAL VALUE TASK: DATA GENERATION
text: Three standard time series functions are introduced as x(t).
• Sine: x(t) = sin
( 2πt
T
) (27)
where T = 5. The sampling time intervals follow the Poisson distribution with mean parameter λ = 1.

heading: Alg. DM1 DM2 DM3 DM4 DM5 DM6 DM7 DM8 DM9 DM10 DM11 DM12 DM13
text: • Mackey-Glass (MG): a chaotic time series inspired by biological control systems (Glass & Mackey, 1979). MG is the solution to the following delay differential equation.
ẋ(t) = β x(t− τ)
1 + x(t− τ)n − γx(t) (28)
where ẋ denotes dx/dt. We choose β = 0.2, τ = 17, n = 10, and γ = 0.2. There is no closed-form solution to Eq. (28), so the Runge-Kutta method Bogacki & Shampine (1989) is applied to obtain a discrete numerical solution, which is a uniform sequence with sampling interval ∆t. A set of N -sample short uniform sequences are generated from the long sequence by a sliding window with window shift of one. The uniform sequences are subsampled into nonuniform sequences by choosing M (M < N ) sample points uniformly at random.1 ∆t = 2, N = 42, M = 14 on this dataset. The timestamps are normalized such that the expected interval of the nonuniform sequences is one.
• Lorenz: a simplified system describing the 2D flow of fluid (Lorenz, 1963). The Lorenz function is the solution to the following differential equation system.
ẋ(t) = σ(y(t)− x(t)) ẏ(t) = −x(t)z(t) + rx(t)− y(t) ż(t) = x(t)y(t)− bz(t)
(29)
We choose σ = 10, r = 28, b = 8/3. The nonuniform subsequences are generated the same way as in MG with ∆t = 0.05. Only x(t) is observed and predicted.

heading: C.2 PREDICT FUTURE SIGNAL VALUE TASK HYPERPARAMETERS
text: As mentioned, the hyperparameters are set such that all the architectures share the same number of layers, receptive field size, and number of parameters. All the hidden activation functions are ReLU, and all the output activation functions are linear.
CNN: CNN has two 1 × 7 layers, and the number of hidden channels is 84. The total number of parameters is 1,261.
CNNT: CNNT has two 1× 7 layers, and the number of hidden channels is 60. The total number of parameters is 1,261. The sampling time intervals are appended as input features. The time interval appended to the last sample of the sequence is the difference between the prediction time and the time of the last sample.
CNNT-th: The two-hot encoding interval width δ = 0.5, and the two-hot vector dimension is 14. The network has two 1 × 7 layers, and the number of hidden channels is 10. The total number of parameters is 1,261.
ICNN: ICNN takes the interpolated signal at tn+1− k, k = 1, · · · , 13 as input. The network has two 1× 7 layers, and the number of hidden channels is 84. The total number of parameters is 1,261. RNNT:RNNT and RNNT-th have two layers and the number of hidden channels is 32. The total number of parameters is 1153 for RNNT and 1633 for RNNT-th.
CCNN: CCNN has two layers. The first layer is a CCNN layer with output timestamps at tn+1 − k, k = 1, · · · , 13. The bias network has two layers and 72 hidden channels. Its order OB is 7. The
1Equivalent to a Poisson process conditional on the event that the number of occurrences by the timeN isM .
kernel network has two layers and 4 hidden nodes. Its order OK is 3. The kernel length Lk = 3. The second layer is a regular 1× 7 convolutional layer. The total number of parameters is 1,273. CCNN-th: CCNN-th has almost the same structure as CCNN, except that the number of hidden channels is 36. The total number of parameters is 1,261.

heading: C.3 DESCRIPTION OF REAL-WORLD DATASET FOR PREDICTING INTERVALS TO NEXT EVENT
text: Stackoverflow: The dataset contains 26535 training samples, 3315 test samples, and 3315 validation samples. Each sequence represents the history awarding badges to a single user. The sampling timestamps are the time of awarding each badge, and the signal value is the type of the badge (e.g., Guru, Nice Question, Great Answer, etc.). There are 22 types of badges in total.
Retweet: The dataset contains 20000 training samples, 1000 test samples, and 1000 validation samples. The sequence is the history of a tweet being re-posted by other users. According to the number of followers of the users retweeted the post, the label of each retweet, in the whole retweet history, is one of the 3 the user groups.
MIMIC: The dataset is the collection of clinical visit history. The training set contains 2925 sequences; the test and validation set contains 312 each. The diagnosis are filtered to preserve only top-10 common diseases as the label.
NYSE The dataset is book order data collected from NYSE of high-frequency transaction in one day. The dataset contains 2 types of events (sell and buy) with 298710 training sequences, 33190 testing sequences, and 82900 validation sequences.

heading: C.4 CONFIGURATION OF PREDICTING TIME INTERVAL TO NEXT EVENT
text: The input sequence length to NYSE, Stackoverflow, and ReTweet dataset is 13, and the CCNN uses two 1× 7 kernels with 16 filters for each. MIMIC contains only very short sequences, so CCNN uses two 1× 2 kernels and predicts only based on past 3 events.

heading: D ADDITIONAL EXPERIMENTS

heading: D.1 PREDICT FUTURE SIGNAL VALUE ON REAL-WORLD DATASET WITH MISSING DATA
text: In order to test the advantage of CCNN in real-world scenarios with missing observations, 13 timeseries datasets are randomly chosen from the Data Market2, named DM1 through DM13. A brief description of these datasets is given below. Each dataset consists of a univariate uniform time series, which is split into training, test and validation sequences by a ratio of 6:2:2. Nonuniform subsequences are generated the same way as in MG with N = 28 and M = 14. All of the data are monthly data. The network configurations are the same as those in the simulated experiment. In particular, the receptive field size is set to seven, which means the prediction is based on an average of 14 months of historic data. This should lend adequate information for prediction.
DM1: Australia monthly production of cars and station wagons from Jul 1961 to Aug 1995.3 The total length of the sequence is 414.
DM2: Monthly data on Clearwater River at Kamiah, Idaho from 1911 to 1965.4 The total length of the sequence is 604.
DM3: Monthly data on James River at Buchanan, VA from 1911 to 1960.5 The total length of the sequence is 604.
2https://datamarket.com 3https://datamarket.com/data/set/22lf/australia-monthly-production-of-cars-and-station-wagons-jul-1961-aug-1995#
!ds=22lf&display=line 4https://datamarket.com/data/set/22zg/clearwater-river-at-kamiah-idaho-1911-1965#!ds=22zg&display= line 5https://datamarket.com/data/set/22y3/james-river-at-buchanan-va-1911-1960
DM4: Mean monthly precipitation from 1907 to 1972.6 The total length of the sequence is 796.
DM5: Mean monthly temperature from 1907 to 1972.7 The total length of the sequence is 796.
DM6: Monthly data on Middle Boulder Creek at Nederland, CO from 1912 to 1960.8 The total length of the sequence is 592.
DM7: Monthly electricity production in Australia (million kilowatt hours) from Jan 1956 to Aug 1995.9 The total length of the sequence is 480.
DM8: Monthly flows of Chang Jiang (Yangtze River) at Han Kou, China from 1865 to 1979.10 The total length of the sequence is 1372.
DM9: Monthly production of clay bricks (million units) from Jan 1956 to Aug 1995.11 The total length of the sequence is 480.
DM10: Monthly rain in Coppermine (mm) from 1933 to 1976.12 The total length of the sequence is 532.
DM11: Monthly riverflow (cms) in Pigeon River near Middle Falls, Ontario from 1924 to 1977.13 The total length of the sequence is 640.
DM12: Monthly riverflow (cms) in Turtle River near Mine Centre, Ontario from 1921 to 1977.14 The total length of the sequence is 676.
DM13: Monthly temperature in England (F) from 1723 to 1970.15 The total length of the sequence is 2980.
Table 2 shows the mean squared prediction errors. CCNN-th maintains its lead on most datasets. Where it does not, different ICNNs alternately take the lead by small margins. Here are two comments. First, note that the kernel length in ICNN-C and ICNN-Q is much larger than LK , so it falls beyond the representation power of CCNN. Nevertheless, this result shows that an interpolation kernel within the scope of Eq. (1) usually suffices to outperform the standard interpolation methods that fall beyond. Second, unlike in the simulated test, ICNN-L generally performs better than ICNN-C, which emphasizes the importance of choosing a suitable interpolation scheme for each task. CCNN, with its ability to choose its own kernels, avoids such trouble.

heading: D.2 SPEECH INTERPOLATION
text: Since CCNN is motivated by interpolation, it is insightful to see CCNN’s performance in interpolation tasks. The speech interpolation task involves restoring the high-resolution speech signal from the downsampled signal.

heading: THE DATASET
text: To mitigate the complexity in directly working on speech waveforms, the sampling rate of the highresolution speech is set to 4 kHz, and that of the downsampled signals is 2 kHz. Three different downsampling schemes are tested. The first scheme, called uniform filtered, uniformly downsamples the speech to 2 kHz after passing it to an anti-aliasing filter. The second scheme, called uniform unfiltered, uniformly downsamples the signal without the anti-aliasing filter. The third scheme, called nonuniform, randomly preserves half of the speech samples, and thus the resulting signal has an average sampling rate of 2 kHz.
6https://datamarket.com/data/set/22w1/mean-monthly-precipitation-1907-1972 7https://datamarket.com/data/set/22o4/mean-monthly-temperature-1907-1972 8https://datamarket.com/data/set/22vt/middle-boulder-creek-at-nederland-co-1912-1960 9https://datamarket.com/data/set/22l0/monthly-electricity-production-in-australia-million-kilowatt-hours-jan-1956-aug-1995
10https://datamarket.com/data/set/22r8/monthly-flows-chang-jiang-at-han-kou-1865-1979 11https://datamarket.com/data/set/22lv/monthly-production-of-clay-bricks-million-units-jan-1956-aug-1995 12https://datamarket.com/data/set/22n8/monthly-rain-coppermine-mm-1933-1976 13https://datamarket.com/data/set/22mi/monthly-riverflow-in-cms-pigeon-river-near-middle-falls-ont-1924-1977 14https://datamarket.com/data/set/22mf/monthly-riverflow-in-cms-turtle-river-near-mine-centre-ont-1921-1977 15https://datamarket.com/data/set/22vp/monthly-temperature-in-england-f-1723-1970
Our dataset consists of one hour of lab-recorded speech of one speaker reading structured composite sentences. We use 80% of the dataset as training, 10% as validation, and the rest of 10% as test. The high-resolution speech is chunked into 40-point sequences without overlap, and the corresponding downsampled speech into 20-point sequences.

heading: CONFIGURATIONS
text: Similar to the prediction experiment, the ICNN approaches interpolates the low-resolution speech into high-resolution speech (4 kHz) before it is fed to a two-layer regular CNN. A similar practice has also been adopted in Kim et al. (2016). CCNN also has two layers. The first layer outputs at the uniform timestamps at the rate of 4 kHz, and the second layer is a regular convolutional layer. Detailed configurations are shown below. Again, the hyperparameters are set such that the two architectures have the same number of layers, receptive field size and model complexity. The activation functions for CCNN and ICNN are both sigmoid. The hyperparameters are detailed below.
CCNN-th: The timestamps are normalized such that the sampling interval of the original 4 kHz speech is 0.5. CCNN-th has two layers. The first layer is a CCNN layer that outputs the timestamps uniformly distributed at the rate of 4 kHz. The number of hidden channels is 16. The bias network has one layer, and the order OB = 28. The bias kernel network has one layer, and the order OK = 7. The kernel length LK = 10. The two-hot encoding time interval δ = 0.5. The second layer is a 1× 28 convolutional layer.
ICNN-C: The CNN contains two 1× 28 convolutional layers with 80 number of hidden filters. Speech DNN & Speech DNN CP: Speech DNN converts both the high resolution and downsampled speech into amplitude spectra using FFT with 64ms window length and 48ms window shift. Speech DNN has 3 hidden layers, each of which has 1024 hidden nodes. Because our temporal resolution is half of that in Li & Lee (2015), our hidden node number is a half of that in Li & Lee (2015) too. The number of parameters in Speech DNN is around 2.3× 106, which is much larger than that in CCNN and the ICNN baseline models (both have around 5× 103 parameters). Since sample-based speech interpolation methods have yet to achieve the state-of-the-art, we also include a spectrum-based benchmark from Li & Lee (2015) called Speech DNN. Speech DNN only works on the uniform filtered case. It predicts the higher half of the amplitude spectrum of the high-resolution speech of that of the low-resolution speech. The flipped phase spectrum of the downsampled speech is used as an estimate of the higher half of the phase spectrum of the high-resolution speech.
Since the phase spectrum estimate of Speech DNN can be inaccurate, we introduced another version, called Speech DNN with a cheated phase (CP), where the ground truth phase spectrum is applied. Note that this version is given too much oracle information to be fairly compared with. Nevertheless, we will include its results for reference.

heading: RESULTS AND ANALYSIS.
text: Tab. 3 shows the Signal-to-Noise Ratio (SNR) of the signals recovered from different input signals by different models. The Speech DNN with cheated phase yields the best SNR, because it uses the phase information from ground truth. However, the Speech DNN without cheated phase has similar
performance to CNN and CCNN, even though it has much more weights, largely because of the inaccurate phase estimates.
As for the comparison between CCNN and ICNN, they have similar SNR under uniform sampling cases. This verifies that both architectures have similar representation power given uniform data. However, CCNN has much higher SNR than ICNN in nonuniform case. One important reason is that CCNN, by construction, is aware of whether neighboring samples are dense or sparse, and outputs robust interpolation kernels accordingly, despite the variation in sampling patterns; whereas CNN is unable to deal with various random sampling instances.
Fig. 7 shows an example of the restored signal from the nonuniform samples by CCNN and CNN respectively. CCNN can restore some spikes (e.g. ones at 25 and 40) even without an input sample point in the spike, because CCNN can learn the continuous kernels and restore the original spikes. CNN model does poorly in restoring spikes even when there are input sample points in the spikes.

Review summaries:
A method that was proposed by authors deals with a problem of non-uniform data in time series. One of ways to deal with this problem is interpolate input signal between data points. In signal processing a standard way to interpolate is to apply a convolution with a kernel. This operation, by itself, is a non-trivial, since we lack any information about signal's spectrum (and do not know optimal kernel). Thus, the authors propose to search for a kernel in a form neural network. To this term they also add bias term which is also a neural network. 

The paper proposes a continuous CNN model to accommodate the nonuniform time series data. The model learns the interpolation and the convolution kernel functions in an end-to-end manner, so that it can capture the signal patterns and be flexible. A layer has three networks, which learn a kernel function to represent the combination of interpolation and convolution, a bias function to represent the error correction with convolution, and then produce the output based on them. The authors introduce two assumptions and a two-hot encoding scheme for the input to control the model complexity. The paper also introduces an application of the proposed CCNN by combing with temporal point process. Experiments on simulated data compares the proposed method with some degenerative baselines show the advantage of learning the interpolation and the two-hot encoding configuration. The authors compare the performance on time interval prediction task based on real world dataset to show the model produces a better history embedding for the task.