OpenRaiser/Intern-Atlas huggingface dataset:
Performance Analysis and Scaling Law of MRC/MRT Relaying with CSI Error in Massive MIMO Systems
Venue: arXiv cs.NI 2016
Year: 2016

This work provides a comprehensive scaling law and performance analysis for multi-user massive MIMO relay networks, where the relay is equipped with massive antennas and uses MRC/MRT for low-complexity processing. CSI error is considered. First, a sum-rate lower bound is derived which manifests the effect of system parameters including the numbers of relay antennas and users, the CSI quality, and the transmit powers of the sources and the relay. Via a general scaling model on the system parameters with respect to the relay antenna number, the asymptotic scaling law of the SINR as a function of the parameter scalings is obtained, which shows quantitatively the tradeoff between the network parameters and their effect on the network performance. In addition, a sufficient condition on the parameter scalings for the SINR to be asymptotically deterministic is given, which covers existing studies on such analysis as special cases. Then, the scenario where the SINR increases linearly with the relay antenna number is studied. The sufficient and necessary condition on the parameter scaling for this scenario is proved. It is shown that in this case, the interference power is not asymptotically deterministic, then its distribution is derived, based on which the outage probability and average bit error rate of the relay network are analysed.
Enhancing Accountability and Trust in Distributed Ledgers
Venue: arXiv cs.DC 2016
Year: 2016

Permisionless decentralized ledgers ("blockchains") such as the one underlying the cryptocurrency Bitcoin allow anonymous participants to maintain the ledger, while avoiding control or "censorship" by any single entity. In contrast, permissioned decentralized ledgers exploit real-world trust and accountability, allowing only explicitly authorized parties to maintain the ledger. Permissioned ledgers support more flexible governance and a wider choice of consensus mechanisms. Both kinds of decentralized ledgers may be susceptible to manipulation by participants who favor some transactions over others. The real-world accountability underlying permissioned ledgers provides an opportunity to impose fairness constraints that can be enforced by penalizing violators after-the- fact. To date, however, this opportunity has not been fully exploited, unnecessarily leaving participants latitude to manipulate outcomes undetectably. This paper draws attention to this issue, and proposes design principles to make such manipulation more difficult, as well as specific mechanisms to make it easier to detect when violations occur.
Convex Decomposition And Efficient Shape Representation Using Deformable Convex Polytopes
Venue: arXiv cs.CV 2016
Year: 2016

Decomposition of shapes into (approximate) convex parts is essential for applications such as part-based shape representation, shape matching, and collision detection. In this paper, we propose a novel convex decomposition using a parametric implicit shape model called Disjunctive Normal Shape Model (DNSM). The DNSM is formed as a union of polytopes which themselves are formed by intersections of halfspaces. The key idea is by deforming the polytopes, which naturally remain convex during the evolution, the polytopes capture convex parts without the need to compute convexity. The major contributions of this paper include a robust convex decomposition which also results in an efficient part-based shape representation, and a novel shape convexity measure. The experimental results show the potential of the proposed method.
On the Solvability of Inductive Problems: A Study in Epistemic Topology
Venue: arXiv cs.LO 2016
Year: 2016

We investigate the issues of inductive problem-solving and learning by doxastic agents. We provide topological characterizations of solvability and learnability, and we use them to prove that AGM-style belief revision is "universal", i.e., that every solvable problem is solvable by AGM conditioning.
Bayesian Games with Intentions
Venue: arXiv cs.GT 2016
Year: 2016

We show that standard Bayesian games cannot represent the full spectrum of belief-dependent preferences. However, by introducing a fundamental distinction between intended and actual strategies, we remove this limitation. We define Bayesian games with intentions, generalizing both Bayesian games and psychological games, and prove that Nash equilibria in psychological games correspond to a special class of equilibria as defined in our setting.
Standard State Space Models of Unawareness (Extended Abstract)
Venue: arXiv cs.AI 2016
Year: 2016

