OpenRaiser/Intern-Atlas huggingface dataset:
What is an Ontology?
Venue: arXiv cs.AI 2018
Year: 2018

In the knowledge engineering community "ontology" is usually defined in the tradition of Gruber as an "explicit specification of a conceptualization". Several variations of this definition exist. In the paper we argue that (with one notable exception) these definitions are of no explanatory value, because they violate one of the basic rules for good definitions: The defining statement (the definiens) should be clearer than the term that is defined (the definiendum). In the paper we propose a different definition of "ontology" and discuss how it helps to explain various phenomena: the ability of ontologies to change, the role of the choice of vocabulary, the significance of annotations, the possibility of collaborative ontology development, and the relationship between ontological conceptualism and ontological realism.
Optimal terminal dimensionality reduction in Euclidean space
Venue: arXiv cs.DS 2018
Year: 2018

Let $\varepsilon\in(0,1)$ and $X\subset\mathbb R^d$ be arbitrary with $|X|$ having size $n>1$. The Johnson-Lindenstrauss lemma states there exists $f:X\rightarrow\mathbb R^m$ with $m = O(\varepsilon^{-2}\log n)$ such that $$ \forall x\in X\ \forall y\in X, \|x-y\|_2 \le \|f(x)-f(y)\|_2 \le (1+\varepsilon)\|x-y\|_2 . $$ We show that a strictly stronger version of this statement holds, answering one of the main open questions of [MMMR18]: "$\forall y\in X$" in the above statement may be replaced with "$\forall y\in\mathbb R^d$", so that $f$ not only preserves distances within $X$, but also distances to $X$ from the rest of space. Previously this stronger version was only known with the worse bound $m = O(\varepsilon^{-4}\log n)$. Our proof is via a tighter analysis of (a specific instantiation of) the embedding recipe of [MMMR18].
Challenges in Network Management of Encrypted Traffic
Venue: arXiv cs.NI 2018
Year: 2018

This paper summarizes the challenges identified at the MAMI Management and Measurement Summit (M3S) for network management with the increased deployment of encrypted traffic based on a set of use cases and deployed techniques (for network monitoring, performance enhancing proxies, firewalling as well as network-supported DDoS protection and migration), and provides recommendations for future use cases and the development of new protocols and mechanisms. In summary, network architecture and protocol design efforts should 1) provide for independent measurability when observations may be contested, 2) support different security associations at different layers, and 3) replace transparent middleboxes with middlebox transparency in order to increase visibility, rebalance control and enable cooperation.
From Hard to Soft: Understanding Deep Network Nonlinearities via Vector Quantization and Statistical Inference
Venue: arXiv cs.LG 2018
Year: 2018

Nonlinearity is crucial to the performance of a deep (neural) network (DN). To date there has been little progress understanding the menagerie of available nonlinearities, but recently progress has been made on understanding the rôle played by piecewise affine and convex nonlinearities like the ReLU and absolute value activation functions and max-pooling. In particular, DN layers constructed from these operations can be interpreted as {\em max-affine spline operators} (MASOs) that have an elegant link to vector quantization (VQ) and $K$-means. While this is good theoretical progress, the entire MASO approach is predicated on the requirement that the nonlinearities be piecewise affine and convex, which precludes important activation functions like the sigmoid, hyperbolic tangent, and softmax. {\em This paper extends the MASO framework to these and an infinitely large class of new nonlinearities by linking deterministic MASOs with probabilistic Gaussian Mixture Models (GMMs).} We show that, under a GMM, piecewise affine, convex nonlinearities like ReLU, absolute value, and max-pooling can be interpreted as solutions to certain natural "hard" VQ inference problems, while sigmoid, hyperbolic tangent, and softmax can be interpreted as solutions to corresponding "soft" VQ inference problems. We further extend the framework by hybridizing the hard and soft VQ optimizations to create a $β$-VQ inference that interpolates between hard, soft, and linear VQ inference. A prime example of a $β$-VQ DN nonlinearity is the {\em swish} nonlinearity, which offers state-of-the-art performance in a range of computer vision tasks but was developed ad hoc by experimentation. Finally, we validate with experiments an important assertion of our theory, namely that DN performance can be significantly improved by enforcing orthogonality in its linear filters.
On the k-Boundedness for Existential Rules
Venue: arXiv cs.AI 2018
Year: 2018

