OpenRaiser/Intern-Atlas huggingface dataset:
Private Information Retrieval Over Gaussian MAC
Venue: arXiv cs.IT 2020
Year: 2020

Consider the problem of Private Information Retrieval (PIR), where a user wishes to retrieve a single message from $N$ non-communicating and non-colluding databases (servers). All servers store the same set of $M$ messages and they respond to the user through a block fading Gaussian Multiple Access Channel (MAC). The goal in this setting is to keep the index of the required message private from the servers while minimizing the overall communication overhead. This work provides joint privacy and channel coding retrieval schemes for the Gaussian MAC with and without fading. The schemes exploit the linearity of the channel while using the Compute and Forward (CF) coding scheme. Consequently, single-user encoding and decoding are performed to retrieve the private message. In the case of a channel without fading, the achievable retrieval rate is shown to outperform a separation-based scheme, in which the retrieval and the channel coding are designed separately. Moreover, this rate is asymptotically optimal as the SNR grows, and are up to a constant gap of $2$ bits per channel use from the channel capacity without privacy constraints, for all SNR values. When the channel suffers from fading, the asymmetry between the servers' channels forces a more complicated solution, which involves a hard optimization problem. Nevertheless, we provide coding scheme and lower bounds on the expected achievable retrieval rate which are shown to have the same scaling laws as the channel capacity, both in the number of servers and the SNR.
Optimizing Investments in Cyber Hygiene for Protecting Healthcare Users
Venue: arXiv cs.CR 2020
Year: 2020

Cyber hygiene measures are often recommended for strengthening an organization's security posture, especially for protecting against social engineering attacks that target the human element. However, the related recommendations are typically the same for all organizations and their employees, regardless of the nature and the level of risk for different groups of users. Building upon an existing cybersecurity investment model, this paper presents a tool for optimal selection of cyber hygiene safeguards, which we refer as the Optimal Safeguards Tool. The model combines game theory and combinatorial optimization taking into account the probability of each user group to being attacked, the value of assets accessible by each group, and the efficacy of each control for a particular group. The model considers indirect cost as the time employees could require for learning and training against an implemented control. Utilizing a game-theoretic framework to support the Knapsack optimization problem permits us to optimally select safeguards' application levels minimizing the aggregated expected damage within a security investment budget. We evaluate OST in a healthcare domain use case. The Critical Internet Security Control group 17 for implementing security awareness and training programs for employees belonging to the ICT, clinical and administration personnel of a hospital. We compare the strategies implemented by OST against alternative common-sense defending approaches for three different types of attackers: Nash, Weighted and Opportunistic. Nash defending strategies are consistently better than the competing strategies for all attacker types with a minor exception where the Nash defending strategy performs at least as good as other common-sense approaches.
List Decoding of Universal Polar Codes
Venue: arXiv cs.IT 2020
Year: 2020

A list decoding scheme for universal polar codes is presented. Our scheme applies to the universal polar codes first introduced by Sasoglu and Wang, and generalized to processes with memory by the authors. These codes are based on the concatenation of different polar transforms: a sequence of "slow" transforms and Arikan's original "fast" transform. List decoding of polar codes has been previously presented in the context of the fast transform. However, the slow transform is markedly different and requires new techniques and data structures. We show that list decoding is possible with space complexity $O(\mathcal{L} \cdot N)$ and time complexity $O(\mathcal{L} \cdot N \log N)$, where $N$ is the overall blocklength and $\mathcal{L}$ is the list size.
Minimum $2$-vertex-twinless connected spanning subgraph problem
Venue: arXiv cs.DS 2020
Year: 2020

Given a $2$-vertex-twinless connected directed graph $G=(V,E)$, the minimum $2$-vertex-twinless connected spanning subgraph problem is to find a minimum cardinality edge subset $E^{t} \subseteq E$ such that the subgraph $(V,E^{t})$ is $2$-vertex-twinless connected. Let $G^{1}$ be a minimal $2$-vertex-connected subgraph of $G$. In this paper we present a $(2+a_{t}/2)$-approximation algorithm for the minimum $2$-vertex-twinless connected spanning subgraph problem, where $a_{t}$ is the number of twinless articulation points in $G^{1}$.
Collaborative Multi-Agent Multi-Armed Bandit Learning for Small-Cell Caching
Venue: arXiv cs.NI 2020
Year: 2020