The impossibility theorem of Dekel, Lipman and Rustichini has been thought to demonstrate that standard state-space models cannot be used to represent unawareness. We first show that Dekel, Lipman and Rustichini do not establish this claim. We then distinguish three notions of awareness, and argue that although one of them may not be adequately modeled using standard state spaces, there is no reason to think that standard state spaces cannot provide models of the other two notions. In fact, standard space models of these forms of awareness are attractively simple. They allow us to prove completeness and decidability results with ease, to carry over standard techniques from decision theory, and to add propositional quantifiers straightforwardly.
A Dynamic Epistemic Framework for Conformant Planning
Venue: arXiv cs.AI 2016
Year: 2016

In this paper, we introduce a lightweight dynamic epistemic logical framework for automated planning under initial uncertainty. We reduce plan verification and conformant planning to model checking problems of our logic. We show that the model checking problem of the iteration-free fragment is PSPACE-complete. By using two non-standard (but equivalent) semantics, we give novel model checking algorithms to the full language and the iteration-free language.
Translucent Players: Explaining Cooperative Behavior in Social Dilemmas
Venue: arXiv cs.GT 2016
Year: 2016

In the last few decades, numerous experiments have shown that humans do not always behave so as to maximize their material payoff. Cooperative behavior when non-cooperation is a dominant strategy (with respect to the material payoffs) is particularly puzzling. Here we propose a novel approach to explain cooperation, assuming what Halpern and Pass call translucent players. Typically, players are assumed to be opaque, in the sense that a deviation by one player in a normal-form game does not affect the strategies used by other players. But a player may believe that if he switches from one strategy to another, the fact that he chooses to switch may be visible to the other players. For example, if he chooses to defect in Prisoner's Dilemma, the other player may sense his guilt. We show that by assuming translucent players, we can recover many of the regularities observed in human behavior in well-studied games such as Prisoner's Dilemma, Traveler's Dilemma, Bertrand Competition, and the Public Goods game.
Sistem Informasi Pengarsipan Menggunakan Algoritma Levensthein String pada Kecamatan Seberang Ulu II
Venue: arXiv cs.CY 2016
Year: 2016

Archival information systems in government agency is one of the most used applications for daily acitivities. One feature in application management information document is searching. This feature serves to search for documents from a collection of available information based on keywords entered by the user. But some researches on a search engine (searching) concluded that the average user error in the search is quite high due to several factors. Therefore, we need a development on this feature as search suggestion. This study discusses the application of the method of approximate string matching algorithm using levenshtein distance. Levensthein distance algorithm is capable of calculating the minimum distance conversion of a string into another string to the optimum. Archiving information system using Levensthein Algorithm String is an application that will be built to address these problems, this application will help, especially in the administration to enter or save a document, locate and make a report that will be seen by government agencies.
Evaluation method of word embedding by roots and affixes
Venue: arXiv cs.CL 2016
Year: 2016

Word embedding has been shown to be remarkably effective in a lot of Natural Language Processing tasks. However, existing models still have a couple of limitations in interpreting the dimensions of word vector. In this paper, we provide a new approach---roots and affixes model(RAAM)---to interpret it from the intrinsic structures of natural language. Also it can be used as an evaluation measure of the quality of word embedding. We introduce the information entropy into our model and divide the dimensions into two categories, just like roots and affixes in lexical semantics. Then considering each category as a whole rather than individually. We experimented with English Wikipedia corpus. Our result show that there is a negative linear relation between the two attributes and a high positive correlation between our model and downstream semantic evaluation tasks.
Benchmarking Distributed Stream Processing Platforms for IoT Applications
Venue: arXiv cs.DC 2016
Year: 2016

