Khadim Dramé
email: khadim.drame@u-bordeaux.fr

Fleur Mougin
email: fleur.mougin@u-bordeaux.fr

Gayo Diallo
email: gayo.diallo@u-bordeaux.fr

Keywords: Biomedical text classification, semantic indexing, multi-label classification, k-nearest neighbours, explicit semantic analysis, information extraction, machine learning

Background

With the large and increasing volume of textual data, automated methods for identifying significant topics to classify textual documents have received a growing interest. While many efforts have been made in this direction, it still remains a real challenge. Moreover, the issue is even more complexasfull textsare not always freely available. Then, using only partial information to annotatethese documentsis promising but remains a very ambitious issue.

Methods

We propose two classification methods: a k-nearest neighbours (kNN)-based approach and an explicit semantic analysis (ESA)-based approach.Although the kNNbased approach is widely used in text classification, it needs to be improved to perform well in this specific classification problem which deals with partial information. Compared to existing kNN-based methods, our method uses classical Machine Learning (ML) algorithms for ranking the labels. Additional features are also investigated in order to improve the classifiers' performance. In addition, the combination of several learning algorithmswithvarious techniques for fixing the number of relevant topics is performed. On the other hand, ESA seems promising for this classification task as it yielded interesting results in related issues, suchas semantic relatedness computation between texts and text classification. Unlike existing works, which use ESA for enriching the bag-of-words approach with additional knowledge-basedfeatures, ourESA-based method builds astandalone classifier. Furthermore, we investigate if the results of this method could be useful as a complementary feature of our kNN-based approach.

Results

Experimental evaluations performed on large standard annotated datasets, provided by the BioASQ organizers, show that the kNN-based method with the Random Forest learning algorithm achieves good performances compared with the current state-ofthe-art methods, reaching a competitive f-measure of 0.55% while the ESA-based approach surprisingly yielded reserved results.

Conclusions

We have proposed simple classification methods suitable to annotatetextual documents using only partial information. They are therefore adequate for large multilabel classification and particularly in the biomedical domain. Thus, our work contributes to the extraction of relevant information from unstructured documents in order to facilitate their automated processing. Consequently, it could be used for various purposes, including document indexing, information retrieval, etc.

Introduction

The amount of textual data is rapidly growing with an abundant production of digital documents, particularly in the biomedical domain (biomedical scientific articles, medical reports, patient discharge summaries, etc.). Furthermore, thesedataare generally expressed in an unstructured form (i.e., in natural language), which makes its automated processing increasingly difficult. Thus, an efficient access to useful information is challenging. To do so, a suitable representation of textual documents is crucial. Controlled and structured vocabularies, such as the Medical Subject Heading (MeSH®) thesaurus, are widely used to index biomedical texts [START_REF] Trieschnigg | MeSH Up: effective MeSH text classification for improved document retrieval[END_REF] and consequently to facilitate access to useful information [START_REF] Díaz-Galiano | Query expansion with a medical ontology to improve a multimodal information retrieval system[END_REF] [START_REF] Crespo Azcárate | Improving image retrieval effectiveness via query expansion using MeSH hierarchical structure[END_REF]. As regards conceptual indexing, concepts defined in thesauri or ontologies are often used to annotate documents. For example, the MEDLINE® citations are manually indexed by the National Library of Medicine® (NLM) indexers using the MeSH descriptors. Although the task of annotators is now facilitated by a semi-automatic method [START_REF] Aronson | The NLM Indexing Initiative's Medical Text Indexer[END_REF], the rapid growth of biomedical literature makes manual-based indexing approaches complex, timeconsuming and error-prone [START_REF] Huang | Recommending MeSH terms for annotating biomedical articles[END_REF]. Thus, fully automated indexing approaches seem to be essential. While many efforts have been made to this end, indexing full biomedical texts according to specific segments of these texts, such as their title and abstract, remains a real challenge [START_REF] Tsatsaronis | BioASQ: A Challenge on Large-Scale Biomedical Semantic Indexing and Question Answering[END_REF].Furthermore, with the large amounts of data, using only partial information to annotate documents is promising(reduction of computational cost).

In this paper, we propose two classification methods for discovering and selecting relevant topics of new (unannotated)documents: a) a kNN-based approach and b) an ESA-based approach. Our main contribution is to be able to suggest relevant topics to any new document based solely on portion of it thanks to a classification model learnt from a large collection containing several hundreds of thousands of previouslyannotated documents.

Text classification is the process of assigning labels (categories) to unseen documents.

The principle of the kNN-based approach is to consider the set of topics (MeSH descriptors, in this case) assigned manually to the k most similar documents of the target document. Then, these topics are ordered by their relevance score so that the most relevant ones are used to classify the document. In a previous work [START_REF] Huang | Recommending MeSH terms for annotating biomedical articles[END_REF], authors noted that over 85% of MeSH descriptors relevant for classifying a given document are contained in its 20 nearest neighbours. This appearsto better represent the documents rather than what can be found in their title and abstract solely.

First, we have developed a method based on the vector space model (VSM) [START_REF] Salton | A Vector Space Model for Automatic Indexing[END_REF] to determine similar documents. The latter uses the TF.IDF (term frequencyinverse document frequency) weighting scheme for representing documents by vectors constituted by unigrams they contain and the cosine measure for retrieving the document neighbours. Then, we have investigated different types of features and several ML algorithms for selecting relevant topics in order to classify a given document.

On the other hand, ESA [START_REF] Gabrilovich | Computing Semantic Relatedness Using Wikipedia-based Explicit Semantic Analysis[END_REF]has yielded good results in related issues such as semantic relatedness computation between texts [START_REF] Gabrilovich | Computing Semantic Relatedness Using Wikipedia-based Explicit Semantic Analysis[END_REF]and even the text classification [START_REF] Gabrilovich | Wikipedia-based Semantic Interpretation for Natural Language Processing[END_REF]. For this reason, we propose to explore it using different association measures in the context where only partial information is exploited for classifying a whole document.

Unlike most works in document classification, our approaches use only partial information (titles and abstracts) of documents in order to predict relevant topics for representing their full content. Since the content of documents is not fully exploited, using large datasets for building the classifiers could be useful for capturing more information. Forthis reason, we used classifiers built from large collections of previously annotated documents. This is a very challenging task, which has motivated the recent launch of BioASQ: an international challenge on large-scale biomedical semantic indexing and question answering1 [START_REF] Tsatsaronis | BioASQ: A Challenge on Large-Scale Biomedical Semantic Indexing and Question Answering[END_REF].

The rest of the paper is organized as follows. First, related work concerning biomedical document indexing and, more generally, multi-label classification isreviewedin Section 2. Then, the two proposed methods are detailed in Section 3. In Section 4, the experiments are shown while the results are described in Section 5 and discussed in Section 6. Conclusion and future work are finally presented in Section 7.

Related work

The identification of relevant topics from documents in order to des scribe their content is a very important task widely addressed in the literature. In the biomedical domain, the MTI (Medical Text Insdexer) tool [START_REF] Aronson | The NLM Indexing Initiative's Medical Text Indexer[END_REF] is one of the first attempts to index biomedical documents (MEDLINE citations) using controlled vocabularies. To map biomedical text to concepts from the Unified Medical Language System® (UMLS) Metathesaurus -a system that includes and unifiesmore than 160 biomedical terminologies -the MTI tool uses the well-known concept mapper MetaMap [START_REF] Gabrilovich | Computing Semantic Relatedness Using Wikipedia-based Explicit Semantic Analysis[END_REF] and combines its results with the PubMed Related Citations algorithm [START_REF] Lin | PubMed related articles: a probabilistic topic-based model for content similarity[END_REF]. The combination of these methods results in a list of UMLS concepts which is then filtered and recommended to human experts for indexing citations. Recently, the MTI was extended with various filtering techniques and ML algorithms in order to improve its performance [START_REF] Mork | The NLM Medical Text Indexer System for Indexing Biomedical Literature[END_REF]. Ruch has designed a data independent hybrid system using MeSHfor automatically classifying biomedical texts [START_REF] Ruch | Automatic assignment of biomedical categories: toward a generic approach[END_REF]. The first module is based on regular expressions to map texts to concepts while the second is based on a VSM [START_REF] Salton | A Vector Space Model for Automatic Indexing[END_REF] considering the vocabulary concepts as documents and documents as queries.

Then, the rankers of the two components are merged to produce a final ranked list of concepts with their corresponding relevance scores. His results showed that this method achieved good performances, comparable to ML-based approaches. One limitation of this system is that it may return MeSH concepts which match partially the text [START_REF] Trieschnigg | MeSH Up: effective MeSH text classification for improved document retrieval[END_REF].

ML-based approaches are also proposed to deal with such a task. The idea is to learn a model from a training set constituted of already annotated documents and then to use this model to classify new documents. Trieschnigg et al. [START_REF] Trieschnigg | MeSH Up: effective MeSH text classification for improved document retrieval[END_REF] have presented a comparative study of six systems which aim at classifying medical documents using the MeSH thesaurus. In their experiments, they showed that the kNN-based method outperforms the others, including the MTI and the approach developed by Ruch [START_REF] Ruch | Automatic assignment of biomedical categories: toward a generic approach[END_REF].

In their work, the kNN classifier uses a language model [START_REF] Ponte | A Language Modeling Approach to Information Retrieval[END_REF] to retrieve documents which are similar to a given document. The relevance of MeSH descriptors is the sum of the retrieval scores of documents annotated by these descriptors among the neighbouring documents. A similar kNN-based approach has been proposed in [START_REF] Huang | Recommending MeSH terms for annotating biomedical articles[END_REF]. A language model is used to retrieve the neighbours of a given document. Then, a learning-to-rank model [START_REF] Liu | Learning to Rank for Information Retrieval[END_REF] is used to compute relevance scores and consequently to rank candidate labels2 collected from these document neighbours. In this work, the number of labels to classify a document is set to 25. Experiments on two small standard datasets (respectively 200 and 1000 documents) showed that it achieves better performances than the MTI tool.

