OpenRaiser/Intern-Atlas huggingface dataset:
The Landscape of Minimum Label Cut (Hedge Connectivity) Problem
Venue: arXiv cs.DS 2019
Year: 2019

Minimum Label Cut (or Hedge Connectivity) problem is defined as follows: given an undirected graph $G=(V, E)$ with $n$ vertices and $m$ edges, in which, each edge is labeled (with one or multiple labels) from a label set $L=\{\ell_1,\ell_2, ..., \ell_{|L|}\}$, the edges may be weighted with weight set $W =\{w_1, w_2, ..., w_m\}$, the label cut problem(hedge connectivity) problem asks for the minimum number of edge sets(each edge set (or hedge) is the edges with the same label) whose removal disconnects the source-sink pair of vertices or the whole graph with minimum total weights(minimum cardinality for unweighted version). This problem is more general than edge connectivity and hypergraph edge connectivity problem and has a lot of applications in MPLS, IP networks, synchronous optical networks, image segmentation, and other areas. However, due to limited communications between different communities, this problem was studied in different names, with some important existing literature citations missing, or sometimes the results are misleading with some errors. In this paper, we make a further investigation of this problem, give uniform definitions, fix existing errors, provide new insights and show some new results. Specifically, we show the relationship between non-overlapping version(each edge only has one label) and overlapping version(each edge has multiple labels), by fixing the error in the existing literature; hardness and approximation performance between weighted version and unweighted version and some useful properties for further research.
Latent User Linking for Collaborative Cross Domain Recommendation
Venue: arXiv cs.IR 2019
Year: 2019

With the widespread adoption of information systems, recommender systems are widely used for better user experience. Collaborative filtering is a popular approach in implementing recommender systems. Yet, collaborative filtering methods are highly dependent on user feedback, which is often highly sparse and hard to obtain. However, such issues could be alleviated if knowledge from a much denser and a related secondary domain could be used to enhance the recommendation accuracy in the sparse target domain. In this publication, we propose a deep learning method for cross-domain recommender systems through the linking of cross-domain user latent representations as a form of knowledge transfer across domains. We assume that cross-domain similarities of user tastes and behaviors are clearly observable in the low dimensional user latent representations. These user similarities are used to link the domains. As a result, we propose a Variational Autoencoder based network model for cross-domain linking with added contextualization to handle sparse data and for better transfer of cross-domain knowledge. We further extend the model to be more suitable in cold start scenarios and to utilize auxiliary user information for additional gains in recommendation accuracy. The effectiveness of the proposed model was empirically evaluated using multiple datasets. The experiments proved that the proposed model outperforms the state of the art techniques.
Modeling, Analysis, and Optimization of Caching in Multi-Antenna Small-Cell Networks
Venue: arXiv cs.IT 2019
Year: 2019

In traditional cache-enabled small-cell networks (SCNs), a user can suffer strong interference due to contentcentric base station association. This may degenerate the advantage of collaborative content caching among multiple small base stations (SBSs), including probabilistic caching and coded caching. In this work, we tackle this issue by deploying multiple antennas at each SBS for interference management. Two types of beamforming are considered. One is matched-filter (MF) to strengthen the effective channel gain of the desired signal, and the other is zero-forcing (ZF) to cancel interference within a selected SBS cooperation group. We apply these two beamforming techniques in both probabilistic caching and coded caching, and conduct performance analysis using stochastic geometry. We obtain exact and approximate compact integral expressions of system performances measured by average fractional offloaded traffic (AFOT) and average ergodic spectral efficiency (AESE). Based on these expressions, we then optimize the caching parameters for AFOT or AESE maximization. For probabilistic caching, optimal caching solutions are obtained. For coded caching, an efficient greedy-based algorithm is proposed. Numerical results show that multiple antennas can boost the advantage of probabilistic caching and coded caching over the traditional most popular caching with the proper use of beamforming.
Implicit Recursive Characteristics of STOP
Venue: arXiv cs.PL 2019
Year: 2019

