Improved key rate bounds for practical decoy-state quantum key distribution systems

The decoy-state scheme is the most widely implemented quantum key distribution protocol in practice. In order to account for the finite-size key effects on the achievable secret key generation rate, a rigorous statistical fluctuation analysis is required. Originally, a heuristic Gaussian-approximation technique was used for this purpose, which, despite of its analytical convenience, was not sufficiently rigorous. The fluctuation analysis has recently been made rigorous by using the Chernoff bound. There is a considerable gap, however, between the key rate bounds obtained from these new techniques and that obtained from the Gaussian assumption. Here, we develop a tighter bound for the decoy-state method, which yields a smaller failure probability. This improvement results in a higher key rate and increases the maximum distance over which secure key exchange is possible. By optimizing the system parameters, our simulation results show that our new method almost closes the gap between the two previously proposed techniques and achieves a similar performance to that of conventional Gaussian approximations.

I. INTRODUCTION
In theory, quantum key distribution (QKD) [1,2] has been proven to be informationtheoretically secure against eavesdropping attacks [3][4][5], even if we assume that the attacker, Eve, has full control over the channel. The security of QKD stems from the complementary relation of non-commuting measurement operators in quantum mechanics [6]. Due to the uncertainty principle, any Eve's interference that gains her some information about the key would inevitably introduce disturbance. The users, Alice and Bob, can then bound the information leakage to Eve by quantifying the disturbance. The latter requires collecting data from which certain parameters of the system, such as bit and phase error probabilities [5], can accurately be estimated.
In practice, the required probabilities above cannot be directly measured. Instead, one can only measure the rates, i.e., the frequencies of occurrence. If the QKD system runs for an infinitely long time, the rates will converge to the corresponding underlying probabilities.
That is, the parameters needed for data postprocessing can be measured accurately when the data size is sufficiently large. In reality, there are deviations between rates and probabilities due to statistical fluctuations. A finite-key analysis accounts for these deviations and derives a security parameter, the failure probability, for the final key. With the aid of the finite-key analysis, the security of QKD can also be extended to its composable security definition [7,8]. The finite-key analysis of QKD systems with idealized single-photon sources and detectors are well studied in the literature [9]. Here, we develop tight bounds for the secret key rate in practical scenarios when decoy states are in use [10][11][12].
A perfect single-photon source is hard to attain in practice. Alternatively, a highly attenuated laser, described by a weak coherent state, is widely used in QKD. The multiphoton components in the coherent state would introduce security loopholes in practice [13,14]. Such imperfections in realistic devices were originally taken into consideration in the Gottesman-Lo-Lütkenhaus-Preskill (GLLP) security analysis [15]. By directly applying the GLLP analysis to the coherent-state QKD system, however, the performance, measured by key rate and maximum secure transmission distance, is rather limited [16]. A clever twist to the weak-laser QKD, known as the decoy-state method, is introduced in [10][11][12], which, fortunately, can enhance system performance to a level comparable to that of a perfect single-photon source. The decoy-state method is now widely used in QKD systems [17][18][19][20][21][22].
In the decoy-state method, we estimate the channel parameters by sending two types of states. One is called the signal state, which is used to transmit keys similar to the singlephoton source in the ideal situation. The other is called the decoy state, which is used to characterize the channel, by estimating the number of single-photon states traversing the channel. In the information-theoretical security proof of the decoy-state method [11], these two states have the same properties except for their intensity, which results in distinct Poisson distributions for their photon number. Note that the phases of the coherent states must be randomized, in order that the source can be treated as a statistical mixture of Fock states. In this case, the channel, controlled by Eve, will have the same impact on the single-photon components in both signal and decoy states. The channel parameters, such as the probability of a single photon passing through, defined as the single-photon yield, would then be the same for the signal and decoy states. This property is at the core of the security of the decoy-state technique. We revisit this condition in our finite-key analysis.
Estimating the channel parameters, such as the single-photon yield, would become less accurate when one only has a finite set of data. Statistical fluctuation must then be considered, in our security analysis, to account for possible deviations from true (probability) values. It turns out that the statistical fluctuation analysis for the decoy-state method can be a complicated problem. To simplify the problem, a Gaussian distribution assumption on the channel fluctuations was made in early analyses [23]. Throughout the paper, we refer to this Gaussian approximation technique by the Gaussian analysis method. Such an assumption is not necessarily justified when one considers a rigorous security proof. Lately, this Gaussian assumption was removed from the security proof by applying the Chernoff bound and the Hoeffding inequality [24,25]. We refer to this latter technique by the Chernoff+Hoeffding method.
The simulation results show that a large-size key is required to achieve a secure key with the Chernoff+Hoeffding method and the key rate is lower than that of the Gaussian analysis method. In this work, we improve the finite-key analysis method and provide a tighter estimation of QKD parameters by breaking the parameter estimation problem into different regimes of operation and finding tight bounds in each case. After optimizing the system parameters, we show that our improved finite-key analysis method achieves a similar performance to the Gaussian analysis method.
The organization of this paper is as follows. In Sec. II, we review the commonly used vacuum+weak decoy-state scheme [23,26] and develop a general formulation for its finitekey analysis. In Sec. III, we present our new statistical fluctuation method, and provide instructions on how our results can be applied to a realistic experimental setup. Note that our proposed method is generic and can also be used in other decoy-state QKD schemes. In Sec. IV, we first construct a QKD simulation model with typical experimental parameters, and then compare our new method with previous work when each method has been optimized to offer its best performance. We discuss the results and conclude the paper in Sec. V.

II. FINITE-KEY ANALYSIS FOR VACUUM+WEAK DECOY-STATE SCHEME
In this section, we lay out a precise formulation for our finite-key analysis problem in the special case of vacuum+weak decoy-state protocol. This turns out to offer a unifying language, applicable to both the Chernoff+Hoeffding [24,25] and the Gaussian analysis methods, as well as our own proposed method. We will then compare the new formulation with that of the Gaussian analysis method [23], and show how the results there can be employed in our finite-key analysis. In particular, we show that the formulation in the Chernoff+Hoeffding method has an equivalent form to that of the Gaussian analysis method.
In the following, in Sec. II A, we review the widely-used scheme of vacuum+weak decoy-state QKD [26]. Then, the definitions and notations used in this paper are given. In Sec. II B, we formulate the parameter estimation problem in its general form. Finally, in Sec. II C, we use the results in [23] to find analytical bounds for the parameters of interest.

A. Vacuum+weak decoy-state protocol
The vacuum+weak decoy-state protocol, first presented in 2004 [26], is a widely used decoy-state scheme. In this protocol, Alice encodes the pulses with three different intensities, corresponding to vacuum states, weak decoy states and the signal states. This scheme is capable of estimating the single-photon components because, intuitively, when the intensity of a coherent state pulse is very weak, the resulting detection events mainly come from the single-photon components and background. The yield of the background noise can be estimated by the vacuum decoy state. By combining measurement results of weak decoy and vacuum decoy states, the relevant parameters to the single-photon components, including the yield and quantum bit error rate (QBER), can accurately be estimated. With those parameters, secure keys can be obtained from the signal states after postprocessing.
The protocol is described in more detail in the following steps: 1. State preparation: For each bit in her raw key, Alice randomly chooses the intensity and the basis to encode her bit. She can choose from three intensities, namely, vacuum state, weak decoy state and signal state, and then randomly encode her bit in the X or Z basis, and sends it to Bob. The probability of choosing the Z basis could, in general, be different from that of the X basis [27].
2. Measurement: Bob measures the received states in the X or Z basis chosen randomly.
The probability of choosing a measurement basis is the same as that of the encoding stage.
3. Sifting: Over an authenticated channel, Alice announces the basis and signal/decoy information she has used, while Bob announces the locations of valid detections and the bases used for his measurements. If Alice and Bob have chosen the same basis, they keep the corresponding bits as the sifted key. 4. Error correction and verification: Alice calculates some parity information of her sifted key, encrypts the parity bits with pre-shared secure keys, and sends them to Bob. Bob then performs the error correction and, Alice and Bob verify if their keys are now identical [9]. If the verification fails they perform the error correction again or abort the protocol. If the keys are verified to be identical, Bob finds the number of bit errors and evaluates the QBER.