On the other hand, indexing biomedical documents in which each document of the dataset is assigned one or several categories (also called "labels") can be assimilated as a multi-label classification task. Multi-label classification (MLC) is increasingly studied and especially for text classification purposes [START_REF] Tsoumakas | Mining multi-label data[END_REF]. Several methods have been developed to deal with this task [START_REF] Cherman | Multi-label Problem Transformation Methods: a Case Study[END_REF] [START_REF] Spyromitros | An Empirical Study of Lazy Multilabel Classification Algorithms[END_REF]. They can be categorized into two main approaches [START_REF] Tsoumakas | Mining multi-label data[END_REF]: the problem transformation approach [START_REF] Read | Classifier Chains for Multilabel Classification[END_REF] and the algorithm adaptation approach [START_REF] Spyromitros | An Empirical Study of Lazy Multilabel Classification Algorithms[END_REF] [START_REF] Zhang | ML-KNN: A Lazy Learning Approach to Multilabel Learning[END_REF]. The problem transformation approach splits up a multilabel learning problem into a set of single-label classification problems whereas the algorithm adaptation approach adjusts learning algorithms to perform MLC.

In MLC, the kNN-based approach is widely used. This approach has been proven efficient for MLC in terms of simplicity, time complexity, computation cost and performance [START_REF] Spyromitros | An Empirical Study of Lazy Multilabel Classification Algorithms[END_REF]. Zhang and Zhou [START_REF] Zhang | ML-KNN: A Lazy Learning Approach to Multilabel Learning[END_REF] proposed a ML-KNN (for Multi-Label kNN) method which extends the traditional kNN algorithm and uses the maximum a posteriori principle to determine relevant labels of an unseen instance. For an instance t, the ML-KNN identifies its neighbours and estimates respectively the probabilities that t has and has not a label l based on the training set, for each label l. Then, it combines these probabilities with the number of neighbours of t having l as a category to compute the confidence score of l. Spyromitros et al. [START_REF] Spyromitros | An Empirical Study of Lazy Multilabel Classification Algorithms[END_REF] propose a similar method, named BR-KNN (for Binary Relevance KNN), and two extensions of this method.

The proposed approach is an adaptation of the kNN algorithm using a BR method which trains a binary classifier for each label. Confidence scores for each label are computed using the number of neighbours among the k neighbours that include this label. In [START_REF] Madjarov | An extensive experimental comparison of methods for multi-label learning[END_REF], an experimental comparison of several multi-label learning methods is presented. In this work, different approaches were investigated using various evaluation measures and datasets from different application domains. In their experiments, authors showed that the best performing method is based on the Random Forest classifier [START_REF] Kocev | Ensembles of Multi-Objective Decision Trees[END_REF]. Other recent works address MLC with large number of labels [START_REF] Bi | Efficient Multi-label Classification with Many Labels[END_REF]. Indeed, in many applications, the number of labels used to categorize instances is generally very large. For example, in the biomedical domain, the MeSH thesaurus consisting of thousands descriptors [START_REF] Hall | The WEKA Data Mining Software: An Update[END_REF]149 in the 2014 version) is often used to classify documents. This large number of descriptors can affect the effectiveness and performance of multi-label models. To address this issue, a label selection based on randomized sampling is performed [START_REF] Bi | Efficient Multi-label Classification with Many Labels[END_REF].

Methods

In this section, we present the text classification approaches developed in our work: a kNN-based approach and an ESA-based approach.

The kNN-based approach: kNN-Classifier This approach consists of two steps. First, for a given document, represented by a vector of unigrams, its k most similar documents are retrieved. To do so, the TF.IDF weighting scheme is used to determine the weights of different terms in the documents. Then, the cosine similarity between documents is computed. Once the k nearest documents of a target document are retrieved, the set of labels assigned to them are used for training the classifiers (in the training step) or as candidates for classifying the document (in the classification step). Labels, which are the instances here, are first represented by a set of attributes. Thereafter, ML algorithms are used to build models which are then used to rank candidate labels for annotating a given document. For ranking labels, different learning algorithms are explored.

Nearest neighbours' retrieval

OurkNN-based approach requires a collection of documents previously annotated for the neighbours' retrieval. For a given document, the aim is to retrieveits k mostsimilar documents. To do so, like the PubMedRelatedCitations approach [START_REF] Lin | PubMed related articles: a probabilistic topic-based model for content similarity[END_REF], we consider that two documents are similar if they address the same topics. The cosine similarity measure, which is commonly used in text classification and information retrieval (IR) with the VSM [START_REF] Salton | A Vector Space Model for Automatic Indexing[END_REF], is chosen for this purpose.The documents are first segmented into sentences and tokens,whilestop words are removed. From these pre-processed texts, all unigrams are extracted and normalized according to a stemming technique [START_REF] Porter | Readings in Information Retrieval[END_REF].

Then, the cosine measure enables to compute similarity between documents, which are represented by vectors of unigrams. Formally, let 𝐶 = 𝑑 1 , 𝑑 2 , … , 𝑑 𝑛 , a collection of 𝑛 documents, 𝑇 = 𝑡 1 , 𝑡 2 , … , 𝑡 𝑚 , the set of terms appearing in the documents of the collection and the documents 𝑑 𝑖 and 𝑑 𝑗 being represented respectively by the weighted vectors 𝑑 𝑖 = (𝑤 1 𝑖 , 𝑤 2 𝑖 , … , 𝑤 𝑚 𝑖 ) and

𝑑 𝑗 = (𝑤 1 𝑗 , 𝑤 2 𝑗 , … , 𝑤 𝑚 𝑗 )
, their cosine similarity is defined by [START_REF] Ruch | Automatic assignment of biomedical categories: toward a generic approach[END_REF][25]:

𝑆𝑖𝑚 𝑑 𝑖 , 𝑑 𝑗 = 𝑤 𝑘 𝑖 𝑤 𝑘 𝑗 𝑚 𝑘=1 (𝑤 𝑘 𝑖 ) 2 𝑚 𝑘 (𝑤 𝑘 𝑗 ) 2 𝑚 𝑘
where 𝑤 𝑘 𝑙 , is the weight of the term t k in the document 𝑑 𝑙 . It is the TF.IDF value of the term.

In order to optimize the search, the documents in the search space are indexed beforehand using the open source IR API Apache Lucene3 .The k-nearest neighbours' retrieval thus becomes an IR problem where the target document is the query to be processed.

Collection of candidate labels

For a given document, once its kNN are retrieved, all labels assigned to these

Feature extraction

To determine the relevance of a candidate label, it is represented by a vector of features (also called attributes). In the training step, its class is set to 1 if the label is assigned to the target document and otherwise0 while in the classification step, the model uses the label features to determine its class. We defined six features based on related works [5][17].

For each candidate label, the number of neighbour documents to which it is assigned is used as a feature (Feature 1). This value represents an important clue to determine the class of the label. Moreover, in the classical kNN-based approach, it is the only factor used to classify a new instance. In practice, a voting technique is used to assign the instance to the class that is the most commonamong its k nearest neighbours.

For each candidate label, the similarity scores between the document to classify and its nearest neighbours annotated with this candidate label are summed and this sum is another feature (Feature 2). Since the distance between a document and each of its neighbours is not the same, we consider that the relevance of the labels assigned to them for the target document is inversely proportional to this distance. In other words, the closer a document is to the target document, the more its associated labels are likely to be relevant for the latter. In [START_REF] Trieschnigg | MeSH Up: effective MeSH text classification for improved document retrieval[END_REF], this is the only feature used to determine the relevance scores of candidate labels.

Formally, like in [START_REF] Spyromitros | An Empirical Study of Lazy Multilabel Classification Algorithms[END_REF], let 𝐿 = {𝑙 𝑗 }, 𝑗 = 1, … , 𝑛, be the candidate labels set of a new document d, and 𝑉 = {𝑑 𝑖 }, 𝑖 = 1, … , 𝑘, its k nearest neighbours, the values of these attributes for the label 𝑙 𝑗 are respectively defined as:

𝑓 1 (𝑙 𝑗 ) = 1 𝑘 𝑎𝑠𝑠𝑖𝑔𝑛𝑒𝑑(𝑙 𝑗 , 𝑑 𝑖 ) 𝑛 𝑖=1 𝑓 2 (𝑙 𝑗 ) = 1 𝑘 𝑠𝑖𝑚(𝑑, 𝑑 𝑖 ) 𝑛 𝑙 𝑗 ∈𝑑 𝑖
where the binary function 𝑎𝑠𝑠𝑖𝑔𝑛𝑒𝑑 𝑙 𝑗 , 𝑑 𝑖 returns 1 if the label 𝑙 𝑗 is assigned to the document𝑑 𝑖 , 0 otherwise; 𝑠𝑖𝑚 𝑑, 𝑑 𝑖 is the similarity score between the documents𝑑and𝑑 𝑖 and is computed using the cosine measure.

For each candidate label, we also checked if all the constituent tokens appear in the title and abstract of the document and consider it as the third feature (Feature 3). This binary feature has been chosen because it captures disjoint terms (terms constituted of disjoint words) which are frequent in the biomedical texts.

In addition to these features, we computed two other features using term synonyms.

Indeed, for indexing biomedical documents, the MeSH thesaurus is commonly used.

The latter is composed of a set of descriptors (also called main headings) organized into a hierarchical structure. Each descriptor includes synonyms and related terms, which are known as its entry terms. Thus, for each label (called descriptor here), we check whether one of its entries appears in the document. If this is the case, the fourth binary feature (Feature 4) is set to 1 and the descriptor frequency in the document is computed as a value corresponding to the fifth feature (Feature 5), otherwise the two features are set to 0.