This paper investigates learning-based caching in small-cell networks (SCNs) when user preference is unknown. The goal is to optimize the cache placement in each small base station (SBS) for minimizing the system long-term transmission delay. We model this sequential multi-agent decision making problem in a multi-agent multi-armed bandit (MAMAB) perspective. Rather than estimating user preference first and then optimizing the cache strategy, we propose several MAMAB-based algorithms to directly learn the cache strategy online in both stationary and non-stationary environment. In the stationary environment, we first propose two high-complexity agent-based collaborative MAMAB algorithms with performance guarantee. Then we propose a low-complexity distributed MAMAB which ignores the SBS coordination. To achieve a better balance between SBS coordination gain and computational complexity, we develop an edge-based collaborative MAMAB with the coordination graph edge-based reward assignment method. In the non-stationary environment, we modify the MAMAB-based algorithms proposed in the stationary environment by proposing a practical initialization method and designing new perturbed terms to adapt to the dynamic environment. Simulation results are provided to validate the effectiveness of our proposed algorithms. The effects of different parameters on caching performance are also discussed.
Private and Communication-Efficient Edge Learning: A Sparse Differential Gaussian-Masking Distributed SGD Approach
Venue: arXiv cs.DC 2020
Year: 2020

With rise of machine learning (ML) and the proliferation of smart mobile devices, recent years have witnessed a surge of interest in performing ML in wireless edge networks. In this paper, we consider the problem of jointly improving data privacy and communication efficiency of distributed edge learning, both of which are critical performance metrics in wireless edge network computing. Toward this end, we propose a new decentralized stochastic gradient method with sparse differential Gaussian-masked stochastic gradients (SDM-DSGD) for non-convex distributed edge learning. Our main contributions are three-fold: i) We theoretically establish the privacy and communication efficiency performance guarantee of our SDM-DSGD method, which outperforms all existing works; ii) We show that SDM-DSGD improves the fundamental training-privacy trade-off by {\em two orders of magnitude} compared with the state-of-the-art. iii) We reveal theoretical insights and offer practical design guidelines for the interactions between privacy preservation and communication efficiency, two conflicting performance goals. We conduct extensive experiments with a variety of learning models on MNIST and CIFAR-10 datasets to verify our theoretical findings. Collectively, our results contribute to the theory and algorithm design for distributed edge learning.
Attribute-guided Feature Learning Network for Vehicle Re-identification
Venue: arXiv cs.CV 2020
Year: 2020

Vehicle re-identification (reID) plays an important role in the automatic analysis of the increasing urban surveillance videos, which has become a hot topic in recent years. However, it poses the critical but challenging problem that is caused by various viewpoints of vehicles, diversified illuminations and complicated environments. Till now, most existing vehicle reID approaches focus on learning metrics or ensemble to derive better representation, which are only take identity labels of vehicle into consideration. However, the attributes of vehicle that contain detailed descriptions are beneficial for training reID model. Hence, this paper proposes a novel Attribute-Guided Network (AGNet), which could learn global representation with the abundant attribute features in an end-to-end manner. Specially, an attribute-guided module is proposed in AGNet to generate the attribute mask which could inversely guide to select discriminative features for category classification. Besides that, in our proposed AGNet, an attribute-based label smoothing (ALS) loss is presented to better train the reID model, which can strength the distinct ability of vehicle reID model to regularize AGNet model according to the attributes. Comprehensive experimental results clearly demonstrate that our method achieves excellent performance on both VehicleID dataset and VeRi-776 dataset.
Deep Reinforcement Learning for Complex Manipulation Tasks with Sparse Feedback
Venue: arXiv cs.LG 2020
Year: 2020