The most important notations of Communicating Sequential Process(CSP) are the process and the prefix (event)$\rightarrow$(process) operator. While we can formally apply the $\rightarrow$ operator to define a live process's behavior, the STOP process, which usually resulted from deadlock, starving or livelock, is lack of formal description, defined by most literatures as "doing nothing but halt". In this paper, we argue that the STOP process should not be considered as a black box, it should follow the prefix $\rightarrow$ schema and the same inference rules so that a unified and consistent process algebra model can be established. In order to achieve this goal, we introduce a special event called "nil" that any process can take. This nil event will do nothing meaningful and leave nothing on a process's observable record. With the nil event and its well-defined rules, we can successfully use the $\rightarrow$ operator to formally describe a process's complete behavior in its whole life circle. More interestingly, we can use prefix $\rightarrow$ and nil event to fully describe the STOP process's internal behavior and conclude that the STOP's formal equation can be given as simple as STOP$_{αX} = μ$ X. nil $\rightarrow$ X.
Balanced Schnyder woods for planar triangulations: an experimental study with applications to graph drawing and graph separators
Venue: arXiv cs.DS 2019
Year: 2019

In this work we consider balanced Schnyder woods for planar graphs, which are Schnyder woods where the number of incoming edges of each color at each vertex is balanced as much as possible. We provide a simple linear-time heuristic leading to obtain well balanced Schnyder woods in practice. As test applications we consider two important algorithmic problems: the computation of Schnyder drawings and of small cycle separators. While not being able to provide theoretical guarantees, our experimental results (on a wide collection of planar graphs) suggest that the use of balanced Schnyder woods leads to an improvement of the quality of the layout of Schnyder drawings, and provides an efficient tool for computing short and balanced cycle separators.
Heterogeneous Coded Distributed Computing: Joint Design of File Allocation and Function Assignment
Venue: arXiv cs.IT 2019
Year: 2019

This paper studies the computation-communication tradeoff in a heterogeneous MapReduce computing system where each distributed node is equipped with different computation capability. We first obtain an achievable communication load for any given computation load and any given function assignment at each node. The proposed file allocation strategy has two steps: first, the input files are partitioned into disjoint batches, each with possibly different size and computed by a distinct node; then, each node computes additional files from its non-computed files according to its redundant computation capability. In the Shuffle phase, coded multicasting opportunities are exploited thanks to the repetitive file allocation among different nodes. Based on this scheme, we further propose the computation-aware and the shuffle-aware function assignments. We prove that, by using proper function assignments, our achievable communication load for any given computation load is within a constant multiplicative gap to the optimum in an equivalent homogeneous system with the same average computation load. Numerical results show that our scheme with shuffle-aware function assignment achieves better computation-communication tradeoff than existing works in some cases.
Fast End-to-End Wikification
Venue: arXiv cs.CL 2019
Year: 2019

Wikification of large corpora is beneficial for various NLP applications. Existing methods focus on quality performance rather than run-time, and are therefore non-feasible for large data. Here, we introduce RedW, a run-time oriented Wikification solution, based on Wikipedia redirects, that can Wikify massive corpora with competitive performance. We further propose an efficient method for estimating RedW confidence, opening the door for applying more demanding methods only on top of RedW lower-confidence results. Our experimental results support the validity of the proposed approach.
WeGotYouCovered: The Winning Solver from the PACE 2019 Implementation Challenge, Vertex Cover Track
Venue: arXiv cs.DS 2019
Year: 2019