Finally, another feature (Feature 6) is used to verify whether a candidate label is contained in the document's title. Our assumption is that if a label appears in the title, it is relevant for representing this document.

The relevance of each of these features is estimated using the information gain measure (Table 1). The first two features mainly permit to compute relevance scores of candidate labels.

Classifier building

To build the classifiers, a labelled training set consisting of a collection of documents with their manually associated labels is constituted. For each document in the training set, its nearest neighbours and their manually assigned labels are collected.Each label of this collected set is considered as an instance for the training. Thus, for each label, its different features (see the previous section) are computed. Thereafter, labels obtained from neighbours of the different documentsof the training set aregatheredto form the training data. Then, classifiers are built from this labelled training data. We have tested the following classification algorithms: Naive Bayes (NB) [START_REF] John | Estimating Continuous Distributions in Bayesian Classifiers[END_REF], Decision

Trees (DT also known asC4.5 in our case [START_REF] Quinlan | C4.5: Programs for Machine Learning[END_REF]), Multilayer Perceptron (MLP) and Random Forest (RF) [START_REF] Breiman | Random Forests[END_REF].We chose these classifiers as they have yielded the best performances in our tests.

For the implementation of these classifiers, we use the WEKA 4 (Waikato Environment for Knowledge Analysis) tool, which integrates many ML algorithms [START_REF] Hall | The WEKA Data Mining Software: An Update[END_REF], including the four ones we have tested.

Document classification

Given a document to be classified, the candidate labels collected from its neighbours are represented as the training ones (see the previous section). The trained model is then used to estimate the relevance score of each candidate label. Indeed, the model computes, for each candidate label, its probabilities to be relevant or not. From these probability measures,the relevancescore of each label is derived. Candidate labels are then ranked according to their corresponding scoresand the N top-scoring ones are selected to annotate the document, where N is determined using three different techniques.

Selection of the optimal value of N

In order to determine the optimal value of N, we explore three strategies: a) Initially, N is set as the number of labels having a relevance score greater than or equal to a threshold arbitrarily set to 0.5. This strategy based only on the relevance score of the label regarding the document is inspired by the original kNN algorithm. b) We then set the value of N as the average size (number of labels assigned) of the sets of labels collected from the neighbours. This strategy has been successfully used for extending the kNN-based method proposed in [START_REF] Spyromitros | An Empirical Study of Lazy Multilabel Classification Algorithms[END_REF].

c) Finally, in the third strategy, we use the method described in [START_REF] Mao | NCBI at the 2013 BioASQ challenge task: Learning to rank for automatic MeSH indexing[END_REF]. The principle is to compare the relevance scores of successive labels ofa list of candidate labels ranked in descending order for determining the cut off condition enabling to discard the irrelevant or insignificant ones. This strategy is defined by the following formula:

𝑠 𝑖+1 𝑠 𝑖 ≥ 𝑖 𝑖 + 1 + 𝛼
where 𝑠 𝑖 is the relevance score of a label being at position 𝑖 and 𝛼a constant whose optimal value is determined empirically.

The ESA-based approach

ESA is an approach proposed for representing textual documents in a semantic way [START_REF] Gabrilovich | Computing Semantic Relatedness Using Wikipedia-based Explicit Semantic Analysis[END_REF]. In this method, the documents are represented in a conceptual space constituted of explicit concepts automatically extracted from a given knowledge base 5 . For this, statistical techniques are used to explicitly represent any kind of text (simple words, fragments of text, entire document) by weighted vectors of concepts. In the approach proposed in [START_REF] Gabrilovich | Computing Semantic Relatedness Using Wikipedia-based Explicit Semantic Analysis[END_REF], the titles of Wikipedia articles are defined as concepts. Thus, each concept is represented by a vector consisting of all terms(except stop words) that appear in the corresponding Wikipedia article. The weight of each word of this vector is the association score between thetermand the correspondingconcept. Thesesscores are computed using the TF.IDF weighting scheme [START_REF] Salton | Term-weighting Approaches in Automatic Text Retrieval[END_REF].

At the end of this step, each concept is represented by a vector of weighted terms.Then, an inverted index, wherein each term is associated with a vector of its related concepts, is created. In this inverted index, the less significant concepts (i.e., concepts with low weight) for a vector are removed. The index is then used to classify unseentextual documents.

The classification process consists of two steps. For a given document, it is first represented by a vector of terms. The concepts corresponding to these terms are then retrieved in the inverted index and merged to constitute a vector of concepts representing the document. The retrieved concepts are finally ranked according to their relevance score in descending order. The most relevant ones are then selected. This process is illustrated by Figure 1.

Formally, let 𝑇 be a text, 𝑡 𝑖 the termsappearing in 𝑇 and 𝑣 𝑖 , their respective weights. Let 𝑘 𝑗 ,be the association score between the term𝑡 𝑖 and the concept 𝑐 𝑗 with 𝑐 𝑗 ∈ 𝐶, 𝐶 the set of Wikipedia concepts. The weight of the concept 𝑐 𝑗 for the text 𝑇 is defined by:

𝑊 𝑐 𝑗 = 𝑣 𝑖 . 𝑘 𝑗 𝑤 𝑖 ∈𝑇
Our ESA-based approach explores this technique in the specific case where only partial information is considered (i.e., the title and abstract in the case of scientific articles).First, we assume the availability of concepts (generallydefined in semantic resources) to be used for document classification as well as a labeled training set in which each document is assigned a set of concepts. Unlike the original ESA method where each article is associated with a single concept, in our approach, each document in the training set may be assigned one or more concepts (also called labels here).

From the training set, we use statistical techniques to establish associations between labels and terms extracted from the texts. Thus, for each label, the unigrams that are more strongly associated with it are used for its representation. If the concepts are seen as documents, we face with an IR problem where the goal is to retrieve the most relevant documents (concepts) for a given query (a new document). Therefore, the classical IR models can be used to represent documents and queries, but also to compute the relevance of a document with respect to a given query. In this work, the VSM is used to determine the most relevant concepts for annotating the given document.Like in the kNN-based approach, the documents are processed using the following techniques: segmentation into sentences, tokenization, removal of stop words and normalization using the Porter's stemming algorithm [START_REF] Porter | Readings in Information Retrieval[END_REF].

For computing the association scores between a concept𝑐and a term𝑡, we experimented the following measures:

• The TF.ICF measure (the TF.IDF scheme adapted to concepts) [START_REF] Salton | A Vector Space Model for Automatic Indexing[END_REF]:

𝑇𝐹. 𝐼𝐶𝐹 𝑡, 𝑐 = 𝑇𝐹 𝑡, 𝑐 * log 𝑁 𝑛 𝑖 where𝑁is the total number of concepts, 𝑛 𝑖 the number of concepts associated with 𝑡. The factor𝑇𝐹 𝑡, 𝑐 is the number of occurrences of𝑡 in the documents annotated by the concept 𝑐and is defined by:

𝑇𝐹 𝑡, 𝑐 = 𝑓𝑟𝑒𝑞(𝑡, 𝑑) 𝑑 𝑑∈𝐷 𝑐
where 𝑓𝑟𝑒𝑞(𝑡, 𝑑)is the frequency of 𝑡in the document 𝑑,|𝑑| is the number of words of 𝑑 and𝐷 𝑐 the set of documents annotated by the concept 𝑐.

• The Jaccard coefficient [START_REF] Jaccard | The Distribution of the Flora in the Alpine Zone[END_REF]:

𝐽 𝑡, 𝑐 = 𝑐𝑜𝑐𝑐(𝑡, 𝑡) 𝑜𝑐𝑐 𝑡 + 𝑜𝑐𝑐 𝑐 -𝑐𝑜𝑐𝑐(𝑡, 𝑐)

where 𝑐𝑜𝑐𝑐 𝑡, 𝑐 is the number of documents in which the concept 𝑐 and the term𝑡co-occur𝑜𝑐𝑐 𝑐 is the number of documents annotated by the concept 𝑐 and𝑜𝑐𝑐 𝑡 is the number of documents in which the term𝑡appears. where 𝑠𝑐𝑜𝑟𝑒(𝑤, 𝑐)is the association score between the term t and the concept 𝑐 and𝑇𝐹. 𝐼𝐷𝐹 𝑡, 𝑑 is the TF.IDF value of the term in the document 𝑑.

Evaluation

In order to assessthe effectiveness of our approaches, we performed two different experiments: one in the context of the task 2a of the international BioASQ challengeto which we participated [START_REF] Balikas | Results of the BioASQ Track of the Question Answering Lab at CLEF 2014[END_REF] and the second experiment conducted on a derived dataset from the BioASQ challenge, as described below.

Datasets

The BioASQ organizers, within the 2014 edition, provided a collection of over 4 million documents constituted by only titles and abstracts of articles (called also citations), coming from specific scientific journals for the task 2a of this challenge [START_REF] Tsatsaronis | BioASQ: A Challenge on Large-Scale Biomedical Semantic Indexing and Question Answering[END_REF]. These documents, extracted from the MEDLINE database, are annotated by descriptors ofthe MeSH thesaurus.

In addition, during the challenge, the organizers provided each week

PubMed®citations not yet annotated which were used as test sets to evaluate the systems participating in the task 2a. Participants were asked to classify these test sets using descriptors of the MeSH thesaurus. The test sets have subsequently been annotated by PubMed® human indexers for evaluating the proposals of the participating systems.

Experiments

First experiment

For the kNN retrieval, we used a dataset consisting of all articles of this collection published since 2000 (2,268,724 documents). The motivation for this choice is to discard old documents which are not annotated by descriptors recently added to the MeSH thesaurus (the MeSH thesaurus is regularly updated). This dataset is thereafter extended to the entire collection.For training the classifiers we randomly selected 20.000 articles out of those published since 2013; the citations of the training set are discarded from the former dataset. We assume this training set sufficient to capture relevant information for building the classifiers.

