OpenRaiser/Intern-Atlas huggingface dataset:
Approximate Clustering with Same-Cluster Queries
Venue: arXiv cs.DS 2017
Year: 2017

Ashtiani et al. proposed a Semi-Supervised Active Clustering framework (SSAC), where the learner is allowed to make adaptive queries to a domain expert. The queries are of the kind "do two given points belong to the same optimal cluster?" There are many clustering contexts where such same-cluster queries are feasible. Ashtiani et al. exhibited the power of such queries by showing that any instance of the $k$-means clustering problem, with additional margin assumption, can be solved efficiently if one is allowed $O(k^2 \log{k} + k \log{n})$ same-cluster queries. This is interesting since the $k$-means problem, even with the margin assumption, is $\mathsf{NP}$-hard. In this paper, we extend the work of Ashtiani et al. to the approximation setting showing that a few of such same-cluster queries enables one to get a polynomial-time $(1 + \varepsilon)$-approximation algorithm for the $k$-means problem without any margin assumption on the input dataset. Again, this is interesting since the $k$-means problem is $\mathsf{NP}$-hard to approximate within a factor $(1 + c)$ for a fixed constant $0 < c < 1$. The number of same-cluster queries used is $\textrm{poly}(k/\varepsilon)$ which is independent of the size $n$ of the dataset. Our algorithm is based on the $D^2$-sampling technique. We also give a conditional lower bound on the number of same-cluster queries showing that if the Exponential Time Hypothesis (ETH) holds, then any such efficient query algorithm needs to make $Ω\left(\frac{k}{poly \log k} \right)$ same-cluster queries. Our algorithm can be extended for the case when the oracle is faulty. Another result we show with respect to the $k$-means++ seeding algorithm is that a small modification to the $k$-means++ seeding algorithm within the SSAC framework converts it to a constant factor approximation algorithm instead of the well known $O(\log{k})$-approximation algorithm.
A Bayesian algorithm for distributed network localization using distance and direction data
Venue: arXiv cs.IT 2017
Year: 2017

A reliable, accurate, and affordable positioning service is highly required in wireless networks. In this paper, the novel Message Passing Hybrid Localization (MPHL) algorithm is proposed to solve the problem of cooperative distributed localization using distance and direction estimates. This hybrid approach combines two sensing modalities to reduce the uncertainty in localizing the network nodes. A statistical model is formulated for the problem, and approximate minimum mean square error (MMSE) estimates of the node locations are computed. The proposed MPHL is a distributed algorithm based on belief propagation (BP) and Markov chain Monte Carlo (MCMC) sampling. It improves the identifiability of the localization problem and reduces its sensitivity to the anchor node geometry, compared to distance-only or direction-only localization techniques. For example, the unknown location of a node can be found if it has only a single neighbor; and a whole network can be localized using only a single anchor node. Numerical results are presented showing that the average localization error is significantly reduced in almost every simulation scenario, about 50% in most cases, compared to the competing algorithms.
The Interplay of Semantics and Morphology in Word Embeddings
Venue: arXiv cs.CL 2017
Year: 2017

We explore the ability of word embeddings to capture both semantic and morphological similarity, as affected by the different types of linguistic properties (surface form, lemma, morphological tag) used to compose the representation of each word. We train several models, where each uses a different subset of these properties to compose its representations. By evaluating the models on semantic and morphological measures, we reveal some useful insights on the relationship between semantics and morphology.
An Automated Text Categorization Framework based on Hyperparameter Optimization
Venue: arXiv cs.CL 2017
Year: 2017