Internet of Things (IoT) is a technology paradigm where millions of sensors monitor, and help inform or manage, physical, envi- ronmental and human systems in real-time. The inherent closed-loop re- sponsiveness and decision making of IoT applications makes them ideal candidates for using low latency and scalable stream processing plat- forms. Distributed Stream Processing Systems (DSPS) are becoming es- sential components of any IoT stack, but the efficacy and performance of contemporary DSPS have not been rigorously studied for IoT data streams and applications. Here, we develop a benchmark suite and per- formance metrics to evaluate DSPS for streaming IoT applications. The benchmark includes 13 common IoT tasks classified across various func- tional categories and forming micro-benchmarks, and two IoT applica- tions for statistical summarization and predictive analytics that leverage various dataflow compositional features of DSPS. These are coupled with stream workloads sourced from real IoT observations from smart cities. We validate the IoT benchmark for the popular Apache Storm DSPS, and present empirical results.
Deep Learning Relevance: Creating Relevant Information (as Opposed to Retrieving it)
Venue: arXiv cs.IR 2016
Year: 2016

What if Information Retrieval (IR) systems did not just retrieve relevant information that is stored in their indices, but could also "understand" it and synthesise it into a single document? We present a preliminary study that makes a first step towards answering this question. Given a query, we train a Recurrent Neural Network (RNN) on existing relevant information to that query. We then use the RNN to "deep learn" a single, synthetic, and we assume, relevant document for that query. We design a crowdsourcing experiment to assess how relevant the "deep learned" document is, compared to existing relevant documents. Users are shown a query and four wordclouds (of three existing relevant documents and our deep learned synthetic document). The synthetic document is ranked on average most relevant of all.
Neural Network Based Next-Song Recommendation
Venue: arXiv cs.IR 2016
Year: 2016

Recently, the next-item/basket recommendation system, which considers the sequential relation between bought items, has drawn attention of researchers. The utilization of sequential patterns has boosted performance on several kinds of recommendation tasks. Inspired by natural language processing (NLP) techniques, we propose a novel neural network (NN) based next-song recommender, CNN-rec, in this paper. Then, we compare the proposed system with several NN based and classic recommendation systems on the next-song recommendation task. Verification results indicate the proposed system outperforms classic systems and has comparable performance with the state-of-the-art system.
Satellite Images Analysis with Symbolic Time Series: A Case Study of the Algerian Zone
Venue: arXiv cs.DB 2016
Year: 2016

Satellite Image Time Series (SITS) are an important source of information for studying land occupation and its evolution. Indeed, the very large volumes of digital data stored, usually are not ready to a direct analysis. In order to both reduce the dimensionality and information extraction, time series data mining generally gives rise to change of time series representation. In an objective of information intelligibility extracted from the representation change, we may use symbolic representations of time series. Many high level representations of time series have been proposed for data mining, including Fourier transforms, wavelets, piecewise polynomial models, etc. Many researchers have also considered symbolic representations of time series, noting that such representations would potentiality allow researchers to avail of the wealth of data structures and algorithms from the text processing and bioinformatics communities. We present in this work, one of the main symbolic representation methods "SAX"(Symbolic Aggregate Approximation) and we experience this method to symbolize and reduce the dimensionality of a Satellite Image Times Series acquired over a period of 5 years by characterizing the evolution of a vegetation index (NDVI).
Penerapan E-Service Berbasis Android pada Divisi Pelayanan Perbaikan Komputer CV Ria Kencana Ungu (RKU)
Venue: arXiv cs.CY 2016
Year: 2016

Archival information systems in government agency is one of the most used applications for daily acitivities. One feature in application management information document is searching. This feature serves to search for documents from a collection of available information based on keywords entered by the user. But some researches on a search engine (searching) concluded that the average user error in the search is quite high due to several factors. Therefore, we need a development on this feature as search suggestion. This study discusses the application of the method of approximate string matching algorithm using levenshtein distance. Levensthein distance algorithm is capable of calculating the minimum distance conversion of a string into another string to the optimum. Archiving information system using Levensthein Algorithm String is an application that will be built to address these problems, this application will help, especially in the administration to enter or save a document, locate and make a report that will be seen by government agencies.
Efficient Parallel Learning of Word2Vec
Venue: arXiv cs.CL 2016
Year: 2016

