OpenRaiser/Intern-Atlas huggingface dataset:
PeyeDF: an Eye-Tracking Application for Reading and Self-Indexing Research
Venue: arXiv cs.HC 2019
Year: 2019

PeyeDF is a Portable Document Format (PDF) reader with eye tracking support, available as free and open source software. It is especially useful to researchers investigating reading and learning phenomena, as it integrates PDF reading-related behavioural data with gaze-related data. It is suitable for short and long-term research and supports multiple eye tracking systems. We utilised it to conduct an experiment which demonstrated that features obtained from both gaze and reading data collected in the past can predict reading comprehension which takes place in the future. PeyeDF also provides an integrated means for data collection and indexing using the DiMe personal data storage system. It is designed to collect data in the background without interfering with the reading experience, behaving like a modern lightweight PDF reader. Moreover, it supports annotations, tagging and collaborative work. A modular design allows the application to be easily modified in order to support additional eye tracking protocols and run controlled experiments. We discuss the implementation of the software and report on the results of the experiment which we conducted with it.
Fuzzy Rule Interpolation Methods and Fri Toolbox
Venue: arXiv cs.AI 2019
Year: 2019

FRI methods are less popular in the practical application domain. One possible reason is the missing common framework. There are many FRI methods developed independently, having different interpolation concepts and features. One trial for setting up a common FRI framework was the MATLAB FRI Toolbox, developed by Johanyák et. al. in 2006. The goals of this paper are divided as follows: firstly, to present a brief introduction of the FRI methods. Secondly, to introduce a brief description of the refreshed and extended version of the original FRI Toolbox. And thirdly, to use different unified numerical benchmark examples to evaluate and analyze the Fuzzy Rule Interpolation Techniques (FRI) (KH, KH Stabilized, MACI, IMUL, CRF, VKK, GM, FRIPOC, LESFRI, and SCALEMOVE), that will be classified and compared based on different features by following the abnormality and linearity conditions [15].
MISO Wireless Communication Systems via Intelligent Reflecting Surfaces
Venue: arXiv cs.IT 2019
Year: 2019

Intelligent reflecting surfaces (IRSs) have received considerable attention from the wireless communications research community recently. In particular, as low-cost passive devices, IRSs enable the control of the wireless propagation environment, which is not possible in conventional wireless networks. To take full advantage of such IRS-assisted communication systems, both the beamformer at the access point (AP) and the phase shifts at the IRS need to be optimally designed. However, thus far, the optimal design is not well understood. In this paper, a point-to-point IRS-assisted multiple-input single-output (MISO) communication system is investigated. The beamformer at the AP and the IRS phase shifts are jointly optimized to maximize the spectral efficiency. Two efficient algorithms exploiting fixed point iteration and manifold optimization techniques, respectively, are developed for solving the resulting non-convex optimization problem. The proposed algorithms not only achieve a higher spectral efficiency but also lead to a lower computational complexity than the state-of-the-art approach. Simulation results reveal that deploying large-scale IRSs in wireless systems is more efficient than increasing the antenna array size at the AP for enhancing both the spectral and the energy efficiency.
Collage Inference: Using Coded Redundancy for Low Variance Distributed Image Classification
Venue: arXiv cs.CV 2019
Year: 2019

MLaaS (ML-as-a-Service) offerings by cloud computing platforms are becoming increasingly popular. Hosting pre-trained machine learning models in the cloud enables elastic scalability as the demand grows. But providing low latency and reducing the latency variance is a key requirement. Variance is harder to control in a cloud deployment due to uncertainties in resource allocations across many virtual instances. We propose the collage inference technique which uses a novel convolutional neural network model, collage-cnn, to provide low-cost redundancy. A collage-cnn model takes a collage image formed by combining multiple images and performs multi-image classification in one shot, albeit at slightly lower accuracy. We augment a collection of traditional single image classifier models with a single collage-cnn classifier which acts as their low-cost redundant backup. Collage-cnn provides backup classification results if any single image classification requests experience slowdown. Deploying the collage-cnn models in the cloud, we demonstrate that the 99th percentile tail latency of inference can be reduced by 1.2x to 2x compared to replication based approaches while providing high accuracy. Variation in inference latency can be reduced by 1.8x to 15x.
Synthetic Data Generation and Adaption for Object Detection in Smart Vending Machines
Venue: arXiv cs.CV 2019
Year: 2019