A great variety of text tasks such as topic or spam identification, user profiling, and sentiment analysis can be posed as a supervised learning problem and tackle using a text classifier. A text classifier consists of several subprocesses, some of them are general enough to be applied to any supervised learning problem, whereas others are specifically designed to tackle a particular task, using complex and computational expensive processes such as lemmatization, syntactic analysis, etc. Contrary to traditional approaches, we propose a minimalistic and wide system able to tackle text classification tasks independent of domain and language, namely microTC. It is composed by some easy to implement text transformations, text representations, and a supervised learning algorithm. These pieces produce a competitive classifier even in the domain of informally written text. We provide a detailed description of microTC along with an extensive experimental comparison with relevant state-of-the-art methods. mircoTC was compared on 30 different datasets. Regarding accuracy, microTC obtained the best performance in 20 datasets while achieves competitive results in the remaining 10. The compared datasets include several problems like topic and polarity classification, spam detection, user profiling and authorship attribution. Furthermore, it is important to state that our approach allows the usage of the technology even without knowledge of machine learning and natural language processing.
Probabilistic Recurrence Relations for Work and Span of Parallel Algorithms
Venue: arXiv cs.DS 2017
Year: 2017

In this paper we present a method for obtaining tail-bounds for random variables satisfying certain probabilistic recurrences that arise in the analysis of randomized parallel divide and conquer algorithms. In such algorithms, some computation is initially done to process an input x, which is then randomly split into subproblems $h_1(x), ..., h_n(x)$, and the algorithm proceeds recursively in parallel on each subproblem. The total work on input x, W(x), then satisfies a probabilistic recurrence of the form $W(x) = a(x) + \sum_{i=1}^n W (h_i(x))$, and the span (the longest chain of sequential dependencies), satisfies $S(x) = b(x) + \max_{i=1}^n S(h_i(x))$, where a(x) and b(x) are the work and span to split x and combine the results of the recursive calls. Karp has previously presented methods for obtaining tail-bounds in the case when n = 1, and under certain stronger assumptions for the work-recurrence when n > 1, but left open the question of the span-recurrence. We first show how to extend his technique to handle the span-recurrence. We then show that in some cases, the work-recurrence can be bounded under simpler assumptions than Karp's by transforming it into a related span-recurrence and applying our first result. We demonstrate our results by deriving tail bounds for the work and span of quicksort and the height of a randomly generated binary search tree.
Improving content marketing processes with the approaches by artificial intelligence
Venue: arXiv cs.AI 2017
Year: 2017

Content marketing is todays one of the most remarkable approaches in the context of marketing processes of companies. Value of this kind of marketing has improved in time, thanks to the latest developments regarding to computer and communication technologies. Nowadays, especially social media based platforms have a great importance on enabling companies to design multimedia oriented, interactive content. But on the other hand, there is still something more to do for improved content marketing approaches. In this context, objective of this study is to focus on intelligent content marketing, which can be done by using artificial intelligence. Artificial Intelligence is todays one of the most remarkable research fields and it can be used easily as multidisciplinary. So, this study has aimed to discuss about its potential on improving content marketing. In detail, the study has enabled readers to improve their awareness about the intersection point of content marketing and artificial intelligence. Furthermore, the authors have introduced some example models of intelligent content marketing, which can be achieved by using current Web technologies and artificial intelligence techniques.
CCL: Cross-modal Correlation Learning with Multi-grained Fusion by Hierarchical Network
Venue: arXiv cs.MM 2017
Year: 2017

Cross-modal retrieval has become a highlighted research topic for retrieval across multimedia data such as image and text. A two-stage learning framework is widely adopted by most existing methods based on Deep Neural Network (DNN): The first learning stage is to generate separate representation for each modality, and the second learning stage is to get the cross-modal common representation. However, the existing methods have three limitations: (1) In the first learning stage, they only model intra-modality correlation, but ignore inter-modality correlation with rich complementary context. (2) In the second learning stage, they only adopt shallow networks with single-loss regularization, but ignore the intrinsic relevance of intra-modality and inter-modality correlation. (3) Only original instances are considered while the complementary fine-grained clues provided by their patches are ignored. For addressing the above problems, this paper proposes a cross-modal correlation learning (CCL) approach with multi-grained fusion by hierarchical network, and the contributions are as follows: (1) In the first learning stage, CCL exploits multi-level association with joint optimization to preserve the complementary context from intra-modality and inter-modality correlation simultaneously. (2) In the second learning stage, a multi-task learning strategy is designed to adaptively balance the intra-modality semantic category constraints and inter-modality pairwise similarity constraints. (3) CCL adopts multi-grained modeling, which fuses the coarse-grained instances and fine-grained patches to make cross-modal correlation more precise. Comparing with 13 state-of-the-art methods on 6 widely-used cross-modal datasets, the experimental results show our CCL approach achieves the best performance.
Modeling and Analysis of HetNets with mm-Wave Multi-RAT Small Cells Deployed Along Roads
Venue: arXiv cs.IT 2017
Year: 2017

