Improving Distributed Representations of Tweets - Present and Future

Unsupervised representation learning for tweets is an important research field which helps in solving several business applications such as sentiment analysis, hashtag prediction, paraphrase detection and microblog ranking. A good tweet representation learning model must handle the idiosyncratic nature of tweets which poses several challenges such as short length, informal words, unusual grammar and misspellings. However, there is a lack of prior work which surveys the representation learning models with a focus on tweets. In this work, we organize the models based on its objective function which aids the understanding of the literature. We also provide interesting future directions, which we believe are fruitful in advancing this field by building high-quality tweet representation learning models.

Introduction
Twitter is a widely used microblogging platform, where users post and interact with messages, "tweets". Understanding the semantic representation of tweets can benefit a plethora of applications such as sentiment analysis (Ren et al., 2016;Giachanou and Crestani, 2016), hashtag prediction (Dhingra et al., 2016), paraphrase detection (Vosoughi et al., 2016) and microblog ranking (Huang et al., 2013;Shen et al., 2014). However, tweets are difficult to model as they pose several challenges such as short length, informal words, unusual grammar and misspellings. Recently, researchers are focusing on leveraging unsupervised representation learning methods based on neural networks to solve this problem. Once these representations are learned, we can use off-the-shelf predictors taking the representation as input to solve the downstream task (Bengio, 2013a;Bengio et al., 2013b). These methods enjoy several advantages: (1) they are cheaper to train, as they work with unlabelled data, (2) they reduce the dependence on domain level experts, and (3) they are highly effective across multiple applications, in practice.
Despite this, there is a lack of prior work which surveys the tweet-specific unsupervised representation learning models. In this work, we attempt to fill this gap by investigating the models in an organized fashion. Specifically, we group the models based on the objective function it optimizes. We believe this work can aid the understanding of the existing literature. We conclude the paper by presenting interesting future research directions, which we believe are fruitful in advancing this field by building high-quality tweet representation learning models.

Unsupervised Tweet Representation Models
There are various models spanning across different model architectures and objective functions in the literature to compute tweet representation in an unsupervised fashion. These models work in a semi-supervised way -the representations generated by the model is fed to an off-the-shelf predictor like Support Vector Machines (SVM) to solve a particular downstream task. These models span across a wide variety of neural network based architectures including average of word vectors, convolutional-based, recurrent-based and so on. We believe that the performance of these models is highly dependent on the objective function it optimizes -predicting adjacent word (withintweet relationships), adjacent tweet (inter-tweet relationships), the tweet itself (autoencoder), mod-  eling from structured resources like paraphrase databases and weak supervision. In this section, we provide the first of its kind survey of the recent tweet-specific unsupervised models in an organized fashion to understand the literature. Specifically, we categorize each model based on the optimized objective function as shown in Figure 1. Next, we study each category one by one.

Modeling within-tweet relationships
Motivation: Every tweet is assumed to have a latent topic vector, which influences the distribution of the words in the tweet. For example, though the appearance of the phrase catch the ball is frequent in the corpus, if we know that the topic of a tweet is about "technology", we can expect words such as bug or exception after the word catch (ignoring the) instead of the word ball since catch the bug/exception is more plausible under the topic "technology". On the other hand, if the topic of the tweet is about "sports", then we can expect ball after catch. These intuitions indicate that the prediction of neighboring words for a given word strongly relies on the tweet also. Models: (Le and Mikolov, 2014)'s work is the first to exploit this idea to compute distributed document representations that are good at predicting words in the document. They propose two models: PV-DM and PV-DBOW, that are extensions of Continuous Bag Of Words (CBOW) and Skip-gram model variants of the popular Word2Vec model (Mikolov et al., 2013) respectively -PV-DM inserts an additional document token (which can be thought of as another word) which is shared across all contexts generated from the same document; PV-DBOW attempts to predict the sampled words from the document given the document representation. Although originally employed for paragraphs and documents, these models work better than the traditional models: BOW (Harris, 1954) and LDA (Blei et al., 2003) for tweet classification and microblog retrieval tasks (Wang et al., 2016). The authors in (Wang et al., 2016) make the PV-DM and PV-DBOW models concept-aware (a rich semantic signal from a tweet) by augmenting two features: attention over contextual words and conceptual tweet embedding, which jointly exploit concept-level senses of tweets to compute better representations. Both the discussed works have the following characteristics: (1) they use a shallow architecture, which enables fast training, (2) computing representations for test tweets requires computing gradients, which is time-consuming for real-time Twitter applications, and (3) most importantly, they fail to exploit textual information from related tweets that can bear salient semantic signals.

Modeling inter-tweet relationships
Motivation: To capture rich tweet semantics, researchers are attempting to exploit a type of sentence-level Distributional Hypothesis (Harris, 1954;Polajnar et al., 2015). The idea is to infer the tweet representation from the content of adjacent tweets in a related stream like users' Twitter timeline, topical, retweet and conversational stream. This approach significantly alleviates the context insufficiency problem caused due to the ambiguous and short nature of tweets (Ren et al., 2016;Ganesh et al., 2017). Models: Skip-thought vectors  (STV) is a widely popular sentence encoder, which is trained to predict adjacent sentences in the book corpus . Although the testing is cheap as it involves a cheap forward propagation of the test sentence, STV is very slow to train thanks to its complicated model architecture. To combat this computational inefficiency, FastSent (Hill et al., 2016) propose a simple additive (log-linear) sentence model, which predicts adjacent sentences (represented as BOW) taking the BOW representation of some sentence in context. This model can exploit the same signal, but at a much lower computational expense. Parallel to this work, Siamase CBOW (Kenter et al., 2016) develop a model which directly compares the BOW representation of two sentence to bring the embeddings of a sentence closer to its adjacent sentence, away from a randomly occurring sentence in the corpus. For FastSent and Siamese CBOW, the test sentence representation is a simple average of word vectors obtained after training. Both of these models are general purpose sentence representation models trained on book corpus, yet give a competitive performance over previous models on the tweet semantic similarity computation task. (Ganesh et al., 2017)'s model attempt to exploit these signals directly from Twitter. With the help of attention technique and learned user representation, this log-linear model is able to capture salient semantic information from chronologically adjacent tweets of a target tweet in users' Twitter timeline.

Modeling from structured resources
Motivation: In recent times, building representation models based on supervision from richly structured resources such as Paraphrase Database (PPDB) (Ganitkevitch et al., 2013) (containing noisy phrase pairs) has yielded high quality sentence representations. These methods work by maximizing the similarity of the sentences in the learned semantic space. Models: CHARAGRAM (Wieting et al., 2016a) embeds textual sequences by learning a characterbased compositional model that involves addition of the vectors of its character n-grams followed by an elementwise nonlinearity. This simpler architecture trained on PPDB is able to beat models with complex architectures like CNN, LSTM on SemEval 2015 Twitter textual similarity task by a large margin. This result emphasizes the importance of character-level models that address differences due to spelling variation and word choice. The authors in their subsequent work (Wieting et al., 2016b) conduct a comprehensive analysis of models spanning the range of complexity from word averaging to LSTMs for its ability to do transfer and supervised learning after optimizing a margin based loss on PPDB. For transfer learning, they find models based on word averaging perform well on both the in-domain and out-of-domain textual similarity tasks, beating LSTM model by a large margin. On the other hand, the word averaging models perform well for both sentence similarity and textual entailment tasks, outperforming the LSTM. However, for sentiment classification task, they find LSTM (trained on PPDB) to beat the averaging models to establish a new state of the art. The above results suggest that structured resources play a vital role in computing general-purpose embeddings useful in downstream applications.