Learning optimal policies from sparse feedback is a known challenge in reinforcement learning. Hindsight Experience Replay (HER) is a multi-goal reinforcement learning algorithm that comes to solve such tasks. The algorithm treats every failure as a success for an alternative (virtual) goal that has been achieved in the episode and then generalizes from that virtual goal to real goals. HER has known flaws and is limited to relatively simple tasks. In this thesis, we present three algorithms based on the existing HER algorithm that improves its performances. First, we prioritize virtual goals from which the agent will learn more valuable information. We call this property the \textit{instructiveness} of the virtual goal and define it by a heuristic measure, which expresses how well the agent will be able to generalize from that virtual goal to actual goals. Secondly, we designed a filtering process that detects and removes misleading samples that may induce bias throughout the learning process. Lastly, we enable the learning of complex, sequential, tasks using a form of curriculum learning combined with HER. We call this algorithm \textit{Curriculum HER}. To test our algorithms, we built three challenging manipulation environments with sparse reward functions. Each environment has three levels of complexity. Our empirical results show vast improvement in the final success rate and sample efficiency when compared to the original HER algorithm.
Complementary Network with Adaptive Receptive Fields for Melanoma Segmentation
Venue: arXiv cs.CV 2020
Year: 2020

Automatic melanoma segmentation in dermoscopic images is essential in computer-aided diagnosis of skin cancer. Existing methods may suffer from the hole and shrink problems with limited segmentation performance. To tackle these issues, we propose a novel complementary network with adaptive receptive filed learning. Instead of regarding the segmentation task independently, we introduce a foreground network to detect melanoma lesions and a background network to mask non-melanoma regions. Moreover, we propose adaptive atrous convolution (AAC) and knowledge aggregation module (KAM) to fill holes and alleviate the shrink problems. AAC explicitly controls the receptive field at multiple scales and KAM convolves shallow feature maps by dilated convolutions with adaptive receptive fields, which are adjusted according to deep feature maps. In addition, a novel mutual loss is proposed to utilize the dependency between the foreground and background networks, thereby enabling the reciprocally influence within these two networks. Consequently, this mutual training strategy enables the semi-supervised learning and improve the boundary-sensitivity. Training with Skin Imaging Collaboration (ISIC) 2018 skin lesion segmentation dataset, our method achieves a dice co-efficient of 86.4% and shows better performance compared with state-of-the-art melanoma segmentation methods.
Wearable Haptics for Remote Social Walking
Venue: arXiv cs.HC 2020
Year: 2020

Walking is an essential activity for a healthy life, which becomes less tiring and more enjoyable if done together. Common difficulties we have in performing sufficient physical exercise, for instance the lack of motivation, can be overcome by exploiting its social aspect. However, our lifestyle sometimes makes it very difficult to find time together with others who live far away from us to go for a walk. In this paper we propose a novel system enabling people to have a 'remote social walk' by streaming the gait cadence between two persons walking in different places, increasing the sense of mutual presence. Vibrations provided at the users' ankles display the partner's sensation perceived during the heel-strike. In order to achieve the aforementioned goal in a two users experiment, we envisaged a four-step incremental validation process: i) a single walker has to adapt the cadence with a virtual reference generated by a software; ii) a single user is tasked to follow a predefined time varying gait cadence; iii) a leader-follower scenario in which the haptic actuation is mono-directional; iv) a peer-to-peer case with bi-directional haptic communication. Careful experimental validation was conducted involving a total of 50 people, which confirmed the efficacy of our system in perceiving the partners' gait cadence in each of the proposed scenarios.
Efficient decoding of polar codes with some 16$\times$16 kernels
Venue: arXiv cs.IT 2020
Year: 2020