We characterize a multi tier network with classical macro cells, and multi radio access technology (RAT) small cells, which are able to operate in microwave and millimeter-wave (mm-wave) bands. The small cells are assumed to be deployed along roads modeled as a Poisson line process. This characterization is more realistic as compared to the classical Poisson point processes typically used in literature. In this context, we derive the association and RAT selection probabilities of the typical user under various system parameters such as the small cell deployment density and mm-wave antenna gain, and with varying street densities. Finally, we calculate the signal to interference plus noise ratio (SINR) coverage probability for the typical user considering a tractable dominant interference based model for mm-wave interference. Our analysis reveals the need of deploying more small cells per street in cities with more streets to maintain coverage, and highlights that mm-wave RAT in small cells can help to improve the SINR performance of the users.
Network Slicing to Enable Scalability and Flexibility in 5G Mobile Networks
Venue: arXiv cs.NI 2017
Year: 2017

We argue for network slicing as an efficient solution that addresses the diverse requirements of 5G mobile networks, thus providing the necessary flexibility and scalability associated with future network implementations. We elaborate on the challenges that emerge when we design 5G networks based on network slicing. We focus on the architectural aspects associated with the coexistence of dedicated as well as shared slices in the network. In particular, we analyze the realization options of a flexible radio access network with focus on network slicing and their impact on the design of 5G mobile networks. In addition to the technical study, this paper provides an investigation of the revenue potential of network slicing, where the applications that originate from such concept and the profit capabilities from the network operator's perspective are put forward.
Egocentric Video Description based on Temporally-Linked Sequences
Venue: arXiv cs.CV 2017
Year: 2017

Egocentric vision consists in acquiring images along the day from a first person point-of-view using wearable cameras. The automatic analysis of this information allows to discover daily patterns for improving the quality of life of the user. A natural topic that arises in egocentric vision is storytelling, that is, how to understand and tell the story relying behind the pictures. In this paper, we tackle storytelling as an egocentric sequences description problem. We propose a novel methodology that exploits information from temporally neighboring events, matching precisely the nature of egocentric sequences. Furthermore, we present a new method for multimodal data fusion consisting on a multi-input attention recurrent network. We also publish the first dataset for egocentric image sequences description, consisting of 1,339 events with 3,991 descriptions, from 55 days acquired by 11 people. Furthermore, we prove that our proposal outperforms classical attentional encoder-decoder methods for video description.
Variance Based Moving K-Means Algorithm
Venue: arXiv cs.LG 2017
Year: 2017

Clustering is a useful data exploratory method with its wide applicability in multiple fields. However, data clustering greatly relies on initialization of cluster centers that can result in large intra-cluster variance and dead centers, therefore leading to sub-optimal solutions. This paper proposes a novel variance based version of the conventional Moving K-Means (MKM) algorithm called Variance Based Moving K-Means (VMKM) that can partition data into optimal homogeneous clusters, irrespective of cluster initialization. The algorithm utilizes a novel distance metric and a unique data element selection criteria to transfer the selected elements between clusters to achieve low intra-cluster variance and subsequently avoid dead centers. Quantitative and qualitative comparison with various clustering techniques is performed on four datasets selected from image processing, bioinformatics, remote sensing and the stock market respectively. An extensive analysis highlights the superior performance of the proposed method over other techniques.
EELECTION at SemEval-2017 Task 10: Ensemble of nEural Learners for kEyphrase ClassificaTION
Venue: arXiv cs.CL 2017
Year: 2017