Modeling as an autoencoder
Motivation: The autoencoder based approach learns latent (or compressed) representation by reconstructing its own input. Since textual data like tweets contain discrete input signals, sequenceto-sequence models (Sutskever et al., 2014) like STV can be used to build the solution. The encoder model which encodes the input tweet can typically be a CNN (Kim, 2014), recurrent models like RNN, GRU, LSTM (Karpathy et al., 2015) or memory networks (Sukhbaatar et al., 2015). The decoder model which generates the output tweet can typically be a recurrent model that predicts a output token at every time step. Models: Sequential Denoising Autoencoders (SDAE) (Hill et al., 2016) is a LSTM-based sequence-to-sequence model, which is trained to recover the original data from the corrupted version. SDAE produces robust representations by learning to represent the data in terms of features that explain its important factors of variation. Tweet2Vec (Vosoughi et al., 2016) is a recent model which uses a character-level CNN-LSTM encoder-decoder architecture trained to construct the input tweet directly. This model outperforms competitive models that work on word-level like PV-DM, PV-DBOW on semantic similarity computation and sentiment classification tasks, thereby showing that the character-level nature of Tweet2Vec is best-suited to deal with the noise and idiosyncrasies of tweets. Tweet2Vec controls the generalization error by using a data augmentation technique, wherein tweets are replicated and some of the words in the replicated tweets are replaced with their synonyms. Both SDAE and Tweet2Vec has the advantage that they don't need a coherent inter-sentence narrative (like STV), which is hard to obtain in Twitter.

Modeling using weak supervision
Motivation: In a weakly supervised setup, we create labels for a tweet automatically and predict them to learn potentially sophisticated models than those obtained by unsupervised learning alone. Examples of labels include sentiment of the overall tweet, words like hashtag present in the tweet and so on. This technique can create a huge labeled dataset especially for building datahungry, sophisticated deep learning models. Models: (Tang et al., 2016) learns sentimentspecific word embedding (SSWE), which encodes the polarity information in the word representations so that words with contrasting polarities and similar syntactic context (like good and bad) are pushed away from each other in the semantic space that it learns. SSWE utilizes the massive distant-supervised tweets collected by positive and negative emoticons to build a powerful tweet representation, which are shown to be useful in tasks such as sentiment classification and word similarity computation in sentiment lexicon. (Dhingra et al., 2016) observes that hashtags in tweets can be considered as topics and hence tweets with similar hashtags must come closer to each other. Their model predicts the hashtags by using a Bi-GRU layer to embed the tweets from its characters. Due to subword modeling, such characterlevel models can approximate the representations for rare words and new words (words not seen during training) in the test tweets really well. This model outperforms the word-level baselines for hashtag prediction task, thereby concluding that exploring character-level models for tweets is a worthy research direction to pursue. Both these works fail to study the model's generality (Weston et al., 2014), i.e., the ability of the model to transfer the learned representations to diverse tasks.

Future Directions
In this section we present the future research directions which we believe can be worth pursuing to generate high quality tweet embeddings.
• (Ren et al., 2016) propose a supervised neural network utilizing contextualized features from conversation, author and topic based context about a target tweet to perform well in classification of tweet. Apart from (Ganesh et al., 2017)'s work which utilizes author context, there is no other work which builds unsupervised tweet representation model on Twitter-specific contexts such as conversation and topical streams. We believe such a solution directly exploits semantic signals (or nuances) from Twitter, unlike STV or Siamese CBOW which are trained on books corpus.
• (dos Santos and Gatti, 2014) propose a supervised, hybrid model exploiting both the character and word level information for Twitter sentiment analysis task. Since the settings when the character level model beats the word level model is not well understood yet, we believe it would be interesting to explore such a hybrid compositional model to build unsupervised tweet representations.
• Twitter provides a platform for the users to interact with other users. To the best of our knowledge, there is no related work that computes unsupervised tweet representation by exploiting the user profile attributes like profile picture, user biography and set of followers, and social interactions like retweet context (set of surrounding tweets in a users retweet stream) and favorite context (set of surrounding tweets in a users favorite tweet stream).
• DSSM (Huang et al., 2013;Shen et al., 2014) propose a family of deep models that are trained to maximize the relevance of clicked documents given a query. Such a ranking loss function helps the model cater to a wide variety of applications 1 such as web search ranking, ad selection/relevance, question answering, knowledge inference and machine translation. We observe such a loss function has not been explored for building unsupervised tweet representations. We believe employing a ranking loss directly on tweets using a large scale microblog dataset 2 can result in representations which can be useful to Twitter applications beyond those studied in the tweet representation learning literature.
• Linguists assume that language is best understood as a hierarchical tree of phrases, rather than a flat sequence of words or characters. It's difficult to get the syntactic trees for tweets as most of them are not grammatically correct. The average of word vectors model has the most simplest compositional architecture with no additional parameters, yet displays a strong performance outperforming complex architectures such as CNN, LSTM and so on for several downstream applications (Wieting et al., 2016a,b). We believe a theoretical understanding of why word averaging models perform well can help in embracing these models by linguists.
• Models in (Wieting et al., 2016a,b) learn from noisy phrase pairs of PPDB. Note that the source of the underlying texts is completely different from Twitter. It can be interesting to see the effectiveness of such models when directly trained on structural resources from Twitter like Twitter Paraphrase Corpus (Xu et al., 2014). The main challenge with this approach is the small size of the annotated Twitter resources, which can encourage models like (Arora et al., 2017) that work well even when the training data is scarce or nonexistent.
• Tweets mostly have an accompanying image which sometimes has visual correspondence with its textual content Wang et al., 2014) ('visual' tweet).
To the best of our knowledge, there is no work which explores the following question: can we build multimodal representations for tweets accompanying correlated visual content and compare with traditional benchmarks?. We can leverage insights from multimodal skip-gram model (Lazaridou et al., 2015) which builds multimodally-enhanced word vectors that perform well in the traditional semantic benchmarks. However, it's hard to detect visual tweets and learning from a non-visual tweet can degrade its tweet representation. It would be interesting to see if a dispersion metric (Kiela et al., 2014) for tweets can be explored to overcome this problem of building a nondegradable, improved tweet representation.
• Interpreting the tweet representations to unearth the encoded features responsible for its performance on a downstream task is an important, but a less studied research area. (Ganesh et al., 2016)'s work is the first to open the blackbox of vector embeddings for tweets. They propose elementary property prediction tasks which predicts the accuracy to which a given tweet representation encodes the elementary property (like slang words, hashtags, mentions, etc). The main drawback of the work is that they fail to correlate their study with downstream applications. We believe performing such a correlation study can clearly highlight the set of elementary features behind the performance of a particular representation model over other for a given downstream task.

Conclusion
In this work we study the problem of learning unsupervised tweet representations. We believe our survey of the existing works based on the objective function can give vital perspectives to researchers and aid their understanding of the field. We also believe the future research directions studied in this work can help in breaking the barriers in building high quality, general purpose tweet representation models.


extfieldsofstudy:
Computer Science
Mathematics

text:
Alphabet-dependent Parallel Algorithm for Suffix Tree Construction for Pattern Searching

Suffix trees have recently become very successful data structures in handling large data sequences such as DNA or Protein sequences. Consequently parallel architectures have become ubiquitous. We present a novel alphabet-dependent parallel algorithm which attempts to take advantage of the perverseness of the multicore architecture. Microsatellites are important for their biological relevance hence our algorithm is based on time efficient construction for identification of such. We experimentally achieved up to 15x speedup over the sequential algorithm on different input sizes of biological sequences.