Only the kNN-based approach was used for our participation to the challenge.To assess this method, five of the different test sets provided by the challenge organizers were used.

Second experiment

For the second experiment, we first extracted all articles published since 2013 (133,770 documents) from the previous dataset provided by the challenge organizers.

We then selected randomly 20,000 documents to be used for training the classifiers and one thousand for constituting the test set. The data used to train the classifiers werethen extended to 50,000 documents, sincewe believed it could improve the classification performances; using large training dataset should enable the classifiers to capture more information. The test collection was also increased to 2,000 documents. Like in the training dataset, each document in the test set was assigned a set of labels by PubMed® annotators. These manually assigned labels were thus used to evaluate the results of our different methods.

Regarding the evaluation of our ESA-based approach, except the documents in the test set, the rest of the collection (i.e., 4,430,399 documents) was exploited to compute the association scores between words and labels.

Evaluation measures

As formerlysaid, indexing biomedical documents can be assimilated to a multi-label classification (MLC) problem. Instead of one class label, each document is assigned a list of labels. Thus, measures usually used for evaluating indexing methods were adapted for the MLC context [START_REF] Tsoumakas | Mining multi-label data[END_REF]. The example-based precision (EBP) measures how many of the predicted labels are correct while the example-based recall (EBR) measures how many of the manually assigned labels are retrieved. Since EBP and EBR evaluate partially the performance of a method, the example-based f-measure (EBF) combines both measures for a global evaluation. The accuracy (Acc) is also a complementary measure [START_REF] Tsoumakas | Mining multi-label data[END_REF]. These measures are computed as follows. Let 𝑌𝑖 be, the set of true labels (labels manually assigned to the documents), 𝑍𝑖 the set of predicted labels and 𝑚 the size of the test set:

𝐸𝐵𝑃 = 1 𝑚 𝑌𝑖 ∩ 𝑍𝑖 𝑍𝑖 𝑚 𝑖=1 𝐸𝐵𝑅 = 1 𝑚 𝑌𝑖 ∩ 𝑍𝑖 𝑌𝑖 𝑚 𝑖=1 𝐸𝐵𝐹 = 1 𝑚 𝑌𝑖 ∩ 𝑍𝑖 𝑍𝑖 + 𝑌𝑖 𝑚 𝑖=1 𝐴𝑐𝑐 = 1 𝑚 𝑌𝑖 ∩ 𝑍𝑖 𝑍𝑖 ∪ 𝑌𝑖 𝑚 𝑖=1
These measures, in addition to being common, are representative and enable the global evaluation of the systems' performances.. The results of our two approaches are presented in the next section.

Experiment environment

In our different experiments, we used the computing facility of the Bordeaux Mésocentre, Avakas6 , which includes:

• the compute nodes c6100 (x264), which are the machines on which algorithms are executed. They have the following characteristics:

o Two processors of hexa-cores (12 cores per node) Intel Xeon X5675@3.06GHz; o 48GB RAM.

• the computation nodes bigmem R910 (x4), which have more memory and whose cores have slower processors: o 4 processors of 10 cores (40 cores per node) Intel Xeon E7-4870@2.4GHz;

o 512 GB RAM.

In our case, we used two computation nodes c6100, which provide 48 GB of RAM and 24 cores Intel Xeon X5675.

Results

Results of the kNN-based approach

Experiment within the BioASQ challenge First, we present the results obtained in the task 2a of the BioASQ challenge. For that purpose, we report results of batch 3 in terms of EBP, EBR and EBF. We chose only these measures since they are representative and allow estimating the global performance of the MLC methods. Table 2 shows the results of our best system using the kNN-based approach and the ones which obtained the highest measures within the different tests of batch 3. In tests 2 and 5, our best system uses a Naïve Bayes classifier and selects only labels having a confidence score greater than or equal to 0.5 while in the others, the best system sets N to the average size of the sets of labels collected from the neighbours. In most cases, using this value for N yields better or similar results than the other strategy. In the challenge, we do not use the automatic cut-off method to fix the number of labels as described in [START_REF] Mao | NCBI at the 2013 BioASQ challenge task: Learning to rank for automatic MeSH indexing[END_REF] but in the second experiment, this technique is explored.

Second experiment

We evaluate our kNN-based approach with different configurations in the test set of the second experiment and compare the achieved performances. Thus, we test combinations of various classifiers with different techniques for determining the number of labels for annotating a given document. The evaluation of configurations with the two best classifiers in our experiments, NB and RF, are presented in Table 3.

The parameter k is empirically set to 25 using a cross-validation technique.When the minimal score threshold is used, the precision often increases significantly, mainly with the RF classifier but the recall is lower. Regarding the "average size strategy", it yields a good recall but the precision decreases slightly. In this case, the results of both classifiers are similar but the RF one slightly outperforms the NB classifier. The best results are achieved with the cut-off method which balances both precision and recall, and yields the best F-measure. Except for the minimum threshold technique where the NB classifier results are better, the best F-measure is achieved with the RF classifier. The DT (C4.5 algorithm of Weka) and the Multilayer Perceptron (MLP) classifiers have also been tested but their results are less interesting. The former yieldslowerperformances while the latter performs very slowly and gets results comparable to the RF ones. The MLP classifier requires more CPU and memory during the training process.

When the training set is raised from 20,000 to 50,000, the performancesareslightly improved in two test sets (one of 1000 documents and another of 2000). Table 4 presents the results of the different classifiers in this larger training set. The value of𝛼(constant used in the strategy based on label scores comparison -strategy c-for optimizing N) also affects the classification performance. The lower the value of𝛼, the higher the precision is but the lower the recall is and vice versa. In these experiments, we set𝛼to 1.6 which yields the best results using cross-validation techniques. Furthermore, we note that when the classifiers are trained on this extended dataset, they yield similar performances but the RF classifier slightly outperforms the others. Table 5 gives an example of labels suggested for classifying the document having the PMID 23044786 (Figure 2) with the kNN-based approach.

In

Results of the ESA-based approach

After processing the training set composed of a collection of 4,432,399 documents (titles and abstracts), we obtain 1,630,405 distinct words and 26,631 descriptors assigned to these documents among the 27,149 MeSH descriptors (98.1%). To simplify the computation and optimize the results of the classification, each concept is represented by a vector consisting of 200 terms, which are the most strongly associated with it. Only terms appearing in at least five documents are considered.

Our choice is motivated by the will to simplify the scores computation by excluding the less representative terms. Here, since we used test sets already labelled, the number of concepts which are relevant to annotatethe document is known and is used;therefore, EBP and EBR are equivalent; thus we only report the EBF and the accuracy measures.

After evaluating the ESA-based approach, we note, as in previous work, that its performance varies depending on the measure used to estimate the association scores between words and concepts. This behaviour is illustrated in Table 6 where the Jaccard measure yields the best results.

Discussion

While textualclassification has been widely investigated, few approaches arecurrently able to efficiently handle large collections of documents, in particular when only a portion of the information is available. This is a challenging task, particularly in the biomedical domain.

Our experiments show that our kNN-based approach is promising for biomedical documents classification in the context of a large collection. Our results confirm the findings presented in [START_REF] Trieschnigg | MeSH Up: effective MeSH text classification for improved document retrieval[END_REF], where among the multiple classification systems, thekNNbased one yielded the best results. If we compare our method with the latter, we use more advanced features to determine the relevance of a candidate label. Indeed,

Trieschnigg and his colleagues determine the relevance of a label by summing the retrieval scores of the k neighbour documents that are assigned to the label [START_REF] Trieschnigg | MeSH Up: effective MeSH text classification for improved document retrieval[END_REF]. In our method, this sum is only considered as one feature among others for determining the confidence scores of labels. While the results of our method do not outperform the extended (and improved) MTI system [START_REF] Mork | The NLM Medical Text Indexer System for Indexing Biomedical Literature[END_REF] which is currently used by the NLMcurators, it getspromising results (0.49 against 0.56 of F-measure). A direct comparison with the method proposed in [START_REF] Huang | Recommending MeSH terms for annotating biomedical articles[END_REF] is not simple since the authors used an older collection than the official datasets provided in the BioASQ challenge, which are recent and annotated with descriptors of the recentMeSHthesaurus (2014 version).Similarly to their experiments, when our method is evaluated on 1,000 randomly selected documents, it outperforms this method (0.55 against 0.50 for the Fmeasure). But a comparison with their recent results in the first challenge of BioASQ [START_REF] Mao | NCBI at the 2013 BioASQ challenge task: Learning to rank for automatic MeSH indexing[END_REF] where they integrated the MTI outputs, their system performs better than ours (Fmeasure of 0.56 against 0.49). Compared with the two approaches proposed in [START_REF] Zhu | An Incremental Approach for MEDLINE MeSH Indexing[END_REF],

one based on the MetaMap tool [START_REF] Aronson | An overview of MetaMap: historical perspective and recent advances[END_REF]and another using IR techniques, our method gets better results (0.49 against 0.42 for the F-measure). Our approach outperforms also the hierarchical text categorization approach proposed in [START_REF] Ribadas-Pena | Two Hierarchical Text Categorization Approaches for BioASQ Semantic Indexing Challenge[END_REF].

As part of our participation in the challenge, the NB classifier is combined with the average size of labels assigned to the neighbours to determine relevant descriptors for a given document. In the second experiment, we note however that a combination of RF with the cut-off technique proposed in [START_REF] Mao | NCBI at the 2013 BioASQ challenge task: Learning to rank for automatic MeSH indexing[END_REF] yields better results [START_REF] Dramé | A k-nearest neighbor based method for improving large scale biomedical document annotation[END_REF]. A more recent evaluation of our kNN-based approach using a large dataset (50,000 documents) for training the classifiers shows that it provides better performances, comparable to the best methods described in the literature(with an f-measure of 0.55).