Since its introduction, Word2Vec and its variants are widely used to learn semantics-preserving representations of words or entities in an embedding space, which can be used to produce state-of-art results for various Natural Language Processing tasks. Existing implementations aim to learn efficiently by running multiple threads in parallel while operating on a single model in shared memory, ignoring incidental memory update collisions. We show that these collisions can degrade the efficiency of parallel learning, and propose a straightforward caching strategy that improves the efficiency by a factor of 4.
Spatial Aggregation of Holistically-Nested Networks for Automated Pancreas Segmentation
Venue: arXiv cs.CV 2016
Year: 2016

Accurate automatic organ segmentation is an important yet challenging problem for medical image analysis. The pancreas is an abdominal organ with very high anatomical variability. This inhibits traditional segmentation methods from achieving high accuracies, especially compared to other organs such as the liver, heart or kidneys. In this paper, we present a holistic learning approach that integrates semantic mid-level cues of deeply-learned organ interior and boundary maps via robust spatial aggregation using random forest. Our method generates boundary preserving pixel-wise class labels for pancreas segmentation. Quantitative evaluation is performed on CT scans of 82 patients in 4-fold cross-validation. We achieve a (mean $\pm$ std. dev.) Dice Similarity Coefficient of 78.01% $\pm$ 8.2% in testing which significantly outperforms the previous state-of-the-art approach of 71.8% $\pm$ 10.7% under the same evaluation criterion.
Matroid Online Bipartite Matching and Vertex Cover
Venue: arXiv cs.DS 2016
Year: 2016

The Adwords and Online Bipartite Matching problems have enjoyed a renewed attention over the past decade due to their connection to Internet advertising. Our community has contributed, among other things, new models (notably stochastic) and extensions to the classical formulations to address the issues that arise from practical needs. In this paper, we propose a new generalization based on matroids and show that many of the previous results extend to this more general setting. Because of the rich structures and expressive power of matroids, our new setting is potentially of interest both in theory and in practice. In the classical version of the problem, the offline side of a bipartite graph is known initially while vertices from the online side arrive one at a time along with their incident edges. The objective is to maintain a decent approximate matching from which no edge can be removed. Our generalization, called Matroid Online Bipartite Matching, additionally requires that the set of matched offline vertices be independent in a given matroid. In particular, the case of partition matroids corresponds to the natural scenario where each advertiser manages multiple ads with a fixed total budget. Our algorithms attain the same performance as the classical version of the problems considered, which are often provably the best possible. We present $1-1/e$-competitive algorithms for Matroid Online Bipartite Matching under the small bid assumption, as well as a $1-1/e$-competitive algorithm for Matroid Online Bipartite Matching in the random arrival model. A key technical ingredient of our results is a carefully designed primal-dual waterfilling procedure that accommodates for matroid constraints. This is inspired by the extension of our recent charging scheme for Online Bipartite Vertex Cover.
Fully Dynamic Spanners with Worst-Case Update Time
Venue: arXiv cs.DS 2016
Year: 2016