We present the winning solver of the PACE 2019 Implementation Challenge, Vertex Cover Track. The minimum vertex cover problem is one of a handful of problems for which kernelization---the repeated reducing of the input size via data reduction rules---is known to be highly effective in practice. Our algorithm uses a portfolio of techniques, including an aggressive kernelization strategy, local search, branch-and-reduce, and a state-of-the-art branch-and-bound solver. Of particular interest is that several of our techniques were not from the literature on the vertex over problem: they were originally published to solve the (complementary) maximum independent set and maximum clique problems. Aside from illustrating our solver's performance in the PACE 2019 Implementation Challenge, our experiments provide several key insights not yet seen before in the literature. First, kernelization can boost the performance of branch-and-bound clique solvers enough to outperform branch-and-reduce solvers. Second, local search can significantly boost the performance of branch-and-reduce solvers. And finally, somewhat surprisingly, kernelization can sometimes make branch-and-bound algorithms perform worse than running branch-and-bound alone.
3D Marketplace: Distributed Attestation of 3D Designs on Blockchain
Venue: arXiv cs.CR 2019
Year: 2019

Additive manufacturing (AM), or 3D printing, is an emerging manufacturing technology that is expected to have far-reaching socioeconomic, environmental, and geopolitical implications. As the use of this technology increases, the need for validation of 3D designs grows. In order to create a marketplace in which 3D designs are traded, it is necessary to develop a platform that enables the attestation of the 3D designs and promotes truthfulness. In this paper, we introduce a novel concept of a distributed marketplace that will support the attestation of 3D printing designs. We build a mathematical trust model that ensures truthfulness among rational, selfish, and independent agents, which is based on a reward/penalty system. The payment for participating in the evaluation is calculated by factoring in agents' reputation and peer feedback. Moreover, we describe the architecture and the implementation of the trust model on blockchain using smart contracts for the creation of a distributed marketplace. Our model relies both on theoretical and practical best practices to create an unique platform that elicit effort and truthfulness from the participants.
PrivFT: Private and Fast Text Classification with Homomorphic Encryption
Venue: arXiv cs.CR 2019
Year: 2019

The need for privacy-preserving analytics is higher than ever due to the severity of privacy risks and to comply with new privacy regulations leading to an amplified interest in privacy-preserving techniques that try to balance between privacy and utility. In this work, we present an efficient method for Text Classification while preserving the privacy of the content using Fully Homomorphic Encryption (FHE). Our system (named \textbf{Priv}ate \textbf{F}ast \textbf{T}ext (PrivFT)) performs two tasks: 1) making inference of encrypted user inputs using a plaintext model and 2) training an effective model using an encrypted dataset. For inference, we train a supervised model and outline a system for homomorphic inference on encrypted user inputs with zero loss to prediction accuracy. In the second part, we show how to train a model using fully encrypted data to generate an encrypted model. We provide a GPU implementation of the Cheon-Kim-Kim-Song (CKKS) FHE scheme and compare it with existing CPU implementations to achieve 1 to 2 orders of magnitude speedup at various parameter settings. We implement PrivFT in GPUs to achieve a run time per inference of less than 0.66 seconds. Training on a relatively large encrypted dataset is more computationally intensive requiring 5.04 days.
A survey on intrinsic motivation in reinforcement learning
Venue: arXiv cs.LG 2019
Year: 2019

The reinforcement learning (RL) research area is very active, with an important number of new contributions; especially considering the emergent field of deep RL (DRL). However a number of scientific and technical challenges still need to be addressed, amongst which we can mention the ability to abstract actions or the difficulty to explore the environment which can be addressed by intrinsic motivation (IM). In this article, we provide a survey on the role of intrinsic motivation in DRL. We categorize the different kinds of intrinsic motivations and detail for each category, its advantages and limitations with respect to the mentioned challenges. Additionnally, we conduct an in-depth investigation of substantial current research questions, that are currently under study or not addressed at all in the considered research area of DRL. We choose to survey these research works, from the perspective of learning how to achieve tasks. We suggest then, that solving current challenges could lead to a larger developmental architecture which may tackle most of the tasks. We describe this developmental architecture on the basis of several building blocks composed of a RL algorithm and an IM module compressing information.
On Regularization Properties of Artificial Datasets for Deep Learning
Venue: arXiv cs.LG 2019
Year: 2019