Moreover, unlike the extendedMTI system [START_REF] Mork | The NLM Medical Text Indexer System for Indexing Biomedical Literature[END_REF], we do not use any specific filtering rules. This makes our approach generic and its reuse in other domains straightforward.

A comparison of our basic kNN-based system (trained on 20,000 documents, and improved later) tothe performing classification systems [START_REF] Liu | The Fudan-UIUC Participation in the BioASQ Challenge Task 2a: The Antinomyra system[END_REF][37] [START_REF] Mao | NCBI at the 2014 BioASQ Challenge Task: Large-scale Biomedical Semantic Indexing and Question Answering[END_REF], which alsoparticipatedin the 2014 BioASQ challenge [START_REF] Balikas | Results of the BioASQ Track of the Question Answering Lab at CLEF 2014[END_REF] and the baseline (extended MTI) [START_REF] Mork | The NLM Medical Text Indexer System for Indexing Biomedical Literature[END_REF]is shown in Table 7.The two best systems, Antinomyra [START_REF] Liu | The Fudan-UIUC Participation in the BioASQ Challenge Task 2a: The Antinomyra system[END_REF] and L2R [START_REF] Mao | NCBI at the 2014 BioASQ Challenge Task: Large-scale Biomedical Semantic Indexing and Question Answering[END_REF],

rely on the learning to rank (LTR) method. The former extends features generated from the neighbour document retrieval with binary classifiers and the results of the MTI and uses then the LTR method to rank the candidate labels. Meanwhile, the other system, combines information obtained by the neighbours' retrieval, binary classifiers and the MTI results as features and also uses theLTRfor the ranking. The Hippocrates system presented in [START_REF] Papanikolaou | Ensemble Approaches for Large-Scale Multi-Label Classification and Question Answering in Biomedicine[END_REF]only relies on binary SVM (Support Vector Machine) classifiers and trains them on a large dataset (1.5 million documents) in contrast to our basic kNN approach trained on 20,000 documents. Note that these three systems use binary classifiers for building a model for each label [START_REF] Balikas | Results of the BioASQ Track of the Question Answering Lab at CLEF 2014[END_REF]. These systemsrequire therefore considerable resources in terms of computation and storage compared to our kNN-based approach.

For the kNN retrieval, we have investigated the cosine similarity which is widely used in IR. It would be interesting to combine this measure with domain knowledge resources, such as ontologies,to overcome the limitation of similarity computation based only on common words.

The second method based on the ESA, meanwhile, yields very low performances comparable to basic methods using a simple correspondence between the text and the semantic resource inputs. Thus, although the ESA technique has shown interesting results in text classification [START_REF] Gabrilovich | Wikipedia-based Semantic Interpretation for Natural Language Processing[END_REF], it does not seem appropriate for our targeted classification problem where only partial information is available. Indeed, to compute the association scores between a term and a label, this method exploits the occurrences of thisterm in the documents annotated by the label. However, in this specific classification problem, labels used to annotate a document are not always explicitly mentioned in the later. Documents are short and it is thereby unlikely that they contain mentions of all relevant labels.It is worth mentioning that in our approach, each concept is represented by a vector consisting of 200 terms, and only terms appearing in at least five documents are considered. For example, the most associated stemmed terms (with their corresponding Jaccard scores) to the label Body Mass Index are: index (0.1), waist (0.087), mass (0.079), bodi (0.077), circumfer (0.068), anthropometr (0.062), fat (0.059), adipos (0.048), smoke (0.039), weight (0.038), nutrit (0.037).

Note that we do not use the large Wikipedia's knowledge base,like the work presented in [START_REF] Gabrilovich | Computing Semantic Relatedness Using Wikipedia-based Explicit Semantic Analysis[END_REF], for the conceptual representation of documents since most of the MeSH descriptors cannot be directly mapped to this resource.Furthermore, contrary to existing works [START_REF] Gabrilovich | Wikipedia-based Semantic Interpretation for Natural Language Processing[END_REF], which use ESA for enriching the bag-of-words approach with additional knowledge-based features, our ESA-based method builds a standalone classifier. However, this approach will be explored in the futurein order to enrich the features and consequentlyimprove the performance of our k-NN approach.

Conclusion

In this paper, we have described two approaches for improving the classification of large collections of biomedical documents. The first one is based on the kNN algorithm while the second approach relies on the ESA technique. The former uses the cosine measure with the TF.IDF weighting method to compute similarity between documents and therefore to find the nearest neighbours for a given document. Simple classification methods determine the most relevant labels from a set of candidates of each document. We have investigated an important feature of the classification problem: the decision boundary which permits to determine the relevant label(s) for a target document. Thus, instead of using voting techniques like in the classical kNN algorithm, ML methods were used to classify documents. The latter is based on the ESA technique which exploits associations between words and labels.

Thanks to an evaluation on standard benchmarks, we noted that the kNN based method using the RF classifier with the cut-off method yielded the best results. We also noted that this approach achieved promising performances compared with the best existing methods. In contrast, our findings suggest that the ESA is not suitable for classifying a large collection of documents when only partial information is available.

For indexing purpose, the representation of documents as bags of words is limited since similarity between the latter is only based on the words they share. Therefore, to improve the performance of our kNN-based approach, we plan to use a wide biomedical resource, such as the UMLS Metathesaurus, for computing the similarity between documents (exploitation of synonyms and relations) and thus to overcome this limitation. Other features and similarity measures will be studied to improve the performances of our method.

Figures Figure 1 -The process of the Explicit Semantic Analysis based approach

The two steps of the ESA-basedapproach are presented: the indexing step and the classification step.

  documents are gathered in order to constitute a set of candidate labels likely to annotate this document. Sincethis can be seen as a classification problem, we use ML techniques to rankthese candidate labels. Thus, classical classifiers are used to build classification models which are then exploitedto determine the relevant labels for annotating anyunseendocument. For that purpose, candidate labels are used as training instances (in the training step) or instances to be classified (in the classification step).

Finally, to estimate

  the relevance of aconcept to annotate a document, we use the following metric. The relevance score of a concept𝑐for a new document𝑑 is defined by: 𝑅𝑒𝑙 𝑐, 𝑑 = 𝑇𝐹. 𝐼𝐷𝐹 𝑡, 𝑑 * 𝑠𝑐𝑜𝑟𝑒(𝑡, 𝑐) 𝑤 ∈𝑑

  terms of training time, NB, DT and RF classifiers performed similarly with respectively 4, 6 and 9 minutes once data were represented in suitable formatfor Weka (e.g. ARFFformat(Attribute-Relation File Format)). The pre-processing step (retrieval of neighbours and computation of features values) however takes more time (1 hour and 43 minutes). Note that since we have different types (binary and numeric) of attributes, we discretize the latter in nominal attributes. The MLP classifier is, meanwhile, very costly in terms of training time (23 hours).

Figure 2 -

 2 Example of a PubMed® (23044786) citation manually annotated by human indexers using MeSH descriptorsThis is an example of a PubMed citation, consisting of a title and an abstract, with MeSH descriptors manually selected by indexers for annotating it.

Table 1 -Importance of each feature for the prediction according to the Information Gain measure

 1

	Tables
	Feature	Description

Table 2 -Results of our kNN-based system and the best systemsparticipating in the BioASQ challenge on the different tests of the batch 3.

 2

	Test	Number of	System	EBP	EBR	EBF
		documents
			kNN-Classifier	0.55	0.48	0.49
	test 1	2,961	Best	0.59	0.62	0.58
			kNN-Classifier	0.52	0.50	0.48
	test 2	5,612	Best	0.62	0.60	0.60
			kNN-Classifier	0.55	0.49	0.49
	test 3	2,698	Best	0.64	0.63	0.62
			kNN-Classifier	0.49	0.55	0.49
	test 4	2,982	Best	0.63	0.62	0.62
			kNN-Classifier	0.50	0.53	0.48
	test 5	2,697	Best	0.64	0.61	0.61

Table 3 -Results of the kNN-Classifieraccording to the classifier and strategy used for fixing N: a) 0.5 as the minimal confidence score threshold, b) the average size of the sets of labels collected from the neighbours and c) the cut- off method. A training set of 20,000 documents is used.

 3

	Strategy Classifier	EBP	EBR	EBF
		NB	0.58	0.49	0.49
	a)	RF	0.74	0.34	0.43
		NB	0.51	0.54	0.51
	b)	RF	0.52	0.54	0.52
		NB	0.56	0.52	0.51
	c)	RF	0.61	0.52	0.53

Table 4 -Results of the kNN-Classifier according to the classifier using the cut- off method with a training set of 50,000 documents.

 4

	Classifier	EBP	EBR	EBF	Acc
	NB	0.59	0.54	0.54	0.39

Table 7 -Comparison of our kNN-Classifierused for participating in the challenge with the best systems and the MTI baseline on the test set of the week 2 of batch 3consisting of 3009 documents. The used measures are: example-based precision (EBP), example-based recall (EBR), example-based f- measure (EBF) and micro f-measure (MiF) (Source BioASQ 2014).

 7

	Systems	EBP	EBR	EBF	MiF
	Antinomyra [36]	0.59	0.62	0.59	0.60
	L2R [38]	0.59	0.60	0.58	0.59
	Hippocrates [37]	0.59	0.60	0.57	0.59
	MTI	0.59	0.58	0.56	0.57
	kNN-Classifier	0.55	0.49	0.49	0.51

http://bioasq.lip6.fr

Labels are categories used to classify documents

http://lucene.apache.org/core/

http://www.cs.waikato.ac.nz/ml/weka/

http://www.mcia.univ-bordeaux.fr/index.php?id=45

