Domains such as bio-informatics, social network analysis, and computer vision, describe relations between entities and cannot be interpreted as vectors or fixed grids, instead, they are naturally represented by graphs. Often this kind of data evolves over time in a dynamic world, respecting a temporal order being known as temporal graphs. The latter became a challenge since subgraph patterns are very difficult to find and the distance between those patterns may change irregularly over time. While state-of-the-art methods are primarily designed for static graphs and may not capture temporal information, recent works have proposed mapping temporal graphs to static graphs to allow for the use of conventional static kernels and graph neural approaches. In this study, we compare the transitive reduction impact on these mappings in terms of accuracy and computational efficiency across different classification tasks. Furthermore, we introduce a novel mapping method using a transitive reduction approach that outperforms existing techniques in terms of classification accuracy. Our experimental results demonstrate the effectiveness of the proposed mapping method in improving the accuracy of supervised classification for temporal graphs while maintaining reasonable computational efficiency.

This paper deals with imbalanced time series classification problems. In particular, we propose to learn time series classifiers that maximize the minimum recall of the classes rather than the accuracy. Consequently, we manage to obtain classifiers which tend to give the same importance to all the classes. Unfortunately, for most of the traditional classifiers, learning to maximize the minimum recall of the classes is not trivial (if possible), since it can distort the nature of the classifiers themselves. Neural networks, in contrast, are classifiers that explicitly define a loss function, allowing it to be modified. Given that the minimum recall is not a differentiable function, and therefore does not allow the use of common gradient-based learning methods, we apply and evaluate several smooth approximations of the minimum recall function. A thorough experimental evaluation shows that our approach improves the performance of state-of-the-art methods used in imbalanced time series classification, obtaining higher recall values for the minority classes, incurring only a slight loss in accuracy.

Times series classification can be successfully tackled by jointly learning a shapelet-based representation of the series in the dataset and classifying the series according to this representation. This shapelet-based classification is both accurate and explainable since the shapelets are time series themselves and thus can be visualized and be provided as a classification explanation. In this paper, we claim that not all shapelets are good visual explanations and we propose a simple, yet also accurate, adversarily regularized EXplainable Convolutional Neural Network, XCNN, that can learn shapelets that are, by design, suited for explanations. We validate our method on the usual univariate time series benchmarks of the UCR repository.

Image segmentation consists in creating partitions within an image into meaningful areas and objects. It can be used in scene understanding and recognition, in fields like biology, medicine, robotics, satellite imaging, amongst others. In this work we take advantage of the learned model in a deep architecture, by extracting side-outputs at different layers of the network for the task of image segmentation. We study the impact of the amount of side-outputs and evaluate strategies to combine them. A post-processing filtering based on mathematical morphology idempotent functions is also used in order to remove some undesirable noises. Experiments were performed on the publicly available KITTI Road Dataset for image segmentation. Our comparison shows that the use of multiples side outputs can increase the overall performance of the network, making it easier to train and more stable when compared with a single output in the end of the network. Also, for a small number of training epochs (500), we achieved a competitive performance when compared to the best algorithm in KITTI Evaluation Server.

A family of algorithms for time series classification (TSC) involve running a sliding window across each series, discretising the window to form a word, forming a histogram of word counts over the dictionary, then constructing a classifier on the histograms. A recent evaluation of two of this type of algorithm, Bag of Patterns (BOP) and Bag of Symbolic Fourier Approximation Symbols (BOSS) found a significant difference in accuracy between these seemingly similar algorithms. We investigate this phenomenon by deconstructing the classifiers and measuring the relative importance of the four key components between BOP and BOSS. We find that whilst ensembling is a key component for both algorithms, the effect of the other components is mixed and more complex. We conclude that BOSS represents the state of the art for dictionary-based TSC. Both BOP and BOSS can be classed as bag of words approaches. These are particularly popular in Computer Vision for tasks such as image classification. We adapt three techniques used in Computer Vision for TSC: Scale Invariant Feature Transform; Spatial Pyramids; and Histogram Intersection. We find that using Spatial Pyramids in conjunction with BOSS (SP) produces a significantly more accurate classifier. SP is significantly more accurate than standard benchmarks and the original BOSS algorithm. It is not significantly worse than the best shapelet-based or deep learning approaches, and is only outperformed by an ensemble that includes BOSS as a constituent module.

The adequate operation of IPTV distribution networks heavily relies on the effective maintenance and management of their underlay DSL infrastructure. New hardware and software is required in order to improve monitoring capabilities and to directly diagnose anomalies that other segments of the DSL network cannot identify. In this work we initially compare the accuracy performance of SVM-specific formulations for constructing a robust ground truth within our classification procedure regarding abnormalities issued at anomaly-aware Digital Subscriber Line Access Multiplexers (DSLAMs) of the DSL infrastructure. Moreover, we consider the pragmatic cost of repairing anomalies that were misclassified and characterize each classifier according to the overall cost that is possible to incur to the network operator. In parallel, this work attempts to practically improve the network-wide anomaly classification performance by proposing a semi-supervised classification scheme that updates the initial supervised scheme by testing unlabelled anomalies occurring at anomaly-unaware DSLAMs.