A decoding algorithm for polar codes with binary 16$\times$16 kernels with polarization rate 0.51828 and scaling exponents 3.346 and 3.450 is presented. The proposed approach exploits the relationship of the considered kernels and the Arikan matrix to significantly reduce the decoding complexity without any performance loss. Simulation results show that polar (sub)codes with 16$\times$16 kernels can outperform polar codes with Arikan kernel, while having lower decoding complexity.
Bridging the gap between AI and Healthcare sides: towards developing clinically relevant AI-powered diagnosis systems
Venue: arXiv cs.CV 2020
Year: 2020

Despite the success of Convolutional Neural Network-based Computer-Aided Diagnosis research, its clinical applications remain challenging. Accordingly, developing medical Artificial Intelligence (AI) fitting into a clinical environment requires identifying/bridging the gap between AI and Healthcare sides. Since the biggest problem in Medical Imaging lies in data paucity, confirming the clinical relevance for diagnosis of research-proven image augmentation techniques is essential. Therefore, we hold a clinically valuable AI-envisioning workshop among Japanese Medical Imaging experts, physicians, and generalists in Healthcare/Informatics. Then, a questionnaire survey for physicians evaluates our pathology-aware Generative Adversarial Network (GAN)-based image augmentation projects in terms of Data Augmentation and physician training. The workshop reveals the intrinsic gap between AI/Healthcare sides and solutions on Why (i.e., clinical significance/interpretation) and How (i.e., data acquisition, commercial deployment, and safety/feeling safe). This analysis confirms our pathology-aware GANs' clinical relevance as a clinical decision support system and non-expert physician training tool. Our findings would play a key role in connecting inter-disciplinary research and clinical applications, not limited to the Japanese medical context and pathology-aware GANs.
Feedback Channel Communication with Low Precision Arithmetic
Venue: arXiv cs.IT 2020
Year: 2020

The problem of communicating over an additive white Gaussian noise channel with feedback, using low precision arithmetic, is considered. The Schalkwijk-Kailath (SK) scheme is known to achieve an error probability that decays double exponentially in the number of interaction rounds, for any rate below channel capacity. However, SK is also known to suffer from numerical issues. Transmission close to channel capacity requires a moderate number of interaction rounds. This may lead to a huge constellation size. Furthermore, the internal variables of the scheme decay to zero exponentially fast. As a result, the SK scheme fails when implemented with low precision variables, which are widely used in hardware implementations. In this work we propose a new, modified scheme termed Zoom-in SK (ZSK), which breaks the SK protocol into several stages. Each stage comprises several SK iterations followed by a synchronized zoom step. The zoom-in allows the receiver and transmitter to keep the scheme's parameters relatively large such that low precision arithmetic can be used even for a large rate or a large number of interaction rounds. We prove that the new scheme achieves approximately the same error probability as SK while not suffering from numerical issues. We further verify our results in simulation and compare ZSK to the original SK scheme.
Broadcasting Competitively against Adaptive Adversary in Multi-channel Radio Networks
Venue: arXiv cs.DC 2020
Year: 2020

Broadcasting in wireless networks is vulnerable to adversarial jamming. To thwart such behavior, \emph{resource competitive analysis} is proposed. In this framework, sending, listening, or jamming on one channel for one time slot costs one unit of energy. The adversary can employ arbitrary strategy to disrupt communication, but has a limited energy budget $T$. The honest nodes, on the other hand, aim to accomplish broadcast while spending only $o(T)$. Previous work has shown, in a $C$-channels network containing $n$ nodes, for large $T$ values, each node can receive the message in $\tilde{O}(T/C)$ time, while spending only $\tilde{O}(\sqrt{T/n})$ energy. However, these multi-channel algorithms only work for certain values of $n$ and $C$, and can only tolerate an oblivious adversary. In this work, we provide new upper and lower bounds for broadcasting in multi-channel radio networks, from the perspective of resource competitiveness. Our algorithms work for arbitrary $n,C$ values, require minimal prior knowledge, and can tolerate a powerful adaptive adversary. More specifically, in our algorithms, for large $T$ values, each node's runtime is $O(T/C)$, and each node's energy cost is $\tilde{O}(\sqrt{T/n})$. We also complement algorithmic results with lower bounds, proving both the time complexity and the energy complexity of our algorithms are optimal or near-optimal (within a poly-log factor). Our technical contributions lie in using "epidemic broadcast" to achieve time efficiency and resource competitiveness, and employing coupling techniques in the analysis to handle the adaptivity of the adversary. At the lower bound side, we first derive a new energy complexity lower bound for 1-to-1 communication in the multi-channel setting, and then apply simulation and reduction arguments to obtain the desired result.
Communications-Caching-Computing Tradeoff Analysis for Bidirectional Data Computation in Mobile Edge Networks
Venue: arXiv cs.IT 2020
Year: 2020

