OpenRaiser/Intern-Atlas huggingface dataset:
A Scalable Approach for Service Chain (SC) Mapping with Multiple SC Instances in a Wide-Area Network
Venue: arXiv cs.NI 2017
Year: 2017

Network Function Virtualization (NFV) aims to simplify deployment of network services by running Virtual Network Functions (VNFs) on commercial off-the-shelf servers. Service deployment involves placement of VNFs and in-sequence routing of traffic flows through VNFs comprising a Service Chain (SC). The joint VNF placement and traffic routing is called SC mapping. In a Wide-Area Network (WAN), a situation may arise where several traffic flows, generated by many distributed node pairs, require the same SC; then, a single instance (or occurrence) of that SC might not be enough. SC mapping with multiple SC instances for the same SC turns out to be a very complex problem, since the sequential traversal of VNFs has to be maintained while accounting for traffic flows in various directions. Our study is the first to deal with the problem of SC mapping with multiple SC instances to minimize network resource consumption. We first propose an Integer Linear Program (ILP) to solve this problem. Since ILP does not scale to large networks, we develop a column-generation-based ILP (CG-ILP) model. However, we find that exact mathematical modeling of the problem results in quadratic constraints in our CG-ILP. The quadratic constraints are made linear but even the scalability of CG-ILP is limited. Hence, we also propose a two-phase column-generation-based approach to get results over large network topologies within reasonable computational times. Using such an approach, we observe that an appropriate choice of only a small set of SC instances can lead to a solution very close to the minimum bandwidth consumption. Further, this approach also helps us to analyze the effects of number of VNF replicas and number of NFV nodes on bandwidth consumption when deploying these minimum number of SC instances.
On Multi-Relational Link Prediction with Bilinear Models
Venue: arXiv cs.LG 2017
Year: 2017

We study bilinear embedding models for the task of multi-relational link prediction and knowledge graph completion. Bilinear models belong to the most basic models for this task, they are comparably efficient to train and use, and they can provide good prediction performance. The main goal of this paper is to explore the expressiveness of and the connections between various bilinear models proposed in the literature. In particular, a substantial number of models can be represented as bilinear models with certain additional constraints enforced on the embeddings. We explore whether or not these constraints lead to universal models, which can in principle represent every set of relations, and whether or not there are subsumption relationships between various models. We report results of an independent experimental study that evaluates recent bilinear models in a common experimental setup. Finally, we provide evidence that relation-level ensembles of multiple bilinear models can achieve state-of-the art prediction performance.
Synapse at CAp 2017 NER challenge: Fasttext CRF
Venue: arXiv cs.CL 2017
Year: 2017

We present our system for the CAp 2017 NER challenge which is about named entity recognition on French tweets. Our system leverages unsupervised learning on a larger dataset of French tweets to learn features feeding a CRF model. It was ranked first without using any gazetteer or structured external data, with an F-measure of 58.89\%. To the best of our knowledge, it is the first system to use fasttext embeddings (which include subword representations) and an embedding-based sentence representation for NER.
MODNet: Moving Object Detection Network with Motion and Appearance for Autonomous Driving
Venue: arXiv cs.CV 2017
Year: 2017

We propose a novel multi-task learning system that combines appearance and motion cues for a better semantic reasoning of the environment. A unified architecture for joint vehicle detection and motion segmentation is introduced. In this architecture, a two-stream encoder is shared among both tasks. In order to evaluate our method in autonomous driving setting, KITTI annotated sequences with detection and odometry ground truth are used to automatically generate static/dynamic annotations on the vehicles. This dataset is called KITTI Moving Object Detection dataset (KITTI MOD). The dataset will be made publicly available to act as a benchmark for the motion detection task. Our experiments show that the proposed method outperforms state of the art methods that utilize motion cue only with 21.5% in mAP on KITTI MOD. Our method performs on par with the state of the art unsupervised methods on DAVIS benchmark for generic object segmentation. One of our interesting conclusions is that joint training of motion segmentation and vehicle detection benefits motion segmentation. Motion segmentation has relatively fewer data, unlike the detection task. However, the shared fusion encoder benefits from joint training to learn a generalized representation. The proposed method runs in 120 ms per frame, which beats the state of the art motion detection/segmentation in computational efficiency.
Hybrid Beamforming with Spatial Modulation in Multi-user Massive MIMO mmWave Networks
Venue: arXiv cs.IT 2017
Year: 2017