An $α$-spanner of a graph $ G $ is a subgraph $ H $ such that $ H $ preserves all distances of $ G $ within a factor of $ α$. In this paper, we give fully dynamic algorithms for maintaining a spanner $ H $ of a graph $ G $ undergoing edge insertions and deletions with worst-case guarantees on the running time after each update. In particular, our algorithms maintain: (1) a $3$-spanner with $ \tilde O (n^{1+1/2}) $ edges with worst-case update time $ \tilde O (n^{3/4}) $, or (2) a $5$-spanner with $ \tilde O (n^{1+1/3}) $ edges with worst-case update time $ \tilde O (n^{5/9}) $. These size/stretch tradeoffs are best possible (up to logarithmic factors). They can be extended to the weighted setting at very minor cost. Our algorithms are randomized and correct with high probability against an oblivious adversary. We also further extend our techniques to construct a $5$-spanner with suboptimal size/stretch tradeoff, but improved worst-case update time. To the best of our knowledge, these are the first dynamic spanner algorithms with sublinear worst-case update time guarantees. Since it is known how to maintain a spanner using small amortized but large worst-case update time [Baswana et al. SODA'08], obtaining algorithms with strong worst-case bounds, as presented in this paper, seems to be the next natural step for this problem.
P2P-PL: A Pattern Language to Design Efficient and Robust Peer-to-Peer Systems
Venue: arXiv cs.DC 2016
Year: 2016

To design peer-to-peer (P2P) software systems is a challenging task, because of their highly decentralized nature, which may cause unexpected emergent global behaviors. The last fifteen years have seen many P2P applications to come out and win favor with millions of users. From success histories of applications like BitTorrent, Skype, MyP2P we have learnt a number of useful design patterns. Thus, in this article we present a P2P pattern language (shortly, P2P-PL) which encompasses all the aspects that a fully effective and efficient P2P software system should provide, namely consistency of stored data, redundancy, load balancing, coping with asymmetric bandwidth, decentralized security. The patterns of the proposed P2P-PL are described in detail, and a composition strategy for designing robust, effective and efficient P2P software systems is proposed.
Label Tree Embeddings for Acoustic Scene Classification
Venue: arXiv cs.MM 2016
Year: 2016

We present in this paper an efficient approach for acoustic scene classification by exploring the structure of class labels. Given a set of class labels, a category taxonomy is automatically learned by collectively optimizing a clustering of the labels into multiple meta-classes in a tree structure. An acoustic scene instance is then embedded into a low-dimensional feature representation which consists of the likelihoods that it belongs to the meta-classes. We demonstrate state-of-the-art results on two different datasets for the acoustic scene classification task, including the DCASE 2013 and LITIS Rouen datasets.
A Distributed Sensor Data Search Platform for Internet of Things Environments
Venue: arXiv cs.NI 2016
Year: 2016

Recently, the number of devices has grown increasingly and it is hoped that, between 2015 and 2016, 20 billion devices will be connected to the Internet and this market will move around 91.5 billion dollars. The Internet of Things (IoT) is composed of small sensors and actuators embedded in objects with Internet access and will play a key role in solving many challenges faced in today's society. However, the real capacity of IoT concepts is constrained as the current sensor networks usually do not exchange information with other sources. In this paper, we propose the Visual Search for Internet of Things (ViSIoT) platform to help technical and non-technical users to discover and use sensors as a service for different application purposes. As a proof of concept, a real case study is used to generate weather condition reports to support rheumatism patients. This case study was executed in a working prototype and a performance evaluation is presented.
Some lower bounds in parameterized ${\rm AC}^0$
Venue: arXiv cs.CC 2016
Year: 2016

We demonstrate some lower bounds for parameterized problems via parameterized classes corresponding to the classical ${\rm AC}^0$. Among others, we derive such a lower bound for all fpt-approximations of the parameterized clique problem and for a parameterized halting problem, which recently turned out to link problems of computational complexity, descriptive complexity, and proof theory. To show the first lower bound, we prove a strong ${\rm AC}^0$ version of the planted clique conjecture: ${\rm AC}^0$-circuits asymptotically almost surely can not distinguish between a random graph and this graph with a randomly planted clique of any size $\le n^ξ$ (where $0 \le ξ< 1$).
Computing the Convolution of Analog and Discrete Time Exponential Signals Algebraically
Venue: arXiv cs.SY 2016
Year: 2016

We present a procedure for computing the convolution of exponential signals without the need of solving integrals or summations. The procedure requires the resolution of a system of linear equations involving Vandermonde matrices. We apply the method to solve ordinary differential/difference equations with constant coefficients.