This paper presents an improved scheme for the generation and adaption of synthetic images for the training of deep Convolutional Neural Networks(CNNs) to perform the object detection task in smart vending machines. While generating synthetic data has proved to be effective for complementing the training data in supervised learning methods, challenges still exist for generating virtual images which are similar to those of the complex real scenes and minimizing redundant training data. To solve these problems, we consider the simulation of cluttered objects placed in a virtual scene and the wide-angle camera with distortions used to capture the whole scene in the data generation process, and post-processed the generated images with a elaborately-designed generative network to make them more similar to the real images. Various experiments have been conducted to prove the efficiency of using the generated virtual images to enhance the detection precision on existing datasets with limited real training data and the generalization ability of applying the trained network to datasets collected in new environment.
SurfaceBrush: From Virtual Reality Drawings to Manifold Surfaces
Venue: arXiv cs.GR 2019
Year: 2019

Popular Virtual Reality (VR) tools allow users to draw varying-width, ribbon-like 3D brush strokes by moving a hand-held controller in 3D space. Artists frequently use dense collections of such strokes to draw virtual 3D shapes. We propose SurfaceBrush, a surfacing method that converts such VR drawings into user-intended manifold free-form 3D surfaces, providing a novel approach for modeling 3D shapes. The inputs to our method consist of dense collections of artist-drawn stroke ribbons described by the positions and normals of their central polylines, and ribbon widths. These inputs are highly distinct from those handled by existing surfacing frameworks and exhibit different sparsity and error patterns, necessitating a novel surfacing approach. We surface the input stroke drawings by identifying and leveraging local coherence between nearby artist strokes. In particular, we observe that strokes intended to be adjacent on the artist imagined surface often have similar tangent directions along their respective polylines. We leverage this local stroke direction consistency by casting the computation of the user-intended manifold surface as a constrained matching problem on stroke polyline vertices and edges. We first detect and smoothly connect adjacent similarly-directed sequences of stroke edges producing one or more manifold partial surfaces. We then complete the surfacing process by identifying and connecting adjacent similarly directed edges along the borders of these partial surfaces. We confirm the usability of the SurfaceBrush interface and the validity of our drawing analysis via an observational study. We validate our stroke surfacing algorithm by demonstrating an array of manifold surfaces computed by our framework starting from a range of inputs of varying complexity, and by comparing our outputs to reconstructions computed using alternative means.
Classification and Detection in Mammograms with Weak Supervision via Dual Branch Deep Neural Net
Venue: arXiv cs.CV 2019
Year: 2019

The high cost of generating expert annotations, poses a strong limitation for supervised machine learning methods in medical imaging. Weakly supervised methods may provide a solution to this tangle. In this study, we propose a novel deep learning architecture for multi-class classification of mammograms according to the severity of their containing anomalies, having only a global tag over the image. The suggested scheme further allows localization of the different types of findings in full resolution. The new scheme contains a dual branch network that combines region-level classification with region ranking. We evaluate our method on a large multi-center mammography dataset including $\sim$3,000 mammograms with various anomalies and demonstrate the advantages of the proposed method over a previous weakly-supervised strategy.
Tight FPT Approximations for $k$-Median and $k$-Means
Venue: arXiv cs.DS 2019
Year: 2019

