Theses supervised by Doç. Dr. Süleyman Serdar Kozat
10 theses · İhsan Doğramacı Bilkent University
Çekişmeli ortamlarda bağlamsal haydut problemi için asimptotik olarak en uygun çözüm
We propose online algorithms for sequential learning in the contextual multi-armed 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 algorithms 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 efficient implementations for our algorithms in various hierarchical partitioning structures such as lexicographical or arbitrary position splitting and binary trees (and several other partitioning examples). For instance, in the case of binary tree 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 (w.r.t. 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 multi-class classification with real and synthetic data. In these experiments, we show that our algorithms are highly superior over the state-of-the-art techniques while maintaining the introduced mathematical guarantees and a computationally decent scalability.
Yinelenen sinir ağları ile çevrimiçi öğrenim
In this thesis, we study online learning with Recurrent Neural Networks (RNNs). Particularly, in Chapter 2, we investigate online nonlinear regression and introduce novel regression structures based on the Long Short Term Memory (LSTM) network, i.e., is an advanced RNN architecture. To train these novel LSTM based structures, we introduce highly efficient and e ffective Particle Filtering (PF) based updates. We also provide Stochastic Gradient Descent (SGD) and Extended Kalman Filter (EKF) based updates. Our PF based training method guarantees convergence to the optimal parameter estimation in the Mean Square Error (MSE) sense. In Chapter 3, we investigate online training of LSTM architectures in a distributed network of nodes, where each node employs an LSTM based structure for online regression. We first provide a generic LSTM based regression structure for each node. In order to train this structure, we introduce a highly e ffective and efficient Distributed PF (DPF) based training algorithm. We also introduce a Distributed EKF (DEKF) based training algorithm. Here, our DPF based training algorithm guarantees convergence to the performance of the optimal centralized LSTM parameters in the MSE sense. In Chapter 4, we investigate variable length data regression in an online setting and introduce an energy efficient regression structure build on LSTM networks. To reduce the complexity of this structure, we first replace the regular multiplication operations with an energy e cient operator. We then apply factorizations to the weight matrices so that the total number of parameters to be trained is signi ficantly reduced. We then introduce online training algorithms. Through a set of experiments, we illustrate signi cant performance gains and complexity reductions achieved by the introduced algorithms with respect to the state of the art methods.
UKSB ağları ile düşük karmaşıklığa sahip verimli çevrimiçi öğrenme algoritmaları
In this thesis, we implement efficient online learning algorithms using the Long Short Term Memory (LSTM) networks with low time and computational complexity. In Chapter 2, we investigate efficient covariance information-based online learning using the LSTM networks known as Co-LSTM networks. We utilize the covariance information into the LSTM gating structure and propose various efficient models. We reduce the computational complexity by applying the Weight Matrix Factorization (WMF) trick and derive the additive gradient based updates. In Chapter 3, we give a practical application of the network intrusion detection using the Co-LSTM networks. In Chapter 4, we propose a boosted binary version of Tree-LSTM networks which we call BBT-LSTM networks. We introduce the depth and windowing factor into the N-ary Tree-LSTM networks where each LSTM node is binarily split and the whole tree architecture grows in a balanced manner. In order to reduce the computational complexity of the BBT-LSTM networks, we apply WMF trick, replace the regular multiplication operator with the energy efficient operator and finally introduce the slicing operation on the BBT-LSTM network weight matrices. In Chapter 5, we propose another low complexity LSTM network based on a minimum number of hopping over the input data sequence. We study two methods to select the appropriate value of the hopping distance. Through an extensive set of experiments using the real-life data sets, we demonstrate the significant increase in the performance of the proposed algorithms at the end of each chapter.
Karşıt koşullar altında çevrimiçi öğrenme
We present novel solutions for contemporary real life applications that generate data at unforeseen rates in unpredictable forms including non-stationarity, corruptions, missing/mixed attributes and high dimensionality. In particular, we introduce novel algorithms for online learning, where the observations are received sequentially and processed only once without being stored, under adverse settings: i) no or limited assumptions can be made about the data source, ii) the observations can be corrupted and iii) the data is to be processed at extremely fast rates. The introduced algorithms are highly effective and efficient with strong mathematical guarantees; and are shown, through the presented comprehensive real life experiments, to significantly outperform the competitors under such adverse conditions. We develop a novel highly dynamical ensemble method without any stochastic assumptions on the data source. The presented method is asymptotically guaranteed to perform as well as, i.e., competitive against, the best expert in the ensemble, where the competitor, i.e., the best expert, itself is also specifically designed to continuously improve over time in a completely data adaptive manner. In addition, our algorithm achieves a significantly superior modeling power (hence, a significantly superior prediction performance) through a hierarchical and self-organizing approach while mitigating over training issues by combining (taking finite unions of) low-complexity methods. On the contrary, the state-of-the-art ensemble techniques are heavily dependent on static and unstructured expert ensembles. In this regard, we rigorously solve the resulting issues such as the over sensitivity to source statistics as well as the incompatibility between the modeling power and the computational load/precision. Our results uniformly hold for every possible input stream in the deterministic sense regardless of the stationary or non-stationary source statistics. Furthermore, we directly address the data corruptions by developing novel versatile imputation methods and thoroughly demonstrate that the anomaly detection -in addition to being stand alone an important learning problem- is extremely effective for corruption detection/imputation purposes. To that end, as the first time in the literature, we develop the online implementation of the Neyman-Pearson characterization for anomalies in stationary or non-stationary fast streaming temporal data. The introduced anomaly detection algorithm maximizes the detection power at a specified controllable constant false alarm rate with no parameter tuning in a truly online manner. Our algorithms can process any streaming data at extremely fast rates without requiring a training phase or a priori information while bearing strong performance guarantees. Through extensive experiments over real/synthetic benchmark data sets, we also show that our algorithms significantly outperform the state-of-the-art as well as the most recently proposed techniques in the literature with remarkable adaptation capabilities to non-stationarity.
Dağıtılmış ağ üzerinde online öğrenme
We study online learning strategies over distributed networks. Here, we have a distributed collection of agents with learning and cooperation capabilities. These agents observe a noisy version of a desired state of the nature through a linear model. The agents seek to learn this state by also interacting with each other yet the communication load plays significant role. To this end, we propose compressive diffusion strategies that extract the compressed information from the diffused data. Agents can compress the information into a scalar or a single bit, i.e., a substantial reduction in the communication load. Importantly, we show that agents can achieve a comparable performance to the conventional diffusion strategies that require the direct diffusion of information without compression and with infinite precision. We also examine which information to disclose and how to utilize them optimally in the mean-square-error (MSE) sense. Note that all the well-known distributed learning strategies achieve suboptimal learning performance in the MSE sense. Hence, we provide algorithms that achieve distributed minimum MSE (MMSE) performance over an arbitrary network topology based on the aggregation of information at each agent. This approach differs from the diffusion of information across network, i.e., exchange of local estimates. Notably, exchange of local estimates is sufficient only over the certain network topologies. For these networks, we also propose strategies that achieve the distributed MMSE performance through the diffusion of information. Hence, we can substantially reduce the communication load while achieving the best possible MSE performance. Finally, for practical implementations we provide approaches to reduce the complexity of the algorithms through the time-windowing of the observations.
Düşük iletişim yüklü olay-tetikli dağıtık kestirim
We propose a novel algorithm for distributed processing applications constrained by the available communication resources using diffusion strategies that achieves up to a 10^3 fold reduction in the communication load over the network, while delivering a comparable performance with respect to the state of the art. After the computation of the local estimates, the information is diffused among the processing elements (or nodes) non-uniformly in time by conditioning the information transfer on level-crossings of the diffused parameter, resulting in a greatly reduced communication requirement. We provide the mean and mean-square stability analyses of the proposed algorithm, and illustrate the gain in communication efficiency compared to other reduced-communication distributed estimation schemes.
İkinci dereceden yöntemler ile ardışık bağlanım teknikleri
Sequential regression problem is one of the widely investigated topics in the machine learning and the signal processing literatures. In order to adequately model the underlying structure of the real life data sequences, many regression methods employ nonlinear modeling approaches. In this context, in the first chapter, we introduce highly efficient sequential nonlinear regression algorithms that are suitable for real life applications. We process the data in a truly online manner such that no storage is needed. For nonlinear modeling we use a hierarchical piecewise linear approach based on the notion of decision trees where the space of the regressor vectors is adaptively partitioned. As the first time in the literature, we learn both the piecewise linear partitioning of the regressor space as well as the linear models in each region using highly effective second order methods, i.e., Newton-Raphson Methods. Hence, we avoid the well-known over fi tting issues by using piecewise linear models and achieve substantial performance compared to the state of the art. In the second chapter, we investigate the problem of sequential prediction for real life big data applications. The second order Newton-Raphson methods asymptotically achieve the performance of the "best" possible predictor much faster compared to the fi rst order algorithms. However, their usage in real life big data applications is prohibited because of the extremely high computational needs. To this end, in order to enjoy the outstanding performance of the second order methods, we introduce a highly efficient implementation where the computational complexity is reduced from quadratic to linear scale. For both chapters, we demonstrate our gains over the well-known benchmark and real life data sets and provide performance results in an individual sequence manner guaranteed to hold without any statistical assumptions.
Tekrarlamalı sinir ağları ve heceleri kullanarak metin sınıflandırma
We investigate multi class categorization of short texts. To this end, in the third chapter, we introduce highly efficient dimensionality reduction techniques suitable for online processing of high dimensional feature vectors generated from freely-worded text. Although text processing and classification are highly important due to many applications such as emotion recognition, advertisement selection, etc., online classification and regression algorithms over text are limited due to need for high dimensional vectors to represent natural text inputs. We overcome such limitations by showing that randomized projections and piecewise linear models can be efficiently leveraged to significantly reduce the computational cost for feature vector extraction from the tweets. We demonstrate our results over tweets collected from a real life case study where the tweets are freely-worded and unstructured. We implement several well-known machine learning algorithms as well as novel regression methods and demonstrate that we can significantly reduce the computational complexity with insignificant change in the classification and regression performance. Furthermore, in the fourth chapter, we introduce a simple and novel technique for short text classification based on LSTM neural networks. Our algorithm obtains two distributed representations for a short text to be used in classification task. We derive one representation by processing vector embeddings corresponding to words consecutively in LSTM structure and taking average of the produced outputs at each time step of the network. We also take average of distributed representations of the words in the short text to obtain the other representation. For classification, weighted combination of both representations are calculated. Moreover, for the first time in literature we propose to use syllables to exploit the sequential nature of the data in a better way. We derive distributed representations of the syllables and feed them to an LSTM network to obtain the distributed representation for the short text. Softmax layer is used to calculate categorical distribution at the end. Classification performance is evaluated in terms of AUC measure. Experiments show that utilizing two distributed representations improves classification performance by ≈ 2%. Furthermore, we demonstrate that using distributed representations of syllables in short text categorization also provides performance improvements.
Durağan olmayan ortamlarda çevrimiçi minimaks optimal yoğunluk tahmini ve anomali tespiti
Online anomaly detection has attracted significant attention in recent years due to its applications in network monitoring, cybersecurity, surveillance and sensor failure. To this end, we introduce an algorithm that sequentially processes data to detect anomalies in time series. Our algorithm consists of two stages: density estimation and anomaly detection. First, we construct a probability density function to model the normal data. Then, we threshold the density of the newly observed data to detect anomalies. We approach this problem from an information theoretic perspective and, for the first time in the literature, propose minimax optimal schemes for both stages to create an optimal anomaly detection algorithm in a strong deterministic sense. For the first stage, we introduce an online density estimator that is minimax optimal for general nonstationary exponential-family of distributions without any assumptions on the observation sequence. Our algorithm does not require a priori knowledge of the time horizon, the drift of the underlying distribution or the time instances the parameters of the source changes. Our results are guaranteed to hold in an individual sequence manner. For the second stage, we propose an online threshold selection scheme that has logarithmic performance bounds against the best threshold chosen in hindsight. Our complete algorithm adaptively updates its parameters in a truly sequential manner to achieve log-linear regrets in both stages. Because of its universal prediction perspective on its density estimation, our anomaly detection algorithm can be used in unsupervised, semi-supervised and supervised manner. Through synthetic and real life experiments, we demonstrate substantial performance gains with respect to the state-of-the-art.
Sualti akustik kanal kestiriminde sağlam adaptif algoritmalar ve performans analizi
We introduce a novel family of adaptive robust channel estimators for highly challenging underwater acoustic channels. Since the underwater environment is highly non-stationary and subjected to impulsive noise, we use adaptive iterating techniques based on minimization of a logarithmic cost function, which results in a better trade-off between the convergence rate and the steady state performance of the algorithm. To improve the convergence performance of the conventional first and second order linear estimation methods while mitigating the stability issues related to impulsive noise, we intrinsically combine different norms of the error in the cost function using a logarithmic term. Hence, we achieve a comparable convergence rate to the faster algorithms, while significantly enhancing the stability against impulsive noise in such an adverse communication medium. Furthermore, we provide a thorough analysis for the tracking and steady-state performances of our proposed methods in the presence of impulsive noise. In our analysis, we not only consider the impulsive noise but also take into account the frequency and phase offsets commonly experienced in real life experiments. We demonstrate the performance of our algorithms through highly realistic experiments performed on accurately simulated underwater acoustic channels.