Spatiotemporal Sequence Prediction With Point Processes and Self-Organizing Decision Trees.

We study the spatiotemporal prediction problem and introduce a novel point-process-based prediction algorithm. Spatiotemporal prediction is extensively studied in machine learning literature due to its critical real-life applications, such as crime, earthquake, and social event prediction. Despite these thorough studies, specific problems inherent to the application domain are not yet fully explored. Here, we address the nonstationary spatiotemporal prediction problem on both densely and sparsely distributed sequences. We introduce a probabilistic approach that partitions the spatial domain into subregions and models the event arrivals in each region with interacting point processes. Our algorithm can jointly learn the spatial partitioning and the interaction between these regions through a gradient-based optimization procedure. Finally, we demonstrate the performance of our algorithm on both simulated data and two real-life datasets. We compare our approach with baseline and state-of-the-art deep learning-based approaches, where we achieve significant performance improvements. Moreover, we also show the effect of using different parameters on the overall performance through empirical results and explain the procedure for choosing the parameters.

Multi-Label Sentiment Analysis on 100 Languages With Dynamic Weighting for Label Imbalance.

We investigate cross-lingual sentiment analysis, which has attracted significant attention due to its applications in various areas including market research, politics, and social sciences. In particular, we introduce a sentiment analysis framework in multi-label setting as it obeys Plutchik's wheel of emotions. We introduce a novel dynamic weighting method that balances the contribution from each class during training, unlike previous static weighting methods that assign non-changing weights based on their class frequency. Moreover, we adapt the focal loss that favors harder instances from single-label object recognition literature to our multi-label setting. Furthermore, we derive a method to choose optimal class-specific thresholds that maximize the macro-f1 score in linear time complexity. Through an extensive set of experiments, we show that our method obtains the state-of-the-art performance in seven of nine metrics in three different languages using a single model compared with the common baselines and the best performing methods in the SemEval competition. We publicly share our code for our model, which can perform sentiment analysis in 100 languages, to facilitate further research.

Markovian RNN: An Adaptive Time Series Prediction Network With HMM-Based Switching for Nonstationary Environments.

We investigate nonlinear regression for nonstationary sequential data. In most real-life applications such as business domains including finance, retail, energy, and economy, time series data exhibit nonstationarity due to the temporally varying dynamics of the underlying system. We introduce a novel recurrent neural network (RNN) architecture, which adaptively switches between internal regimes in a Markovian way to model the nonstationary nature of the given data. Our model, Markovian RNN employs a hidden Markov model (HMM) for regime transitions, where each regime controls hidden state transitions of the recurrent cell independently. We jointly optimize the whole network in an end-to-end fashion. We demonstrate the significant performance gains compared to conventional methods such as Markov Switching ARIMA, RNN variants and recent statistical and deep learning-based methods through an extensive set of experiments with synthetic and real-life datasets. We also interpret the inferred parameters and regime belief values to analyze the underlying dynamics of the given sequences.

Achieving Online Regression Performance of LSTMs With Simple RNNs.

Recurrent neural networks (RNNs) are widely used for online regression due to their ability to generalize nonlinear temporal dependencies. As an RNN model, long short-term memory networks (LSTMs) are commonly preferred in practice, as these networks are capable of learning long-term dependencies while avoiding the vanishing gradient problem. However, due to their large number of parameters, training LSTMs requires considerably longer training time compared to simple RNNs (SRNNs). In this article, we achieve the online regression performance of LSTMs with SRNNs efficiently. To this end, we introduce a first-order training algorithm with a linear time complexity in the number of parameters. We show that when SRNNs are trained with our algorithm, they provide very similar regression performance with the LSTMs in two to three times shorter training time. We provide strong theoretical analysis to support our experimental results by providing regret bounds on the convergence rate of our algorithm. Through an extensive set of experiments, we verify our theoretical work and demonstrate significant performance improvements of our algorithm with respect to LSTMs and the other state-of-the-art learning models.

Online Anomaly Detection With Bandwidth Optimized Hierarchical Kernel Density Estimators.