We investigate the fine-grained complexity of approximating the classical $k$-median / $k$-means clustering problems in general metric spaces. We show how to improve the approximation factors to $(1+2/e+\varepsilon)$ and $(1+8/e+\varepsilon)$ respectively, using algorithms that run in fixed-parameter time. Moreover, we show that we cannot do better in FPT time, modulo recent complexity-theoretic conjectures.
Efficient Black-Box Identity Testing over Free Group Algebra
Venue: arXiv cs.CC 2019
Year: 2019

Hrubeš and Wigderson [HW14] initiated the study of noncommutative arithmetic circuits with division computing a noncommutative rational function in the free skew field, and raised the question of rational identity testing. It is now known that the problem can be solved in deterministic polynomial time in the white-box model for noncommutative formulas with inverses, and in randomized polynomial time in the black-box model [GGOW16, IQS18, DM18], where the running time is polynomial in the size of the formula. The complexity of identity testing of noncommutative rational functions remains open in general (when the formula size is not polynomially bounded). We solve the problem for a natural special case. We consider polynomial expressions in the free group algebra $\mathbb{F}\langle X, X^{-1}\rangle$ where $X=\{x_1, x_2, \ldots, x_n\}$, a subclass of rational expressions of inversion height one. Our main results are the following. 1. Given a degree $d$ expression $f$ in $\mathbb{F}\langle X, X^{-1}\rangle$ as a black-box, we obtain a randomized $\text{poly}(n,d)$ algorithm to check whether $f$ is an identically zero expression or not. We obtain this by generalizing the Amitsur-Levitzki theorem [AL50] to $\mathbb{F}\langle X, X^{-1}\rangle$. This also yields a deterministic identity testing algorithm (and even an expression reconstruction algorithm) that is polynomial time in the sparsity of the input expression. 2. Given an expression $f$ in $\mathbb{F}\langle X, X^{-1}\rangle$ of degree at most $D$, and sparsity $s$, as black-box, we can check whether $f$ is identically zero or not in randomized $\text{poly}(n,\log s, \log D)$ time.
Towards a New Extracting and Querying Approach of Fuzzy Summaries
Venue: arXiv cs.DB 2019
Year: 2019

Diversification of DB applications highlighted the limitations of relational database management system (RDBMS) particularly on the modeling plan. In fact, in the real world, we are increasingly faced with the situation where applications need to handle imprecise data and to offer a flexible querying to their users. Several theoretical solutions have been proposed. However, the impact of this work in practice remained negligible with the exception of a few research prototypes based on the formal model GEFRED. In this chapter, the authors propose a new approach for exploitation of fuzzy relational databases (FRDB) described by the model GEFRED. This approach consists of 1) a new technique for extracting summary fuzzy data, Fuzzy SAINTETIQ, based on the classification of fuzzy data and formal concepts analysis; 2) an approach of assessing flexible queries in the context of FDB based on the set of fuzzy summaries generated by our fuzzy SAINTETIQ system; 3) an approach of repairing and substituting unanswered query.
Toward Undetectable Quantum Key Distribution over Bosonic Channels
Venue: arXiv cs.IT 2019
Year: 2019

We show that covert secret key expansion is possible using a public authenticated classical channel and a quantum channel largely under control of an adversary, which we precisely define. We also prove a converse result showing that, under the golden standard of quantum key distribution by which the adversary completely controls the quantum channel, no covert key generation is possible. We propose a protocol based on pulse-position modulation and multi-level coding that allows one to use traditional quantum key distribution (QKD) protocols while ensuring covertness, in the sense that no statistical test by the adversary can detect the presence of communication better than a random guess. When run over a bosonic channel, our protocol can leverage existing discrete-modulated continuous variable protocols. Since existing techniques to bound Eve's information do not directly apply, we develop a new bound that results in positive throughput for a range of channel parameters.
Machine Learning in the Air
Venue: arXiv cs.IT 2019
Year: 2019