With the advent of the modern mobile traffic, e.g., online gaming, augmented reality delivery and etc., a novel bidirectional computation task model where the input data of each task consists of two parts, one generated at the mobile device in real-time and the other originated from the Internet proactively, is emerging as an important use case of 5G. In this paper, for ease of analytical analysis, we consider the homogeneous bidirectional computation task model in a mobile edge network which consists of one mobile edge computing (MEC) server and one mobile device, both enabled with computing and caching capabilities. Each task can be served via three mechanisms, i.e., local computing with local caching, local computing without local caching and computing at the MEC server. To minimize the average bandwidth, we formulate the joint caching and computing optimization problem under the latency, cache size and average power constraints. We derive the closed-form expressions for the optimal policy and the minimum bandwidth. The tradeoff among communications, computing and caching is illustrated both analytically and numerically, which provides insightful guideline for the network designers.
Computational Hardness of Multidimensional Subtraction Games
Venue: arXiv cs.CC 2020
Year: 2020

We study algorithmic complexity of solving subtraction games in a~fixed dimension with a finite difference set. We prove that there exists a game in this class such that any algorithm solving the game runs in exponential time. Also we prove an existence of a game in this class such that solving the game is PSPACE-hard. The results are based on the construction introduced by Larsson and Wästlund. It relates subtraction games and cellular automata.
Head and Tail Localization of C. elegans
Venue: arXiv cs.CV 2020
Year: 2020

C. elegans is commonly used in neuroscience for behaviour analysis because of it's compact nervous system with well-described connectivity. Localizing the animal and distinguishing between its head and tail are important tasks to track the worm during behavioural assays and to perform quantitative analyses. We demonstrate a neural network based approach to localize both the head and the tail of the worm in an image. To make empirical results in the paper reproducible and promote open source machine learning based solutions for C. elegans behavioural analysis, we also make our code publicly available.
Unbiased and Efficient Log-Likelihood Estimation with Inverse Binomial Sampling
Venue: arXiv cs.LG 2020
Year: 2020

The fate of scientific hypotheses often relies on the ability of a computational model to explain the data, quantified in modern statistical approaches by the likelihood function. The log-likelihood is the key element for parameter estimation and model evaluation. However, the log-likelihood of complex models in fields such as computational biology and neuroscience is often intractable to compute analytically or numerically. In those cases, researchers can often only estimate the log-likelihood by comparing observed data with synthetic observations generated by model simulations. Standard techniques to approximate the likelihood via simulation either use summary statistics of the data or are at risk of producing severe biases in the estimate. Here, we explore another method, inverse binomial sampling (IBS), which can estimate the log-likelihood of an entire data set efficiently and without bias. For each observation, IBS draws samples from the simulator model until one matches the observation. The log-likelihood estimate is then a function of the number of samples drawn. The variance of this estimator is uniformly bounded, achieves the minimum variance for an unbiased estimator, and we can compute calibrated estimates of the variance. We provide theoretical arguments in favor of IBS and an empirical assessment of the method for maximum-likelihood estimation with simulation-based models. As case studies, we take three model-fitting problems of increasing complexity from computational and cognitive neuroscience. In all problems, IBS generally produces lower error in the estimated parameters and maximum log-likelihood values than alternative sampling methods with the same average number of samples. Our results demonstrate the potential of IBS as a practical, robust, and easy to implement method for log-likelihood evaluation when exact techniques are not available.