OpenRaiser/Intern-Atlas huggingface dataset:
Type Theory based on Dependent Inductive and Coinductive Types
Venue: arXiv cs.LO 2016
Year: 2016

We develop a dependent type theory that is based purely on inductive and coinductive types, and the corresponding recursion and corecursion principles. This results in a type theory with a small set of rules, while still being fairly expressive. For example, all well-known basic types and type formers that are needed for using this type theory as a logic are definable: propositional connectives, like falsity, conjunction, disjunction, and function space, dependent function space, existential quantification, equality, natural numbers, vectors etc. The reduction relation on terms consists solely of a rule for recursion and a rule for corecursion. The reduction relations for well-known types arise from that. To further support the introduction of this new type theory, we also prove fundamental properties of its term calculus. Most importantly, we prove subject reduction and strong normalisation of the reduction relation, which gives computational meaning to the terms. The presented type theory is based on ideas from categorical logic that have been investigated before by the first author, and it extends Hagino's categorical data types to a dependently typed setting. By basing the type theory on concepts from category theory we maintain the duality between inductive and coinductive types, and it allows us to describe, for example, the function space as a coinductive type.
Inference-based semantics in Data Exchange
Venue: arXiv cs.DB 2016
Year: 2016

Data Exchange is an old problem that was firstly studied from a theoretical point of view only in 2003. Since then many approaches were considered when it came to the language describing the relationship between the source and the target schema. These approaches focus on what it makes a target instance a "good" solution for data-exchange. In this paper we propose the inference-based semantics that solves many certain-answer anomalies existing in current data-exchange semantics. To this we introduce a new mapping language between the source and the target schema based on annotated bidirectional dependencies (abd) and, consequently define the semantics for this new language. It is shown that the ABD-semantics can properly represent the inference-based semantics, for any source-to-target mappings. We discovered three dichotomy results under the new semantics for solution-existence, solution-check and UCQ evaluation problems. These results rely on two factors describing the annotation used in the mappings (density and cardinality). Finally we also investigate the certain-answers evaluation problem under ABD-semantics and discover many tractable classes for non-UCQ queries even for a subclass of CQ with negation.
Online Learning and Optimization of Markov Jump Affine Models
Venue: arXiv cs.IT 2016
Year: 2016

The problem of online learning and optimization of unknown Markov jump affine models is considered. An online learning policy, referred to as Markovian simultaneous perturbations stochastic approximation (MSPSA), is proposed for two different optimization objectives: (i) the quadratic cost minimization of the regulation problem and (ii) the revenue (profit) maximization problem. It is shown that the regret of MSPSA grows at the order of the square root of the learning horizon. Furthermore, by the use of van Trees inequality, it is shown that the regret of any policy grows no slower than that of MSPSA, making MSPSA an order optimal learning policy. In addition, it is also shown that the MSPSA policy converges to the optimal control input almost surely as well as in the mean square sense. Simulation results are presented to illustrate the regret growth rate of MSPSA and to show that MSPSA can offer significant gain over the greedy certainty equivalent approach.
Latency Analysis of Systems with Multiple Interfaces for Ultra-Reliable M2M Communication
Venue: arXiv cs.IT 2016
Year: 2016

One of the ways to satisfy the requirements of ultra-reliable low latency communication for mission critical Machine-type Communications (MTC) applications is to integrate multiple communication interfaces. In order to estimate the performance in terms of latency and reliability of such an integrated communication system, we propose an analysis framework that combines traditional reliability models with technology-specific latency probability distributions. In our proposed model we demonstrate how failure correlation between technologies can be taken into account. We show for the considered scenario with fiber and different cellular technologies how up to 5-nines reliability can be achieved and how packet splitting can be used to reduce latency substantially while keeping 4-nines reliability. The model has been validated through simulation.
A corpus of preposition supersenses in English web reviews
Venue: arXiv cs.CL 2016
Year: 2016

We present the first corpus annotated with preposition supersenses, unlexicalized categories for semantic functions that can be marked by English prepositions (Schneider et al., 2015). That scheme improves upon its predecessors to better facilitate comprehensive manual annotation. Moreover, unlike the previous schemes, the preposition supersenses are organized hierarchically. Our data will be publicly released on the web upon publication.
Deeply Exploit Depth Information for Object Detection
Venue: arXiv cs.CV 2016
Year: 2016