Thanks to the recent advances in processing speed and data acquisition and storage, machine learning (ML) is penetrating every facet of our lives, and transforming research in many areas in a fundamental manner. Wireless communications is another success story -- ubiquitous in our lives, from handheld devices to wearables, smart homes, and automobiles. While recent years have seen a flurry of research activity in exploiting ML tools for various wireless communication problems, the impact of these techniques in practical communication systems and standards is yet to be seen. In this paper, we review some of the major promises and challenges of ML in wireless communication systems, focusing mainly on the physical layer. We present some of the most striking recent accomplishments that ML techniques have achieved with respect to classical approaches, and point to promising research directions where ML is likely to make the biggest impact in the near future. We also highlight the complementary problem of designing physical layer techniques to enable distributed ML at the wireless network edge, which further emphasizes the need to understand and connect ML with fundamental concepts in wireless communications.
Optimal Task Assignment and Power Allocation for NOMA Mobile-Edge Computing Networks
Venue: arXiv cs.IT 2019
Year: 2019

Mobile edge computing (MEC) can enhance the computing capability of mobile devices, and non-orthogonal multiple access (NOMA) can provide high data rates. Combining these two technologies can effectively benefit the network with spectrum and energy efficiency. In this paper, we investigate the task completion time minimization in NOMA multiuser MEC networks, where multiple users can offload their tasks simultaneously via the same frequency band. We adopt the \emph{partial} offloading, in which each user can partition its computation task into offloading computing and locally computing parts. We aim to minimize the maximum task latency among users by optimizing their tasks partition ratios and offloading transmit power. By considering the energy consumption and transmitted power limitation of each user, the formulated problem is quasi-convex. Thus, a bisection search (BSS) iterative algorithm is proposed to obtain the minimum task completion time. To reduce the complexity of the BSS algorithm and evaluate its optimality, we further derive the closed-form expressions of the optimal task partition ratio and offloading power for two-user NOMA MEC networks based on the analysed results. Simulation results demonstrate the convergence and optimality of the proposed a BSS algorithm and the effectiveness of the proposed optimal derivation.
Algorithm Diversity for Resilient Systems
Venue: arXiv cs.CR 2019
Year: 2019

Diversity can significantly increase the resilience of systems, by reducing the prevalence of shared vulnerabilities and making vulnerabilities harder to exploit. Work on software diversity for security typically creates variants of a program using low-level code transformations. This paper is the first to study algorithm diversity for resilience. We first describe how a method based on high-level invariants and systematic incrementalization can be used to create algorithm variants. Executing multiple variants in parallel and comparing their outputs provides greater resilience than executing one variant. To prevent different parallel schedules from causing variants' behaviors to diverge, we present a synchronized execution algorithm for DistAlgo, an extension of Python for high-level, precise, executable specifications of distributed algorithms. We propose static and dynamic metrics for measuring diversity. An experimental evaluation of algorithm diversity combined with implementation-level diversity for several sequential algorithms and distributed algorithms shows the benefits of algorithm diversity.
Dichotomy for symmetric Boolean PCSPs
Venue: arXiv cs.CC 2019
Year: 2019