The chase is a fundamental tool for existential rules. Several chase variants are known, which differ on how they handle redundancies possibly caused by the introduction of nulls. Given a chase variant, the halting problem takes as input a set of existential rules and asks if this set of rules ensures the termination of the chase for any factbase. It is well-known that this problem is undecidable for all known chase variants. The related problem of boundedness asks if a given set of existential rules is bounded, i.e., whether there is a predefined upper bound on the number of (breadth-first) steps of the chase, independently from any factbase. This problem is already undecidable in the specific case of datalog rules. However, knowing that a set of rules is bounded for some chase variant does not help much in practice if the bound is unknown. Hence, in this paper, we investigate the decidability of the k-boundedness problem, which asks whether a given set of rules is bounded by an integer k. We prove that k-boundedness is decidable for three chase variants, namely the oblivious, semi-oblivious and restricted chase.
Adversarial Online Learning with noise
Venue: arXiv cs.LG 2018
Year: 2018

We present and study models of adversarial online learning where the feedback observed by the learner is noisy, and the feedback is either full information feedback or bandit feedback. Specifically, we consider binary losses xored with the noise, which is a Bernoulli random variable. We consider both a constant noise rate and a variable noise rate. Our main results are tight regret bounds for learning with noise in the adversarial online learning model.
Fast Dual Simulation Processing of Graph Database Queries (Supplement)
Venue: arXiv cs.DB 2018
Year: 2018

Graph database query languages feature expressive, yet computationally expensive pattern matching capabilities. Answering optional query clauses in SPARQL for instance renders the query evaluation problem immediately Pspace-complete. Therefore, light-weight graph pattern matching relations, such as simulation, have recently been investigated as promising alternatives to more expensive query mechanisms like, e.g., computing subgraph isomorphism. Still, graph pattern matching alone lacks expressive query capabilities: all patterns are combined by usual join constructs, where more sophisticated capabilities would be inevitable for making solutions useful to emerging applications. In this paper we bridge this gap by introducing a new dual simulation process operating on SPARQL queries. In addition to supporting the full syntactic structure of SPARQL queries, it features polynomial-time pattern matching to compute an overapproximation of query results from the database. Moreover, to achieve runtimes competing with state-of-the-art database systems, we develop a novel algorithmic solution to dual simulation graph pattern matching, based on a system of inequalities that allows for several optimization heuristics. Finally, we achieve soundness of our process for SPARQL queries including UNION, AND and OPTIONAL operators not restricted to well-designed patterns. Our experiments on synthetic and real-world graph data promise a clear gain for graph database systems when incorporating the new dual simulation techniques. In this supplement paper we present in detail all proofs, discussions of experimental results, and complexity analysis for the original paper "Fast Dual Simulation Processing of Graph Database Queries" included in the Proceedings of the 35th IEEE International Conference on Data Engineering (ICDE 2019), Macau, China.
Data Motif-based Proxy Benchmarks for Big Data and AI Workloads
Venue: arXiv cs.DC 2018
Year: 2018

For the architecture community, reasonable simulation time is a strong requirement in addition to performance data accuracy. However, emerging big data and AI workloads are too huge at binary size level and prohibitively expensive to run on cycle-accurate simulators. The concept of data motif, which is identified as a class of units of computation performed on initial or intermediate data, is the first step towards building proxy benchmark to mimic the real-world big data and AI workloads. However, there is no practical way to construct a proxy benchmark based on the data motifs to help simulation-based research. In this paper, we embark on a study to bridge the gap between data motif and a practical proxy benchmark. We propose a data motif-based proxy benchmark generating methodology by means of machine learning method, which combine data motifs with different weights to mimic the big data and AI workloads. Furthermore, we implement various data motifs using light-weight stacks and apply the methodology to five real-world workloads to construct a suite of proxy benchmarks, considering the data types, patterns, and distributions. The evaluation results show that our proxy benchmarks shorten the execution time by 100s times on real systems while maintaining the average system and micro-architecture performance data accuracy above 90%, even changing the input data sets or cluster configurations. Moreover, the generated proxy benchmarks reflect consistent performance trends across different architectures. To facilitate the community, we will release the proxy benchmarks on the project homepage http://prof.ict.ac.cn/BigDataBench.
Predictive Linguistic Features of Schizophrenia
Venue: arXiv cs.CL 2018
Year: 2018

Schizophrenia is one of the most disabling and difficult to treat of all human medical/health conditions, ranking in the top ten causes of disability worldwide. It has been a puzzle in part due to difficulty in identifying its basic, fundamental components. Several studies have shown that some manifestations of schizophrenia (e.g., the negative symptoms that include blunting of speech prosody, as well as the disorganization symptoms that lead to disordered language) can be understood from the perspective of linguistics. However, schizophrenia research has not kept pace with technologies in computational linguistics, especially in semantics and pragmatics. As such, we examine the writings of schizophrenia patients analyzing their syntax, semantics and pragmatics. In addition, we analyze tweets of (self pro-claimed) schizophrenia patients who publicly discuss their diagnoses. For writing samples dataset, syntactic features are found to be the most successful in classification whereas for the less structured Twitter dataset, a combination of features performed the best.
Selection of BJI configuration: Approach based on minimal transversals
Venue: arXiv cs.DB 2018
Year: 2018