This paper addresses the issue on how to more effectively coordinate the depth with RGB aiming at boosting the performance of RGB-D object detection. Particularly, we investigate two primary ideas under the CNN model: property derivation and property fusion. Firstly, we propose that the depth can be utilized not only as a type of extra information besides RGB but also to derive more visual properties for comprehensively describing the objects of interest. So a two-stage learning framework consisting of property derivation and fusion is constructed. Here the properties can be derived either from the provided color/depth or their pairs (e.g. the geometry contour adopted in this paper). Secondly, we explore the fusion method of different properties in feature learning, which is boiled down to, under the CNN model, from which layer the properties should be fused together. The analysis shows that different semantic properties should be learned separately and combined before passing into the final classifier. Actually, such a detection way is in accordance with the mechanism of the primary neural cortex (V1) in brain. We experimentally evaluate the proposed method on the challenging dataset, and have achieved state-of-the-art performance.
On the Performance of Mismatched Data Detection in Large MIMO Systems
Venue: arXiv cs.IT 2016
Year: 2016

We investigate the performance of mismatched data detection in large multiple-input multiple-output (MIMO) systems, where the prior distribution of the transmit signal used in the data detector differs from the true prior. To minimize the performance loss caused by this prior mismatch, we include a tuning stage into our recently-proposed large MIMO approximate message passing (LAMA) algorithm, which allows us to develop mismatched LAMA algorithms with optimal as well as sub-optimal tuning. We show that carefully-selected priors often enable simpler and computationally more efficient algorithms compared to LAMA with the true prior while achieving near-optimal performance. A performance analysis of our algorithms for a Gaussian prior and a uniform prior within a hypercube covering the QAM constellation recovers classical and recent results on linear and non-linear MIMO data detection, respectively.
Active Learning for Community Detection in Stochastic Block Models
Venue: arXiv cs.LG 2016
Year: 2016

The stochastic block model (SBM) is an important generative model for random graphs in network science and machine learning, useful for benchmarking community detection (or clustering) algorithms. The symmetric SBM generates a graph with $2n$ nodes which cluster into two equally sized communities. Nodes connect with probability $p$ within a community and $q$ across different communities. We consider the case of $p=a\ln (n)/n$ and $q=b\ln (n)/n$. In this case, it was recently shown that recovering the community membership (or label) of every node with high probability (w.h.p.) using only the graph is possible if and only if the Chernoff-Hellinger (CH) divergence $D(a,b)=(\sqrt{a}-\sqrt{b})^2 \geq 1$. In this work, we study if, and by how much, community detection below the clustering threshold (i.e. $D(a,b)<1$) is possible by querying the labels of a limited number of chosen nodes (i.e., active learning). Our main result is to show that, under certain conditions, sampling the labels of a vanishingly small fraction of nodes (a number sub-linear in $n$) is sufficient for exact community detection even when $D(a,b)<1$. Furthermore, we provide an efficient learning algorithm which recovers the community memberships of all nodes w.h.p. as long as the number of sampled points meets the sufficient condition. We also show that recovery is not possible if the number of observed labels is less than $n^{1-D(a,b)}$. The validity of our results is demonstrated through numerical experiments.
Game-theoretic Demand-side Management Robust to Non-Ideal Consumer Behavior in Smart Grid
Venue: arXiv cs.GT 2016
Year: 2016

This paper investigates effects of realistic, non-ideal, decisions of energy users as to whether to participate in an energy trading system proposed for demand-side management of a residential community. The energy trading system adopts a non-cooperative Stackelberg game between a community energy storage (CES) device and users with rooftop photovoltaic panels where the CES operator is the leader and the users are the followers. Participating users determine their optimal energy trading starting time to minimize their personal daily energy costs while subjectively viewing their opponents' actions. Following a non-cooperative game, we study the subjective behavior of users when they decide on energy trading starting time using prospect theory. We show that depending on the decisions of participating-time, the proposed energy trading system has a unique Stackelberg equilibrium at which the CES operator maximizes their revenue while users minimize their personal energy costs attaining a Nash equilibrium. Simulation results confirm that the benefits of the energy trading system are robust to decisions of participating-time that significantly deviate from complete rationality.
On Deep Holes of Projective Reed-Solomon Codes
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we obtain new results on the covering radius and deep holes for projective Reed-Solomon (PRS) codes.
Learning Discriminative Features with Class Encoder
Venue: arXiv cs.CV 2016
Year: 2016

Deep neural networks usually benefit from unsupervised pre-training, e.g. auto-encoders. However, the classifier further needs supervised fine-tuning methods for good discrimination. Besides, due to the limits of full-connection, the application of auto-encoders is usually limited to small, well aligned images. In this paper, we incorporate the supervised information to propose a novel formulation, namely class-encoder, whose training objective is to reconstruct a sample from another one of which the labels are identical. Class-encoder aims to minimize the intra-class variations in the feature space, and to learn a good discriminative manifolds on a class scale. We impose the class-encoder as a constraint into the softmax for better supervised training, and extend the reconstruction on feature-level to tackle the parameter size issue and translation issue. The experiments show that the class-encoder helps to improve the performance on benchmarks of classification and face recognition. This could also be a promising direction for fast training of face recognition models.
How Much Cache is Needed to Achieve Linear Capacity Scaling in Backhaul-Limited Dense Wireless Networks?
Venue: arXiv cs.IT 2016
Year: 2016