A PCSP is a combination of two CSPs defined by two similar templates; the computational question is to distinguish a YES instance of the first one from a NO instance of the second. The computational complexity of many PCSPs remains unknown. Even the case of Boolean templates (solved for CSP by Schaefer [STOC'78]) remains wide open. The main result of Brakensiek and Guruswami [SODA'18] shows that Boolean PCSPs exhibit a dichotomy (PTIME vs. NPC) when "all the clauses are symmetric and allow for negation of variables''. In this paper we remove the "allow for negation of variables'' assumption from the theorem. The "symmetric" assumption means that changing the order of variables in a constraint does not change its satisfiability. The "negation of variables" means that both of the templates share a relation which can be used to effectively negate Boolean variables. The main result of this paper establishes dichotomy for all the symmetric boolean templates. The tractability case of our theorem and the theorem of Brakensiek and Guruswami are almost identical. The main difference, and the main contribution of this work, is the new reason for hardness and the reasoning proving the split.
Attribute Guided Unpaired Image-to-Image Translation with Semi-supervised Learning
Venue: arXiv cs.CV 2019
Year: 2019

Unpaired Image-to-Image Translation (UIT) focuses on translating images among different domains by using unpaired data, which has received increasing research focus due to its practical usage. However, existing UIT schemes defect in the need of supervised training, as well as the lack of encoding domain information. In this paper, we propose an Attribute Guided UIT model termed AGUIT to tackle these two challenges. AGUIT considers multi-modal and multi-domain tasks of UIT jointly with a novel semi-supervised setting, which also merits in representation disentanglement and fine control of outputs. Especially, AGUIT benefits from two-fold: (1) It adopts a novel semi-supervised learning process by translating attributes of labeled data to unlabeled data, and then reconstructing the unlabeled data by a cycle consistency operation. (2) It decomposes image representation into domain-invariant content code and domain-specific style code. The redesigned style code embeds image style into two variables drawn from standard Gaussian distribution and the distribution of domain label, which facilitates the fine control of translation due to the continuity of both variables. Finally, we introduce a new challenge, i.e., disentangled transfer, for UIT models, which adopts the disentangled representation to translate data less related with the training set. Extensive experiments demonstrate the capacity of AGUIT over existing state-of-the-art models.
Typer vs. CAPTCHA: Private information based CAPTCHA to defend against crowdsourcing human cheating
Venue: arXiv cs.CR 2019
Year: 2019

Crowdsourcing human-solving or online typing attacks are destructive problems. However, studies into these topics have been limited. In this paper, we focus on this kind of attacks whereby all the CAPTCHAs can be simply broken because of its design purpose. After pursuing a comprehensive analysis of the Typer phenomenon and the attacking mechanism of CAPTCHA, we present a new CAPTCHA design principle to distinguish human (Typer) from human (user). The core idea is that the challenge process of the CAPTCHA should contain the unique information with a private attribute. The notion of our idea is based on the information asymmetry between humans. Without this private information, Typers will not be able to finish the attack even if they recognize all the characters from the CAPTCHA. We formalize, design and implement two examples on our proposed principle, a character-based, and a datagram-based case, according to a web interaction and password handling program. We challenge the user to select the password from the random characters that are not in the password sequence or to place the randomly sorted sequences into the correct order. A novel generation algorithm with a fuzzy matching method has been proposed to add the capability of human error tolerance and the difficulty of random guess attack. Unlike other solutions, our approach does not need to modify the primary authentication protocol, user interface, and experience of the typical web service. The several user studies' results indicate that our proposed method is both simple (can be solved by humans accurately within less than 20 seconds) and efficient (the Typer can only deploy a random guess attack with a very low success rate).
Link Stream Graph for Temporal Recommendations
Venue: arXiv cs.IR 2019
Year: 2019

Several researches on recommender systems are based on explicit rating data, but in many real world e-commerce platforms, ratings are not always available, and in those situations, recommender systems have to deal with implicit data such as users' purchase history, browsing history and streaming history. In this context, classical bipartite user-item graphs (BIP) are widely used to compute top-N recommendations. However, these graphs have some limitations, particularly in terms of taking temporal dynamic into account. This is not good because users' preference change over time. To overcome this limit, the Session-based Temporal Graph (STG) was proposed by Xiang et al. to combine long- and short-term preferences in a graph-based recommender system. But in the STG, time is divided into slices and therefore considered discontinuously. This approach loses details of the real temporal dynamics of user actions. To address this challenge, we propose the Link Stream Graph (LSG) which is an extension of link stream representation proposed by Latapy et al. and which allows to model interactions between users and items by considering time continuously. Experiments conducted on four real world implicit datasets for temporal recommendation, with 3 evaluation metrics, show that LSG is the best in 9 out of 12 cases compared to BIP and STG which are the most used state-of-the-art recommender graphs.