We propose a novel unsupervised anomaly detection algorithm that can work for sequential data from any complex distribution in a truly online framework with mathematically proven strong performance guarantees. First, a partitioning tree is constructed to generate a doubly exponentially large hierarchical class of observation space partitions, and every partition region trains an online kernel density estimator (KDE) with its own unique dynamical bandwidth. At each time, the proposed algorithm optimally combines the class estimators to sequentially produce the final density estimation. We mathematically prove that the proposed algorithm learns the optimal partition with kernel bandwidths that are optimized in both region-specific and time-varying manner. The estimated density is then compared with a data-adaptive threshold to detect anomalies. Overall, the computational complexity is only linear in both the tree depth and data length. In our experiments, we observe significant improvements in anomaly detection accuracy compared with the state-of-the-art techniques.

Energy-Efficient LSTM Networks for Online Learning.

We investigate variable-length data regression in an online setting and introduce an energy-efficient regression structure build on long short-term memory (LSTM) networks. For this structure, we also introduce highly effective online training algorithms. We first provide a generic LSTM-based regression structure for variable-length input sequences. To reduce the complexity of this structure, we then replace the regular multiplication operations with an energy-efficient operator, i.e., the ef-operator. To further reduce the complexity, we apply factorizations to the weight matrices in the LSTM network so that the total number of parameters to be trained is significantly reduced. We then introduce online training algorithms based on the stochastic gradient descent (SGD) and exponentiated gradient (EG) algorithms to learn the parameters of the introduced network. Thus, we obtain highly efficient and effective online learning algorithms based on the LSTM network. Thanks to our generic approach, we also provide and simulate an energy-efficient gated recurrent unit (GRU) network in our experiments. Through an extensive set of experiments, we illustrate significant performance gains and complexity reductions achieved by the introduced algorithms with respect to the conventional methods.

Unsupervised Anomaly Detection With LSTM Neural Networks.

We investigate anomaly detection in an unsupervised framework and introduce long short-term memory (LSTM) neural network-based algorithms. In particular, given variable length data sequences, we first pass these sequences through our LSTM-based structure and obtain fixed-length sequences. We then find a decision function for our anomaly detectors based on the one-class support vector machines (OC-SVMs) and support vector data description (SVDD) algorithms. As the first time in the literature, we jointly train and optimize the parameters of the LSTM architecture and the OC-SVM (or SVDD) algorithm using highly effective gradient and quadratic programming-based training methods. To apply the gradient-based training method, we modify the original objective criteria of the OC-SVM and SVDD algorithms, where we prove the convergence of the modified objective criteria to the original criteria. We also provide extensions of our unsupervised formulation to the semisupervised and fully supervised frameworks. Thus, we obtain anomaly detection algorithms that can process variable length data sequences while providing high performance, especially for time series data. Our approach is generic so that we also apply this approach to the gated recurrent unit (GRU) architecture by directly replacing our LSTM-based structure with the GRU-based structure. In our experiments, we illustrate significant performance gains achieved by our algorithms with respect to the conventional methods.

Asymptotically Optimal Contextual Bandit Algorithm Using Hierarchical Structures.

We propose an online algorithm for sequential learning in the contextual multiarmed bandit setting. Our approach is to partition the context space and, then, optimally combine all of the possible mappings between the partition regions and the set of bandit arms in a data-driven manner. We show that in our approach, the best mapping is able to approximate the best arm selection policy to any desired degree under mild Lipschitz conditions. Therefore, we design our algorithm based on the optimal adaptive combination and asymptotically achieve the performance of the best mapping as well as the best arm selection policy. This optimality is also guaranteed to hold even in adversarial environments since we do not rely on any statistical assumptions regarding the contexts or the loss of the bandit arms. Moreover, we design an efficient implementation for our algorithm using various hierarchical partitioning structures, such as lexicographical or arbitrary position splitting and binary trees (BTs) (and several other partitioning examples). For instance, in the case of BT partitioning, the computational complexity is only log-linear in the number of regions in the finest partition. In conclusion, we provide significant performance improvements by introducing upper bounds (with respect to the best arm selection policy) that are mathematically proven to vanish in the average loss per round sense at a faster rate compared to the state of the art. Our experimental work extensively covers various scenarios ranging from bandit settings to multiclass classification with real and synthetic data. In these experiments, we show that our algorithm is highly superior to the state-of-the-art techniques while maintaining the introduced mathematical guarantees and a computationally decent scalability.

Nonuniformly Sampled Data Processing Using LSTM Networks.