Introduction
There has been a technological breakthrough in the last decade, which saw a huge improvement in DNA sequencing technologies [1][2][3] and availability of multicore architectures in desktop computers [4][5].
The DNA sequences are very large and can span to 3 billion characters for the whole human genome. Such sizes have performance issues during analysis hence this attempt to improve the analysis by taking advantage of multicore architectures which has become ubiquitous. One alternate step in performance challenge is to take advantage of the multicore revolution. To do this, algorithms and data structures should be modified to make them well suited for the parallel architectures [4]. Most of these tools for analysis of genomes are sequential, memory intensive and therefore cannot easily scale to larger genomes [2]. One such data structure is the suffix tree. The suffix tree was first introduced by Weiner. A suffix tree of a string s represents all suffices of S. A suffix tree is a very useful data structure with many applications and many sequential algorithms for suffix tree construction have been proposed [6][7][8][9]. However all these suffer from high performance requirements such as in string processing algorithms which processes huge sequences like DNA or Protein sequences. Due to this challenge, there is need for new approaches to improve performance on this data structure [10,11]. A very strong property of a suffix tree is that, after preprocessing and construction, a pattern, p, can be found in a string, S, in O (|p|), furthermore in O (|p|+k) where k, is the number of occurrences of p.
Generally, when considering a parallel solution for suffix tree construction, the most difficult part, is on partitioning the tree [12]. In this paper we attempt to provide an Inmemory parallel suffix tree construction approach to improve the time requirements. We partition the tree basing on the alphabet of the string which yields independent construction. This paper proposes a novel alphabet-dependant parallel algorithm for suffix tree construction (kmer-based) involving assigning suffices to processors based on their initial character. The algorithm achieves a performance speedup of up to 15x over the sequential algorithm.
The remainder of the paper is organized as follows; we introduce the Preliminaries, that is, the foundation of the concepts used in the entire paper in Section 2. We provide brief related work in Section 3 and provide our parallel algorithm in section 4 and then experiments and analysis of results in Section 5. The paper is concluded with a conclusion section in Section 6 which discusses the summary and future work.

Preliminaries
Analysis of our algorithm is done using the Circuit Model of the Work Depth model, which uses Concurrent Read and Exclusive Write (CREW). In this model, the depth D is the number of time steps needed and work W is the number of operations needed. if P processors are available, using Brent's scheduling theorem [24] ,we can calculate the running time as O (T w /P + T d ) [14]. Then the speedup of the algorithm will be equal to O (T 1 /T ∞ ) where T 1 is equal to time under 1 processor and T ∞ time under multiple processors. Concurrent reading and exclusive writing is allowed in our model. This model can still be converted to PRAM model by using the Brent Theorem as stated earlier [13].
In order to show parallel execution, we will include three concurrency keywords, that is, spawn, sync and parfor as done in [13] The concurrency keywords indicates which parts of computation should be executed in parallel thus expressing logical parallelism, The spawn keyword represents that the procedure call that comes before it will be executed in parallel. The sync keyword shows that all spawned procedures must complete before going to the next instruction in the stream. Lastly, parfor which we will use, is a parallel for loop which is the same as the ordinary for loop in serial algorithms, except that the iterations can execute concurrently. We denote a sequence of length n by S = We also denote an alphabet by ∑ = {0,…,σ -1} [10], where σ is the alphabet size. We use |p| to represent, n is the length of the string S, σ is the size of the alphabet and ∑ is the set of the alphabet.
Although the programming community has adopted the random access model for serial algorithms, no single model for parallel algorithms has gained wide acceptance. This is the case since parallel computers can have shared memory model or distributed memory model hence vendors have not agreed on a single architectural model. However each new desktop and laptop is now a shared memory parallel computer and this trend appears to be going towards the shared memory multiprocessing. Although time will tell, in this paper we will also take such approach or route.
Let S = s 1 …s n be a string with some symbols of the alphabet ∑ . In this paper the suffix tree of string S, is a rooted tree with edges and nodes that are labeled with their indices thereby using constant space for each label. The suffix tree will satisfy the following properties: Property 1: 1. The root edges store the indices of different characters that starts with different symbols away from the root. 2. Every internal node has at least two children. 3. Each node is labeled by the index positions formed by combining edge labels from root to the node.
An example of a suffix tree for string S = {xabxac} with σ = 4, numbers on the leaves represent indexes of the suffices as shown in Figure. 1. At this this point the suffix tree is an implicit suffix tree, since a suffix can be a prefix of another suffix.

Figure 1. Implicit Suffix Tree of S
It is a standard practice to append the string with ‗$' as the terminal symbol so as to generate an explicit suffix tree, as shown in Figure.