Decision systems deal with a large volume of data stored in new databases called data warehouses. Data warehouses are typically modeled by a star schema that conventionally presents a central fact table and a set of dimension tables. The corresponding queries for this type of model are therefore very complex. In order to reduce the cost of executing complex queries, which contain very expensive joins, the solution envisaged would be to guarantee a good physical design of the data warehouses. Binary join indexes are very suitable to reduce the cost of executing these joins. In this work, we proposed a binary join index selection approach based on the notion of minimal transversal. The final configuration obtained is composed of several indexes, which make it possible to optimize the execution cost of the query set.
An Efficient Bandit Algorithm for Realtime Multivariate Optimization
Venue: arXiv cs.LG 2018
Year: 2018

Optimization is commonly employed to determine the content of web pages, such as to maximize conversions on landing pages or click-through rates on search engine result pages. Often the layout of these pages can be decoupled into several separate decisions. For example, the composition of a landing page may involve deciding which image to show, which wording to use, what color background to display, etc. Such optimization is a combinatorial problem over an exponentially large decision space. Randomized experiments do not scale well to this setting, and therefore, in practice, one is typically limited to optimizing a single aspect of a web page at a time. This represents a missed opportunity in both the speed of experimentation and the exploitation of possible interactions between layout decisions. Here we focus on multivariate optimization of interactive web pages. We formulate an approach where the possible interactions between different components of the page are modeled explicitly. We apply bandit methodology to explore the layout space efficiently and use hill-climbing to select optimal content in realtime. Our algorithm also extends to contextualization and personalization of layout selection. Simulation results show the suitability of our approach to large decision spaces with strong interactions between content. We further apply our algorithm to optimize a message that promotes adoption of an Amazon service. After only a single week of online optimization, we saw a 21% conversion increase compared to the median layout. Our technique is currently being deployed to optimize content across several locations at Amazon.com.
Explainable artificial intelligence (XAI), the goodness criteria and the grasp-ability test
Venue: arXiv cs.AI 2018
Year: 2018

This paper introduces the "grasp-ability test" as a "goodness" criteria by which to compare which explanation is more or less meaningful than others for users to understand the automated algorithmic data processing.
A Theory of Lazy Imperative Timing
Venue: arXiv cs.PL 2018
Year: 2018

We present a theory of lazy imperative timing.
Point-cloud-based place recognition using CNN feature extraction
Venue: arXiv cs.CV 2018
Year: 2018

This paper proposes a novel point-cloud-based place recognition system that adopts a deep learning approach for feature extraction. By using a convolutional neural network pre-trained on color images to extract features from a range image without fine-tuning on extra range images, significant improvement has been observed when compared to using hand-crafted features. The resulting system is illumination invariant, rotation invariant and robust against moving objects that are unrelated to the place identity. Apart from the system itself, we also bring to the community a new place recognition dataset containing both point cloud and grayscale images covering a full $360^\circ$ environmental view. In addition, the dataset is organized in such a way that it facilitates experimental validation with respect to rotation invariance or robustness against unrelated moving objects separately.
One Bit Matters: Understanding Adversarial Examples as the Abuse of Redundancy
Venue: arXiv cs.LG 2018
Year: 2018

Despite the great success achieved in machine learning (ML), adversarial examples have caused concerns with regards to its trustworthiness: A small perturbation of an input results in an arbitrary failure of an otherwise seemingly well-trained ML model. While studies are being conducted to discover the intrinsic properties of adversarial examples, such as their transferability and universality, there is insufficient theoretic analysis to help understand the phenomenon in a way that can influence the design process of ML experiments. In this paper, we deduce an information-theoretic model which explains adversarial attacks as the abuse of feature redundancies in ML algorithms. We prove that feature redundancy is a necessary condition for the existence of adversarial examples. Our model helps to explain some major questions raised in many anecdotal studies on adversarial examples. Our theory is backed up by empirical measurements of the information content of benign and adversarial examples on both image and text datasets. Our measurements show that typical adversarial examples introduce just enough redundancy to overflow the decision making of an ML model trained on corresponding benign examples. We conclude with actionable recommendations to improve the robustness of machine learners against adversarial examples.
numpywren: serverless linear algebra
Venue: arXiv cs.DC 2018
Year: 2018