The paper discusses regularization properties of artificial data for deep learning. Artificial datasets allow to train neural networks in the case of a real data shortage. It is demonstrated that the artificial data generation process, described as injecting noise to high-level features, bears several similarities to existing regularization methods for deep neural networks. One can treat this property of artificial data as a kind of "deep" regularization. It is thus possible to regularize hidden layers of the network by generating the training data in a certain way.
CommentsRadar: Dive into Unique Data on All Comments on the Web
Venue: arXiv cs.IR 2019
Year: 2019

We introduce an entity-centric search engineCommentsRadarthatpairs entity queries with articles and user opinions covering a widerange of topics from top commented sites. The engine aggregatesarticles and comments for these articles, extracts named entities,links them together and with knowledge base entries, performssentiment analysis, and aggregates the results, aiming to mine fortemporal trends and other insights. In this work, we present thegeneral engine, discuss the models used for all steps of this pipeline,and introduce several case studies that discover important insightsfrom online commenting data.
Autonomous, Monocular, Vision-Based Snake Robot Navigation and Traversal of Cluttered Environments using Rectilinear Gait Motion
Venue: arXiv cs.RO 2019
Year: 2019

Rectilinear forms of snake-like robotic locomotion are anticipated to be an advantage in obstacle-strewn scenarios characterizing urban disaster zones, subterranean collapses, and other natural environments. The elongated, laterally-narrow footprint associated with these motion strategies is well-suited to traversal of confined spaces and narrow pathways. Navigation and path planning in the absence of global sensing, however, remains a pivotal challenge to be addressed prior to practical deployment of these robotic mechanisms. Several challenges related to visual processing and localization need to be resolved to to enable navigation. As a first pass in this direction, we equip a wireless, monocular color camera to the head of a robotic snake. Visiual odometry and mapping from ORB-SLAM permits self-localization in planar, obstacle-strewn environments. Ground plane traversability segmentation in conjunction with perception-space collision detection permits path planning for navigation. A previously presented dynamical reduction of rectilinear snake locomotion to a non-holonomic kinematic vehicle informs both SLAM and planning. The simplified motion model is then applied to track planned trajectories through an obstacle configuration. This navigational framework enables a snake-like robotic platform to autonomously navigate and traverse unknown scenarios with only monocular vision.
360-Degree Textures of People in Clothing from a Single Image
Venue: arXiv cs.CV 2019
Year: 2019

In this paper we predict a full 3D avatar of a person from a single image. We infer texture and geometry in the UV-space of the SMPL model using an image-to-image translation method. Given partial texture and segmentation layout maps derived from the input view, our model predicts the complete segmentation map, the complete texture map, and a displacement map. The predicted maps can be applied to the SMPL model in order to naturally generalize to novel poses, shapes, and even new clothing. In order to learn our model in a common UV-space, we non-rigidly register the SMPL model to thousands of 3D scans, effectively encoding textures and geometries as images in correspondence. This turns a difficult 3D inference task into a simpler image-to-image translation one. Results on rendered scans of people and images from the DeepFashion dataset demonstrate that our method can reconstruct plausible 3D avatars from a single image. We further use our model to digitally change pose, shape, swap garments between people and edit clothing. To encourage research in this direction we will make the source code available for research purpose.
MicroTEE: Designing TEE OS Based on the Microkernel Architecture
Venue: arXiv cs.CR 2019
Year: 2019