Acknowledgements

The work presented in this paper is supported by the French Fondation Plan Alzheimer.The authors would like to thank the BioASQ 2014 challenge organizers who provided the datasets used in this study for evaluating the classification methods.

They would also like to thank the anonym reviewers of the previous version of our paper in the SMBM2014.

Large scale biomedical texts classification: a kNN and an ESA-based approaches

Competing interests

The authors declare that they have no competing interest.

Authors' contributions


Stefan Haar

Simon Theissing Mexico

Predicting Traffic Load in Public Transportation Networks

Keywords:

This work is part of an ongoing effort to understand the dynamics of passenger loads in modern, multimodal transportation networks (TNs) and to mitigate the impact of perturbations, under the restrictions that the precise number of passengers in some point of the TN that intend to reach a certain destination (i.e. their distribution over different trip profiles) is unknown. We introduce an approach based on a stochastic hybrid automaton model for a TN that allows to compute how such probabilistic load vectors are propagated through the TN, and develop a computation strategy for forecasting the network's load a certain time in the future.

INTRODUCTION

We continue here the work begun in [START_REF] Haar | A hybrid-dynamical model for passenger-flow in transportation systems[END_REF] for capturing both the discrete vehicle movements and continuous passenger transfers in a multimodal public transportation network (TN). In [START_REF] Haar | A hybrid-dynamical model for passenger-flow in transportation systems[END_REF], a deterministic hybrid automaton (DHA) model was used, in order to overcome the state space explosion problem via fluidification. For its specification we were using discrete and continuous Petri nets (PNs) as the basic modelling blocks [START_REF] David | Discrete, Continuous, and Hybrid Petri Nets[END_REF], with the feature that the marking of the continuous places and thus the flows in-between were not restricted to scalars. Instead, we were integrating different passenger profiles into vector markings and -flows, together with routing matrices relating both. Now -and this is the starting point of the present work -a real TN is everything but deterministic. On the one hand, there are highly unpredictable asynchronous events for which statistical data is hard to obtain. It is thus difficult to include them in the daily network operation [START_REF] Schmöecker | Metro service delay recovery: comparison of strategies and constraints across systems[END_REF], e.g. by means of minuteby-minute or hourly forecasts. Typical examples are passenger incidents. Now, note that -apart from few exceptions -such incidents originate locally, in one mode or line, and then propagate to other modes or lines by passenger transfers. And these transfers are predictable, not necessarily deterministic, if one knows the destination or trip profile of the passengers; in general, this can only be known through probabilistic estimates. Finally, there are the more "continuous" passenger arrival processes for which statistical data is easier to obtain: How many passenger will arrive at a station at which time? According to which route, including which vehicle missions, will they travel? Fig. 1: A discrete mode of the SHA model is defined by the (discrete) state of the vehicle operation. Each mode enables a set of possible passenger transfers and thus the framework for the continuous dynamics associated with it. Statedependent conditions trigger forced jumps between the modes.

Here, we will extend the DHA from [START_REF] Haar | A hybrid-dynamical model for passenger-flow in transportation systems[END_REF] in that we will replace all deterministic passenger arrival processes by their stochastic counterparts, and, in doing so, introduce a Markovian stochastic hybrid automaton (SHA) with jumps between the discrete modes at a priori defined equidistantly spaced discrete points in time. We will then informally define a computation strategy for the forecast of a TN's load in form of a probabilistic forward reachability problem. A look into the literature then reveals that our SHA model knows many preceding -similar or alternative -modelling approaches that have been developed notably in the past two decades, with every approach introducing the uncertainty at a different point in the model dynamics. For instance, the authors of [START_REF] Trivedi | FSPNs: Fluid stochastic Petri nets[END_REF] extended the dynamics underlying a DHA in that the jumps between the discrete modes are either exponentially distributed functions of time or immediate; with a weighting function as a means to resolve conflicts among simultaneously enabled immediate transitions [START_REF] Balbo | Introduction to generalized stochastic Petri nets[END_REF]. Thus, as compared to our modelling approach, the jumps in [START_REF] Balbo | Introduction to generalized stochastic Petri nets[END_REF] are not confined to a countable set of discrete points in time. However, in their modelling approach the discrete jumps are decoupled from the continuous states, and the latter evolve according to deterministic differential balance equations; whereas in our model the continuous states evolve according to stochastic differential equations (SDEs) and jumps might be coupled to the continuous states. The authors of [START_REF] Horton | Fluid stochastic Petri nets: Theory, applications, and solution techniques[END_REF] bridge the gap between the continuous states and the discrete jumps by means of a guard function. Finally, the deterministic balance equations were replaced by normally distributed balance equations in [START_REF] Wolter | Modelling hybrid systems with fluid stochastic Petri nets[END_REF]. Outside the framework of PNs, the authors of [START_REF] Hu | Towards a theory of stochastic hybrid systems[END_REF] introduced an SHA that exhibits state-driven (forced) jumps between the discrete modes subjected to sets of SDEs; for each mode one set. This approach was extended in [START_REF] Bujorianu | Toward a general theory of stochastic hybrid systems[END_REF] in that the mode transitions are no longer restricted to forced jumps, but can be initiated by spontaneous jumps with statedependent transition rates as well. The author of [START_REF] Bect | A unifying formulation of the Fokker-Planck-Kolmogorov equation for general stochastic hybrid systems[END_REF], then showed how the SHA from [START_REF] Bujorianu | Toward a general theory of stochastic hybrid systems[END_REF] can be formulated in an equivalent system of integro-differential equations together with boundary conditions. Regarding the probabilistic forward reachability problem, note that the authors of [START_REF] Prandini | A numerical approximation scheme for reachability analysis of stochastic hybrid systems with state-dependent switchings[END_REF] presented a grid-based asymptotic approximation method for a backward reachability problem subjected to the dynamics of an SHA that encounters spontaneous jumps between the discrete modes; with a system of SDEs assigned to every mode. That system is approximated by a Markov chain following a space and subsequent time discretization; whereas in our approach the discretization of the time precedes the discretization of the space, and the latter comes along with a numerical integration of the continuous states in a discrete mode.

In the rest of this paper, we will introduce the basic ingredients for our SHA model in Sec. 2, on top of which we will elaborate in Sec. 3 the continuous dynamics for a particular discrete mode in it (cf. Fig. 1). We will then define a network's vehicle load in Sec. 4 that we will use in Sec. 5 for computing forecasts.

BASIC INGREDIENTS

Infrastructure

The operation of all vehicles (V ) involving a finite set of runs (Z) and missions (X ), and the routing of all passengers according to a finite set of trip profiles (Y ), define the dynamics of our SHA model. They are specified on a shared infrastructure comprising a finite set of stations (S), another finite set of transportation grids (G), and yet another finite set of interfaces (I ) connecting grids and stations. We will informally introduce first this infrastructure, and then the vehicle operation and the passenger routing. A more detailed description can be found in [START_REF] Haar | A hybrid-dynamical model for passenger-flow in transportation systems[END_REF].

Every transportation grid (TG) g ∈ G confines the lines and thus the vehicle movements of one particular mode. It comprises a finite set of waypoints and routes connecting them, in which a particular waypoint refers to a distinct discrete vehicle position and a route between two waypoints to the possibility of a vehicle transfer between both. A waypoint is either empty or accommodates one vehicle at a time. A rule set then defines a deterministic resolution between conflicting vehicle movements. Fig. 2: Sample transportation grid Fig. 2 shows a simple TG that may accommodate two orbital metro (sub-)lines: A vehicle at the waypoint "Stop 1" can either drive to the waypoint "Stop 2" and then to the waypoint "Stop 3", or it can pass the second stop. Regarding the two integers "1" and "2" written in brackets next to "Pass stop 2" and "Drive to stop 3", they indicate that a vehicle movement from the first stop to the third stop is privileged over a conflicting vehicle movement from the second stop to the third stop.

Every station s ∈ S can be decomposed into a finite set of gathering points (GPs) that are connected by the possibility of passenger transfers to other GPs, the outdoor area of the TN, or the waypoints in the TGs. They accommodate the transferring passengers and have limited capacities.

As an example, Fig. 3 depicts an extract of a sample station: Before joining the station's entrance area (= GP), the passengers have to step down the stairs (= possibility of a passenger transfer) starting from the TN's outdoor area. They can then cross the turnstiles so as to transfer to the platform that itself is dedicated to the boarding of a vehicle executing mission x ∈ X . Moreover, the entrance area can accomodate 50 passengers, and the platform 200.

Step down the stairs

Entrance area [50]

Cross the turnstiles

Platform [200]

x Board Fig. 3: Extract of a sample station Finally, every interface i ∈ I establishes the link between a GP of a station and a waypoint in a TG, or vice versa (cf. 4): A passenger on-board a vehicle stopped at the waypoint "Stop 1" and executing the mission x 1 ∈ X can alight from it to the GP "Platform 1" from which s/he can either exit the station or transfer to the GP "Platform 2". Then, from the "Platform 2" a passenger can board a vehicle iff that vehicle is executing the mission x 2 ∈ X and stopped at the waypoint "Stop 2".

Vehicle operation

Every vehicle mission x ∈ X defines a path in a TG, a sequence of stops at the waypoints, and deterministic driving times in between: The vehicle stops are specified by pairs of minimum and maximum dwell times that are assigned to every waypoint. In particular, a positive minimum dwell time indicates that a vehicle has to stop at a waypoint. A positive maximum dwell time, on the contrary, applies iff a vehicle's intended movement is not conflicting with that of another one, i.e., a vehicle movement with a higher priority. Now every vehicle run z ∈ Z specifies a sequence of vehicle missions, and assumes a vehicle realizing it to be in the operational state "Parking" shortly before and afterwards. Finally, the dispatch plan P d defines which vehicle is supposed to start realizing which vehicle run at which time. The emphasis here is on "supposed" since the dispatch of a vehicle at a particular time obviously requires that the vehicle is available, i.e., parked at the correct waypoint.