We investigate classification and regression for nonuniformly sampled variable length sequential data and introduce a novel long short-term memory (LSTM) architecture. In particular, we extend the classical LSTM network with additional time gates, which incorporate the time information as a nonlinear scaling factor on the conventional gates. We also provide forward-pass and backward-pass update equations for the proposed LSTM architecture. We show that our approach is superior to the classical LSTM architecture when there is correlation between time samples. In our experiments, we achieve significant performance gains with respect to the classical LSTM and phased-LSTM architectures. In this sense, the proposed LSTM architecture is highly appealing for the applications involving nonuniformly sampled sequential data.

Online Training of LSTM Networks in Distributed Systems for Variable Length Data Sequences.

In this brief, we investigate online training of long short term memory (LSTM) architectures in a distributed network of nodes, where each node employs an LSTM-based structure for online regression. In particular, each node sequentially receives a variable length data sequence with its label and can only exchange information with its neighbors to train the LSTM architecture. We first provide a generic LSTM-based regression structure for each node. In order to train this structure, we put the LSTM equations in a nonlinear state-space form for each node and then introduce a highly effective and efficient distributed particle filtering (DPF)-based training algorithm. We also introduce a distributed extended Kalman filtering-based training algorithm for comparison. Here, our DPF-based training algorithm guarantees convergence to the performance of the optimal LSTM coefficients in the mean square error sense under certain conditions. We achieve this performance with communication and computational complexity in the order of the first-order gradient-based methods. Through both simulated and real-life examples, we illustrate significant performance improvements with respect to the state-of-the-art methods.

An Online Minimax Optimal Algorithm for Adversarial Multiarmed Bandit Problem.

We investigate the adversarial multiarmed bandit problem and introduce an online algorithm that asymptotically achieves the performance of the best switching bandit arm selection strategy. Our algorithms are truly online such that we do not use the game length or the number of switches of the best arm selection strategy in their constructions. Our results are guaranteed to hold in an individual sequence manner, since we have no statistical assumptions on the bandit arm losses. Our regret bounds, i.e., our performance bounds with respect to the best bandit arm selection strategy, are minimax optimal up to logarithmic terms. We achieve the minimax optimal regret with computational complexity only log-linear in the game length. Thus, our algorithms can be efficiently used in applications involving big data. Through an extensive set of experiments involving synthetic and real data, we demonstrate significant performance gains achieved by the proposed algorithm with respect to the state-of-the-art switching bandit algorithms. We also introduce a general efficiently implementable bandit arm selection framework, which can be adapted to various applications.

Online Density Estimation of Nonstationary Sources Using Exponential Family of Distributions.

We investigate online probability density estimation (or learning) of nonstationary (and memoryless) sources using exponential family of distributions. To this end, we introduce a truly sequential algorithm that achieves Hannan-consistent log-loss regret performance against true probability distribution without requiring any information about the observation sequence (e.g., the time horizon $T$ and the drift of the underlying distribution $C$ ) to optimize its parameters. Our results are guaranteed to hold in an individual sequence manner. Our log-loss performance with respect to the true probability density has regret bounds of $O(({CT})^{1/2})$ , where $C$ is the total change (drift) in the natural parameters of the underlying distribution. To achieve this, we design a variety of probability density estimators with exponentially quantized learning rates and merge them with a mixture-of-experts notion. Hence, we achieve this square-root regret with computational complexity only logarithmic in the time horizon. Thus, our algorithm can be efficiently used in big data applications. Apart from the regret bounds, through synthetic and real-life experiments, we demonstrate substantial performance gains with respect to the state-of-the-art probability density estimation algorithms in the literature.

Efficient Online Learning Algorithms Based on LSTM Neural Networks.

We investigate online nonlinear regression and introduce novel regression structures based on the long short term memory (LSTM) networks. For the introduced structures, we also provide highly efficient and effective online training methods. To train these novel LSTM-based structures, we put the underlying architecture in a state space form and introduce highly efficient and effective particle filtering (PF)-based updates. We also provide stochastic gradient descent and extended Kalman filter-based updates. Our PF-based training method guarantees convergence to the optimal parameter estimation in the mean square error sense provided that we have a sufficient number of particles and satisfy certain technical conditions. More importantly, we achieve this performance with a computational complexity in the order of the first-order gradient-based methods by controlling the number of particles. Since our approach is generic, we also introduce a gated recurrent unit (GRU)-based approach by directly replacing the LSTM architecture with the GRU architecture, where we demonstrate the superiority of our LSTM-based approach in the sequential prediction task via different real life data sets. In addition, the experimental results illustrate significant performance improvements achieved by the introduced algorithms with respect to the conventional methods over several different benchmark real life data sets.