5.
Parameter estimation: Using the parameters obtained in the experiment, a lower bound on the number of successful detection events resulted from single-photon components of the signal states, M s 1 , and an upper bound on the corresponding phase error rate, e ps 1 , will be obtained in each basis. The latter quantifies the leaked information to a potential eavesdropper.
6. Privacy amplification: Alice and Bob apply universal hashing function based on the parameters M s 1 and e ps 1 in each basis. Then, according to the GLLP analysis [15], a shorter but more secure key can be extracted with a length of M s The final key length in each basis is then lower bounded by where f denotes the inefficiency of error correction, and h( is the Shannon binary entropy function. Here, for the sake of simplicity, we assume that Alice and Bob only extract secure keys from the signal states. In principle, they can also extract secure keys from the decoy states as well. The other parameters in Eq. (1) are defined below.
Below, the notation used throughout the paper, including the parameters in Eq. (1), is presented.
1. The superscripts x and z denote the X and Z bases, respectively. For brevity of notation, we often do not explicitly mention the basis superscript, unless otherwise needed. All parameters defined below are then for a certain fixed basis γ = x, z, although the superscript γ is not shown.
2. Capital letters K, N, and M, respectively, denote the number of the final key bits, the pulses sent by Alice and the valid, after basis sifting, detections on Bob's side.
3. Q denotes the gain, i.e., the rate of creating a sifted key bit, and E denotes the total QBER in the sifted key bit.
4. Y i denotes the yield of i-photon states, and is given by 5. e i denotes the error rate corresponding to the transmission of i-photon states. Note that it should not be confused with the letter e without the subscript, which is the base of the natural logarithm.
7. The superscripts b and p refer to bit and phase (in error-rate terms), respectively.
8. The superscripts L and U refer to the lower bound and the upper bound, respectively.
9. q a ≡ N a /N denotes the rate Alice encodes a state with intensity µ a .
10. On Alice's side, p a i denotes the conditional probability that an i-photon state corresponds to a coherent pulse with intensity µ a , i.e., where the approximation is caused by statistical fluctuations. The approximation becomes equality in the asymptotic (infinite-key) limit. Due to the Poisson distribution of the photon numbers in different states and N a = q a N, these probabilities are given by, Note that p a i is the only probability term used in this paper. All other terms are rates, i.e., the ratio between two counts.

B. Statistical fluctuation analysis: Formulation
Our key objective in the statistical fluctuation analysis of the decoy-state schemes is to bound M s 1 and e ps 1 , by allowing a certain failure rate, by using the measurement results obtained in a QKD round. A QKD round consists of transmitting N pulses by Alice, out of which K key bits are to be extracted. In this subsection and next, all the terms refer to the parameters in a particular basis, e.g., the Z basis. The same results hold for the other basis as well. In each QKD round, Alice and Bob can specify M a and E a M a for different values of a. Based on these measurement results, they consider a worst-case scenario by finding the minimum value of M s 1 and the maximum value of e ps 1 that is consistent with the measurement results.
From the GLLP security analysis [15], Eve cannot get any key information from the singlephoton states without introducing disturbance, while she can in principle get information about the key when multiple photons are sent, say, via photon-number-splitting attacks [13,14]. Eve's objective is then to minimize M s 1 , within the constraints of the decoy-state scheme.
Note that some parameters, such as N i and M i are, in principle, known to Eve assuming that she can perform non-demolition measurements on the signals generated by Alice. From Alice and Bob's perspective, these variables are, however, unknown, but have a fixed value in each round of the QKD protocol once Bob's measurements are completed. On the other hand, the choice of a for each transmitted state is known to Alice, while Eve has no information about that before the sifting stage. This is the key advantage that Alice and Bob have over Eve in specifying the range of values that the key parameters of interest would take. In the following, we will try to find relationships between the measurable parameters M a and E a M a and the unknown (to Alice and Bob), but fixed, parameters M i . We will then show how this can help us bound M s 1 and e ps 1 . For phase-randomized coherent sources, the state prepared by Alice can be considered as a mixture of Fock states. The channel, controlled by Eve, behaves the same to different Fock states. This is called the photon number channel model [28]. For an i-photon state, the conditional detection probability for Bob that the originally encoded state has an intensity where the approximation becomes equality in the asymptotic case. Note that the terms on the left hand side of Eq. (6) are measurable counts, while the ones on the right hand side are mixed with probabilities. When the data size is finite, the statistical fluctuation may lead to deviations between M a i (e a i M a i ) and p a i M i (p a i e i M i ), in Eq. (4), and similarly in Eq. (6). Our objective is to bound these deviations while meeting a certain failure rate for the protocol, as we show next.
The key idea that we use to bound the right-hand side of Eq. (6)  Let us first look at M a i in a more detailed way. Before the sifting stage, but after Bob's measurements, M i has a fixed value, but M a i is random to Eve. We can then rewrite M a i as follows where are independent and identically distributed indicator random variables. It will then follow that where E[·] is the expectation value with respect to χ a i,j variables. Finally, from Eqs. (5) and (9) we find where, again, the expectation values are taken with respect to χ a i,j variables. Note that these expectation values would represent the average values for our observables from Eve's perspective before the sifting stage, but after Bob's measurements. At this stage, Alice and Bob can safely assume that Eve can no longer change the values of M i variables on the right-hand side of the above equations. The measured values for M a and E a M a will then set some constraints on the expectation values in Eq. (10), and, correspondingly, the right-hand side of the above equations. In particular, we can show that for any set of values for observables M a (E a M a ), we can find lower and upper bounds for their corresponding expected values, respectively, denoted by Our finite-key analysis can then be formulated as the following optimization problem: Find In Sec. III, starting with the Chernoff bound, we show how the required lower and upper bounds above can be related to the measured observables. Before doing that, however, let us find the correspondence between the above formulation and that of the previous work in [23].

C. Correspondence with Gaussian Analysis Method
In order to compare our formulation in sec. II B with that of the Gaussian analysis method proposed in [23], we rewrite Eq. (10) by dividing both sides of it by N a . We obtain the following Here we implicitly assume that, to her advantage, N a is known to Eve, and where is the asymptotic limit of N i when N → ∞. Alternatively, we can think of N ∞ i as the expected number of i-photon states sent by Alice. Note that e i Y * i should be regarded as one variable. Equation (12) can be expanded as follows In order to find the bounds of M 1 and e 1 M 1 in our original problem, we find the corresponding bounds for Y * 1 and e 1 Y * 1 by calculating which results in the following The interesting point about Eqs. (12) and (15) is that, by some simple substitutions, they have the same form as Eq. (13) in [23]. In fact, by replacing and and Y i , we reach to the same result as in Eq. (13) in [23]. Note that the definitions for Q and Y terms here, in our finite-key analysis, are slightly different from the definitions given in [23] for the infinite-key scenario. Nevertheless, the equations look similar, and one can use the analytical results obtained in [23], after necessary substitution, and recycle them here. For instance, the bounds obtained in Eq. (16) can directly be obtained from Eqs. (34) and (37) in [23].
Thus far, we have shown that the formulation that we need in either the finite-key analysis here and in [24], or the infinitely-long key case in [23] will both result to solving a similar optimization problem. That is, once one specifies, in our formulation, the values of E L [M a ], as a function of our observations. In [23], the authors use a heuristic Gaussian assumption, which is not exact but convenient to use. In [24], the required bounds are obtained by using Chernoff and Hoeffding inequalities, which are rigorous but a bit too loose in certain regions. In our work, we obtain tighter bounds for these average terms, which, not only are rigorous, but also offer higher key rates and/or lower failure probabilities as compared to the Chernoff+Hoeffding method.

III. STATISTICAL FLUCTUATION ANALYSIS
In this section, we first provide a step-by-step instruction on how to use our theoretical results in a real experimental setup. We then summarize all the tools that we have developed in our statistical fluctuation analysis. The full derivations for each of these tools will appear in Appendixes A and B.

A. Instructions for experimentalists
Suppose we run a QKD experiment according to the decoy-state scheme, as formulated here. After sifting and error correction, we will then have certain observables, namely, M az and E az . The next step in the procedure is to apply sufficient privacy amplification that guarantees a failure probability below a given threshold ε. In the privacy amplification procedure, the length of the extracted secure key and hence, the size of the corresponding universal hashing function are determined by M sz 1 and e psz 1 . Thus we need to estimate these two parameters before performing privacy amplification. Note that it is common to estimate the phase error rate e psz 1 by using the observed bit error rate e bsx 1 in its complement basis [5]. One should, however, account for deviations from the bit error rate value once finite-key issues are considered [9], as we do here. In this section, we only calculate the length of the secure key, K z , extracted from the Z-basis measurements. The key length extracted from the X basis, K x , can be obtained similarly and the final key length is given by K z + K x .
We assume that all the secure key bits come from the signal states. The final key length, K z , is given by  (16) and (17)  In the end, we comment on the differences between our approach and that of [24].
The Chernoff bound for a set of n independent Bernoulli random variables χ i ∈ {0, 1} can be expressed as follows [29,30]. For χ = n i=1 χ i andχ = E[χ], we have the following bounds and where δ L > 0, 0 < δ U < 1, and g(δ,χ) = e δ (1+δ) 1+δ χ . The above formulation can be applied to M a and E a M a , whose average values need to be bounded. For instance, in the data postprocessing step, the total number of detections obtained by Bob in the Z basis is given by M z . For each valid detection event, we can define the indicator random variable χ j that determines whether or not Alice has originally prepared the jth received pulse in the signal state. That is, χ j = 1 means that a signal state has caused the jth detection event, whereas χ j = 0 implies that another state (weak decoy or vacuum state) has been used. Then, the total number of detected signal states is given by M sz = M z j=1 χ j , with χ j being independent Bernoulli random variables. A similar formulation can be used for error terms as well. In the rest of this section, the parameter χ will then represent any of the parameters of interest in the form M a and E a M a in a particular basis.
The Chernoff bound in Eqs. (19) and (20) bounds the probability that the observed value deviates from its average value. That is, if we know the average value of χ, we can define a confidence interval [χ U , χ L ], where χ L = (1 + δ L )χ and χ U = (1 − δ U )χ, the probability of being outside of which is bounded by functions of δ L , δ U , andχ. The problem that we have in hand is, however, the opposite. We need to boundχ for a given observed value of χ in such a way that the failure probability is below a certain threshold.
To define the failure probability precisely, we use the same framework that we developed in Sec. II B in which we showed that after the measurement phase,χ is fixed, but unknown.
Nevertheless, even for a fixedχ, the value χ that Alice and Bob observe in their experiment is a random variable. The failure probability in this setting can then be defined as follows.
For a fixed but unknown value ofχ, we find the probability that the observed value for χ results in either of the following events: where E L (χ) is the procedure/function by which we relate an observed value to the lower limit onχ, and where E U (χ) is the procedure/function by which we relate an observed value to the upper limit onχ. For instance, the probability of failure corresponding to Event 1 is given by Now, in order to bound the above probability, we define our function E L (χ) in such a way that it satisfies the following condition where ε L , as we see next, is the failure probability, and we have solved the equation g(δ L ,χ) = ε L in order to write δ L as a function of ε L andχ. The left-hand-side of Eq. (24) is then equivalent to the left-hand-side of Eq. (19), which will then result in In other words, by choosing E L (χ) in such a way that it satisfies Eq. (24) we can use the Chernoff bound to bound the failure probability. The same holds if one works out the upper limit for the average terms with the difference that now one should find E U (χ) such that with ε U being the failure probability for Event 2 and δ U (ε U ,χ) is the solution to g(−δ U ,χ) = ε U .
Provided that functions χ L = (1 + δ L (ε L ,χ))χ and χ U = (1 − δ U (ε U ,χ)χ are increasing functions ofχ, one obvious choice for E L (χ) (E U (χ)) is the inverse function of χ L (χ U ). In Appendix A, we show that the above monotonicity condition, in fact, holds, and that would offer a solution to find very tight bounds for all terms of interest.
Our approach offers tighter bounds than the ones proposed in [24]. One reason for the difference is that, in [24], the authors use looser forms of the Chernoff bound than the ones we use in Eqs. (19) and (20), especially when χ has small values. But, more importantly, the procedure for finding E U (χ) in [24] is somehow heuristic, as compared to our exact calculations, and results in looser upper bounds even in the case of large values of χ. In our numerical results we show how these differences will result in our improving the bounds, and correspondingly the failure rate and/or key rate, in the decoy-state QKD setup. In the rest of this section, we then provide a summary of our analytical results that can be used to bound relevant terms in our formulation.

C. From χ toχ
Given a measurement result χ, we can bound the underlying expectation valueχ for a failure probability bounded by ε = 2ε L = 2ε U . The results are summarized below and the details of calculations are shown in Appendix A.
2. If χ > 0, we use where δ L and δ U can be obtained by solving the following equations It turns out that the solutions δ L and δ U to Eq. (29) are difficult to calculate when χ is large. A simplified analytical approximation is given next.
3. If χ ≥ 6β, we use in Eq. (28). This will provide us with a slightly looser bound than the one we can obtain by solving (29), but the difference is negligible.

D. Fromχ to χ
Once, using the relationships in Sec. III C, E L (χ) and E U (χ) are found for all relevant parameters χ, we use Eqs. (16) and (17)  ]. Let us use our more general notation χ representing the sum of a number of independent Bernoulli random variables. M sz 1 satisfies this condition as written in Eq. (7). Then, we can solve the following equation and, using the symmteric form of the Chernoff bound given by [31,32] Pr we obtain a confidence interval [χ L , In our problem, we have the lower bound forχ = E[M sz 1 ] given by p sz 1 M zL 1 . We can then use the relationship for χ L above to calculate M szL 1 with a failure probability bounded by ε.

IV. NUMERICAL RESULTS
In this section, we provide additional insight into our proposed method by numerically comparing it with the other two methods of Chernoff+Hoefding and the Gaussian analysis.
We compare the three methods in terms of the tightness of their confidence intervals, or their failure probability, as well as the secret key generation rate and the maximum secure distance in the finite-key setting.

A. Tightness of the bounds
Here, we compare the two previously proposed methods in [23] and [24] with ours in terms We also compare the three fluctuation analysis methods from another perspective where we fix the fluctuation deviations, χ−E L [χ] or E U [χ]−χ, and evaluate the failure probabilities.
The results are shown in Table I. We find that in the Chernoff+Hoeffding method [24], the failure probability for Event 2, at an identical deviation, is higher than that of Event 1. This is the same for our method as well as the Gaussian analysis one. It can be seen that the failure probability guaranteed by our method is roughly within one order of magnitude of that of the Gaussian analysis method. Note that, however, in the latter case, the failure probabilities are not guaranteed and they rely on an underlying Gaussian assumption, which is not necessarily the case. Table I can Here, ε G , ε C+H , and ε new , respectively, denote the sum failure probability for Events 1 and 2 for the Gaussian analysis, the Chernoff+Hoeffding method [24], and our new method. Our method is particularly attractive when the observed counts are small. As shown in Another interesting feature of our methodology is the dependence of the failure probability on the observed value χ. As shown in Fig. 1 and Table I, given a fixed failure probability ε, the fluctuation deviation can be written as a constant multiplied by σ = √ χ. One could ask the opposite question that for a given fluctuation deviation of n α σ, for a fixed value It can be seen that for large values of χ, the fluctuation probability approaches the constant value given in Table I. For small values of χ, however, the failure probability goes up as now, for the given confidence interval, the chance of making an error is higher. This is in contrast with what the Gaussian analysis method assumes in that the failure probability for a fixed value of n α is independent of χ; see Eq. (C3) in Appendix C. This is how our method offers a more rigorous approach to the finite-key analysis as compared to the Gaussian analysis method.

B. Key rate comparison
In order to compare the performance of our technique, in terms of the final key rate and the maximum secure transmission distance, with previous work, we simulate our QKD system by assuming that the observed values for different parameters of interest is given by their asymptotic values in an Eve-free experiment. These values have been summarized below [23]: where η is the total transmittance, Q a and E a are the overall gain and QBER, e d is the misalignment error rate, and the error rate of the background noise, e 0 , is equal to 1/2. can be estimated accurately, we use the following formula where Y i and e i are the yield and the error rate of the i-photon channel.
In our numerical results, we optimize the choice of the intensities and the ratios of the signal, weak decoy, and vacuum state to maximize the final key rate. To perform parameter optimization, the local search algorithm (LSA) [33] is employed. In the following simulation, we use the parameters of a practical QKD system [34], as listed in Table II. Note that, in our work, ε represents the failure probability of each step. In our method, the failure probability of a single upper (lower) bound is ε/2 and therefore, the failure probability of a confidence interval, composed of an upper bound and a lower bound, is ε. The total failure probability of the whole QKD system (including both X and Z bases) is 8ε. We compare the three discussed fluctuation analysis methods with the asymptotic case, where, in the latter, the data size is infinitely large and its statistical fluctuations can be ignored. The results are shown in Fig. 4. It is clear that our new method always provides a larger final key rate than the Chernoff+Hoeffding method [24]. For N = 10 10 , our analysis method increases the maximum secure transmission distance by 7 km. In the limit of short transmission distances, the number of pulses detected by Bob is very large, and, therefore, the improvement of our new method is not substantial. In the regime around the maximum secure transmission distance, the value of χ is small and our new method is advantageous.
Meanwhile, from Fig. 4, one can clearly see that our new method achieves a very close performance to the widely-used Gaussian analysis method [23].
For our method, at short QKD distances, the optimized intensity of the signal state µ is equal to 0.45. As the distance increases, the optimum intensity of the signal state decreases.
At a distance of 100 km, the optimized µ decreases to 0.37 with other optimized parameters listed in Table III. All the results are consistent with the Gaussian analysis case [23].  size of a QKD protocol is larger than 10 14 , its maximum secure transmission distance is very close to the asymptotic limit of 142 km. No secret keys can be exchanged at a data size, N, roughly below 10 7 . The curves of our method and the Gaussian case are almost the same.
When N is smaller than 10 12 , all three curves are very steep. Consequently, the gap between maximum secure transmission distances of our method and the Chernoff+Hoeffding method is distinct. For example, as shown in both Fig. 4 and Fig. 5, our method increases the maximum transmission distance by 7 km when total data size N = 10 10 .

V. CONCLUSIONS AND DISCUSSION
In this paper, we developed a tight bound for the decoy-state QKD system when the finitedata-size effects are taken into account. As compared to the early work on this topic, which relied on Gaussian approximations, our method offered a rigorous approach to estimating the failure probability. In that sense, our method was similar to the recently proposed techniques relying on Chernoff and Hoeffding inequalities. Our proposed method could,  Table III. No secure keys can be generated for N ≤ 10 7 . The asymptotic limit for the maximum secure transmission distance is 142 km when N ≥ 10 14 .
however, substantially improve the performance by yielding a smaller failure probability, for a similar confidence interval, than what the Chernoff+Hoeffding method could offer. In fact, after parameter optimization, our method could offer similar performance to the widely-used Gaussian analysis method, which uses non-rigorous Gaussian approximations.
There are several problems to which our methodology can be applied. In this work, we assumed that the phase of the weak coherent state was continuously randomized. When the phase is not randomized, we know that security loopholes may allow for certain attacks [35,36]. In practice, it is difficult to randomize the phase of a laser pulse continuously.
Instead one can apply the discrete phase randomization [37], using which the final secure key rate is slightly reduced. Our finite-key analysis for the decoy-state method can then be applied to the discrete phase randomization case. Our method is also applicable to the biased BB84 protocol [38], in which the choice of basis is not symmetric. The analysis method in this work can also be used in other protocols, such as measurement-device-independent QKD protocol [39,40] and round-robin differential-phase-shift QKD protocol [41,42]. We expect that our methodology will offer similar performance to the Gaussian analysis method, while the security parameters have been rigorously estimated. In addition to finite-size effects, laser source intensity fluctuations should also be taken into consideration in practice [43,44].
It is important to investigate all these practical issues together for QKD systems.

VI. ACKNOWLEDGMENTS
The author acknowledges insightful discussions with Z. Cao In this section, we provide a confidence interval for the expectation valueχ based on the observed value χ. We use the methodology described in Sec. III B and the original forms of the Chernoff bound in Eqs. (19) and (20). Our proposed method works even if χ approaches 0, and unlike the Chernoff+Hoesffding method, we do not need to use the Hoeffding inequality in this regime. Without loss of generality, we assume that the failure probabilities for Events 1 and 2 are equal and are given by ε/2. the total failure probability in bounding the expected values is then given by ε. As mentioned in Sec. III B, the lower and upper bounds onχ can be obtained by, respectively, solving the following set of equations: and or equivalently, for given values of χ and ε, we need to solve the following two equations g(δ L , χ/(1 + δ L )) = ε/2 g(−δ U , χ/(1 − δ U )) = ε/2 (A3) to obtain δ L and δ U . The lower and upper bounds of E[χ] are then given by Claim A.1. For all χ > 0, there exist unique answers for δ L > 0 and 0 < δ U < 1 in Eq. (A3).
This would guarantee that there exists solutions for δ L and δ U in their respective regions.
Furthermore, it can be verified that g 2 (δ) is a monotonic function of δ in both regions of where δ L and δ U can be obtained from Eq. (A4).
Claim A.3. In the limit of χ → ∞, the lower and upper bounds ofχ in Eq. (A4) are given by, Proof. For large values of χ, β/χ is small, and therefore the corresponding solutions for δ L and δ U would be small too. In this regime, one can use the Taylor series for the log function, up to two terms, to simplify Eq. (A5) to obtain The conclusion will follow if we replace the above answer into Eq. (A4).

Simplified result when χ is large
In Appendix A 1, we showed how to tightly bound the expectation valueχ. The above numerical method can, however, become tedious when χ is very large. To overcome this problem, we use the symmetric form of the Chernoff bound in Eq. (32) and give an explicit result in the specific case of χ > 6β.
Claim A.4. For χ > 6β, the lower and upper bounds ofχ are given by Proof. As shown in Sec. III B, we need to solve the following equations 2e −(δ L ) 2χ /(2+δ L ) = ε, and 2e −(δ U ) 2χ /(2+δ U ) = ε, χ = χ 1 − δ U , 0 < δ U < 1, (A13) whose positive roots are obtained to be δ L = 3β + 8βχ + β 2 2(χ − β) , δ U = 8βχ + 9β 2 − β 2(χ + β) . (A14) In order to have 0 < δ U , δ L < 1, the value of χ should be larger than 6β. One can in principle use the above equations for δ L and δ U to find the corresponding lower and upper bounds forχ. In Eq. (A11), we have used a symmetric form for the deviation parameter by choosing δ = δ L for both lower and upper bounds. This sysmmteric form would give us a slightly looser upper bound as it can be shown that δ U is smaller than δ L . In the limit of χ → ∞, the above symmetric formulation would nevertheless give us the same asymptotic values as obtained in Claim A.2, which indicates that the two methodologies are more or less the same for large values of χ.

Appendix B: Random sampling
Here, we review the standard random sampling method used for the phase error rate estimation [45]. Suppose there are n x + n z qubits (or basis-independent quantum states) in total. Alice and Bob randomly pick n x qubits, measured in the X basis, and obtain a bit error rate of e bx . They need to estimate the phase error rate, e pz , for the remaining n z qubits measured in the Z basis. When the data size is infinite, for basis-independent states, e pz = e bx . When statistical fluctuations are taken into account, a deviation θ is expected between the two error rates. According to the random sampling analysis, the (failure) probability for e pz ≥ e bx + θ is given by [45] P r(e pz ≥ e bx + θ) ≤ √ n x + n z e bx (1 − e bx )n x n z 2 −(nx+nz)ξ(θ) , where ξ(θ) = h(e bx + θ − q x θ) − q x h(e bx ) − (1 − q x )h(e bx + θ) and q x = n x /(n x + n z ). For a given failure probability ε, one can then numerically find θ that satisfies ε = √ n x + n z e bx (1 − e bx )n x n z 2 −(nx+nz)ξ(θ) .
In the decoy-state scheme considered here, we can use the above random sampling method to upper bound θ, by using the following substitutions Note that in order to estimate the phase error rate in the Z-basis signal states, we can use all the data points in the X basis. That is why we use M xL 1 rather than M xsL 1 in Eq. (B3).

Appendix C: Gaussian analysis
Here, we summarize the Gaussian analysis method in Ref. [23,46], where the quantum channel is assumed to fluctuate according to a Gaussian distribution. According to the central limit theorem, a lower bound of y 1 , an upper bound of e 1 y 1 and hence, an upper bound of e 1 can be obtained by min y 1 , s.t., (1 − n α √ M a )Q a ≤ e −µa Y 0 + · · · + e −µa (µ a ) i i! Y i + · · · ≤ (1 + n α √ M a )Q a , a ∈ {s, w, v}.
The number of standard deviation n α in Eq. (C1) is directly related to the failure probability, where erf(x) = 2 √ π x 0 e −t 2 dt is the error function [47].


A Smart Device Enabled System for Autonomous Fall Detection and Alert

The activity model based on 3D acceleration and gyroscope is created in this paper, and the difference between the activities of daily living (ADLs) and falls is analyzed at first. Meanwhile, the kNN algorithm and sliding window are introduced to develop a smart device enabled system for fall detection and alert, which is composed of a wearable motion sensor board and a smart phone. The motion sensor board integrated with triaxial accelerometer, gyroscope, and Bluetooth is attached to a custom vest worn by the elderly to capture the reluctant acceleration and angular velocity of ADLs in real time. The stream data via Bluetooth is then sent to a smart phone, which runs a program based on the kNN algorithm and sliding window to analyze the stream data and detect falls in the background. At last, the experiment shows that the system identifies simulated falls from ADLs with a high accuracy of 97.7%, while sensitivity and specificity are 94% and 99%, respectively. Besides, the smart phone can issue an alarm and notify caregivers to provide timely and accurate help for the elderly, as soon as a fall is detected.

Introduction
There are about 30% living people over the age of 65 who fall at least one time each year in the USA, and the prevalence of fall in the elderly is about 20% in China [1]. Falls and fall induced injuries account for over 80% of all injury-related hospital admissions among people over 65 [2]. Consequently, falls affect tens of millions of the elderly throughout the world. For example, falls among the elderly cost the National Health Service more than m4.6 million per day according to a report by the Centre for Social Justice UK [3]. Researches showed that the risk of hospitalization could be reduced by 26% and death by over 80% after fall event detection followed by immediate notification to caregivers [4]. Therefore, the high incidences of falls, combined with their associated costs, make it imperative to develop a reliable and effective fall detection solution.
Over the last decade, a variety of different methods were developed to automatically detect falls. They are categorized into three different classes depending on the deployed sensor technology, namely, vision-based sensors [5], ambient sensors [6], and wearable devices [7]. For example, Yu's team [8] developed a vision-based fall detection method by applying background subtraction to extract the foreground human body and postprocessing to improve the result, and information is fed into a directed acyclic graph SVM for posture recognition in order to detect a fall. Yazar et al. introduced vibration and PIR sensors and deployed winner-takes-all decision algorithm to detect fall [9]. However, both visionbased and ambient sensors have a constrained monitoring area and require installation, adjustment, and maintenance which can result in higher costs. Recently, technological advancements in the fields of electrical, mechanical, and computer engineering, particularly involving microelectromechanical systems (MEMS), have resulted in smaller and cheaper inertial sensors. An inertial sensor (such as 3D accelerometer, 3D gyroscope, and 3D compass) is as tiny as 5 * 5 millimeters and is as cheap as one US dollar [7]. Therefore, it is widely used to develop wearable devices which allow the measurement of physical activity under real-life environment. This includes indoor and outdoor activities as well as recordings in very private areas like the bathroom or the toilet [10]. Meanwhile, smart phone integrated with inertia sensors is more and more popular; many works have been 2 International Journal of Distributed Sensor Networks done for the fall detection on the smartphone. For example, Bai et al. proposed a system based on a triaxis accelerometer embedded in a smart phone with global positioning system (GPS) function to detect falls [11]. But such systems face the relatively high energy consumption of current smart phones, and it is inconvenient for the elderly to take smart phone at any time.
This paper presents a smart device enabled fall detection solution by using a smart phone and a custom vest integrated with triaxial accelerometer and gyroscope. The system incorporates an array of features, such as sending alerts, shortest message service (SMS), and global positioning system (GPS) location for easy alerting and monitoring. In short, the system takes advantage of wearable device and smart phone and can provide the elderly with an unobtrusive fall detection.
The rest of this paper is organized as follows. Section 2 introduces the available technology for automatic fall detection based on inertial sensors. The methodology to deploy the system is discussed in Section 3. Section 4 presents the implementation of the system. The simulated experiment and its analysis are discussed in Section 5. The conclusion and future research are proposed in Section 6.

Related Work Based on Inertial Sensors
Different approaches have been explored to solve the fall detection problem by using inertial sensors. The majority of these approaches can be divided in two main types: threshold-based and machine learning (or data mining) [12]. Both types are based on features extracted from the recorded signals.
Threshold-based methods for fall detection use single or multiple thresholds on the extracted features. Bourke et al. [13] presented an approach to detect falls, which is based on an assumption that acceleration in falls is sharper than those in ADLs. Purwar et al. [14] used a triaxial accelerometer to set thresholds of acceleration and orientation of trunk through experiments to detect falls and achieved an accuracy of 81%. Lindemann et al. [15] integrated a triaxial accelerometer into a hearing aid device and used thresholds for acceleration and velocity to judge whether a fall had occurred. Noury et al. [16] developed a sensor with two orthogonally oriented accelerometers and used this sensor to monitor the inclination and inclination speed to detect falls. Though body orientation can improve the fall detection accuracy. Using one single device can only monitor the body orientation, and sufficient posture information cannot be collected using this method. Wang et al. [17] applied triaxial accelerometer and wireless sensor network to develop an enhanced fall detection system for the elderly monitoring. The main problem was that the use of only acceleration for fall detection led to many false positives. For instance, sitting down quickly produced similar vertical acceleration data. As a result, more and more researchers study technology of combining triaxial accelerometer with gyroscope to detect fall events accurately. Li et al. [18] proposed a system where two accelerometers are placed on the abdomen and the right thigh, and the data stream is segmented into one second window. The system could reduce both false alarms by deriving the posture information from both gyroscopes and accelerometers. Gjoreski et al. [19] introduced RAReFall which measures the difference between maximum value and minimum value within one-second window; if the difference is larger than 1 g and the maximum value is at the back of minimum value, then a fall is detected.
Machine learning techniques use automatic methods starting from the extracted features and try to differentiate between a fall and ADLs [20]. Ojetola et al. [3] introduce two sensor motes (each has one accelerometer and one gyroscope) that are wore on chest and right thigh to differentiate ADLs and fall. In the system, raw data is first processed by mean filter and lower resampling; then vector magnitude of acceleration and angular velocity are used as features to train a C4.5 Decision Tree model. However, the accuracy and timeliness were not mentioned. Zhang et al. [21] presented a fall detection method based on one-class support vector machine where a triaxial accelerometer is used to capture the movement data of human. This method needs specific activity patterns and computation, which is not appropriate for realtime and comfort fall detection. Tong et al. [22] used hidden Markov model (HMM) and triaxial accelerometer to detect and predict falls through analyzing the features of human motion series during fall processes. The experiment results showed that this method could predict falls in 200∼400 ms before the impact and also accurately distinguish falls from other daily activities. However, the HMM and thresholds of the system were set based on the data samples of young people's simulated activities; the mathematical model and thresholds should be trained and reset based on the large real-world samples of the elderly. Dinh and Struck transform the acceleration data from Cartesian coordinates to spherical coordinates and develop the algorithm based on a fuzzy logic and a neural network to detect falls [23]. Gjoreski et al. [24] study a combination of body-worn inertial and location sensors, and the Random Forest classifier is introduced to detect falls. However, hybrid sensor approaches or location information increases energy consumption and data storage, which thereby limits recording duration and increases cost, size, and so forth.
Since wearable device based on inertial sensors is limited to its computing power, storage, and energy consumption, it is not suitable for running complex algorithm. Nevertheless, the smart phone has strong computing and communicating capability. So an innovative technology which takes advantage of wearable device and smart phone is introduced to provide the elderly with an unobtrusive fall detection.

Method and System Setup
Researches [25] studied acceleration of falls and activities of daily living (ADLs) from the waist, wrist, and head. The research data show that the upper trunk, which is below the neck and above the waist, is the most suitable feature region for distinguishing falls from other movements using acceleration. Meanwhile, in order to reduce the inconvenience caused by wearable device, the motion sensor board is put on the top of the custom vest to capture the activities of the individual in this paper.

Activity Model.
In the process of human motion, the acceleration and the deflection angle vary in real time. So the upper trunk Cartesian coordinate system oxyz, whose origin is close to the neck of human body, is paralleled with the geodetic coordinate system OXYZ as shown in Figure 1.
Accelerations along -, -, and -axis are denoted as , , and , respectively. The resultant acceleration can be calculated in The resultant angular velocity ( ) can be calculated in (2). , , and are the angular velocity along the -, -, and -axis. In general falls, is very small: Falls are usually characterized by rapid acceleration and angular velocity. In order to find out the differences between ADLs and falls, 3 typical subcategories of ADLs, walkingturning-walking (W-T-W), sitting down-standing up (Sd-Su), squatting-standing (Sq-Su), are analyzed and compared with two types of falls: Bw-Fall means backward falling without recovery in 2 seconds (as shown in Figure 2), and Sd-Fall means falling either to the left or to the right side (as shown in Figure 3). Figure 4 shows the resultant acceleration and angular velocity curves from each kind of motion process. Both the resultant acceleration and angular velocity are normalized treatment so as to simplify the expression. The horizontal axis is for time in unit of 0.1 s, while the longitudinal axis is for the resultant acceleration or angular velocity.
As can be seen from Figure 4, falls are usually characterized by rapid acceleration and great angular velocity, and they could be identified from ADLs as long as proper features are extracted.

Data Processing and NN Algorithm.
In the process of human motion, the reluctant acceleration and angular velocity vary real-timely and then make up stream data. It faces great challenges to classify stream data because of its infinite length. Hence, sliding window which just takes the last seen N elements of the stream into account is introduced to maintain similarity queries over stream data. Figure 5 illustrates the conventions that new data elements are coming from the right and the elements at the left are ones already seen. The sliding window covers a time period of × , where is the same sampling period. Each element of sensor data stream has an arrival time, which increments by one at each arrival, with the leftmost element considered to have arrived at time 1, since the duration of fall is less than 2 seconds, and the sample period is 0.1 second. So is set to 2, and the width of the sliding window is 20.
For an illustration of this notation, consider the situation presented in Figure 5. The start time of the sliding window is 17, the current time instant is 36, and the last seen element of the stream data is 36 . Each element consists of the resultant acceleration and angular velocity collected by sensors at time .
Based on such sliding window, two kinds of features are selected to classify falls from ADLs. The first one (namely, ) is the set of 20 reluctant accelerations, and the other one (namely, ) is the set of 20 reluctant angular velocities. Meanwhile NN algorithm is used as a classification model. Algorithm 1 represents the program code for how the sliding window slides through the data stream. train is the training dataset for fall patterns.
NN algorithm is introduced to measure the difference or similarity between instances according to a distance function.   Given a test instance , its closest neighbors, 1 , . . . , , are calculated, and a vote is conducted to assign the most common class to . That is, the class of , denoted by ( ), is determined as follows [26]: where ( ) is the class of and is a function that ( , V) = 1 if = V.
Since there are two kinds of features (namely, and ) used for classifying, Euclidean distance defined in formula (4) is selected as the distance function. Among formula (4), ( , ) is the Euclidean distance, is a test instance, is a training instance, and both of them are 2-dimensional real vector:

Implementation
Since most smart devices (such as smart phone and pad) are also integrated with the Bluetooth module and have strong computing capability, a smart phone integrated with Bluetooth is introduced to receive the stream data from sensors, and program based on the above technologies is developed to detect fall and issue alarm.

System
Architecture. Figure 6 shows the architecture of the system. The system mainly consists of a custom vest and a smart phone running the fall detection program. First the mainboard reads the individual accelerations and angular velocities from the accelerometer and gyroscope. Then it calculates the resultant acceleration and angular velocity and sends the data to the smart phone via the Bluetooth. After getting the data from the mainboard, the fall detection program judges whether the individual is falling or not based on the NN algorithm presented in Section 2. The phone can make a call or send a message with GPS position to a healthcare center or family member as soon as it detects a fall. This then provides a timely warning that a fall has occurred.

Data Acquisition.
The sensor board measures 24 mm × 38 mm × 9 mm (width × length × thickness), which is suitable for use in a vest. It consists of a high-performance, lowpower microcontroller and a class 2 Bluetooth module. The Bluetooth module has a range of 10 m and a default transmission rate of 115 k baud. The microcontroller reads the data from the accelerometer and gyroscope and calculates the resultant acceleration and angular velocity and transmits them to the smart phone. The triaxial accelerometer has a range of ±16 g. The triaxial gyroscope has a full-scale range of ±2000 ∘ /sec. Ten healthy individuals (5 males and 5 females, aged from 20 to 45) are asked to perform the intentional falls and ADLs both indoors and outdoors so as to get the training dataset. There are three kinds of ADLs (namely, W-T-W, Sd-Su, and Sq-Su) and fall. Each one includes 5 sets of resultant acceleration and angular velocity. As a result, there are a total of 200 sets of training samples in the training dataset. After getting the training dataset, the NN classification algorithm can be easily adapted for fall detection program. According to the instance of a sliding window from the input stream, the similarity between the instance and training sample in the training dataset is calculated using Euclidean distance function. If the similarity score of all NNs (from 1 to ) of the instance is voted to fall label, then it is classified as a fall pattern immediately. Otherwise, it is not classified as a fall pattern. The pseudocode for the adapted NN algorithm is presented in Algorithm 2.

Experiment
Since it is very dangerous for the elderly to test falls, there is not any experiment on the elderly over 50 years old. Fifteen healthy individuals, including 10 males and 5 females, aged from 20 to 45 years, are asked to perform the simulated falls and normal ADLs indoors and outdoors. The average height and mass of volunteers are 172.3 cm and 64.5 kg, respectively. According to the fall simulation protocol [27], fall simulation is conducted onto a 15 cm thick spongy cushion (hardness = 4 kPa, pressure to compass a piece of foam by 35% of its original height) to reduce the impact. Participants stand at a distance of 1.5 times the lengths of their foot apart from the spongy cushion and are instructed to do Sd-Fall (or Bw-Fall) like a frail old person, and there are no warm-up trials to familiarize with spongy cushion. In order to evaluate the fall detection system, the sensitivity and specificity are introduced.   detected successfully; only a few samples are undetected. Table 1 shows the statistic for the test samples. It can be calculated that the accuracy is 97.7%, while the sensitivity and specificity are 94% and 99%, respectively. It proves that the algorithm coupled with accelerometers and gyroscopes reduces both false positives and false negatives, while improving fall detection accuracy. Compared with the thresholds method using accelerations or gyroscopes at several single time points, the technology in this paper is an effective method for human fall detection. Most thresholds methods use the results of sensing information at uncontinuous time points to detect falls; thus some misdetection may be caused by the incomplete information in some experiments. For example, Wang et al. [17] achieved sensitivity of 91% and specificity of 92%. In this paper, the new method analyzes the steam data of accelerations and angular velocities during the whole course of human fall process in a 2 s sliding window, so more complete sensing information is used to study the features of human fall process. As a result, the experiment shows better results.

Experiment
Report shows that approximately 3% of all fallers lie for more than 20 min without external support, and 80% of the fallers aged 90 years or older are unable to get up by themselves [27]. Hence, an autonomous notification to caregiver after detecting fall will be greatly helpful for the elderly by reducing the time between the fall and the arrival of medical attention. The NN-based program running on smart phone takes advantage of several smart phone components (such as XML file, phone, and GPS) to provide a convenient and efficient alerting service. For example, Figure 7 shows the interface where user can set the interval time for autonomous notification to caregiver after detecting fall and can configure different warning methods on the smart phone. All of the configurations are stored into an XML file. Each of the detected falls triggers an alarm. If the user could not stop the alarm in the interval time, a call notifying caregiver is made, or an emergency message with GPS location is immediately sent to caregivers, so as to provide a timely and accurate help.    for data mining is introduced to compare NN with other learning algorithms according to the same training dataset and experimental data. A Lenovo ThinkCenter m6200t with an i5 CPU and 4 G memory is selected to run Weka. Table 2 shows the comparison of different learning algorithms. It can be seen that NN algorithm has the most correctness, and its running time is much less than 0.01 seconds. The sensitivity of NN while equals 7 is less than others (i.e., equals 3 or 5), and they have the same specificity. Besides, native Bayes algorithm has the most sensitivity (namely, 95.2%), but its specificity is less than NN, and its running time is about 0.01 seconds. The correctness of ANN is about 97.5%; it takes more than 0.44 seconds to run ANN algorithm. Figure 9 shows the correctness comparison of different learning algorithms between male and female. It can be seen that the male's correctness is usually higher than female's correctness except the Bayes Net and Bagging algorithms. Figure 10 shows the correctness comparison of different learning algorithms in different ages. It can be seen that NN algorithms have higher accuracy in those aged 21-25 and 36-40. ANN algorithm has higher accuracy in those aged 21-25, 26-30, and 41-45 than in those aged 31-35 and 41-45. There is not any clearly accurate difference on Decision Tree algorithm among different ages. Since NN is the most efficient learning algorithm with highest accuracy, it is quite suitable for running on smart phone.

Discussion.
Because of ethical constraints, a spongy cushion is used to avoid injuries to the participants during the simulated fall. While many (injurious) falls occur on hard materials (e.g., tiles), the spongy cushion can absorb the impact. As a result, the acceleration values of the simulated falls could not reflect a real-world fall. Besides, though there is not any warm-up trials for anticipants to familiarize with spongy cushion, the anticipants know that they will fall. This leads to anticipation that the anticipants may change postural control and response mechanisms. Just as Bagalà et al. outlined, algorithms calculated from fall simulations in healthy young subjects lack the necessary accuracy requirements for real-world fall detection [28]. Due to access problems to the elderly and other difficulties (e.g., cost and adherence), the number of recorded, documented, and published real-world fall data of older people is minimal [29]. Bourke et al. made a systematic review of a total number of 96 articles on fall detection with bodyworn sensors published between 1998 and 2012. It showed that less than 7% of studies have used fall data recorded from elderly people in real life, and simulated fall data were used in 90 (93.8%) studies. However, recently the FARSEEING is a European collaborating project, and one goal of the project is to generate a large metadatabase of real-world fall signals [30]. We plan to verify our system as soon as we can access the database of real-world falls.
In Schwickert et al. 's review [29], most of the sensors were placed at waist, chest, thorax, and trunk. In order to reduce the inconvenience for anticipants caused by wearable device and protect the motion sensor board from being broken, it is put on the top of the custom vest. Figure 11 shows that this results in higher impact signals than of those which the motion sensor board is putting at waist.
Since our fall detection system aims to detect fall and issue alarm, we do not divide the fall process into multiple phases, such as prefall phase, fall phase, and recovery phase. The system will just issue an alarm as soon as it detects fall, and a call to notify caregiver is made, or an emergency message with GPS location is sent to caregiver, as long as the user does not stop the alarm in the interval time.

Conclusion and Future Work
Taking into account the results and analysis provided above, it can be concluded that the proposed system is able to detect simulated falls with sufficient accuracy and can provide timely help for the elderly. In China, there is not any available data of real-world fall as well nowadays. Based on the encouraging results achieved, we will cooperate with community geracomium, supply our motion sensor board and software to the elderly without compensation, so as to collect data of the daily activities, and harvest the database of real-world falls. After getting the database of real-world falls, our fall detection system will be verified and improved. Besides, we will study different important aspects of a fall event according to the multiphase model of fall supposed by Klenk et al. [27]. For example, we will study algorithm to predict fall according to the research of the prefall activity.


Modelling Context with User Embeddings for Sarcasm Detection in Social Media

We introduce a deep neural network for automated sarcasm detection. Recent work has emphasized the need for models to capitalize on contextual features, beyond lexical and syntactic cues present in utterances. For example, different speakers will tend to employ sarcasm regarding different subjects and, thus, sarcasm detection models ought to encode such speaker information. Current methods have achieved this by way of laborious feature engineering. By contrast, we propose to automatically learn and then exploit user embeddings, to be used in concert with lexical signals to recognize sarcasm. Our approach does not require elaborate feature engineering (and concomitant data scraping); fitting user embeddings requires only the text from their previous posts. The experimental results show that our model outperforms a state-of-the-art approach leveraging an extensive set of carefully crafted features.

Introduction
Existing social media analysis systems are hampered by their inability to accurately detect and interpret figurative language. This is particularly relevant in domains like the social sciences and politics, in which the use of figurative communication devices such as verbal irony (roughly, sarcasm) is common. Sarcasm is often used by individuals to express opinions on complex matters and regarding specific targets (Carvalho et al., 2009).
Early computational models for verbal irony and sarcasm detection tended to rely on shallow methods exploiting conditional token count regularities. But lexical clues alone are insufficient to discern ironic intent. Appreciating the context of utterances is critical for this; even for humans (Wallace et al., 2014). Indeed, the exact same sentence can be interpreted as literal or sarcastic, depending on the speaker. Consider the sarcastic tweet in Figure 1 (ignoring for the moment the attached #sarcasm hashtag). Without knowing the author's political leanings, it would be difficult to conclude with certainty whether the remark was intended sarcastically or in earnest.
Recent work in sarcasm detection on social media has tried to incorporate contextual information by exploiting the preceding messages of a user, to e.g., detect contrasts in sentiments expressed towards named entities (Khattri et al., 2015), infer behavioural traits (Rajadesingan et al., 2015) and capture the relationship between authors and the audience (Bamman and Smith, 2015). However, all of these approaches require the design and implementation of complex features that explicitly encode the content and (relevant) context of messages to be classified. This feature engineering is labor intensive, and depends on external tools and resources. Therefore, deploying such systems in practice is expensive, time-consuming and unwieldy.
We propose a novel approach to sarcasm detection on social media that does not require extensive manual feature engineering. Instead, we develop a neural model that learns to represent and exploit embeddings of both content and context. For the former, we induce vector lexical repre-sentations via a convolutional layer; for the latter, our model learns user embeddings. Inference concerning whether an utterance (tweet) was intended ironically (or not) is then modelled as a joint function of lexical representations and corresponding author embeddings.
The main contributions of this paper are as follows. (i) We propose a novel convolutional neural network based model that explicitly learns and exploits user embeddings in conjunction with features derived from utterances. (ii) We show that this model outperforms the strong baseline recently proposed by Bamman and Smith (2015) by more than 2% in absolute accuracy, while obviating the need to manually engineer features. (iii) We show that the learned user embeddings can capture relevant user attributes.

Related Work
Verbal irony is a rhetorical device in which speakers say something other than, and often opposite to, what they actually mean. 1 Sarcasm may be viewed as a special case of irony, where the positive literal meaning is perceived as an indirect insult (Dews et al., 1995).
Most of the previously proposed computational models to detect irony and sarcasm have used features similar to those used in sentiment analysis. Carvalho et al. (2009) analyzed comments posted by users on a Portuguese online newspaper and found that oral and gestural cues indicate irony. These included: emoticons, onomatopoeic expressions for laughter, heavy punctuation, quotation marks and positive interjections. Others have used text classifiers with features based on word and character n-grams, sentiment lexicons, surface patterns and textual markers (Davidov et al., 2010;González-Ibánez et al., 2011;Reyes et al., 2013;Lukin and Walker, 2013). Elsewhere, Barbieri and Saggion (2014) derived new wordfrequency based features to detect irony, e.g., combinations of frequent and rare words, ambiguous words, 'spoken style' words combined with 'written style' words and intensity of adjectives. Riloff et al. (2013) demonstrated that one may exploit the apparent expression of contrasting sentiment in the same utterance as a marker of verbal irony.
The aforementioned approaches rely predominantly on features intrinsic to texts, but these will often be insufficient to infer figurative meaning: context is needed. There have been some recent attempts to exploit contextual information, e.g. Khattri et al. (2015) extended the notion of contrasting sentiments beyond the textual content at hand. In particular, they analyzed previous posts to estimate the author's prior sentiment towards specific targets (i.e., entities). A tweet is then predicted to be sarcastic if it expresses a sentiment about an entity that contradicts the author's (estimated) prior sentiment regarding the same. Rajadesingan et al. (2015) built a system based on theories of sarcasm expression from psychology and behavioral sciences. To operationalize such theories, they used several linguistic tools and resources (e.g. lexicons, sentiment classifiers and a PoS tagger), in addition to user profile information and previous posts, to model a range of behavioural aspects (e.g., mood, writing style).  developed an approach for classifying posts on reddit 2 as sarcastic or literal, based in part on the interaction between the specific sub-reddit to which a post was made, the entities mentioned, and the (apparent) sentiment expressed. For example, if a post in the (politically) conservative sub-reddit mentions Obama, it is more likely to have been intended ironically than posts mentioning Obama in the progressive sub-reddit. But this approach is limited because it relies on the unique sub-reddit structure. Bamman and Smith (2015) proposed an approach that relied on an extensive, rich set of features capturing various contextual information about authors of tweets and the audience (in addition to lexical cues). We review these at length in Section 5.1.
A major downside of these and related approaches, however, is the amount of manual effort required to derive these feature sets. A primary goal of this work is to explore whether neural models can effectively learn these rich contextualizing features, thus obviating the need to manually craft them. In particular, the model we propose similarly aims to combine lexical clues with extralinguistic information. Unlike prior work, however, our model attempts to automatically induce representations for the content and the author of a message that are predictive of sarcasm.

Learning User Embeddings
Our goal is to learn representations (vectors) that encode latent aspects of users and capture homophily, by projecting similar users into nearby regions of the embedding space. We hypothesize that such representations will naturally capture some of the signals that have been described in the literature as important indicators of sarcasm, such as contrasts between what someone believes and what they have ostensibly expressed (Campbell and Katz, 2012) or Kreuz (1996) principle of inferability, stating that sarcasm requires a common ground between parties to be understood.
To induce the user embeddings, we adopt an approach similar to that described in the preliminary work of Li et al. (2015). In particular, we capture relations between users and the content they produce by optimizing the conditional probability of texts, given their authors (or, more precisely, given the vector representations of their authors). This method is akin to Le and Mikolov (2014)'s Paragraph Vector model, which jointly estimates embeddings for words and paragraphs by learning to predict the occurrence of a word w within a paragraph p conditioned on the (learned) representation for p.
Given a sentence S = {w 1 , . . . , w N } where w i denotes a word drawn from a vocabulary V, we aim to maximize the following probability: Where C(w i ) denotes the set of words in a prespecified window around word w i , e k ∈ R d and u j ∈ R d denote the embeddings of word k and user j, respectively. This objective function encodes the notion that the occurrence of a word w, depends both on the author of S and it's neighbouring words. The conditional probabilities in Equation 1 can be estimated with log-linear models of the form: Where x denotes a feature vector, W k and b k are the weight vectors and bias for class k. In our case, we treat words as classes to be predicted.
Calculating the denominator thus requires summing over all of the words in the (large) vocabulary, an expensive operation. To avoid this computational bottleneck, we approximate the term P (w i |e k ) with Morin and Bengio (2005) Hierarchical Softmax. 3 To learn meaningful user embeddings, we seek representations that are predictive of individual word-usage patterns. In light of this motivation, we approximate P (w i |u j ) via the following hinge-loss objective which we aim to minimize: Here, each w l (and corresponding embedding, e l ) is a negative example, i.e., a word not in the sentence under consideration, which was authored by user j. The intuition is that in the aggregate, such words are less likely to be employed by user j than words observed in sentences she has authored. Thus minimizing this objective attempts to induce a representation that is discriminative with respect to word usage.
In practice, V will be very large and hence we approximate the objective via negative sampling, a variant of Noise Contrastive Estimation. The idea is to approximate the objective function in a binary classification task by learning to discriminate between observed positive examples (sampled from the true distribution) and pseudo-negative examples (sampled from a large space of predominantly negative instances). Intuitively, this shifts probability mass to plausible observations. See Dyer (2014) for notes on Negative Sampling and Noise Contrastive Estimation.
Previous work by Collobert et al. (2011) showed that this approach works well in representation learning tasks when a sufficient amount of training data is available . However, we have access to only a limited amount of text for each user (see Section 5). We hypothesize that this problem can be alleviated by carefully selecting the negative samples that mostly contribute to 'push' the vectors into the appropriate region of the embedding space (i.e., closer to the words commonly employed by a given user and far from other words). This requires designing a strategy for selectively sampling negative examples. One straightforward approach would be to sample from a user-specific unigram model, informing which words are less likely to be utilized by that user. But estimating the parameters of such model with scarce data would be prone to overfitting. Instead, we sample from a unigram distribution estimated from the posts authored by all the users. The goal is to select the most commonly used words as the negative samples, thereby forcing the representations to capture the differences between the words a given individual employs and the words that everyone commonly uses.

Proposed Model
We now present the details of our proposed sarcasm detection model. Given a message S authored by user u, we wish to capture both the relevant aspects of the content and the relevant contextual information about the author. To represent the content, we use pre-trained word embeddings as the input to a convolutional layer that extracts high-level features. More formally, let E ∈ R d×|V| be a pre-trained word embedding matrix, where each column represents a word from the vocabulary V as a d dimensional vector. By selecting the columns of E corresponding to the words in S, we form the sentence matrix: A convolutional layer is composed of a set of filters F ∈ R d×h where h is the height of the filter. Filters slide across the input, extracting hgram features that constitute a feature map m ∈ R |S|−h+1 , where each entry is obtained as Here, S [i:j] denotes a sub-matrix of S (from row i to row j), b ∈ R is an additive bias and α(·) denotes a non-linear activation function, applied elementwise. We transform the resultant feature map into a scalar using max-pooling, i.e., we extract the largest value in the map. We use 3 filters (with varying heights) each of which generates M feature maps that are reduced to a vector where ⊕ denotes concatenation. We set α(·) to be the Rectified Linear Unit activation function (Nair and Hinton, 2010). The output of all the filters is then combined to form the final representation c = [f 1 ⊕ f 2 ⊕ f 3 ]. We will denote this feature vector of a specific sentence S by c S . To represent the context, we assume there is a user embedding matrix U ∈ R d×N , where each column represents one of N users with a d dimensional vector. The parameters of this embedding matrix can be initialized randomly or using the approach described in Section 3. Then, we simply map the author of the message into the user embedding space by selecting the corresponding column of U. Letting U u denote the user embedding of author u, we formulate our sarcasm detection model as follows: where g(·) denote the activations of a hidden layer, capturing the relations between the content and context representations, and θ = {Y, b, H, h, F 1 , F 2 , F 3 , E, U} are parameters to be estimated during training. Here, Y ∈ R 2×z and b ∈ R 2 are the weights and bias of the output layer; H ∈ R z×3M +d and h ∈ R z are the weights and bias of the hidden layer; and F i are the weights of the convolutional filters. Henceforth, we will refer to this approach as Content and User Embedding Convolutional Neural Network (CUE-CNN). Figure 2 provides an illustrative schematic depicting this model.

Experimental Setup
We replicated Bamman and Smith (2015) experimental setup using (a subset of) the same Twitter corpus. The labels were inferred from selfdeclarations of sarcasm, i.e., a tweet is considered sarcastic if it contains the hashtag #sarcasm or #sarcastic and deemed non-sarcastic otherwise. 4 To comply with Twitter terms of service, we were given only the tweet ids along with the corresponding labels and had to retrieve the messages ourselves. By the time we tried to retrieve the messages, some of them were not available.
We also did not have access to the historical user tweets used by Bamman and Smith, hence, for each author and mentioned user, we scraped additional tweets from their Twitter feed. Due to restrictions in the Twitter API, we were only able to crawl at most 1000 historical tweets per user. 5 Furthermore, we were unable to collect historical tweets for a significant proportion of the users, thus, we discarded messages for which no contextual information was available, resulting in a corpus of 11, 541 tweets involving 12, 500 unique users (authors and mentioned users). It should also be noted that our historical tweets were posted after the ones in the corpus used for the experiments.

Baselines
We reimplemented Bamman and Smith (2015)'s sarcasm detection model. This a simple, logisticregression based classifier that exploits rich feature sets to achieve strong performance. These are detailed at length in the original paper, but we briefly summarize them here: • tweet-features, encoding attributes of the target tweet text, including: uni-and bigram bag of words (BoW) features; Brown et al. (1992) word clusters indicators; unlabeled dependency bigrams (both BoW and with Brown cluster representations); part-ofspeech, spelling and abbreviation features; inferred sentiment, at both the tweet and word level; and 'intensifier' indicators.
• author-features, aimed at encoding attributes of the author, including: historically 5 The original study (Bamman and Smith, 2015) was done with at most 3, 200 historical tweets. 'salient' terms used by the author; the inferred distribution over topics 6 historically tweeted about by the user; inferred sentiment historically expressed by the user; and author profile information (e.g., profile BoW features).
• audience-features, capturing properties of the addressee of tweets, in those cases that a tweet is directed at someone (via the @ symbol). A subset of these, duplicate the aforementioned author features for the addressee. Additionally, author/audience interaction features are introduced, which capture similarity between the author and addressee, w.r.t. inferred topic distributions. Finally, this set includes a feature capturing the frequency of past communication between the author and addressee.
• response-features, for tweets written in response to another tweet. This set of features captures information relating the two, with BoW features of the original tweet and pairwise cluster indicator features, which the encode Brown clusters observed in both the original and response tweet.
We emphasize that implementing this rich set of features took considerable time and effort. This motivates our approach, which aims to effectively induce and exploit contextually-aware representations without manual feature engineering.
To assess the importance of modelling contextual information in sarcasm detection, we considered two groups of models as baselines: the first only takes into account the content of a target tweet. The second, combines lexical cues with contextual information. The first group includes the following models: • UNIGRAMS: 2 -regularized logistic regression classifier with binary unigrams as features.
• NBOW: Logistic regression with neural word embeddings as features. Given a sentence matrix S (Eq. 4) as input, a d-dimensional feature vector is computed by summing the individual word embeddings.
• NLSE: The Non-linear subspace embedding model due to Astudillo et al. (2015). The NLSE model adapts pre-trained word embeddings for specific tasks by learning a projection into a small subspace. The idea is that this subspace captures the most discriminative latent aspects encoded in the word embeddings. Given a sentence matrix S, each word vector is first projected into the subspace and then transformed through an element-wise sigmoid function. The final sentence representation is obtained by summing the (adapted) word embeddings and passed into a softmax layer that outputs the predictions.
• CNN: The CNN model for text classification proposed by Kim (2014), using only features extracted from the convolutional layer acting on the lexical content. The input layer was initialized with pre-trained word embeddings.
The second group of baselines consists of the following models: • TWEET+*: 2 -regularized logistic regression classifier with a combination of tweetfeatures and each of the aforementioned Bamman and Smith (2015) feature sets.
• SHALLOW CUE-CNN: A simplified version of our neural model for sarcasm detection, without the hidden layer. We evaluated two variants: initializing the user embeddings at random, and initializing the user embeddings with the approach described in Section 3 (SHALLOW CUE-CNN+USER2VEC). In both cases, the (word and user) embeddings weights were updated during training.
• CUE-CNN+*: Our proposed neural network for sarcasm detection. We also evaluated the two aforementioned variants: randomly initialized user embeddings and pretrained user embeddings. But here we compared two different approaches for the negative sampling procedure, namely, sampling from a unigram distribution (CUE-CNN+USER2VEC) and sampling uniformly at random from the vocabulary (CUE-CNN+USER2VEC-UNIFRAND).

Pre-Training Word and User Embeddings
We To induce user embeddings, we estimated a unigram distribution with maximum likelihood estimation. Then, for each word in a tweet, we extracted 15 negative samples (for the first term in Eq.1) and used the skip-gram model to precompute the conditional probabilities of words occurring in a window of size 5 (for the second term in Eq.1). Finally, Equation 1 was minimized via Stochastic Gradient Descent on 90% of the historical data, holding out the remainder for validation and using the P (tweet text|user) as early stopping criteria.
Note that the parameters for each user only depend on their own tweets; this allowed us to perform these computations in parallel to speed-up the training. m

Model Training and Evaluation
Evaluation was performed via 10-fold crossvalidation. For each split, we fit models to 80% of the data, tuned them on 10% and tested on the remaining, held-out 10%. These data splits were kept fixed in all the experiments. For the linear classifiers, in each split, the regularization constant was selected with a linear search over the (a) Performance of the linear classifier baselines. We include the results reported by Bamman and Smith (2015) as a reference. Discrepancies between their reported results and those we achieved with our re-implementation reflect the fact that their experiments were performed using a significantly larger training set and more historical tweets than we had access to.
(b) Performance of the proposed neural models. We compare simple neural models that only consider the lexical content of a message (first 3 bars) with architectures that explicitly model the context. Bars 4 and 5 show the gains obtained by pretraining the user embeddings. The last 2 bars compare different negative sampling procedures for the user embedding pre-training. Figure 3: Comparison of different models. The left sub-plot shows linear model performance; the right shows the performance of neural variants. The horizontal line corresponds to the best performance achieved via linear models with rich feature sets. Performance was measured in terms of average accuracy over 10-fold cross-validation; error bars depict the variance.
range C = [1e −4 , 1e −3 , 1e −2 , 1e −1 , 1, 10] using the training set to fit the model and evaluating on the tuning set. After selecting the best regularization constant, the model was re-trained on the union of the train and tune sets, and evaluated on the test set.
To train our neural model, we first had to choose a suitable architecture and hyperparameter set. However, selecting the optimal network parametrization would require an extensive search over a large configuration space. Therefore, in these experiments, we followed the recommendations in Zhang and Wallace (2015) We performed random search by sampling without replacement over half of the possible configurations. For each data split, 20% of the training set was reserved for early stopping. We compared the sampled configurations by fitting the model on the remaining training data and testing on the tune set. After choosing the best configuration, we retrained the model on the union of the train and tune set (again reserving 20% of the data for early stopping) and evaluated on the test set.
The model was trained by minimizing the crossentropy error between the predictions and true labels, the gradients w.r.t to the network parameters were computed with backpropagation (Rumelhart et al., 1988) and the model weights were updated with the AdaDelta rule (Zeiler, 2012).

Classification Results
Figure 3 presents the main experimental results. In Figure 3a, we show the performance of linear classifiers with the manually engineered feature sets proposed by Bamman and Smith (2015). Our results differ slightly from those originally reported. Nonetheless, we observe the same general trends: namely, that including contextual features significantly improves the performance, and that the biggest gains are attributable to features encoding information about the authors of tweets.
The results of neural model variants are shown in Figure 3b. Once again, we find that modelling the context (i.e., the author) of a tweet yields significant gains in accuracy. The difference is that here the network jointly learns appropriate user representations, lexical feature extractors and, finally, the classification model. Further improvements are realized by pre-training the user embed-(a) Users colored according to the politicians they follow on Twitter: the blue circles represent users that follow at least one of the (democrats) accounts: @BarackObama, @HillaryClinton and @BernieSanders; the red circles represent users that follow at least one of the (republicans) accounts: @marcorubio, @tedcruz and @realDonaldTrump. Users that follow accounts from both groups were excluded. We can see that users with a similar political leaning tend to have similar vectors.
(b) Users colored with respect to the likelihood of following a sports account. The 500 most popular accounts (according to the authors in our training data) were manually inspected and 100 sports related accounts were selected, e.g., @SkySports, @NBA and @cristiano. We should note that users for which the probabilities lied in the range between 0.3 − 0.7 were discarded to emphasize the extremes. Figure 4: T-SNE projection of the user embeddings into 2-dimensions. The users are color coded according to their political preferences and interest in sports. The visualization suggests that the learned embeddings capture some notion of homophily. dings (we elaborate on this in the following section). We see additional gains when we introduce a hidden layer capturing the interactions between the context (i.e., user vectors) and the content (lexical vectors). This is intuitively agreeable: the recognition of sarcasm is possible when we jointly consider the speaker and the utterance at hand. Interestingly, we observed that our proposed model not only outperforms all the other baselines, but also shows less variance over the cross-validation experiments.
Finally, we compared the effect of obtaining negative samples uniformly at random with sampling from a unigram distribution. The experimental results show that the latter improves the accuracy of the model by 0.8%. We believe the reason is that considering the most likely words (under the model) as negative samples, helps by pushing the user vectors away from non-informative words and simultaneously closer to the most discriminative words for that user.

User Embedding Analysis
We now investigate the user embeddings in more detail. In particular, we are interested in two questions: first, what aspects are being captured in these representations; and second, how they contribute to the improved performance of our model. To investigate the first question, we plotted a T-SNE projection (Maaten and Hinton, 2008) of the high-dimensional vector space where the users are represented into two-dimensions. We then colored each point (representing a user) according to their apparent political leaning (Figure 4a), and according to their interest in sports (Figure 4b). These attributes were inferred using the Twitter accounts that a user follows, as a proxy. The plots suggest that the user vectors are indeed able to cap-ture latent aspects, such as political preferences and personal interests. Moreover, the embeddings seem to uncover a notion of homophily, i.e. similar users tend to occupy neighbouring regions of the embedding space. Regarding the second question, we examined the influence of the contextual information on the model's predictions. To this end, we measured the response of our model to the same textual content with different hypothetical contexts (authors). We selected two examples that were misclassified by a simple CNN and ran them trough the CUE-CNN model with three different user embeddings. In Figure 5, we show these examples along with the predicted probabilities of being a sarcastic post, when no user information is considered and when the author is taken into account. We can see that the predictions drastically change when contextual information is available and that two of the authors trigger similar responses on both examples. This example provides evidence that our model captures the intuition that the same utterance can be interpreted as sarcastic or not, depending on the speaker.

Conclusions
We have introduced CUE-CNN, a novel, deep neural network for automatically recognizing sarcastic utterances on social media. Our model jointly learns and exploits embeddings for the content and users, thus integrating information about the speaker and what he or she has said. This is accomplished without manual feature engineering. Nonetheless, our model outperforms (by over 2% in absolute accuracy) a recently proposed stateof-the-art model that exploits an extensive, handcrafted set of features encoding user attributes and other contextual information. Unlike other approaches that explicitly exploit the structure of particular social media services, such as the forum where a message was posted or metadata about the users, learning user embeddings only requires their preceding messages. Yet, the obtained vectors are able to capture relevant user attributes and a soft notion of homophily. This, we believe, makes our model easier to deploy over different social media environments.
Our implementation of the proposed method and the datasets used in this paper have been made publicly available 7 . As future work, we intended to further explore the user embeddings for context