Linear algebra operations are widely used in scientific computing and machine learning applications. However, it is challenging for scientists and data analysts to run linear algebra at scales beyond a single machine. Traditional approaches either require access to supercomputing clusters, or impose configuration and cluster management challenges. In this paper we show how the disaggregation of storage and compute resources in so-called "serverless" environments, combined with compute-intensive workload characteristics, can be exploited to achieve elastic scalability and ease of management. We present numpywren, a system for linear algebra built on a serverless architecture. We also introduce LAmbdaPACK, a domain-specific language designed to implement highly parallel linear algebra algorithms in a serverless setting. We show that, for certain linear algebra algorithms such as matrix multiply, singular value decomposition, and Cholesky decomposition, numpywren's performance (completion time) is within 33% of ScaLAPACK, and its compute efficiency (total CPU-hours) is up to 240% better due to elasticity, while providing an easier to use interface and better fault tolerance. At the same time, we show that the inability of serverless runtimes to exploit locality across the cores in a machine fundamentally limits their network efficiency, which limits performance on other algorithms such as QR factorization. This highlights how cloud providers could better support these types of computations through small changes in their infrastructure.
Color naming guided intrinsic image decomposition
Venue: arXiv cs.CV 2018
Year: 2018

Intrinsic image decomposition is a severely under-constrained problem. User interactions can help to reduce the ambiguity of the decomposition considerably. The traditional way of user interaction is to draw scribbles that indicate regions with constant reflectance or shading. However the effect scopes of the scribbles are quite limited, so dozens of scribbles are often needed to rectify the whole decomposition, which is time consuming. In this paper we propose an efficient way of user interaction that users need only to annotate the color composition of the image. Color composition reveals the global distribution of reflectance, so it can help to adapt the whole decomposition directly. We build a generative model of the process that the albedo of the material produces both the reflectance through imaging and the color labels by color naming. Our model fuses effectively the physical properties of image formation and the top-down information from human color perception. Experimental results show that color naming can improve the performance of intrinsic image decomposition, especially in cleaning the shadows left in reflectance and solving the color constancy problem.
On the Secrecy Unicast Throughput Performance of NOMA Assisted Multicast-Unicast Streaming With Partial Channel Information
Venue: arXiv cs.IT 2018
Year: 2018

This paper considers a downlink single-cell non-orthogonal multiple access (NOMA) network with uniformly deployed users, while a mixed multicast and unicast traffic scenario is taken into account. By guaranteeing the quality of service (QoS) of the multicast traffic, the multicast outage and secrecy unicast throughput performance is evaluated. In particular, two types of partial channel state information (CSI), namely the imperfect CSI and CSI based on second order statistics (SOS), are investigated in the analytical framework. For both two cases, the closed-form approximations for the multicast outage probability and secrecy unicast throughput are derived except that the approximation for the secrecy unicast throughput in SOS-based CSI only concerns two users. As to the multicast outage probability, the simulation results demonstrate that the NOMA scheme considered in both two cases achieves superior performance compared to the traditional orthogonal multiple access (OMA) scheme, while for the secrecy unicast throughput, the NOMA scheme shows great advantages over the OMA scheme in good condition (high signal-to-noise ratio (SNR)), but is inferior to the OMA scheme in poor condition (low SNR). Moreover, both two cases achieve similar performance except that the NOMA scheme with imperfect CSI obtains larger secrecy unicast throughput than that based on SOS under high SNR condition. Finally, the provided numerical results also confirm that the derived approximations of both two cases for the multicast outage probability and secrecy unicast throughput match well with the Monte Carlo simulations.
Mechanism Design for Social Good
Venue: arXiv cs.GT 2018
Year: 2018

Across various domains--such as health, education, and housing--improving societal welfare involves allocating resources, setting policies, targeting interventions, and regulating activities. These solutions have an immense impact on the day-to-day lives of individuals, whether in the form of access to quality healthcare, labor market outcomes, or how votes are accounted for in a democratic society. Problems that can have an out-sized impact on individuals whose opportunities have historically been limited often pose conceptual and technical challenges, requiring insights from many disciplines. Conversely, the lack of interdisciplinary approach can leave these urgent needs unaddressed and can even exacerbate underlying socioeconomic inequalities. To realize the opportunities in these domains, we need to correctly set objectives and reason about human behavior and actions. Doing so requires a deep grounding in the field of interest and collaboration with domain experts who understand the societal implications and feasibility of proposed solutions. These insights can play an instrumental role in proposing algorithmically-informed policies. In this article, we describe the Mechanism Design for Social Good (MD4SG) research agenda, which involves using insights from algorithms, optimization, and mechanism design to improve access to opportunity. The MD4SG research community takes an interdisciplinary, multi-stakeholder approach to improve societal welfare. We discuss three exciting research avenues within MD4SG related to improving access to opportunity in the developing world, labor markets and discrimination, and housing. For each of these, we showcase ongoing work, underline new directions, and discuss potential for implementing existing work in practice.