The cost of radio frequency (RF) chains is the biggest drawback of massive MIMO millimeter wave networks. By employing spatial modulation (SM), it is possible to implement lower number of RF chains than transmit antennas but still achieve high spectral efficiency. In this work, we propose a system model of the SM scheme together with hybrid beamforming at the transmitter and digital combining at the receiver. In the proposed model, spatially-modulated bits are mapped onto indices of antenna arrays. It is shown that the proposed model achieves approximately 5dB gain over classical multi-user SM scheme with only 8 transmit antennas at each antenna array. This gain can be improved further by increasing the number of transmit antennas at each array without increasing the number of RF chains.
ClouNS - A Cloud-native Application Reference Model for Enterprise Architects
Venue: arXiv cs.SE 2017
Year: 2017

The capability to operate cloud-native applications can generate enormous business growth and value. But enterprise architects should be aware that cloud-native applications are vulnerable to vendor lock-in. We investigated cloud-native application design principles, public cloud service providers, and industrial cloud standards. All results indicate that most cloud service categories seem to foster vendor lock-in situations which might be especially problematic for enterprise architectures. This might sound disillusioning at first. However, we present a reference model for cloud-native applications that relies only on a small subset of well standardized IaaS services. The reference model can be used for codifying cloud technologies. It can guide technology identification, classification, adoption, research and development processes for cloud-native application and for vendor lock-in aware enterprise architecture engineering methodologies.
Shared Learning : Enhancing Reinforcement in $Q$-Ensembles
Venue: arXiv cs.LG 2017
Year: 2017

Deep Reinforcement Learning has been able to achieve amazing successes in a variety of domains from video games to continuous control by trying to maximize the cumulative reward. However, most of these successes rely on algorithms that require a large amount of data to train in order to obtain results on par with human-level performance. This is not feasible if we are to deploy these systems on real world tasks and hence there has been an increased thrust in exploring data efficient algorithms. To this end, we propose the Shared Learning framework aimed at making $Q$-ensemble algorithms data-efficient. For achieving this, we look into some principles of transfer learning which aim to study the benefits of information exchange across tasks in reinforcement learning and adapt transfer to learning our value function estimates in a novel manner. In this paper, we consider the special case of transfer between the value function estimates in the $Q$-ensemble architecture of BootstrappedDQN. We further empirically demonstrate how our proposed framework can help in speeding up the learning process in $Q$-ensembles with minimum computational overhead on a suite of Atari 2600 Games.
Integrating Context of Statements within Description Logics
Venue: arXiv cs.LO 2017
Year: 2017

We address the problem of providing contextual information about a logical formula (eg provenance, date of validity, or confidence) and representing it within a logical system. In this case, it is needed to rely on a higher order or non standard formalism, or some kind of reification mechanism. We explore the case of reification and formalize the concept of contextualizing logical statements in the case of Description Logics. Then, we define several properties of contextualization that are desirable. No previous approaches satisfy all of the them. Consequently, we define a new way of contextually annotating statements. It is inspired by NdFluents, which is itself an extension of the 4dFluents approach for annotating statements with temporal context. In NdFluents, instances that are involved in a contextual statement are sliced into contextual parts, such that only parts in the same context hold relations to one another, with the goal of better preserving inferences. We generalize this idea by defining contextual parts of relations and classes. This formal construction better satisfies the properties, although not entirely. We show that it is a particular case of a general mechanism that NdFluents also instantiates, and present other variations.
WOAH: Preliminaries to Zero-shot Ontology Learning for Conversational Agents
Venue: arXiv cs.CL 2017
Year: 2017