Passenger routing

In the infrastructure from Fig. 4, we decorate every arc with a subset of the set Y = {1, 2, 3, 4} of trip profiles (with set brackets omitted) for their specification. Every trip profile y ∈ Y fixes routing of the corresponding group of passengers in the TN along a tree in the infrastructure. That way one can account for alternative vehicle missions in the routing of the same group of passengers. For instance, a particular trip profile might be specified s.t. a passenger at the platform of a station will only board one particular vehicle mission, whereas a passenger, who is travelling according to another trip profile, is taking whatever vehicle mission is arriving next. Once having specified all trip profiles, they can then be mapped to square matrices assigned to all possible passenger transfers in the infrastructure. We can also integrate the possibility of re-routing into these routing matrices; such a re-routing means that passenger change their trip profiles [START_REF] Haar | A hybrid-dynamical model for passenger-flow in transportation systems[END_REF].

PASSENGER FLOWS IN A MACRO STATE

Macro states

At any given time, the TN is in one of its discrete states in terms of the vehicle operation (where are the vehicles, are they stopped in a station allowing boarding, or moving between stations etc); we call these untimed discrete states macro states of the SHA. That is, a macro state gives (i) the positions of all vehicles in form of discrete waypoints in the TGs, (ii) which vehicles are in operation, (iii) which of them are stopped, and (iv) the run, together with the current mission, that each vehicle is executing.

Definition 1. A macro state of a TN = {G, S, I , V , X , Z, Y , P d } is a tuple M := (V + , V -, ν p , ν r ν x ), where -V + ⊆ V is the set of vehicles in operation, -V -⊆ V + is the set of stopped vehicles, -ν p : V → g∈G P (g) gives the position ν p (v) of v ∈ V , in which P (g) denotes the set of all waypoints in g ∈ G, -ν r : V + → Z gives the run ν r (v) of v ∈ V + , and -ν x : V + → X gives the mission ν x (v) of v ∈ V + .
Thus, every macro state uniquely fixes all passenger flows that are possible in it: the flow of passengers entering the system, and the flows between the GP's in the stations and the stopped vehicles, in which we assume that the passengers on-board a vehicle can alight from it iff the vehicle is stopped at a waypoint, and, according to the specification of all interfaces, that waypoint is connected to a GP in a station. Similarly, we also assume that a passenger at a platform can board a vehicle iff that vehicle is stopped at a waypoint that can be accessed from the platform.

Balance equations

The continuous dynamics in any macro state is given by a system of decoupled stochastic differential (Itô) equations for time τ ≥ 0, of the form

dX s (τ) = A s (X s (τ)) dτ + B s dW(τ), (1)
with one such equation for every station s ∈ S. In Eqn. 1, X s is the state vector of the passenger loads of (i) every GP in s, and (ii) every vehicle docked to s, i.e., every v ∈ V -that can be accessed from a GP in s due to the specification of a particular interface. Assuming that there are c 1 ∈ N >0 GPs in s and c 2 ∈ N ≥0 vehicles docked to s, then X s ∈ R m , in which m := (c 1 +c 2 ) n, and n := |Y | denotes the number of different trip profiles. A s is the drift of X s , and B s its diffusion. Finally, W denotes an n-dimensional Wiener process1 [START_REF] Szabados | An elementary introduction to the Wiener process and stochastic integrals[END_REF]. Again, note that the equations for different stations are decoupled. We obtain Eqn. 1 by setting up the balance equations for all passenger loads contributing to X s . In this context, we note that we do not have to set up separate balance equations for the complementary free capacities since they can be deduced from the capacity limits of the GPs and the vehicles, respectively. Thus, if (i) P s denotes the set of all GPs in s, (ii) V s the set of all stopped vehicles that are docked to s, and (iii) m s (k, τ), with m s : P s ∪ V s × R ≥0 → R n , the ndimensional passenger load of a GP k ∈ P s or a vehicle k ∈ V s , we can then compute its complementary free capacity m s (k, τ), with m s (k, τ) :

P s ∪ V s × R ≥0 → R, from the invariant m s k , τ = m s k, 0 + 1 T (m s (k, 0) -m s (k, τ)) .
(

) 2
Therein, 1 denotes an n-dimensional column matrix with ones only, and 1 T its transpose. Moreover, note that the domains for passenger loads and free capacities are not restricted to the positive reals in Eqn. 1; a constraint that we will explicitly enforce in its numerical computation. That being said, the balance equation for the passenger load of every k ∈ P s ∪ V s at τ ≥ 0 reads

dm s (k, τ) := t∈ • k R s (t) φ s (t, τ) dτ + D s (t) dW(τ) - t∈k • φ s (t, τ) dτ. (3)
Equation 3 relates the temporal change of m s (k, τ) to the diffusion, passenger flow, and routing matrix that come along with every passenger transfer t ∈ • k ∪ k • joining or leaving it, in which • k/k • denotes the set of all incoming/outgoing passenger transfers w.r.t. k. In particular, D s (t), D s : T s → K ∈ R n×n : K[i, j] = 0 for any i j specifies the diffusion, φ s (t, τ), φ s : T s × R ≥0 → R ≥0 n , the passenger flow, and R s (t), R s :

T s → K ∈ [0, 1] n×n : K[•, i] ∈ {0, 1} for any i ∈ {1, 2, . . . , n}
the routing of φ s (t, τ) assigned to t at τ; in which K[•, j] denotes the j-th column of a matrix K, and K[i, j] the element in the i-th row thereof. Now regarding the specification of D s , recall that uncertainty enters the TN in form of the passengers arriving at the stations from its outdoor area.

In other words, we do not know how many passengers arrive at which time and according to which trip profile. However, once having entered, the routing of every passenger including the vehicle operation is deterministic. We then demand D s to be zero for every passenger transfer (not arrival), i.e. either (i) a transfer in a station between two GPs, or (ii) a transfer between a vehicle docked to a station and a GP, or (iii) a flow of passengers leaving a station from a GP to the outdoor area of the TN. For the arrival processes, D s is a tuning parameter that modulates the variances of the multidimensional Wiener process; again, one dimension per trip profile. Then, turning towards φ s , we note that its specification depends on the particular use case as discussed in [START_REF] Haar | A hybrid-dynamical model for passenger-flow in transportation systems[END_REF]. Finally, R s is deduced from the graphical specification of all trip profiles and the re-routing of the passengers; again, compare the discussion in [START_REF] Haar | A hybrid-dynamical model for passenger-flow in transportation systems[END_REF].

Numerical integration

In practice, there are two dominant approaches to computing the temporal change of an initial distribution subjected to Eqn. 1. On the one hand, there is the Monte Carlo method [START_REF] Mackay | Introduction to monte carlo methods[END_REF]: From the pool of all possible solution paths, some paths are selected "randomly" and possibly several times [14, pp. 274-277]. In this approach, one thus would have to ensure that the correlation between the selected solution paths matches the correlation found in the actual stochastic process. Of course, this is a difficult task especially if the statistical data is not at hand, as is often the case in degraded modes of operation of TNs. The second approach is the one we will use here: Integrate the Itô process from Eqn. 1 into systems of linear parabolic partial differential equations (one for every station s ∈ S):

∂ ∂τ p s (x, τ) = - N i=1 ∂ ∂x i A s (x)[i] p s (x, τ) + 1 2 N i=1 N j=1 Ψ s [i, j] ∂ 2 ∂x i x j p s (x, τ), (4)
with A s , B s from (1) and the abbreviation Ψ s := B s B T s . This system is also known as the (multidimensional) Fokker-Planck (FP) or the Kolmogorov forward equation, and describes the time evolution of the probability density function (PDF)

p s : R m × R ≥0 → [0, ∞).
We then note that by introducing the probability flux

f s (x, τ) := A s (x) p s (x, τ) - 1 2 Ψ s                       ∂ ∂x 1 p s (x, τ) ∂ ∂x 2 p s (x, τ) . . . ∂ ∂x m p s (x, τ)                       , ( 5
)
we can rewrite Eqn. 4 and obtain the continuity equation

∂ ∂τ p s (x, τ) + div (f s (x, τ)) = 0 (6)
in its differential form. Therein,

div (f s (x, τ)) := N i=1 ∂ ∂x i f s (x, τ) (7)
denotes the divergence operation applied to the probability flux from Eqn. 5. Now from this continuity equation we can derive reflecting boundary conditions for the numerical integration of Eqn. 4 that confine the probability flux to the closed convex polytope K s ⊂ R m . Note that K s comprises all those states x ∈ R m that do not violate the capacity limits of the GPs and vehicles on the one hand, nor the non-negativity of the passenger loads themselves on the other hand. Here, we summarize only the major steps in their derivation in an informal manner, and refer to the literature [15, Chapter 5] for more details: Starting point is the insight that the cumulative probability of X s adopting a value in K s at any time instant τ ∈ R ≥0 must be one. Thus, the time derivative of this cumulative probability must be zero. Then, after some transformations employing the divergence theorem, we obtain the reflecting boundary condition

f s (x, τ) n s (x) = 0, ∀τ ∈ R ≥0 . ( 8
)
Therein, n s (x), with n s : ∂K s → R m , denotes the orthonormal vector that (i) has its origin at the state x ∈ ∂K s , i.e., the boundary of K s , and (ii) is pointing in the outward direction of K s . From this, it will be possible to compute the time evolution of the PDF subjected to Eqn. 1 starting from τ = 0, by including the initial value problem (IVP) in form of Eqn. 4, Eqn. 5, and Eqn. 8 in a numerical integration scheme such as the Crank-Nicolson method in combination with the multigrid method [START_REF] Zubair | Multigrid for high-dimensional elliptic partial differential equations on non-equidistant grids[END_REF].