Sequential Nonlinear Learning for Distributed Multiagent Systems via Extreme Learning Machines.

We study online nonlinear learning over distributed multiagent systems, where each agent employs a single hidden layer feedforward neural network (SLFN) structure to sequentially minimize arbitrary loss functions. In particular, each agent trains its own SLFN using only the data that is revealed to itself. On the other hand, the aim of the multiagent system is to train the SLFN at each agent as well as the optimal centralized batch SLFN that has access to all the data, by exchanging information between neighboring agents. We address this problem by introducing a distributed subgradient-based extreme learning machine algorithm. The proposed algorithm provides guaranteed upper bounds on the performance of the SLFN at each agent and shows that each of these individual SLFNs asymptotically achieves the performance of the optimal centralized batch SLFN. Our performance guarantees explicitly distinguish the effects of data- and network-dependent parameters on the convergence rate of the proposed algorithm. The experimental results illustrate that the proposed algorithm achieves the oracle performance significantly faster than the state-of-the-art methods in the machine learning and signal processing literature. Hence, the proposed method is highly appealing for the applications involving big data.

A unified approach to universal prediction: generalized upper and lower bounds.

We study sequential prediction of real-valued, arbitrary, and unknown sequences under the squared error loss as well as the best parametric predictor out of a large, continuous class of predictors. Inspired by recent results from computational learning theory, we refrain from any statistical assumptions and define the performance with respect to the class of general parametric predictors. In particular, we present generic lower and upper bounds on this relative performance by transforming the prediction task into a parameter learning problem. We first introduce the lower bounds on this relative performance in the mixture of experts framework, where we show that for any sequential algorithm, there always exists a sequence for which the performance of the sequential algorithm is lower bounded by zero. We then introduce a sequential learning algorithm to predict such arbitrary and unknown sequences, and calculate upper bounds on its total squared prediction error for every bounded sequence. We further show that in some scenarios, we achieve matching lower and upper bounds, demonstrating that our algorithms are optimal in a strong minimax sense such that their performances cannot be improved further. As an interesting result, we also prove that for the worst case scenario, the performance of randomized output algorithms can be achieved by sequential algorithms so that randomized output algorithms do not improve the performance.

Data imputation through the identification of local anomalies.

We introduce a comprehensive and statistical framework in a model free setting for a complete treatment of localized data corruptions due to severe noise sources, e.g., an occluder in the case of a visual recording. Within this framework, we propose: 1) a novel algorithm to efficiently separate, i.e., detect and localize, possible corruptions from a given suspicious data instance and 2) a maximum a posteriori estimator to impute the corrupted data. As a generalization to Euclidean distance, we also propose a novel distance measure, which is based on the ranked deviations among the data attributes and empirically shown to be superior in separating the corruptions. Our algorithm first splits the suspicious instance into parts through a binary partitioning tree in the space of data attributes and iteratively tests those parts to detect local anomalies using the nominal statistics extracted from an uncorrupted (clean) reference data set. Once each part is labeled as anomalous versus normal, the corresponding binary patterns over this tree that characterize corruptions are identified and the affected attributes are imputed. Under a certain conditional independency structure assumed for the binary patterns, we analytically show that the false alarm rate of the introduced algorithm in detecting the corruptions is independent of the data and can be directly set without any parameter tuning. The proposed framework is tested over several well-known machine learning data sets with synthetically generated corruptions and experimentally shown to produce remarkable improvements in terms of classification purposes with strong corruption separation capabilities. Our experiments also indicate that the proposed algorithms outperform the typical approaches and are robust to varying training phase conditions.

A Deterministic Analysis of an Online Convex Mixture of Experts Algorithm.