Related work
In this section, we briefly survey the parallel algorithms for construction of suffix trees. Some work related to parallel processing of suffix trees has been done.There are basically two classes of suffix tree algorithms, that is, In-memory and Disk-based. In-memory can be used if both the string S and the suffix tree can fit in the main memory and these classes of algorithms suffer from poor locality reference. However the latter tries to address this problem by storing some parts of the string S or suffix tree on the disk memory.
The first O (n) sequential algorithm for suffix tree construction was done by Weiner [15]. The algorithm takes O (m log σ) time, where σ =|∑|, the number of characters of the alphabet. McCreight [9] improved this algorithm by giving it a more efficient construction within the same asymptotic bound [7].
Apostolico et. al. [16] proposed the first parallel algorithm for suffix tree construction. This parallel algorithm was based on doubling approach with a technique they called naming. Given a parameter value 0 < є ≤ 1, the algorithm runs in O ( ) time, O ( work and space using CRCW PRAM Model. On binary alphabet, this algorithm is not very space efficient since it has polynomial space complexity. Hariharan [17] later improved the parallel construction of suffix trees to linear space and time. The algorithm takes O (log 4 n) time and O (n) for work and space on CREW PRAM model. A further improvement was also done by Farach and Muthukrishnan to O (log n) time on randomized CRCW PRAM [29]. Very recently Satish et al. [2] proposed a parallel algorithm for suffix tree construction. Their parallel algorithm is based on the MapReduce programming model. Their approach vertically partitions the suffix tree and then constructs the subtrees independently in parallel by extending Ukkonnen's algorithm [6] as shown in Fig. 3.

Figure 3. Sub-tree for S-prefix T and sample suffix link in its context [2]
Currently there are only two parallel practical implementation of the suffix tree construction, that is, Wavefront [19] and ERA [20]. Hence this paper has emphasis on parallel implementation of the parallel algorithm. The Wavefront works by splitting the sequence into partitions of the resulting complete tree. The partitioning process is done by making use of variable length prefixes making sure that every partition starts with the same prefix thereby guaranteeing independence of each sub tree which can then later be merged. ERA also partitions the sequence into independent sub-trees which are then subdivided into partitions making it possible to process each partition in memory. Also most recently Comin and Ferrares [21] introduced their parallel suffix tree algorithm called Parallel Continuous Flow (PCF) which works by dividing a string into independent sub trees with a time complexity of O(log 2 (N/√P).These sub trees are further divided into partitions which then can be processed in memory and works as shown in Fig. 4:

Parallel Suffix Tree Construction
We now describe our parallel algorithm for suffix tree construction with the help of an example. Our algorithm adopts a Generalized Suffix Tree idea and constructs the suffix tree, branch by branch in parallel and each branch is a sub-tree which will later be merged to form the complete suffix tree. We make use of Example 1. to explain our idea.
Example 1: Given a string S = {aaabaca,…} the algorithm first extract the alphabet from S, ∑ = {a,b,c}, each processor processes all suffices starting with the same symbol of the alphabet and these are executed independently in parallel. For example, given the String S = {acgttacg…}, and we need to search for all repeats of size 4 then the first step is to extracts the alphabet ∑ = {a,c,g,t,…,λ}(where λ is the last symbol in the sequence) and generate the sets (P α where P is the set containing all the suffices starting the symbol α) by grouping all the suffices which start with same symbol of the alphabet with exact lengths of 4, that is, To create the suffix tree, we introduce a terminal symbol, $, (as stated in section 2), to the substrings hence suffices. We do so by following the following two rules which will guarantee an explicit suffix tree. And this leads us to the final phase.

No suffix of S is a prefix of a different suffix of S.
2. There is a leaf for each suffix of S. Our algorithm then construct the suffix tree branch wise independently for each set in parallel as shown in Fig. 5. The construction of branches is done in parallel however the construction of the generalized sub suffix tree for each branch is done sequentially. That is, the branches are computed sequentially in an ordinary generalized suffix tree fashion word by word but using the sliding window approach. Finally the algorithm merges these branches to a common root to come up with the complete suffix tree for the string S as shown in Fig. 6. The merging process is trivial since they all just need the common root to generate the complete suffix tree which can reduce the cost of expensive I/O.  Proof: Let S = abaabc, then ∑ ={a,b,c} and σ = 3 and the required pattern is of size 3 (|p|). Thus we assume that e ≠ 4 where e is the number of root edges of the suffix tree of S. So we then assume that, the suffix tree has e = 5. We want to prove that, e = σ + 1 given that σ = 3. We construct the suffix tree for S in Figure 7. S has the following set of k-mer substrings {aba, baa, aab, abc},by property 1(Section 2) which states that -The root edges stores the indices of different characters that starts with different symbols away from the root‖ To construct the suffix tree, we now introduce $ as our terminal symbol to maintain the definition of an implicit suffix tree where $ < ∑ and $ ∉ ∑. So finally we have {aba$, baa$ ,aab$, abc$, $} as our substrings. We show the suffix tree of S in Figure. 7.

Figure 7. Suffix Tree of {abaabc} with |p| =3
As shown in Fig. 7, e ≠ 5 as assumed earlier but rather e = 4, that is, e = σ + 1 if all the alphabet characters have been used. □ We present our parallel algorithm in Figure 7. as pseudo-code and provide follow-up description of our algorithm.

Figure 8: Parallel Algorithm for Suffix Tree construction
We now describe our suffix tree construction algorithm, expanding from example 1, which constructs all branches of the suffix tree in parallel. We refer to this algorithm as PaST. Since each branch needs only suffices starting with the same characters to do the construction, groups of sets of suffices are generated. We made use of the observation from Lemma 1 and Property 1.
We start by extracting all the suffices, that is, those with initial similar symbols and group them in their respective sets (lines 4 -6) and this extraction is done in parallel and independently since each processor is looking for its symbol in S. However there is access control on the shared string/sequence. The second phase starts with the independent construction of branches or sub-trees by taking each suffix to build the respective branches suffix by suffix in (lines 7 -8) which is similar the process of constructing a generalized suffix tree. Then finally the merging process is done sequentially to come up with a complete suffix tree (lines 9 -10).

Experiments & Analysis of Results
Implementation was done in Python. All parts of the algorithm were implemented. We utilized pythons' variant of Mark Carlson C++ code for similar analysis which depends on the Ukkonen O (n) time algorithm which is suffix tree based (ST-based) [22], [23].

A. Experimental setup
Implementation was done utilizing Python version 3.5.2 and Anaconda version 4.1.1 to our proposed algorithm. The experiments were run on a HP Z820 Workstation with a 3.30 GHz 16-core Intel Xeon E5-2623 chip which has 10 MB L3 Cache, and we applied parallelism on a shared-memory as in our algorithm. The computer runs Ubuntu 14.04LTS (64-bit) OS with 32 GB internal memory, swap space of 64 GB, and 1 TB Serial ATA Hard Disk Drive at 7,200 RPM. We made use of real genomic data of DNA and Protein sequences.
We measure the programs' execution time for the construction only. We use pythons' time method to measure the running time of the suffix tree construction process which is measured in seconds as shown in Table 1. and Table 2.   Table 1. shows the construction times measured in seconds to construct the complete suffix tree per k = 5,10 and 15. Text size column shows the input sizes in megabytes which varies from 5 upto 50 megabytes.  Table 2. depicts construction times for different biological datasets, that is, the full chromosomes and the whole human genome, however the ST-Based did not run to completion for all these datasets even after several days, which we eventually terminated, and this is also discussed in detail under observations section.

B. Analysis
We observed and recorded the running times of our algorithm versus the Suffix Treebased technique (ST-Based) [22]. The accompanying primary perceptions were noted from this test study: 1. Our algorithm shows improved performance in terms of execution time. The algorithm achieves a performance speedup of up to 15x over the sequential algorithm with better speedup in lower pattern size construction as opposed to bigger pattern size, that is, k = 5 versus k = 15 (Fig. 12) 2. When the text size becomes larger than 25MB our method shows a huge improvement in terms of time cost compared to the ST-based method. The STbased time cost increases as the text file exceeds 25MB. Both algorithms perform the same in terms of the running time when the text size if less than 25MB. This improvement can be attributed to parallelism since parallelism benefits are significant when the amount of processing increases.
3. We also observed that the ST-Based method construction does not complete when the text size exceeds 35MB which is possibly due to the high memory requirements of the ST-based method. Our method only requires to construct a tree of equal branch sizes of 5,10 or 15 meaning it has a small memory foot print compared to constructing the complete suffix tree of size n where n is the size of the string to be indexed. 4. We further noticed that, the construction time of the chromosomes and the whole human genome was impressive since the ST-based could not complete the construction even after several days. The whole human genome of repeat size 5 took approximately 3 and half hours to complete construction. (Table. 2).

Figure 12. Speedup relative to text size
Our algorithm can be useful in detection of small repeats such as microsatellites since they are of size 2 to 6 long. Microsatellites are important since they used as DNA markers for different biological functions [37]. These types of repeats allow you to specify size before detecting them prior to the analysis. The parallel programs ERA [20] and Wavefront [19] were not compared with our parallel program since these two parallel programs implements a complete construction of a suffix tree (and also not generalized suffix tree) whereas ours implements a parallel algorithm of k-mer based of a sequential algorithm for the generalized suffix tree. This means, to the best of our knowledge, this is the first parallel version of k-mer based approach on a generalized suffix tree.

Conclusion
In this paper we have introduced a novel approach to constructing a suffix tree in parallel. We have also shown that the suffix tree of a string can be constructed optimally in parallel provided the size of the pattern is known beforehand. And we have consequently shown that the construction time of our parallel method is better than that of the sequential version with a speedup of up to 15x. However the approach still suffers poor scalability due to the nature of parallelization method used, that is, alphabetdependant, which can be improved in future.


extfieldsofstudy:
Computer Science
Medicine

text:
Prognostics of Surgical Site Infections using Dynamic Health Data

Surgical Site Infection (SSI) is a national priority in healthcare research. Much research attention has been attracted to develop better SSI risk prediction models. However, most of the existing SSI risk prediction models are built on static risk factors such as comorbidities and operative factors. In this paper, we investigate the use of the dynamic wound data for SSI risk prediction. There have been emerging mobile health (mHealth) tools that can closely monitor the patients and generate continuous measurements of many wound-related variables and other evolving clinical variables. Since existing prediction models of SSI have quite limited capacity to utilize the evolving clinical data, we develop the corresponding solution to equip these mHealth tools with decision-making capabilities for SSI prediction with a seamless assembly of several machine learning models to tackle the analytic challenges arising from the spatial-temporal data. The basic idea is to exploit the low-rank property of the spatial-temporal data via the bilinear formulation, and further enhance it with automatic missing data imputation by the matrix completion technique. We derive efficient optimization algorithms to implement these models and demonstrate the superior performances of our new predictive model on a real-world dataset of SSI, compared to a range of state-of-the-art methods.

Introduction
Surgical Site Infection (SSI) is a national priority in healthcare research [1,2,3]. It occurs in 3-5% of all surgical patients, and up to 33% of patients undergoing abdominal surgery [4,5]. More than 500,000 cases are estimated to occur in the US annually, resulting in additional costs of up to $20,000 per infection. It also results in worse health outcomes for patients, such as prolonged length of hospital stay, increased mortality, and compromised health-related quality of life [6,7,8]. SSI is overall the most costly healthcare-associated infection, yet many of its associated costs are non-reimbursable. Surveillance methods have been invented since the early 1980s to provide appropriate data (such as risk indicators, clinical prediction rules) to surgeons to monitor how changes in practice can impact SSI occurrence [9,10,11]. Many of these surveillance systems follow the standard guidelines established in 1992 by the American Centers for Disease Control and Prevention (CDC)'s National Nosocomial Figure 1: An illustration of the dynamic data from a subject as a spatial-temporal data matrix Infections Surveillance (NNIS) system, and rely on volunteer surgical wards from public or private hospitals that routinely collect nosocomial infection data. Although these surveillance systems are continuously updated with successive risk indicators being included, they are mainly based on individual or very few risk factors. Furthermore, the quality of post-discharge data is poor, as active surveillance is costly and rarely performed prospectively, relying on retrospective review of clinical documentation. Recently, with the rapid advances of sensing and information technologies, new tools have been developed to provide patients the means to monitor their conditions and share this data with their providers. One example is the mobile health (mHealth) tool that we have developed to enable patient-initiated monitoring of surgical wounds and improve patient-provider communication after hospital discharge. Self-reported symptoms of pain, body temperature, and wound features, as well as patientor caregiver-generated images of the wound may be acquired to assess the evolving condition of the wound and the likelihood of SSI. While these emerging mHealth tools have provided unprecedented capacity to closely monitor patients for signs and symptoms of SSI and measure the evolution of the woundrelated variables and other clinical factors, existing prognostic models of SSI have not been able to take advantage of this rich and accumulating information for SSI prediction. Prognostic models of SSI ( [12,13,14,15,16]) in the literature have three main limitations. First, many of these models were based on medical knowledge or heuristics, not data-driven by nature. Thus, their utility is limited on some specific phenotypes or particular time windows of the SSI progression process. Second, these models only predict whether or not the patient will develop SSI, but do not predict when. Third, most existing models only incorporate static variables known as of the end of the operation, e.g., demographics, pre-operative laboratory results, comorbidities, and operative factors. These models do not incorporate the continuous observations of the patients and their wound.
To overcome the limitations of existing SSI prediction models, especially when utilizing the dynamic data collected by mHealth tools (e.g., an illustration of such dynamic data as a spatial-temporal data matrix is shown in Figure 1), we develop a solution that is specifically designed to address the unique analytic challenges from dynamic mHealth data. The collected dynamic data includes continuous measurements on a range of wound variables and clinical factors, for which we form a spatial-temporal data matrix for each individual ( Figure 1). Rather than predicting the development of SSI based on a snapshot of these factors or the static variables known as of the end of the surgical operation, we propose a learning formulation to predict the time to the development of SSI directly based on these spatial-temporal matrices. In our experience with real-world applications, one common data challenge is that there are many patients who do not develop SSI during observational period (in this paper we name them as "censored samples"). What is worse is that, the number of censored samples is usually greater than the number of samples that have observed outcomes (in this paper we name them as "complete samples"). Thus, a learning formulation that can fuse both types of samples is needed. Another data challenge is, as a well-known phenomenon in many healthcare applications, we encounter many missing values that result in a challenge for the learning formulation. We therefore propose a matrix completion approach to overcome this challenge and derive a convex optimization formulation to solve it. Further, with the spatial-temporal matrix representation for the dynamic mHealth data as the input of the prediction model, we investigate the use of a bilinear formalism to reduce the dimensionality of the prediction model. Our main contributions include: • Developed a flexible learning formulation that can convert the dynamic clinical signals of an individual (represented as the "spatial-temporal matrix") into accurate prognostics of SSI onset, even when some data have censored outcome; • Proposed the use of matrix completion to mitigate the missing data problem that has been found ubiquitous in many healthcare applications; • Developed efficient algorithms to implement the machine learning models; specific optimization strategies were developed to ensure the feasibility and robustness of the algorithms; • Conducted extensive numerical studies on a real-world dataset (that includes 860 patients observed in a time window ranging from 2 to 21 days while 167 developed SSI), which generated real-world experience and empirical evidence for using the proposed method with dynamic mHealth data.
The remainder of the paper is organized as follows: In Section 2, a brief review of related work will be provided. In Section 3, our method will be presented with detailed explanations of the formulation, together with the computational algorithm for solving the proposed formulation. The real-world implementation of this method will be presented and discussed in Section 4. Conclusions will be drawn in Section 5.

Related Work
Our work is closely related to the following two areas: prediction models of SSI risk and machine learning methods that are related to the analysis of spatial-temporal data.
Risk prediction models of SSI: Many current risk prediction models for SSI are built upon expert opinions. For instance, the Ventral Hernia Working Group (VHWG) has categorized patients into 4 grades: low risk, comorbid, potentially contaminated, and infected. A grading system has thereafter been developed to predict the risk of SSI, based on expert opinions but not directly on patient data. This model has later been modified by researchers, including the 3-tier system developed in [17], which are still knowledge-driven rather than being data-driven. On the other hand, many data-driven risk scores for SSI have been developed over the years, such as the ones in [12,13,14,15,16]. Among these models, the National Nosocomial Infection Surveillance (NNIS) Risk Index is a well-accepted risk-assessment tool, but it only includes three predictors. Thus, it has limited capacity to utilize the much more information that we could collect nowadays for SSI prediction. For more complex models, such as the model developed in [12], a hierarchical multivariate logistic regression model was used to discriminate SSI from non-SSI patients based on risk factors such as some operative variables, preoperative clinical severity, risk factors, comorbidities, and other variables related to the hospitalization procedure. However, these existing models build on the static measurements of some selected risk factors rather than the dynamic post-operative symptom and wound observations. Recently, [3] investigated the use of the data of "last five days" (defined as the last 5 days prior to SSI onset for SSI patients or the last 5 days for non-SSI patients) for predicting SSI onset, which showed better performance than using only crosssectional measurements. Comparing with [3], our study focuses more on the methodological issues of how to mitigate the statistical challenges in order to automate the process of using the incomplete dynamic data to build and select the best prediction model. More related works that could be applied on a range of disease contexts can be found in [18], which has covered a wide range of prognostic models.
Machine learning methods: Matrix completion [19,20,21,22,23] is an important approach to estimate missing elements in a data matrix, without making strong assumptions on data missing mechanisms. The authors in [19] proved that the low-rank matrix completion technique only needs O(mr log 2 m) to exactly recover the missing values for a m × n matrix with rank r, assuming m ≥ n. A related formalism that can be used for building prediction models using spatial-temporal data could be the bilinear models. The bilinear model is a popular approach to capture information in two different dimensions, for example in text mining [24], computer vision [25], and image processing [26]. A specific example is, for classification using brain image data or EEG signals, the input data for classification are represented as matrices with columns representing space indices and rows representing time indices. It is always possible to apply linear models by creating data vectors as stacking of the elements of the data matrix; however, such stacking approaches can not exploit the spatial and temporal structure in the data matrix and will inevitably lead to a high-dimensional weight vector in the linear model. Thus, we adopt the bilinear formulation to better exploit the data matrix structure to obtain a more parsimonious representation of the weight vector. For instance, Singular Value Decomposition (SVD) is a typical bilinear model that identifies representative vectors (characterized as eigenvectors) in both dimensions to span the data space. A general framework was presented in [24] for solving two-factor tasks using bilinear models, which can characterize factor interactions and employ efficient algorithms based on the singular value decomposition and expectation-maximization. Although not directly applicable here, existing matrix completion formulations and bilinear models provide a great resource for us to develop a systematic data analytic pipeline by building on these models and tackle the data challenges with the dynamic mHealth data for SSI prediction.

An Overview of the Proposed Machine Learning System
The overall goal of the proposed machine learning system is to predict the time to SSI onset using the spatial-temporal matrix data. There are several major data challenges that need to be overcome, such as the fusion of both complete samples and censored samples, missing values in the spatial-temporal matrices, and the complex two-way interaction structure of the spatial-temporal matrices.
To mitigate these challenges, Figure 2 illustrates an overall scheme of the proposed machine learning system. It consists of a novel modeling formulation to fuse both complete samples and censored samples, in which bounded matrix completion is used to mitigate the missing data problem. The learning formulation is further equipped with model regularization techniques such as the bilinear formalism and sparse learning to mitigate the challenges from the high dimensionality of the spatial-temporal matrix and to exploit its inherent spatial and temporal structure. In the following subsections, each of the main machine learning algorithms will be described in details.

Learning Formulation for Data Fusion
Denote the i-th spatial-temporal data sample in the training data as x i ∈ R T ×P , where T denotes the length of observations and P denotes the number of dynamic variables (such as those wound-related variables) that are collected. Note that here, the optimal length of observations T is not a known parameter. Rather, it should be decided using data-driven methods, which will be discussed in Section 4. As we have mentioned, our training data consists of both complete samples and censored samples. We use Ω to denote the index set of complete samples, and useΩ to denote the index set of censored samples. Missing data is referred to the missing elements in the matrix x i . Further, we use y i to denote the time to develop SSI for sample i if this sample is in Ω, or the duration of observations if the sample i is inΩ. For example, suppose that the sample i is the subject i's day 1 through day 5's measurements. If the subject i developed SSI on day 7, which means i ∈ Ω, y i = 7 − 5 = 2. Otherwise, if the subject i did not develop SSI in the observational period of 21 days (i / ∈ Ω), y i = 21−5 = 16. Then, the following learning formulation is proposed to learn the prediction model based on both the complete and censored samples, under the assumption that there is no missing data in x i and the prediction model is linear: (1) Here, x i , w denotes the the sum of entry-wise products of two matrices. Note that, the formulation consists of two components in the objective function. The first component, is the least-square loss function that penalizes the difference between the predicted values, i.e., x i , w + b, with the real outcome data, i.e., y i , from the complete samples. This is the same with classic linear regression models. The second component evaluates the squared hinge loss [27], which corresponds to the loss function for the censored samples. The rationale for the use of the squared hinge loss is that, if the predicted time to SSI onset is larger than the censored time y i , we should not penalize the model; otherwise, we penalize the model. In this way, the censored samples can contribute to the learning of the prediction model in an unbiased way. To balance the contributions of these two types of samples, we further use a parameter, λ, in the formulation, i.e., larger λ will allow the censored samples to give more influence on the model estimation. In practice, this parameter can be selected by model selection methods such as cross-validation to enable data-driven optimal model selection.

Bilinear Formulation for Spatial-Temporal Matrix
Note that the model proposed above imposes no structure on the model parameters w, ignoring the fact that the input data is a spatial-temporal matrix that has an inherent correlation structure in both dimensions. Here, we propose to adopt a bilinear formulation to capture the correlation structure within the spatial-temporal matrix. This is inspired by the success of the bilinear models in a range of applications such as [24,26]. Specifically, here, by using the bilinear formulation, the prediction model can be rewritten as where u ∈ R T ×R and v ∈ R P ×R with u r and v r denoting their corresponding rth column. Actually, the bilinear formulation can be interpreted from another point of view for dimension reduction by noting that In other words, to learn the bilinear prediction model characterized by u ∈ R T ×R and v ∈ R P ×R , it is equivalent to learn the optimal solution of w if we restrict w's rank by R in the formulation (1). This leads to the following transformed learning formulation: Hence, besides the bilinear formalism, we note that this formulation can also be interpreted as a rank-regularized formulation. The low-rank constraint of w is a reasonable treatment here, since due to the potential spatial correlations (i.e., correlations between the variables) and temporal correlations (correlations between the time points), the spatial-temporal data inherently lie on a low-dimensional manifold. Therefore, w has the corresponding low rank. Thus, the bilinear formulation induces the rank-regularized formulation of w.

Preconditioning Reformulation and Optimization
To solve the formulation in (3), first, we rewrite the formulation by vectorizing w and each spatial-temporal data x i . Particularly, we concatenate the rows of the matrix to convert the matrix to be a vector. Similarly, to generate the corresponding design matrices X Ω and XΩ for the complete samples and censored samples respectively, a column vector can be constructed by concatenating the rows of a spatial-temporal matrix x i . A graphical illustration of this concatenation process will be presented in Figure 3. Also, y · denotes the corresponding vector of outcomes or censored outcomes. Then, we can rewrite (3) as the following vectorized form: where 1 denotes the vector whose entries are all one. The objective function in (4) is convex, and the projection onto the rank constraint has a closed form. It is tempting to apply the projected gradient descent (PGD) approach ( [28]) to solve this convex formulation. However, it would be inefficient if one directly applies PGD. The reason is that, due to the large spatial and temporal correlations in the spatial-temporal matrix, the optimization problem could be ill conditioned (recall the way by which we generated the matrix X Ω and XΩ). Thus, we propose the following preconditioning reformulation to enable the application of the PGD on solving for (4). Let vec(ŵ) = (X Ω X ⊤ Ω ) 1 2 vec(w). We can substitute vec(w) by vec(ŵ) in the objective function in (4). The challenging issue is how to substitute vec(w) by vec(ŵ) in the rank constraint. In fact, Lemma 1 indicates that rank(ŵ) = rank(w) as long as (X Ω X ⊤ Ω ) 1 2 is invertible, i.e., in other words, as long as X Ω has full column rank. Lemma 1. For any matrix w, its rank remains the same after the vectorization and a full ranked linear transformation, that is, rank(ŵ) = rank(w), where A is any full rank square matrix and vec(ŵ) = A · vec(w).
Proof. We first prove that range(ŵ) ⊂ range(w). Note that the range of a matrix is defined as the span (set of all possible linear combinations) of its column vectors. It is easy to see that any column ofŵ is the linear combination of all columns in w. So the range (or column) space ofŵ is a subspace of the range (or column) space of w. Next, we show range(w) ⊂ range(ŵ).
Since A is invertible, we can write vec(w) = A −1 · vec(ŵ). For the same reason above, the range space of matrix w is the subset of the range space of matrixŵ. Then, we can complete the proof by combining both conclusions.
Then, ignoring the constant terms, we can finalize the preconditioning reformation as follows: Now we can apply PGD to solve (5). As summarized in Algorithm 1, first, we run gradient descent with a fixed step size η on the smooth part (objective function); and then, solve the proximal mapping (projection) with Singular Value Decomposition (SVD) and recover w by vec(w) = (X Ω X ⊤ Ω ) − 1 2 vec(ŵ). Note that, in Algorithm 1, the criterion of convergence is met when the decrease rate of the objective function value is less than 0.0001 in an iteration.

Algorithm 1 Projected Gradient Descent
Require: X Ω , XΩ, λ, r and η Return: One remaining issue in the implementation of the PGD approach is the selection of the step size η. It can be chosen as a sufficiently small value, or the AMIGO rule [29] can be adopted to dynamically decide the value of η. No matter which approach is used, it has been shown in [28] that the key issue is to ensure that the objective function is decreasing iteratively, which is not a difficult task empirically.

Bounded Matrix Completion (BMC)
In this section, we will develop a matrix completion approach to mitigate the missing data issue in our problem. Missing data has been ubiquitous in many healthcare applications. We found no exception in our study, since the data is collected by patients and for many reasons the patient compliance in data collection has always been a challenge. We propose to use the matrix completion approach to fill in the missing values, rather than using simple heuristic approaches such as using mean values to replace the missing values. Our rationale is, again, the correlations in the spatial-temporal matrix essentially imply that the spatial-temporal matrix is low dimensional. For instance, some variables that are used to measure the wound could be correlated, such as the color and temperature of the wound. Due to this reason, by using their correlations, we could recover many missing values as long as we have observed some values in the matrix. To exploit this idea, we assume that there exist a few basis vectors that span the daily observation vector of each individual (i.e., in the same spirit of many dimensionality reduction methods). Let T n,t denote the t-th day observation vector of the n-th individual. We assume that T n,t can be represented as a linear combination of the basis vectors {U 1 , U 2 , · · · , U r }: Given observed measurements in T n,t , the optimal weights {α 1 , α 2 , · · · , α r } can be obtained by minimizing the difference between the corresponding elements in r i=1 α i U i with the observed measurements in T n,t . In other words, we seek to identify the optimal weights that can best match the projected vector r i=1 α i U i with the observed incomplete vector T n,t . This rationale leads to the following formulation: where M encodes the information of {U 1 , U 2 , · · · , U r } and Φ denotes the set of the missing values. Note that, in this bounded low-rank matrix completion problem, we further restrict the missing elements to be within a certain range [l j , u j ] for the corresponding variable j. This is to ensure that the missing values won't be filled in with unreasonable values. Actually, the lower bound and the upper bound can be decided based on the observed data to ensure the clinical validity of the estimated values: Note that these bounds are obtained from the observed data in Φ c , the complement of Φ.
To solve the BMC problem, we apply the coordinate descent algorithm that iteratively solves the optimization by alternately updating X Φ or M while fixing the other one. Since the value of the objective function decreases iteratively, this algorithm is guaranteed to converge. It is worthy of mentioning that, there is a closed-form solution in each step to solve for M or X Φ . We summarize the BMC algorithm in Algorithm 2.

Missing Value Estimation for the Testing Data
As shown in the previous section, the BMC formulation is used to fill in the missing values in the training data. The rationale is to learn a few basis vectors U i 's, and then, for each incomplete observation vector T n,t , the algorithm seeks to identify the optimal weights that can best match the projected vector r i=1 α i U i with T n,t , where U = [U 1 , U 2 , . . . , U r ] is obtained by applying SVD to the learned low-rank imputation matrix: M = UΣV ⊤ . Then, the missing values in T n,t can be filled in by the corresponding elements in r i=1 α i U i . Thus, it is straightforward to use the results from the BMC formulation learned from the training

Algorithm 2 Bounded Matrix Completion (BMC)
Require: X Φ c , r, l j and u j Return: data to fill in the missing values in the testing data as well. Denote the coming testing data as z. For the new testing data z, its missing elements indexed by S can be estimated by solving the following convex optimization problem: Then, the best estimation can be found by updating z S and α iteratively by following the formulas shown below: Note that, many of the existing missing data imputation methods have been built on different assumptions of the mechanism of why data is missing, such as the Missing Completely At Random (MCAR) and the Missing At Random (MAR). While this may lead to more tailored missing data imputation methods, here, we have difficult in identifying and validating the missing data mechanism in our study. Hence, we pursue this low-rank model that places less strict assumptions on the missing data mechanism, which leads to the development of the low rank based estimation methods. Also, the low rank based estimation method can be applied to scenarios where a large portion of elements (e.g., 50% elements) are missing.

Study population
A prospective cohort study of 1,000 open abdominal surgery patients was conducted at a 1200-bed academic teaching hospital in the Netherlands, described previously [30]. Patients who didn't undergo surgery (n=33) or with < 2 days of wound observations (n=107) were excluded from analysis, leaving 860 patients in total. Subjects were prospectively assessed for CDC-defined superficial, deep and/or organ space infections [9]. Superficial SSI are infections that occur within 30 days after the operation and involve only skin or subcutaneous tissues of the incision and at least one of the following: 1) purulent drainage from the incision, with or without confirmation by laboratory tests; 2) organisms isolated from an aseptically obtained culture or aspiration of the incision; 3) at least one of the following signs or symptoms: pain or tenderness, localized swelling, redness, or heat and superficial incision opened by the surgeon;   Table 1 for both SSI and non-SSI patients, where the p-value is computed by the t-test for comparing the two groups.

Data collection
Subjects in the dataset were examined daily, using a previously described protocol [31], from post-operative day 2 until discharge or 21 days, whichever was earlier. Follow-up was performed at 30 days through clinic visit, phone, or letter to ascertain post-discharge infections. Table 3 shows the dynamic wound data that was collected, including definitions of categorical wound score variables [31]. For analysis purposes, we defined the SSI group as having any of the 3 types of SSI due to the small numbers of deep and organ-space infections. In addition, though a patient may have developed multiple types of SSI during the observation period, we only include their first infection in this analysis. The non-SSI group was defined as having not developed any kind of infection, but may have had a post-discharge infection. For patients who didn't develop SSI during the observational period, their days of observation are 21. For patients who developed SSI during the observational period, the summary statistics of their observational time is shown in Table 2.
Minimum 1st Quantile Median Mean 3rd Quantile Maximum 3 5 7 8.244 11 21 Table 2: Days of post-operative observation for patients developing in-hospital SSI Further, Figure 3 schematically illustrates the process by which we translated the original data into the data structure that will be used by the proposed machine learning system. The basic idea is to use a sliding window to segment each individual's time series measurements into blocks of equal size T .

Parameter tuning and validation
Cross validation is adopted to tune the parameters in each model that we will build in this study. Specifically, we randomly split the samples into multiple sets with equal size. In our implementation, we take a training-testing ratio of 4:1. Then we choose 4 sets as the training data, and the one left as the testing data. For each proposed model, we repeat the training-testing procedure 5 times, to ensure that every set is used as the testing data once. We use the mean absolute prediction error (MAE), i.e., i∈Ω |Ω| −1 | x i , w + b − y i |, to evaluate the prediction performance of each model in predicting the onset time of the individuals.

Comparison with other models
We will compare our proposed learning system with closely related benchmark approaches. The first one is the classic regression model [32] that assumes linear and additive predictive effects of the predictors on a continuous outcome variable. It has been used in many risk prediction models in a wide range of applications. The second one is the Support Vector Regression (SVR) model [33]. It is a more robust model than the classic regression model by using a soft margin loss function, representing the state-of-the-art performance. The performance comparison of these models are shown in Figures 4 and 5. Note that, Figure 4 is to compare the methods under different values of λ which essentially reflects the weight of the censored samples in the learning formulation. Since we have an unbalanced dataset, using weights to balance the contribution of both the complete and censored samples has been a common approach in the use of the existing methods. From both Figures 4 and 5, it can be observed that our methods perform significantly better than both benchmark methods across all the comparisons. Also, it seems that with rank = 2, our method performs better than its companion that has rank = 3, indicating that for this dataset, rank = 3 might result in overfitting. Note that, in generating this result, we didn't include the selection of the rank into the cross-validation procedure. For a given rank, we adopted cross-validation to select for the remaining parameters. Actually, later in Section 4.6, we will show that the "full-scale" cross-validation study that includes the selection of the rank actually selected rank = 2 as the optimal model, which indicates that the cross-validation can help control the model complexity and reduce the risk of over-fitting.

Evaluation of the matrix completion method for missing data imputation
We further evaluate the performance of the matrix completion method for missing data imputation in comparison with other methods. For example, for the "column mean" method, to fill in the missing value on feature j of individual i at a certain time point, the mean value of feature j of all the individuals across all the time points can be used based on the observed measurements. Other methods we used for comparison include the K-Nearest-Neighbor (KNN) method that has been widely used for missing data imputation [34,35] and a recent Bayesian approach [36]. We train the models using different missing data imputation methods under different values of λ and report the results as shown in Figure 6. It clearly shows that our low-rank matrix completion method could lead to superior performance on missing data imputation, providing better prediction performance of the model.

Optimal configuration of the proposed learning system
To identify the optimal configuration of the proposed learning system, we build a sequence of models to investigate the performances of different configurations. Critical parameters include the duration of the dynamic data we could use for building the prediction model, the rank of the model parameters w, and the value of λ. Among these parameters, probably the duration of the dynamic data is the most important parameter. Apparently, there is a trade-off between accuracy and cost. With longer duration, more information could be accumulated which will lead to better prediction accuracy. On the other hand, it will result in higher cost, not only in data collection, but also in the healthcare cost due to the potential delay of identifying the patients who will develop SSI soon. Therefore, it is a practical and important decision to find a reasonable length for observation and prediction. Here, based on the cross validation with the training set ratio set to be 4:1, the prediction performances of the models are shown in Table 4. This demonstrates that the best model could be built if the duration of the dynamic wound data is 5-days and the rank of w is 2. A worse performance was generated when the length of observation is 6. This is probably because that the sample size for training the model drops significantly when the length of observation increases. In Figure 7, we also present the important variables of the best model in Table 4 with their coefficients in decreasing order. We further show the distribution of the predicted onset day for both the complete and censored populations using our best model in Figure 8, and demonstrate that our model can effectively separate the two groups.

Conclusions
Accurate determination of the SSI risk of a particular patient is essential for deciding whether or not particular preventive strategies, i.e., enhanced prophylactic antibiotics, decolonization, or other emerging interventions should be adopted. Furthermore, uncovering developing SSI at the earliest possible time affords the opportunity for anticipatory intervention, preventing progression of infection and its morbid sequelae. It also holds great potential to reduce the healthcare cost since delayed diagnosis of post-discharge SSIs has significant financial and life quality costs, with more than half of patients who develop post-discharge SSI readmitted to the hospital [37]. In this paper, we investigated the problem of predicting  Table 4: Prediction performance of different model configurations Figure 8: Distribution of the predicted onset day for both the complete and censored samples the time to the onset of SSI using the dynamic wound data collected on individuals. The dynamic data of an individual, represented as the spatial-temporal matrix, include the continuous measurements of many wound-related variables. Many of the wound variables are applicable in a post-discharge setting, allowing monitoring of these wounds using automated image analysis to predict infections in real time. Thus, this study aligns well with the emerging mHealth tools that are developed to closely monitor SSI patients. While most existing SSI prediction models only use preoperative and operative variables, [12,13,14,15,16], to the best of our knowledge, we are the first team who developed a systematic treatment to utilize the dynamic wound data of an individual for SSI risk prediction. This study used a unique dataset, coming from a hospital in the Netherlands, which had a significantly longer average length of stay than in the US, allowing us to characterize a longer spectrum of the SSI progression process.
Our study is subject to limitations. First, we have only investigated the use of the dynamic wound data for SSI risk prediction. However, it has been found that many preoperative and operative variables are important in predicting the SSI risk. Knowledge of the potential impact of these predictors may help guide physicians with both preoperative and operative decision-makings, and help develop personalized post-discharge care plans and interventions as well. For instance, previous studies have demonstrated that poor nutrition is associated with increased rates of SSI, probably due to a depressed immune system [38]. Thus, these physiologically impaired patients might benefit from timely and appropriate nutritional support. It has also been found that smokers have higher SSI risk than non-smokers, probably due to the altered perfusion mechanics at the surgical site. There are many other preoperative and operative factors such as age, surgery type, operative time, glucose, length of stay [39,38], that could significantly increase our capability to predict the SSI risk if being combined with the dynamic wound data. Second, SSI was classified into 3 categories based on the depth of infection [9], which include superficial, deep, and organ space SSI. It might be possible that different kinds of SSI would have different risk profiles. Third, many variables that have been found predictive of SSI risk in the literature are not collected in our dataset. For instance, specifics of the operative procedure, such as timing of antibiotics, core body temperature, blood glucose level, are not currently available. On the other hand, we have not included the image-based wound variables, which theoretically can be extracted from the wound images that have been available in the dataset, into our prediction model. The challenge to extract those image-based wound variables from the wound image data includes the enormous variations in the parameters regarding how the images are acquired by the individual patients, i.e., with different angles and different light conditions, etc. Thus, this is also one of our future research directions to extract these image-based wound variables and incorporate them into our prediction model. Finally, although our dataset has longer observation duration than many other datasets studied in the literature, it is still a short period of time considering that the typical follow up period for SSI is thirty days after discharge. This interval of observation is more administratively derived than biologically derived, as SSI could potientilaly occur at longer periods after the surgical event itself.
In summary, in this study, we have developed a systematic treatment of the data challenges associated with the dynamic wound data. The model can predict not only yes-or-no, but also when the SSI will be developed. In addition, this model has potential use in real-time mHealth monitoring systems that can incorporate patient-reported outcomes and automate image analysis to predict post-discharge SSI. In our future research, we will investigate how to integrate the dynamic wound data with some static risk factors such as some preoperative and operative factors to further improve the SSI risk prediction. We will also develop robust image feature extraction method to extract SSI-related features from the wound image data that is available in our dataset. Also, it is of interest to investigate the course of SSI development and evolution for different types of SSI and surgery procedures. We notice that previous works such as [40] raised an interesting question from a conceptual point of view, which is, whether one could generate meaningful features or episodes from variables over time. It is a very interesting question to derive such features or patterns to better understand the characteristics of the underlying health condition. While the pathogenesis and natural history of SSI has been largely unknown, a reasonable assumption is that there is a progression process of SSI that leaves a trail of clinical patterns/features. Through this study, we demonstrate that using dynamic data could improve SSI prediction. It will be our future work to thoroughly study the dynamics of the clinical signals and its connection/implication of the underlying disease progression process. Last but not least, note that we assumed the prediction model is linear. Despite the appearance as a linear model, proper transformations could be applied to extend the proposed linear model for characterizing potential nonlinearity. On the other hand, if the transformation is needed, we do need to base the linear models on interpretable and meaningful variable transformation. Besides the methodological issues for data fusion and predictive modeling, how to integrate the monitoring tool in real surgical settings is definitely a very important problem. We have studied some important aspects of this problem in our previous work [41]. Usability research is also part of our future research directions, e.g., in [41] we only focused on a unique post-acute surgical use case that may not perfectly generalize to medical or chronic care settings.