IPTV networks blindly rely on the adequate operation and management of the underlying infrastructure that in numerous cases is threaten by unexpected anomalous events which consequently cause QoS degradation to the end-user. Thus, it is of great importance to deploy techniques embodied with diagnostic and self-protection metrics for determining and predicting the arrival of such events in order to proactively charge defense mechanisms without the need of an exhaustive manual inspection by the network operator. In this paper we propose and demonstrate the applicability of the Rényi entropy as a useful diagnosis feature for explicitly characterizing DSL-level anomalies issued in an IPTV network of a large European ISP. It is revealed that different orders of the Rényi entropy can formulate meaningful detection and categorization of phenomena occurring on specific Digital Subscriber Line Access Multiplexers (DSLAMs) within the DSL infrastructure. Via the synergistic exploitation of the local maxima peaks generated by each Rényi-based distribution we exhibit the feasibility to extract and identify lightweight anomalies that under simple metrics cannot be detected.

This paper considers the use of punctured quasi-arithmetic (QA) codes for the Slepian-Wolf problem. These entropy codes are defined by finite state machines for memory-less and first-order memory sources. Puncturing an entropy coded bit-stream leads to an ambiguity at the decoder side. The decoder makes use of a correlated version of the original in order to remove this ambiguity. A complete DSC scheme based on QA encoding with side information at the decoder is presented. The proposed scheme is adapted to memoryless and first-order memory sources. Simulation results reveal that the proposed scheme is efficient in terms of decoding performance for short sequences compared to well-known DSC using channel codes.

Optimum soft decoding of sources compressed with variable length codes and quasi-arithmetic codes, transmitted over noisy channels, can be performed on a bit/symbol trellis. However, the number of states of the trellis is a quadratic function of the sequence length leading to a decoding complexity which is not tractable for practical applications. The decoding complexity can be significantly reduced by using an aggregated state model, while still achieving close to optimum performance in terms of bit error rate and frame error rate. However, symbol a posteriori probabilities can not be directly derived on these models and the symbol error rate (SER) may not be minimized. This paper describes a two-step decoding algorithm that achieves close to optimal decoding performance in terms of SER on aggregated state models. A performance and complexity analysis of the proposed algorithm is given.

This paper describes Slepian-Wolf codes based on overlapped quasi-arithmetic codes, where overlapping allows lossy compression of the source below its entropy. In the context of separate decoding, these codes are not uniquely decodable: the overlap introduces ambiguity in the decoding process leading to decoding errors. The presence of correlated side information at the decoder is used to remove this ambiguity and achieve a vanishing error probability. The state models and the automata of the overlapped quasi-arithmetic codes are described. The soft decoding algorithm with side information is then presented. The performance of these codes has been assessed first on theoretical sources and integrated in a distributed video coding platform.

Variable length codes (VLCs) exhibit loss of synchronization problems when transmitted over noisy channels. Trellis decoding techniques based on Maximum A Posteriori (MAP) estimators are often used to minimize the error rate on the estimated sequence. If the number of symbols and/or bits transmitted is known by the decoder, termination constraints can be incorporated in the decoding process. All the paths in the trellis which do not lead to a valid sequence length are suppressed. This correspondence presents an analytic method to assess the expected error resilience of a VLC when trellis decoding with a sequence length constraint is used. The approach is based on the computation, for a given code, of the amount of information brought by the constraint. It is then shown that this quantity is not significantly altered by appropriate trellis states aggregation. This proves that the performance obtained by running a length-constrained Viterbi decoder on aggregated state models approaches the one obtained with the bit/symbol trellis, with a significantly reduced complexity. It is then shown that the complexity can be further decreased by projecting the state model on two state models of reduced size.

In this paper, we propose a method to analyse the error recovery properties of quasi-arithmetic codes. This method is adapted from the one proposed in J. Maxted and J. Robinson (1985) for variable length codes. The expected number of symbols affected by a single bit error and the probability mass function of the gain/loss (P.F. Swaszek and P. DiCicco, 1995) of symbols following a single bit error can be computed with this method. A method to estimate this probability mass function when a bitstream is sent over a binary symmetrical channel is then proposed. The aggregated state model for soft decoding of variable length codes proposed in H. Jegou et al. (2005) is then extended to quasi-arithmetic codes, as the synchronisation recovery properties of both kind of codes are similar. The soft decoding results of this scheme reveal high performance with a reasonable computing cost