This paper describes our approach to the SemEval 2017 Task 10: "Extracting Keyphrases and Relations from Scientific Publications", specifically to Subtask (B): "Classification of identified keyphrases". We explored three different deep learning approaches: a character-level convolutional neural network (CNN), a stacked learner with an MLP meta-classifier, and an attention based Bi-LSTM. From these approaches, we created an ensemble of differently hyper-parameterized systems, achieving a micro-F1-score of 0.63 on the test data. Our approach ranks 2nd (score of 1st placed system: 0.64) out of four according to this official score. However, we erroneously trained 2 out of 3 neural nets (the stacker and the CNN) on only roughly 15% of the full data, namely, the original development set. When trained on the full data (training+development), our ensemble has a micro-F1-score of 0.69. Our code is available from https://github.com/UKPLab/semeval2017-scienceie.
OBTAIN: Real-Time Beat Tracking in Audio Signals
Venue: arXiv cs.SD 2017
Year: 2017

In this paper, we design a system in order to perform the real-time beat tracking for an audio signal. We use Onset Strength Signal (OSS) to detect the onsets and estimate the tempos. Then, we form Cumulative Beat Strength Signal (CBSS) by taking advantage of OSS and estimated tempos. Next, we perform peak detection by extracting the periodic sequence of beats among all CBSS peaks. In simulations, we can see that our proposed algorithm, Online Beat TrAckINg (OBTAIN), outperforms state-of-art results in terms of prediction accuracy while maintaining comparable and practical computational complexity. The real-time performance is tractable visually as illustrated in the simulations.
Hand3D: Hand Pose Estimation using 3D Neural Network
Venue: arXiv cs.CV 2017
Year: 2017

We propose a novel 3D neural network architecture for 3D hand pose estimation from a single depth image. Different from previous works that mostly run on 2D depth image domain and require intermediate or post process to bring in the supervision from 3D space, we convert the depth map to a 3D volumetric representation, and feed it into a 3D convolutional neural network(CNN) to directly produce the pose in 3D requiring no further process. Our system does not require the ground truth reference point for initialization, and our network architecture naturally integrates both local feature and global context in 3D space. To increase the coverage of the hand pose space of the training data, we render synthetic depth image by transferring hand pose from existing real image datasets. We evaluation our algorithm on two public benchmarks and achieve the state-of-the-art performance. The synthetic hand pose dataset will be available.
A Highly-Efficient Memory-Compression Scheme for GPU-Accelerated Intrusion Detection Systems
Venue: arXiv cs.DC 2017
Year: 2017

Pattern Matching is a computationally intensive task used in many research fields and real world applications. Due to the ever-growing volume of data to be processed, and increasing link speeds, the number of patterns to be matched has risen significantly. In this paper we explore the parallel capabilities of modern General Purpose Graphics Processing Units (GPGPU) applications for high speed pattern matching. A highly compressed failure-less Aho-Corasick algorithm is presented for Intrusion Detection Systems on off-the-shelf hardware. This approach maximises the bandwidth for data transfers between the host and the Graphics Processing Unit (GPU). Experiments are performed on multiple alphabet sizes, demonstrating the capabilities of the library to be used in different research fields, while sustaining an adequate throughput for intrusion detection systems or DNA sequencing. The work also explores the performance impact of adequate prefix matching for alphabet sizes and varying pattern numbers achieving speeds up to 8Gbps and low memory consumption for intrusion detection systems.
GLoP: Enabling Massively Parallel Incident Response Through GPU Log Processing
Venue: arXiv cs.DC 2017
Year: 2017