The present paper presents the Weighted Ontology Approximation Heuristic (WOAH), a novel zero-shot approach to ontology estimation for conversational agents development environments. This methodology extracts verbs and nouns separately from data by distilling the dependencies obtained and applying similarity and sparsity metrics to generate an ontology estimation configurable in terms of the level of generalization.
Robust Kernelized Multi-View Self-Representations for Clustering by Tensor Multi-Rank Minimization
Venue: arXiv cs.CV 2017
Year: 2017

Most recently, tensor-SVD is implemented on multi-view self-representation clustering and has achieved the promising results in many real-world applications such as face clustering, scene clustering and generic object clustering. However, tensor-SVD based multi-view self-representation clustering is proposed originally to solve the clustering problem in the multiple linear subspaces, leading to unsatisfactory results when dealing with the case of non-linear subspaces. To handle data clustering from the non-linear subspaces, a kernelization method is designed by mapping the data from the original input space to a new feature space in which the transformed data can be clustered by a multiple linear clustering method. In this paper, we make an optimization model for the kernelized multi-view self-representation clustering problem. We also develop a new efficient algorithm based on the alternation direction method and infer a closed-form solution. Since all the subproblems can be solved exactly, the proposed optimization algorithm is guaranteed to obtain the optimal solution. In particular, the original tensor-based multi-view self-representation clustering problem is a special case of our approach and can be solved by our algorithm. Experimental results on several popular real-world clustering datasets demonstrate that our approach achieves the state-of-the-art performance.
Variable Version Lovász Local Lemma: Beyond Shearer's Bound
Venue: arXiv cs.DM 2017
Year: 2017

A tight criterion under which the abstract version Lovász Local Lemma (abstract-LLL) holds was given by Shearer decades ago. However, little is known about that of the variable version LLL (variable-LLL) where events are generated by independent random variables, though this model of events is applicable to almost all applications of LLL. We introduce a necessary and sufficient criterion for variable-LLL, in terms of the probabilities of the events and the event-variable graph specifying the dependency among the events. Based on this new criterion, we obtain boundaries for two families of event-variable graphs, namely, cyclic and treelike bigraphs. These are the first two non-trivial cases where the variable-LLL boundary is fully determined. As a byproduct, we also provide a universal constructive method to find a set of events whose union has the maximum probability, given the probability vector and the event-variable graph. Though it is #P-hard in general to determine variable-LLL boundaries, we can to some extent decide whether a gap exists between a variable-LLL boundary and the corresponding abstract-LLL boundary. In particular, we show that the gap existence can be decided without solving Shearer's conditions or checking our variable-LLL criterion. Equipped with this powerful theorem, we show that there is no gap if the base graph of the event-variable graph is a tree, while gap appears if the base graph has an induced cycle of length at least 4. The problem is almost completely solved except when the base graph has only 3-cliques, in which case we also get partial solutions. A set of reduction rules are established that facilitate to infer gap existence of an event-variable graph from known ones. As an application, various event-variable graphs, in particular combinatorial ones, are shown to be gapful/gapless.
Trend Detection based Regret Minimization for Bandit Problems
Venue: arXiv cs.LG 2017
Year: 2017