We analyze an online learning algorithm that adaptively combines outputs of two constituent algorithms (or the experts) running in parallel to estimate an unknown desired signal. This online learning algorithm is shown to achieve and in some cases outperform the mean-square error (MSE) performance of the best constituent algorithm in the steady state. However, the MSE analysis of this algorithm in the literature uses approximations and relies on statistical models on the underlying signals. Hence, such an analysis may not be useful or valid for signals generated by various real-life systems that show high degrees of nonstationarity, limit cycles and that are even chaotic in many cases. In this brief, we produce results in an individual sequence manner. In particular, we relate the time-accumulated squared estimation error of this online algorithm at any time over any interval to the one of the optimal convex mixture of the constituent algorithms directly tuned to the underlying signal in a deterministic sense without any statistical assumptions. In this sense, our analysis provides the transient, steady-state, and tracking behavior of this algorithm in a strong sense without any approximations in the derivations or statistical assumptions on the underlying signals such that our results are guaranteed to hold. We illustrate the introduced results through examples.

Measurement of M-mode echocardiographic parameters in healthy adult Van cats.

Cardiomyopathies are the most common type of cardiac diseases in cats. Although some normal echocardiographic values for cats have been published, there are variations based on breeds and gender. The objective of this study is to determine normal reference values for M-mode echocardiographic parameters in nonsedated healthy adult Van cats and to compare those values with data reported for nonsedated healthy cats of other breeds. A total of 40 clinically healthy Van cats of both sexes belonging to the Van Cat Research and Application Center of Yuzuncu Yil University were used. Body weight (BW) and 16 M-mode echocardiographic variables were measured in 40 healthy Van cats. The effect of gender and age on each echocardiographic parameter was analyzed and the relationship between BW and each parameter investigated. There was a significant relationship between gender and left atrial dimension during ventricular systole (LAD) and aortic root dimension at end-diastole (AOD) as well as between BW and interventricular septal thickness at end-diastole (IVSd) and end-systole (IVSs), left ventricular internal dimension at end-diastole (LVIDd), left ventricular posterior wall thickness at end-diastole (LVPWd), LAD, AOD, the left ventricular end diastolic volume (EDV) and the stroke volume (SV). A relationship between age and the SV parameter alone was also established. This present study is the first work on cardiac reference values for Van cats highlighting the differences in some M-mode echocardiographic parameters of healthy adult Van cats and other cat breeds, which should be considered when interpreting echocardiographic findings, in order to draw the correct conclusions regarding cardiac health.

Glucose, lipid, and lipoprotein levels in sheep naturally infected with Fasciola hepatica.

This study was designed to investigate serum glucose, lipid, and lipoprotein in sheep naturally infected with Fasciola hepatica. Ten healthy sheep and 15 infected with F. hepatica were used in study. Serum concentrations of total protein (TP), albumin, glucose, cholesterol, triglyceride, high-density lipoprotein (HDL), low-density lipoprotein (LDL), very-low-density lipoproteins (VLDL), and serum activities of AST, ALT, GGT, and LDH were measured using a Roche-Cobas Integra 800 auto-analyzer. At day 0 (prior to treatment) and on the 28th day (after treatment) the serum concentrations of TP, albumin, glucose, cholesterol, triglyceride, HDL, LDL, and VLDL values in sheep with F. hepatica were significantly lower than those of the control group, while serum activities of AST, ALT, GGT, and LDH of lambs with F. hepatica were significantly higher than those of the control group. At day 56 (after treatment), none of the variables was significantly different between control sheep and those that received treatment for fascioliasis (P > 0.05). Nutritional management may be used to reduce the impact of fascioliasis.

Embedding and retrieving private metadata in electrocardiograms.

Due to the recent explosion of 'identity theft' cases, the safeguarding of private data has been the focus of many scientific efforts. Medical data contain a number of sensitive attributes, whose access the rightful owner would ideally like to disclose only to authorized personnel. One way of providing limited access to sensitive data is through means of encryption. In this work we follow a different path, by proposing the fusion of the sensitive metadata within the medical data. Our work is focused on medical time-series signals and in particular on Electrocardiograms (ECG). We present techniques that allow the embedding and retrieval of sensitive numerical data, such as the patient's social security number or birth date, within the medical signal. The proposed technique not only allows the effective hiding of the sensitive metadata within the signal itself, but it additionally provides a way of authenticating the data ownership or providing assurances about the origin of the data. Our methodology builds upon watermarking notions, and presents the following desirable characteristics: (a) it does not distort important ECG characteristics, which are essential for proper medical diagnosis, (b) it allows not only the embedding but also the efficient retrieval of the embedded data, (c) it provides resilience and fault tolerance by employing multistage watermarks (both robust and fragile). Our experiments on real ECG data indicate the viability of the proposed scheme.