Large industrial systems that combine services and applications, have become targets for cyber criminals and are challenging from the security, monitoring and auditing perspectives. Security log analysis is a key step for uncovering anomalies, detecting intrusion, and enabling incident response. The constant increase of link speeds, threats and users, produce large volumes of log data and become increasingly difficult to analyse on a Central Processing Unit (CPU). This paper presents a massively parallel Graphics Processing Unit (GPU) LOg Processing (GLoP) library and can also be used for Deep Packet Inspection (DPI), using a prefix matching technique, harvesting the full power of off-the-shelf technologies. GLoP implements two different algorithm using different GPU memory and is compared against CPU counterpart implementations. The library can be used for processing nodes with single or multiple GPUs as well as GPU cloud farms. The results show throughput of 20Gbps and demonstrate that modern GPUs can be utilised to increase the operational speed of large scale log processing scenarios, saving precious time before and after an intrusion has occurred.
HiFrames: High Performance Data Frames in a Scripting Language
Venue: arXiv cs.DC 2017
Year: 2017

Data frames in scripting languages are essential abstractions for processing structured data. However, existing data frame solutions are either not distributed (e.g., Pandas in Python) and therefore have limited scalability, or they are not tightly integrated with array computations (e.g., Spark SQL). This paper proposes a novel compiler-based approach where we integrate data frames into the High Performance Analytics Toolkit (HPAT) to build HiFrames. It provides expressive and flexible data frame APIs which are tightly integrated with array operations. HiFrames then automatically parallelizes and compiles relational operations along with other array computations in end-to-end data analytics programs, and generates efficient MPI/C++ code. We demonstrate that HiFrames is significantly faster than alternatives such as Spark SQL on clusters, without forcing the programmer to switch to embedded SQL for part of the program. HiFrames is 3.6x to 70x faster than Spark SQL for basic relational operations, and can be up to 20,000x faster for advanced analytics operations, such as weighted moving averages (WMA), that the map-reduce paradigm cannot handle effectively. HiFrames is also 5x faster than Spark SQL for TPCx-BB Q26 on 64 nodes of Cori supercomputer.
Efficient Synchronous Byzantine Consensus
Venue: arXiv cs.DC 2017
Year: 2017

We present new protocols for Byzantine state machine replication and Byzantine agreement in the synchronous and authenticated setting. The celebrated PBFT state machine replication protocol tolerates $f$ Byzantine faults in an asynchronous setting using $3f+1$ replicas, and has since been studied or deployed by numerous works. In this work, we improve the Byzantine fault tolerance threshold to $n=2f+1$ by utilizing a relaxed synchrony assumption. We present a synchronous state machine replication protocol that commits a decision every 3 rounds in the common case. The key challenge is to ensure quorum intersection at one honest replica. Our solution is to rely on the synchrony assumption to form a post-commit quorum of size $2f+1$, which intersects at $f+1$ replicas with any pre-commit quorums of size $f+1$. Our protocol also solves synchronous authenticated Byzantine agreement in expected 8 rounds. The best previous solution (Katz and Koo, 2006) requires expected 24 rounds. Our protocols may be applied to build Byzantine fault tolerant systems or improve cryptographic protocols such as cryptocurrencies when synchrony can be assumed.
Average-radius list-recovery of random linear codes: it really ties the room together
Venue: arXiv cs.IT 2017
Year: 2017

We analyze the list-decodability, and related notions, of random linear codes. This has been studied extensively before: there are many different parameter regimes and many different variants. Previous works have used complementary styles of arguments---which each work in their own parameter regimes but not in others---and moreover have left some gaps in our understanding of the list-decodability of random linear codes. In particular, none of these arguments work well for list-recovery, a generalization of list-decoding that has been useful in a variety of settings. In this work, we present a new approach, which works across parameter regimes and further generalizes to list-recovery. Our main theorem can establish better list-decoding and list-recovery results for low-rate random linear codes over large fields; list-recovery of high-rate random linear codes; and it can recover the rate bounds of Guruswami, Hastad, and Kopparty for constant-rate random linear codes (although with large list sizes).