We study a variation of the classical multi-armed bandits problem. In this problem, the learner has to make a sequence of decisions, picking from a fixed set of choices. In each round, she receives as feedback only the loss incurred from the chosen action. Conventionally, this problem has been studied when losses of the actions are drawn from an unknown distribution or when they are adversarial. In this paper, we study this problem when the losses of the actions also satisfy certain structural properties, and especially, do show a trend structure. When this is true, we show that using \textit{trend detection}, we can achieve regret of order $\tilde{O} (N \sqrt{TK})$ with respect to a switching strategy for the version of the problem where a single action is chosen in each round and $\tilde{O} (Nm \sqrt{TK})$ when $m$ actions are chosen each round. This guarantee is a significant improvement over the conventional benchmark. Our approach can, as a framework, be applied in combination with various well-known bandit algorithms, like Exp3. For both versions of the problem, we give regret guarantees also for the \textit{anytime} setting, i.e. when the length of the choice-sequence is not known in advance. Finally, we pinpoint the advantages of our method by comparing it to some well-known other strategies.
Interleaved sequences of geometric sequences binarized with Legendre symbol of two types
Venue: arXiv cs.IT 2017
Year: 2017

A pseudorandom number generator is widely used in cryptography. A cryptographic pseudorandom number generator is required to generate pseudorandom numbers which have good statistical properties as well as unpredictability. An m-sequence is a linear feedback shift register sequence with maximal period over a finite field. M-sequences have good statistical properties, however we must nonlinearize m-sequences for cryptographic purposes. A geometric sequence is a binary sequence given by applying a nonlinear feedforward function to an m-sequence. Nogami, Tada and Uehara proposed a geometric sequence whose nonlinear feedforward function is given by the Legendre symbol. They showed the geometric sequences have good properties for the period, periodic autocorrelation and linear complexity. However, the geometric sequences do not have the balance property. In this paper, we introduce geometric sequences of two types and show some properties of interleaved sequences of the geometric sequences of two types. These interleaved sequences have the balance property and double the period of the geometric sequences by the interleaved structure. Moreover, we show correlation properties and linear complexity of the interleaved sequences. A key of our observation is that the second type geometric sequence is the complement of the left shift of the first type geometric sequence by half-period positions.
Fast OLAP Query Execution in Main Memory on Large Data in a Cluster
Venue: arXiv cs.DB 2017
Year: 2017

Main memory column-stores have proven to be efficient for processing analytical queries. Still, there has been much less work in the context of clusters. Using only a single machine poses several restrictions: Processing power and data volume are bounded to the number of cores and main memory fitting on one tightly coupled system. To enable the processing of larger data sets, switching to a cluster becomes necessary. In this work, we explore techniques for efficient execution of analytical SQL queries on large amounts of data in a parallel database cluster while making maximal use of the available hardware. This includes precompiled query plans for efficient CPU utilization, full parallelization on single nodes and across the cluster, and efficient inter-node communication. We implement all features in a prototype for running a subset of TPC-H benchmark queries. We evaluate our implementation using a 128 node cluster running TPC-H queries with 30 000 gigabyte of uncompressed data.
Mutually Uncorrelated Primers for DNA-Based Data Storage
Venue: arXiv cs.IT 2017
Year: 2017

We introduce the notion of weakly mutually uncorrelated (WMU) sequences, motivated by applications in DNA-based data storage systems and for synchronization of communication devices. WMU sequences are characterized by the property that no sufficiently long suffix of one sequence is the prefix of the same or another sequence. WMU sequences used for primer design in DNA-based data storage systems are also required to be at large mutual Hamming distance from each other, have balanced compositions of symbols, and avoid primer-dimer byproducts. We derive bounds on the size of WMU and various constrained WMU codes and present a number of constructions for balanced, error-correcting, primer-dimer free WMU codes using Dyck paths, prefix-synchronized and cyclic codes.
A Data Mining Approach Combining K-Means Clustering with Bagging Neural Network for Short-term Wind Power Forecasting
Venue: arXiv cs.CE 2017
Year: 2017