Dense wireless networks are a promising solution to meet the huge capacity demand in 5G wireless systems. However, there are two implementation issues, namely the interference and backhaul issues. To resolve these issues, we propose a novel network architecture called the backhaul-limited cached dense wireless network (C-DWN), where a physical layer (PHY) caching scheme is employed at the base stations (BSs) but only a fraction of the BSs have wired payload backhauls. The PHY caching can replace the role of wired backhauls to achieve both the cache-induced MIMO cooperation gain and cache-assisted Multihopping gain. Two fundamental questions are addressed. Can we exploit the PHY caching to achieve linear capacity scaling with limited payload backhauls? If so, how much cache is needed? We show that the capacity of the backhaul-limited C-DWN indeed scales linearly with the number of BSs if the BS cache size is larger than a threshold that depends on the content popularity. We also quantify the throughput gain due to cache-induced MIMO cooperation over conventional caching schemes (which exploit purely the cached-assisted multihopping). Interestingly, the minimum BS cache size needed to achieve a significant cache-induced MIMO cooperation gain is the same as that needed to achieve the linear capacity scaling.
Information Theoretically Secure Databases
Venue: arXiv cs.CR 2016
Year: 2016

We introduce the notion of a database system that is information theoretically "Secure In Between Accesses"--a database system with the properties that 1) users can efficiently access their data, and 2) while a user is not accessing their data, the user's information is information theoretically secure to malicious agents, provided that certain requirements on the maintenance of the database are realized. We stress that the security guarantee is information theoretic and everlasting: it relies neither on unproved hardness assumptions, nor on the assumption that the adversary is computationally or storage bounded. We propose a realization of such a database system and prove that a user's stored information, in between times when it is being legitimately accessed, is information theoretically secure both to adversaries who interact with the database in the prescribed manner, as well as to adversaries who have installed a virus that has access to the entire database and communicates with the adversary. The central idea behind our design is the construction of a "re-randomizing database" that periodically changes the internal representation of the information that is being stored. To ensure security, these remappings of the representation of the data must be made sufficiently often in comparison to the amount of information that is being communicated from the database between remappings and the amount of local memory in the database that a virus may preserve during the remappings. The core of the proof of the security guarantee is the following communication/data tradeoff for the problem of learning sparse parities from uniformly random $n$-bit examples: any algorithm that can learn a parity of size $k$ with probability at least $p$ and extracts at most $r$ bits of information from each example, must see at least $p\cdot \left(\frac{n}{r}\right)^{k/2} c_k$ examples.
A minimal model for the emergence of cooperation in randomly growing networks
Venue: arXiv cs.GT 2016
Year: 2016

Cooperation is observed widely in nature and is thought an essential component of many evolutionary processes, yet the mechanisms by which it arises and persists are still unclear. Among several theories, network reciprocity -- a model of inhomogeneous social interactions -- has been proposed as an enabling mechanism to explain the emergence of cooperation. Existing evolutionary models of this mechanism have tended to focus on highly heterogeneous (scale-free) networks, hence typically assume preferential attachment mechanisms, and consequently the prerequisite that individuals have global network knowledge. Within an evolutionary game theoretic context, using the weak prisoner's dilemma as a metaphor for cooperation, we present a minimal model which describes network growth by chronological random addition of new nodes, combined with regular attrition of less fit members of the population. Specifically our model does not require that agents have access to global information and does not assume scale-free network structure or a preferential attachment mechanism. Further our model supports the emergence of cooperation from initially non-cooperative populations. By reducing dependency on a number of assumptions, this model offers broad applicability and as such may support an explanation of the emergence of cooperation in early evolutionary transitions, where few assumptions can be made.
Lower Bounds on Time-Space Trade-Offs for Approximate Near Neighbors
Venue: arXiv cs.DS 2016
Year: 2016

We show tight lower bounds for the entire trade-off between space and query time for the Approximate Near Neighbor search problem. Our lower bounds hold in a restricted model of computation, which captures all hashing-based approaches. In articular, our lower bound matches the upper bound recently shown in [Laarhoven 2015] for the random instance on a Euclidean sphere (which we show in fact extends to the entire space $\mathbb{R}^d$ using the techniques from [Andoni, Razenshteyn 2015]). We also show tight, unconditional cell-probe lower bounds for one and two probes, improving upon the best known bounds from [Panigrahy, Talwar, Wieder 2010]. In particular, this is the first space lower bound (for any static data structure) for two probes which is not polynomially smaller than for one probe. To show the result for two probes, we establish and exploit a connection to locally-decodable codes.
Estimating the number of communities in a network
Venue: arXiv cs.SI 2016
Year: 2016