At this point, note that the numerical computation of the IVP above introduces a discretization of the passenger load space, which we tried to circumvent by the fluidification of all passenger flows before. Given the highdimensionality of Eqn. [START_REF] Haar | A hybrid-dynamical model for passenger-flow in transportation systems[END_REF], this new discretization might be prohibitive assuming that no further model simplifications are made; on which we are currently working.

VEHICLE LOAD

So far, we have introduced the basic ingredients for our SHA model, provided a definition for a macro state, and shown how the SDE system from Eqn. 1 encapsulated in every macro state can be integrated into a numerical integration scheme so as to compute the time evolution of an initial PDF regarding the passenger loads at every GP in a station and on-board every vehicle docked to that station. Now we are going to integrate the numerical integration in a macro state into a computation strategy, which takes an initial estimation of the TN's load and propagates it into a target set, for prediction of the load's distribution in some time horizon.

The network load can be decomposed into a vehicle load and a passenger load, for every GP in every station and every vehicle; we introduce the vehicle load as a separate mathematical object.

Definition 2. A vehicle load of a TN = {G, S, I , Z, X , Y } is a tuple L := (M , ν dr , ν dw ), where -M is a macro state according to Def. 1, -ν dr : V + \ V -→ R ≥0 gives the elapsed driving time ν dr (v) of v ∈ V + \ V -on its way to ν p (v), and -ν dw : V -→ R ≥0 gives the elapsed dwell time ν dw (v) of v ∈ V -at ν p (v).
Thus, a vehicle v ∈ V + \ V -with its discrete position pointing to a waypoint p in a transportation grid, is not physically located at p. Rather, it is on its way to p (from its previous discrete position) but has not yet arrived.

Definition 3. A network load of a TN = {G, S, I , Z, X , Y } is a tuple Q := (L, m)
, where -L is a vehicle load according to Def. 2, and m :

s∈S P s ∪ V → R n ≥0
gives the passenger load m(a) of a ∈ P s in s ∈ S or a ∈ V , in which P s denotes the set of all GPs in s.

The prediction of the TN's load at a time instant τ 0 ∈ R ≥0 requires the computation of the probability that this network load is contained in some closed region, which is a function of time to be treated with caution. For instance, we might be interested in the probability according to which a platform will be overcrowded within half an hour and half an hour plus r ∈ N >0 minutes, starting from τ 0 . Assuming this to be true, we are then not interested in the network load at any time instant τ ∈ [τ 0 , τ 0 + 30 min) ∪ (τ 0 + 30 min + r min, ∞). In this context, note that we can always deduce the prediction horizon h := max ∆ H from the set ∆ H ⊂ 2 R ≥0 , in which 2 R ≥0 denotes the power set of R ≥0 , of alloverlapping or non-overlapping -time intervals confining the network load to a closed region as a function of time that we will call the target region; providing us an upper bound for our computation strategy: Starting from some initial network load at τ 0 , we will allow the TN to change its vehicle load (= jump of the SHA's discrete state) only at any discrete point in time τ ∈ H, in which H := {τ 0 + ∆ τ, τ 0 + 2 ∆ τ, . . . , τ 0 + γ ∆ τ}, γ := max {i ∈ N : i ∆ τ ≤ h}, and ∆ τ > 0 denotes the resolution of the prediction. However, we might not start from one particular network load, but from a set of initial network loads -denoted by L 0 -instead; in that the possibility of being present in any L ∈ L 0 at τ 0 is positive. Accordingly, the possibility of being present in any other vehicle load L L 0 is zero. Starting from any L ∈ L 0 at τ 0 , we then compute a tree that is unfolding the time evolution of the TN's vehicle load in [τ 0 , τ 0 + h]; and by merging all these trees, we derive a node-labelled digraph in form of a forest that we will call the computation space (CS) of the prediction (cf. Fig. 5):

τ 0 L 0 L 1 τ 0 + ∆ τ L 2 L 3 L 4 τ 0 + 2 ∆ τ L 5 L 6 L 7
Fig. 5: Unfolding of the time evolution of the TN's vehicle load for the prediction horizon marked with two gray shaded target nodes

The label of every node is a vehicle load, and with every arc connecting one node to another comes along with an increase of ∆ τ in the time evolution of the vehicle load. Thus, the label of every node must be a vehicle load in L 0 if it has no parent. The opposite does not necessarily hold, of course.

Finally, note that the set of all possible jumps from a vehicle load at τ ∈ H , with H := {τ 0 , τ 0 + ∆ τ, . . . , τ 0 + h -∆ τ}, to another vehicle load at τ := τ + ∆ τ can be deduced from the specification of the vehicle operation involving the deterministic resolution of all conflicting vehicle movements.

FORECASTING NETWORK LOADS

By restricting the jumps between the vehicle loads to any discrete point in time τ ∈ H, we implicitly assume that the continuous dynamics of the SHA can also only change at any τ ∈ H. In other words, if L = (M, ν dr , ν dw ) is the vehicle load at τ, then it is Eqn. 1 defined by M that defines all passenger flows in the closed time interval [τ, τ + ∆ τ]. The emphasis here is on the attribute "closed": Although, we restrict all jumps to a finite set of consecutive discrete points in time, we are still modelling a continuous-time (stochastic) process; requiring us to ensure the smooth transitioning of all continuous variables. In this context, note that we do not model any continuous-time stochastic process. In fact, Eqn. 1 is Markovian by nature, and its integration into a framework with jumps between vehicles loads gives a continuous-time Markov process again. This is true since the jump condition from a vehicle load at any time instant τ ∈ H to another vehicle load at time instant τ + ∆ τ is completely defined by the vehicle load at any time instant τ ∈ [τ -∆ τ, τ] together with the passenger loads of all GPs and vehicles. We thus can compute the prediction of the network load starting from some initial distribution at τ 0 according to the informally described algorithm:

1. Mark the set of all target nodes in the CS.

2. Invert the CS, and compute every path that is starting from a target node and reaching a node at τ 0 . 3. Invert all computed paths, compute the intersection of their union with the marked CS, and call it the reduced CS. 4. Inscribe every node at τ 0 of the reduced CS with the probability of presence of its vehicle load. 5. Numerically solve the IVP in form of Eqn. 4, Eqn. 5, and Eqn. 8 up to τ + ∆ τ for every node at τ and every s ∈ S; given the PDFs of all passenger loads at τ as input. 6. Extract the probabilities of all jumps that can occur at τ + ∆ τ from the computed PDFs at τ + ∆ τ.

Note that the PDFs in point 5) are assumed to be known for τ = τ 0 . On the contrary, the PDF for the IVP for a vehicle load L at τ > τ 0 is computed as the sum of all PDFs, that are coming along with a jump to L multiplied with the probability of that jump. Moreover, note that the probabilities of all jumps leaving a vehicle load in the reduced CS do not necessarily have to sum up to one as opposed to the jumps in the original CS.

As an example, Fig. 6 depicts a reduced CS with two gray shaded target nodes, that was derived from Fig. 5: From L 0 at τ 0 , we do only have to account for the jump to L 3 at τ 0 + ∆ τ with a probability of 0.1. From L 1 at τ 0 , however, two jumps at τ 0 + ∆ τ can occur, namely one to L 3 with a probability of 0.2, and another one to L 4 with a probability of 0.8. Thus, in the time interval [τ 0 + ∆ τ, τ 0 +2 ∆ τ] the probability of the vehicle load to be L 4 is 0.6×0.8 = 0.48, and to be L 3 is 0.4×0.1+0.6×0.2 = 0.16. Then, from reasoning, the probability to be in L 6 at τ + 2 ∆ τ must also be 0.16 since the TN's load is evolving continuously in time; requiring that the jump from L 3 to L 6 at τ 0 + 2 ∆ τ occurs with probability one. Fig. 6: Reduced CS inscribed with all jump probabilities leading to the set of target nodes (solid lines), together with those nodes and jumps (dotted lines) that belong to the original CS but can be disregarded

DISCUSSIONS

In this paper we have extended the DHA from [START_REF] Haar | A hybrid-dynamical model for passenger-flow in transportation systems[END_REF] in that we have replaced all deterministic passenger arrival processes by their stochastic counterparts for a TN at hand. We then have provided a computation strategy for the forecast of the TN's load in form of a forward reachability problem subjected to the automaton's Markovian hybrid dynamics: Starting from an initial estimation of the network load in form of some PDFs (one for every station), the strategy requires to propagate these PDFs into a target set of timed vehicle loads (= discrete modes). On the way to this target set, the propagation of the PDFs encounters jumps between the discrete modes at a priori defined equidistantly spaced discrete points in time. Within a discrete mode, the propagation is computed by numerically integrating systems of PDEs subjected to boundary conditions. Now the integration of the PDEs is known to be a difficult task, and different strategies have been developed during the last couple of years; with some approaches avoiding it at all such as the grid-based asymptotic approximation of the SDEs by Markov chains from [START_REF] Prandini | A stochastic approximation method for reachability computations[END_REF]. However, at the same time sophisticated numerical integration methods have been evolved with the multigrid method [START_REF] Zubair | Multigrid for high-dimensional elliptic partial differential equations on non-equidistant grids[END_REF] employed in our ongoing implementation. In this context, we do also consider further simplifications targeting the dimensions of the SDEs, e.g. by aggregating trip profiles with common last "miles", or by refining the discrete modes. Finally, note that -due to space limitations -we could not provide the equations that formally describe the propagation of the densities in the vehicle load tree. We intend to provide them in a future publication, though.

Fig. 4 :

 4 Fig. 4: Passenger transfer in a station between two lines including the graphical specification of four trip profiles

A continuous-time stochastic process with independent and stationary increments W t -W s whose law is Gaussian with parameter ts