ARM TrustZone technology is widely used to provide Trusted Execution Environments (TEE) for mobile devices. However, most TEE OSes are implemented as monolithic kernels. In such designs, device drivers, kernel services and kernel modules all run in the kernel, which results in large size of the kernel. It is difficult to guarantee that all components of the kernel have no security vulnerabilities in the monolithic kernel architecture, such as the integer overflow vulnerability in Qualcomm QSEE TrustZone and the TZDriver vulnerability in HUAWEI Hisilicon TEE architecture. This paper presents MicroTEE, a TEE OS based on the microkernel architecture. In MicroTEE, the microkernel provides strong isolation for TEE OS's basic services, such as crypto service and platform key management service. The kernel is only responsible for providing core services such as address space management, thread management, and inter-process communication. Other fundamental services, such as crypto service and platform key management service are implemented as applications at the user layer. Crypto Services and Key Management are used to provide Trusted Applications (TAs) with sensitive information encryption, data signing, and platform attestation functions. Our design avoids the compromise of the whole TEE OS if only one kernel service is vulnerable. A monitor has also been added to perform the switch between the secure world and the normal world. Finally, we implemented a MicroTEE prototype on the Freescale i.MX6Q Sabre Lite development board and tested its performance. Evaluation results show that the performance of cryptographic operations in MicroTEE is better than it in Linux when the size of data is small.
Compliance Change Tracking in Business Process Services
Venue: arXiv cs.LG 2019
Year: 2019

Regulatory compliance is an organization's adherence to laws, regulations, guidelines and specifications relevant to its business. Compliance officers responsible for maintaining adherence constantly struggle to keep up with the large amount of changes in regulatory requirements. Keeping up with the changes entail two main tasks: fetching the regulatory announcements that actually contain changes of interest, and incorporating those changes in the business process. In this paper we focus on the first task, and present a Compliance Change Tracking System, that gathers regulatory announcements from government sites, news sites, email subscriptions; classifies their importance i.e Actionability through a hierarchical classifier, and business process applicability through a multi-class classifier. For these classifiers, we experiment with several approaches such as vanilla classification methods (e.g. Naive Bayes, logistic regression etc.), hierarchical classification methods, rule based approach, hybrid approach with various preprocessing and feature selection methods; and show that despite the richness of other models, a simple hierarchical classification with bag-of-words features works the best for Actionability classifier and multi-class logistic regression works the best for Applicability classifier. The system has been deployed in global delivery centers, and has received positive feedback from payroll compliance officers.
Unsupervised Hierarchical Grouping of Knowledge Graph Entities
Venue: arXiv cs.IR 2019
Year: 2019

Knowledge graphs have attracted lots of attention in academic and industrial environments. Despite their usefulness, popular knowledge graphs suffer from incompleteness of information, especially in their type assertions. This has encouraged research in the automatic discovery of entity types. In this context, multiple works were developed to utilize logical inference on ontologies and statistical machine learning methods to learn type assertion in knowledge graphs. However, these approaches suffer from limited performance on noisy data, limited scalability and the dependence on labeled training samples. In this work, we propose a new unsupervised approach that learns to categorize entities into a hierarchy of named groups. We show that our approach is able to effectively learn entity groups using a scalable procedure in noisy and sparse datasets. We experiment our approach on a set of popular knowledge graph benchmarking datasets, and we publish a collection of the outcome group hierarchies.
Comparing ternary and binary adders and multipliers
Venue: arXiv cs.AR 2019
Year: 2019

While many papers have proposed implementations of ternary adders and ternary multipliers, no comparisons have generally been done with the corresponding binary ones. We compare the implementations of binary and ternary adders and multipliers with the same computing capability according to the basic blocks that are 1-bit and 1-trit adders and 1-bit and 1-trit multipliers. Then we compare the complexity of these basic blocks by using the same CNTFET technology to evaluate the overall complexity of N-bit adders and M-trit adders on one side, and NxN bit multipliers and MxM trits multipliers with M = N/IR (IR = log(3)/log(2) is the information ratio). While ternary adders and multipliers have less input and output connections and use less basic building blocks, the complexity of the ternary building blocks is too high and the ternary adders and multipliers cannot compete with the binary ones.