Community detection, the division of a network into dense subnetworks with only sparse connections between them, has been a topic of vigorous study in recent years. However, while there exist a range of powerful and flexible methods for dividing a network into a specified number of communities, it is an open question how to determine exactly how many communities one should use. Here we describe a mathematically principled approach for finding the number of communities in a network using a maximum-likelihood method. We demonstrate the approach on a range of real-world examples with known community structure, finding that it is able to determine the number of communities correctly in every case.
Brascamp-Lieb Inequality and Its Reverse: An Information Theoretic View
Venue: arXiv cs.IT 2016
Year: 2016

We generalize a result by Carlen and Cordero-Erausquin on the equivalence between the Brascamp-Lieb inequality and the subadditivity of relative entropy by allowing for random transformations (a broadcast channel). This leads to a unified perspective on several functional inequalities that have been gaining popularity in the context of proving impossibility results. We demonstrate that the information theoretic dual of the Brascamp-Lieb inequality is a convenient setting for proving properties such as data processing, tensorization, convexity and Gaussian optimality. Consequences of the latter include an extension of the Brascamp-Lieb inequality allowing for Gaussian random transformations, the determination of the multivariate Wyner common information for Gaussian sources, and a multivariate version of Nelson's hypercontractivity theorem. Finally we present an information theoretic characterization of a reverse Brascamp-Lieb inequality involving a random transformation (a multiple access channel).
RORS: Enhanced Rule-based OWL Reasoning on Spark
Venue: arXiv cs.DB 2016
Year: 2016

The rule-based OWL reasoning is to compute the deductive closure of an ontology by applying RDF/RDFS and OWL entailment rules. The performance of the rule-based OWL reasoning is often sensitive to the rule execution order. In this paper, we present an approach to enhancing the performance of the rule-based OWL reasoning on Spark based on a locally optimal executable strategy. Firstly, we divide all rules (27 in total) into four main classes, namely, SPO rules (5 rules), type rules (7 rules), sameAs rules (7 rules), and schema rules (8 rules) since, as we investigated, those triples corresponding to the first three classes of rules are overwhelming (e.g., over 99% in the LUBM dataset) in our practical world. Secondly, based on the interdependence among those entailment rules in each class, we pick out an optimal rule executable order of each class and then combine them into a new rule execution order of all rules. Finally, we implement the new rule execution order on Spark in a prototype called RORS. The experimental results show that the running time of RORS is improved by about 30% as compared to Kim & Park's algorithm (2015) using the LUBM200 (27.6 million triples).
On Mobile Cloud for Smart City Applications
Venue: arXiv cs.NI 2016
Year: 2016

This paper is devoted to mobile cloud services in Smart City projects. As per mobile cloud computing paradigm, the data processing and storage are moved from the mobile device to a cloud. In the same time, Smart City services typically contain a set of applications with data sharing options. Most of the services in Smart Cities are actually mashups combined data from several sources. This means that access to all available data is vital to the services. And the mobile cloud is vital because the mobile terminals are one of the main sources for data gathering. In our work, we discuss criteria for selecting mobile cloud services.
Web Spam Detection Using Multiple Kernels in Twin Support Vector Machine
Venue: arXiv cs.IR 2016
Year: 2016

Search engines are the most important tools for web data acquisition. Web pages are crawled and indexed by search Engines. Users typically locate useful web pages by querying a search engine. One of the challenges in search engines administration is spam pages which waste search engine resources. These pages by deception of search engine ranking algorithms try to be showed in the first page of results. There are many approaches to web spam pages detection such as measurement of HTML code style similarity, pages linguistic pattern analysis and machine learning algorithm on page content features. One of the famous algorithms has been used in machine learning approach is Support Vector Machine (SVM) classifier. Recently basic structure of SVM has been changed by new extensions to increase robustness and classification accuracy. In this paper we improved accuracy of web spam detection by using two nonlinear kernels into Twin SVM (TSVM) as an improved extension of SVM. The classifier ability to data separation has been increased by using two separated kernels for each class of data. Effectiveness of new proposed method has been experimented with two publicly used spam datasets called UK-2007 and UK-2006. Results show the effectiveness of proposed kernelized version of TSVM in web spam page detection.
Function-Described Graphs for Structural Pattern Recognition
Venue: arXiv cs.AI 2016
Year: 2016

We present in this article the model Function-described graph (FDG), which is a type of compact representation of a set of attributed graphs (AGs) that borrow from Random Graphs the capability of probabilistic modelling of structural and attribute information. We define the FDGs, their features and two distance measures between AGs (unclassified patterns) and FDGs (models or classes) and we also explain an efficient matching algorithm. Two applications of FDGs are presented: in the former, FDGs are used for modelling and matching 3D-objects described by multiple views, whereas in the latter, they are used for representing and recognising human faces, described also by several views.