Wind power forecasting (WPF) is significant to guide the dispatching of grid and the production planning of wind farm effectively. The intermittency and volatility of wind leading to the diversity of the training samples have a major impact on the forecasting accuracy. In this paper, to deal with the training samples dynamics and improve the forecasting accuracy, a data mining approach consisting of K-means clustering and bagging neural network is proposed for short-term WPF. Based on the similarity among historical days, K-means clustering is used to classify the samples into several categories, which contain the information of meteorological conditions and historical power data. In order to overcome the over fitting and instability problems of conventional networks, a bagging-based ensemble approach is integrated into the back propagation neural network. To confirm the effectiveness, the proposed data mining approach is examined on real wind generation data traces. The simulation results show that it can obtain better forecasting accuracy than other baseline and existed short-term WPF approaches.
AndroZoo++: Collecting Millions of Android Apps and Their Metadata for the Research Community
Venue: arXiv cs.SE 2017
Year: 2017

We present a growing collection of Android apps collected from several sources, including the official Google Play app market and a growing collection of various metadata of those collected apps aiming at facilitating the Android-relevant research works. Our dataset by far has collected over five million apps and over 20 types of metadata such as VirusTotal reports. Our objective of collecting this dataset is to contribute to ongoing research efforts, as well as to enable new potential research topics on Android Apps. By releasing our app and metadata set to the research community, we also aim at encouraging our fellow researchers to engage in reproducible experiments. This article will be continuously updated based on the growing apps and metadata collected in the AndroZoo project. If you have specific metadata that you want to collect from AndroZoo and which are not yet provided by far, please let us know. We will thereby prioritise it in our collecting process so as to provide it to our fellow researchers in a short manner.
Are you serious?: Rhetorical Questions and Sarcasm in Social Media Dialog
Venue: arXiv cs.CL 2017
Year: 2017

Effective models of social dialog must understand a broad range of rhetorical and figurative devices. Rhetorical questions (RQs) are a type of figurative language whose aim is to achieve a pragmatic goal, such as structuring an argument, being persuasive, emphasizing a point, or being ironic. While there are computational models for other forms of figurative language, rhetorical questions have received little attention to date. We expand a small dataset from previous work, presenting a corpus of 10,270 RQs from debate forums and Twitter that represent different discourse functions. We show that we can clearly distinguish between RQs and sincere questions (0.76 F1). We then show that RQs can be used both sarcastically and non-sarcastically, observing that non-sarcastic (other) uses of RQs are frequently argumentative in forums, and persuasive in tweets. We present experiments to distinguish between these uses of RQs using SVM and LSTM models that represent linguistic features and post-level context, achieving results as high as 0.76 F1 for "sarcastic" and 0.77 F1 for "other" in forums, and 0.83 F1 for both "sarcastic" and "other" in tweets. We supplement our quantitative experiments with an in-depth characterization of the linguistic variation in RQs.
General Phase Regularized Reconstruction using Phase Cycling
Venue: arXiv cs.CV 2017
Year: 2017

Purpose: To develop a general phase regularized image reconstruction method, with applications to partial Fourier imaging, water-fat imaging and flow imaging. Theory and Methods: The problem of enforcing phase constraints in reconstruction was studied under a regularized inverse problem framework. A general phase regularized reconstruction algorithm was proposed to enable various joint reconstruction of partial Fourier imaging, water-fat imaging and flow imaging, along with parallel imaging (PI) and compressed sensing (CS). Since phase regularized reconstruction is inherently non-convex and sensitive to phase wraps in the initial solution, a reconstruction technique, named phase cycling, was proposed to render the overall algorithm invariant to phase wraps. The proposed method was applied to retrospectively under-sampled in vivo datasets and compared with state of the art reconstruction methods. Results: Phase cycling reconstructions showed reduction of artifacts compared to reconstructions with- out phase cycling and achieved similar performances as state of the art results in partial Fourier, water-fat and divergence-free regularized flow reconstruction. Joint reconstruction of partial Fourier + water-fat imaging + PI + CS, and partial Fourier + divergence-free regularized flow imaging + PI + CS were demonstrated. Conclusion: The proposed phase cycling reconstruction provides an alternative way to perform phase regularized reconstruction, without the need to perform phase unwrapping. It is robust to the choice of initial solutions and encourages the joint reconstruction of phase imaging applications.