OpenRaiser/Intern-Atlas huggingface dataset:
The Optimal Memory-Rate Trade-off for the Non-uniform Centralized Caching Problem with Two Files under Uncoded Placement
Venue: arXiv cs.IT 2019
Year: 2019

A new scheme for the problem of centralized coded caching with non-uniform demands is proposed. The distinguishing feature of the proposed placement strategy is that it admits equal sub-packetization for all files while allowing the users to allocate more cache to the files which are more popular. This creates natural broadcasting opportunities in the delivery phase which are simultaneously helpful for the users who have requested files of different popularities. For the case of two files, we propose a new delivery strategy based on interference alignment which enables each user to decode his desired file following a two-layer peeling decoder. Furthermore, we extend the existing converse bounds for uniform demands under uncoded placement to the nonuniform case. To accomplish this, we construct $N!$ auxiliary users, corresponding to all permutations of the $N$ files, each caching carefully selected sub-packets of the files. Each auxiliary user provides a different converse bound. The overall converse bound is the maximum of all these $N!$ bounds. We prove that our achievable delivery rate for the case of two files meets this converse, thereby establishing the optimal expected memory-rate trade-off for the case of $K$ users and two files with arbitrary popularities under uncoded placement.
Automatic 3D bi-ventricular segmentation of cardiac images by a shape-refined multi-task deep learning approach
Venue: arXiv cs.CV 2019
Year: 2019

Deep learning approaches have achieved state-of-the-art performance in cardiac magnetic resonance (CMR) image segmentation. However, most approaches have focused on learning image intensity features for segmentation, whereas the incorporation of anatomical shape priors has received less attention. In this paper, we combine a multi-task deep learning approach with atlas propagation to develop a shape-constrained bi-ventricular segmentation pipeline for short-axis CMR volumetric images. The pipeline first employs a fully convolutional network (FCN) that learns segmentation and landmark localisation tasks simultaneously. The architecture of the proposed FCN uses a 2.5D representation, thus combining the computational advantage of 2D FCNs networks and the capability of addressing 3D spatial consistency without compromising segmentation accuracy. Moreover, the refinement step is designed to explicitly enforce a shape constraint and improve segmentation quality. This step is effective for overcoming image artefacts (e.g. due to different breath-hold positions and large slice thickness), which preclude the creation of anatomically meaningful 3D cardiac shapes. The proposed pipeline is fully automated, due to network's ability to infer landmarks, which are then used downstream in the pipeline to initialise atlas propagation. We validate the pipeline on 1831 healthy subjects and 649 subjects with pulmonary hypertension. Extensive numerical experiments on the two datasets demonstrate that our proposed method is robust and capable of producing accurate, high-resolution and anatomically smooth bi-ventricular 3D models, despite the artefacts in input CMR volumes.
The Disparate Effects of Strategic Manipulation
Venue: arXiv cs.LG 2019
Year: 2019

When consequential decisions are informed by algorithmic input, individuals may feel compelled to alter their behavior in order to gain a system's approval. Models of agent responsiveness, termed "strategic manipulation," analyze the interaction between a learner and agents in a world where all agents are equally able to manipulate their features in an attempt to "trick" a published classifier. In cases of real world classification, however, an agent's ability to adapt to an algorithm is not simply a function of her personal interest in receiving a positive classification, but is bound up in a complex web of social factors that affect her ability to pursue certain action responses. In this paper, we adapt models of strategic manipulation to capture dynamics that may arise in a setting of social inequality wherein candidate groups face different costs to manipulation. We find that whenever one group's costs are higher than the other's, the learner's equilibrium strategy exhibits an inequality-reinforcing phenomenon wherein the learner erroneously admits some members of the advantaged group, while erroneously excluding some members of the disadvantaged group. We also consider the effects of interventions in which a learner subsidizes members of the disadvantaged group, lowering their costs in order to improve her own classification performance. Here we encounter a paradoxical result: there exist cases in which providing a subsidy improves only the learner's utility while actually making both candidate groups worse-off--even the group receiving the subsidy. Our results reveal the potentially adverse social ramifications of deploying tools that attempt to evaluate an individual's "quality" when agents' capacities to adaptively respond differ.
Explicit 3-colorings for exponential graphs
Venue: arXiv cs.DS 2019
Year: 2019

For a graph $H$ and integer $k \geq 1$, two functions $f, g$ from $V(H)$ into $\{1, \dots, k\}$ are adjacent if for all edges $uv$ of $H$, $f(u) \neq g(v)$. The graph of all such functions is the exponential graph $K_k^H$. El-Zahar and Sauer proved that if $χ(H) \geq 4$, then $K_3^H$ is 3-chromatic. Tardif showed that, implicit in their proof, is an algorithm for 3-coloring $K_3^H$ whose time complexity is polynomial in the size of $K_3^H$. Tardif then asked if there is an "explicit" algorithm for finding such a coloring: Essentially, given a function $f$ belonging to a 3-chromatic component of $K_3^H$, can we assign a color to this vertex in time polynomial in the size of $H$? The main result of this paper is to present such an algorithm, answering Tardif's question affirmatively. Our algorithm yields an alternative proof of the theorem of El-Zahar and Sauer that the categorical product of two 4-chromatic graphs is 4-chromatic.
Stress Field Prediction in Cantilevered Structures Using Convolutional Neural Networks
Venue: arXiv cs.LG 2019
Year: 2019

The demand for fast and accurate structural analysis is becoming increasingly more prevalent with the advance of generative design and topology optimization technologies. As one step toward accelerating structural analysis, this work explores a deep learning based approach for predicting the stress fields in 2D linear elastic cantilevered structures subjected to external static loads at its free end using convolutional neural networks (CNN). Two different architectures are implemented that take as input the structure geometry, external loads, and displacement boundary conditions, and output the predicted von Mises stress field. The first is a single input channel network called SCSNet as the baseline architecture, and the second is the multi-channel input network called StressNet. Accuracy analysis shows that StressNet results in significantly lower prediction errors than SCSNet on three loss functions, with a mean relative error of 2.04% for testing. These results suggest that deep learning models may offer a promising alternative to classical methods in structural design and topology optimization. Code and dataset are available at https://github.com/zhenguonie/stress_net
Real-time Pedestrian Detection Approach with an Efficient Data Communication Bandwidth Strategy
Venue: arXiv cs.CV 2019
Year: 2019

Vehicle-to-Pedestrian (V2P) communication can significantly improve pedestrian safety at a signalized intersection. It is unlikely that pedestrians will carry a low latency communication enabled device and activate a pedestrian safety application in their hand-held device all the time. Because of this limitation, multiple traffic cameras at the signalized intersection can be used to accurately detect and locate pedestrians using deep learning and broadcast safety alerts related to pedestrians to warn connected and automated vehicles around a signalized intersection. However, unavailability of high-performance computing infrastructure at the roadside and limited network bandwidth between traffic cameras and the computing infrastructure limits the ability of real-time data streaming and processing for pedestrian detection. In this paper, we develop an edge computing based real-time pedestrian detection strategy combining pedestrian detection algorithm using deep learning and an efficient data communication approach to reduce bandwidth requirements while maintaining a high object detection accuracy. We utilize a lossy compression technique on traffic camera data to determine the tradeoff between the reduction of the communication bandwidth requirements and a defined object detection accuracy. The performance of the pedestrian-detection strategy is measured in terms of pedestrian classification accuracy with varying peak signal-to-noise ratios. The analyses reveal that we detect pedestrians by maintaining a defined detection accuracy with a peak signal-to-noise ratio (PSNR) 43 dB while reducing the communication bandwidth from 9.82 Mbits/sec to 0.31 Mbits/sec, a 31x reduction.
Greedy Rectilinear Drawings
Venue: arXiv cs.CG 2019
Year: 2019

A drawing of a graph is greedy if for each ordered pair of vertices u and v, there is a path from u to v such that the Euclidean distance to v decreases monotonically at every vertex of the path. The existence of greedy drawings has been widely studied under different topological and geometric constraints, such as planarity, face convexity, and drawing succinctness. We introduce greedy rectilinear drawings, in which each edge is either a horizontal or a vertical segment. These drawings have several properties that improve human readability and support network routing. We address the problem of testing whether a planar rectilinear representation, i.e., a plane graph with specified vertex angles, admits vertex coordinates that define a greedy drawing. We provide a characterization, a linear-time testing algorithm, and a full generative scheme for universal greedy rectilinear representations, i.e., those for which every drawing is greedy. For general greedy rectilinear representations, we give a combinatorial characterization and, based on it, a polynomial-time testing and drawing algorithm for a meaningful subset of instances.
Same Stats, Different Graphs (Graph Statistics and Why We Need Graph Drawings)
Venue: arXiv cs.CG 2019
Year: 2019

Data analysts commonly utilize statistics to summarize large datasets. While it is often sufficient to explore only the summary statistics of a dataset (e.g., min/mean/max), Anscombe's Quartet demonstrates how such statistics can be misleading. Graph mining has a similar problem in that graph statistics (e.g., density, connectivity, clustering coefficient) may not capture all of the critical properties of a given graph. To study the relationships between different graph properties and statistics, we examine all low-order (<= 10) non-isomorphic graphs and provide a simple visual analytics system to explore correlations across multiple graph properties. However, for graphs with more than ten nodes, generating the entire space of graphs becomes quickly intractable. We use different random graph generation methods to further look into the distribution of graph statistics for higher order graphs and investigate the impact of various sampling methodologies. We also describe a method for generating many graphs that are identical over a number of graph properties and statistics yet are clearly different and identifiably distinct.
Profiling and Improving the Duty-Cycling Performance of Linux-based IoT Devices
Venue: arXiv cs.OS 2019
Year: 2019

Minimizing the energy consumption of Linux-based devices is an essential step towards their wide deployment in various IoT scenarios. Energy saving methods such as duty-cycling aim to address this constraint by limiting the amount of time the device is powered on. In this work we study and improve the amount of time a Linux-based IoT device is powered on to accomplish its tasks. We analyze the processes of system boot up and shutdown on two platforms, the Raspberry Pi 3 and Raspberry Pi Zero Wireless, and enhance duty-cycling performance by identifying and disabling time-consuming or unnecessary units initialized in the userspace. We also study whether SD card speed and SD card capacity utilization affect boot up duration and energy consumption. In addition, we propose 'Pallex', a parallel execution framework built on top of the 'systemd init' system to run a user application concurrently with userspace initialization. We validate the performance impact of Pallex when applied to various IoT application scenarios: (i) capturing an image, (ii) capturing and encrypting an image, (iii) capturing and classifying an image using the the k-nearest neighbor algorithm, and (iv) capturing images and sending them to a cloud server. Our results show that system lifetime is increased by 18.3%, 16.8%, 13.9% and 30.2%, for these application scenarios, respectively.
Impact of Device Orientation on Error Performance of LiFi Systems
Venue: arXiv cs.IT 2019
Year: 2019

Most studies on optical wireless communications (OWCs) have neglected the effect of random orientation in their performance analysis due to the lack of a proper model for the random orientation. Our recent empirical-based research illustrates that the random orientation follows a Laplace distribution for a static user equipment (UE). In this paper, we analyze the device orientation and assess its importance on system performance. The reliability of an OWC channel highly depends on the availability and alignment of line-of-sight (LOS) links. In this study, the effect of receiver orientation including both polar and azimuth angles on the LOS channel gain are analyzed. The probability of establishing a LOS link is investigated and the probability density function (PDF) of signal-to-noise ratio (SNR) for a randomly-oriented device is derived. By means of the PDF of SNR, the bit-error ratio (BER) of DC-biased optical orthogonal frequency division multiplexing (DCO-OFDM) in additive white Gaussian noise (AWGN) channels is evaluated. A closed-form approximation for the BER of UE with random orientation is presented which shows a good match with Monte-Carlo simulation results. Furthermore, the impact of the UE's random motion on the BER performance has been assessed. Finally, the effect of random orientation on the average signal-to-interference-plus-noise ratio (SINR) in a multiple access points (APs) scenario is investigated.
Non-linear Pattern Matching with Backtracking for Non-free Data Types
Venue: arXiv cs.PL 2019
Year: 2019

Non-free data types are data types whose data have no canonical forms. For example, multisets are non-free data types because the multiset $\{a,b,b\}$ has two other equivalent but literally different forms $\{b,a,b\}$ and $\{b,b,a\}$. Pattern matching is known to provide a handy tool set to treat such data types. Although many studies on pattern matching and implementations for practical programming languages have been proposed so far, we observe that none of these studies satisfy all the criteria of practical pattern matching, which are as follows: i) efficiency of the backtracking algorithm for non-linear patterns, ii) extensibility of matching process, and iii) polymorphism in patterns. This paper aims to design a new pattern-matching-oriented programming language that satisfies all the above three criteria. The proposed language features clean Scheme-like syntax and efficient and extensible pattern matching semantics. This programming language is especially useful for the processing of complex non-free data types that not only include multisets and sets but also graphs and symbolic mathematical expressions. We discuss the importance of our criteria of practical pattern matching and how our language design naturally arises from the criteria. The proposed language has been already implemented and open-sourced as the Egison programming language.
Simple Fusion: Return of the Language Model
Venue: arXiv cs.CL 2019
Year: 2019

Neural Machine Translation (NMT) typically leverages monolingual data in training through backtranslation. We investigate an alternative simple method to use monolingual data for NMT training: We combine the scores of a pre-trained and fixed language model (LM) with the scores of a translation model (TM) while the TM is trained from scratch. To achieve that, we train the translation model to predict the residual probability of the training data added to the prediction of the LM. This enables the TM to focus its capacity on modeling the source sentence since it can rely on the LM for fluency. We show that our method outperforms previous approaches to integrate LMs into NMT while the architecture is simpler as it does not require gating networks to balance TM and LM. We observe gains of between +0.24 and +2.36 BLEU on all four test sets (English-Turkish, Turkish-English, Estonian-English, Xhosa-English) on top of ensembles without LM. We compare our method with alternative ways to utilize monolingual data such as backtranslation, shallow fusion, and cold fusion.
Exchange-Based Diffusion in Hb-Graphs: Highlighting Complex Relationships
Venue: arXiv cs.DS 2019
Year: 2019

Most networks tend to show complex and multiple relationships between entities. Networks are usually modeled by graphs or hypergraphs; nonetheless a given entity can occur many times in a relationship: this brings the need to deal with multisets instead of sets or simple edges. Diffusion processes are useful to highlight interesting parts of a network: they usually start with a stroke at one vertex and diffuse throughout the network to reach a uniform distribution. Several iterations of the process are required prior to reaching a stable solution. We propose an alternative solution to highlighting the main components of a network using a diffusion process based on exchanges: it is an iterative two-phase step exchange process. This process allows to evaluate the importance not only of the vertices but also of the regrouping level. To model the diffusion process, we extend the concept of hypergraphs that are families of sets to families of multisets, that we call hb-graphs. This version is an extended version of arXiv:1809.00190v1: the overlaps with the v1 are in black, the new content is in blue. The contributions of this extended version are: the proofs of conservation and convergence of the extracted sequences of the diffusion process, as well as the illustration of the speed of convergence and comparison to classical and modified random walks; the algorithms of the exchange-based diffusion and the modified random walk; the application to a use case based on Arxiv publications. All the figures except one have been either modified or added in this extended version to take into account the new developments.
Parity Queries for Binary Classification
Venue: arXiv cs.IT 2019
Year: 2019

Consider a query-based data acquisition problem that aims to recover the values of $k$ binary variables from parity (XOR) measurements of chosen subsets of the variables. Assume the response model where only a randomly selected subset of the measurements is received. We propose a method for designing a sequence of queries so that the variables can be identified with high probability using as few ($n$) measurements as possible. We define the query difficulty $\bar{d}$ as the average size of the query subsets and the sample complexity $n$ as the minimum number of measurements required to attain a given recovery accuracy. We obtain fundamental trade-offs between recovery accuracy, query difficulty, and sample complexity. In particular, the necessary and sufficient sample complexity required for recovering all $k$ variables with high probability is $n = c_0 \max\{k, (k \log k)/\bar{d}\}$ and the sample complexity for recovering a fixed proportion $(1-δ)k$ of the variables for $δ=o(1)$ is $n = c_1\max\{k, (k \log(1/δ))/\bar{d}\}$, where $c_0, c_1>0$.
Translating Xd-C programs to MSVL programs
Venue: arXiv cs.PL 2019
Year: 2019

C language is one of the most popular languages for software systems. In order to verify safety, reliability and security properties of such systems written in C, a tool UMC4M for runtime verification at code level based on Modeling, Simulation and Verification Language (MSVL) and its compiler MC is employed. To do so, a C program $P$ has to be translated to an MSVL program M and the negation of a desired property $Q$ is also translated to an MSVL program M', then "M and M" is compiled and executed armed with MC. Whether $P$ violates $Q$ is checked by evaluating whether there exists an acceptable execution of new MSVL program M and M". Therefore, how to translate a C program to an MSVL program is a critical issue. However, in general, C is of complicated structures with goto statement. In this paper, we confine the syntax of C in a suitable subset called Xd-C without loss of expressiveness. Further, we present a translation algorithm from an Xd-C program to an MSVL program based on translation algorithms for expressions and statements. Moreover, the equivalences between expressions and statements involved in Xd-C and MSVL programs are inductively proved. Subsequently, the equivalence between the original Xd-C program and the translated MSVL program is also proved. In addition, the proposed approach has been implemented by a tool called $C2M$. A benchmark of experiments including 13 real-world Xd-C programs is conducted. The results show that $C2M$ works effectively.
Organ at Risk Segmentation in Head and Neck CT Images by Using a Two-Stage Segmentation Framework Based on 3D U-Net
Venue: arXiv cs.CV 2019
Year: 2019

Accurate segmentation of organ at risk (OAR) play a critical role in the treatment planning of image guided radiation treatment of head and neck cancer. This segmentation task is challenging for both human and automatic algorithms because of the relatively large number of OARs to be segmented, the large variability of the size and morphology across different OARs, and the low contrast of between some OARs and the background. In this paper, we proposed a two-stage segmentation framework based on 3D U-Net. In this framework, the segmentation of each OAR is decomposed into two sub-tasks: locating a bounding box of the OAR and segment it from a small volume within the bounding box, and each sub-tasks is fulfilled by a dedicated 3D U-Net. The decomposition makes each of the two sub-tasks much easier, so that they can be better completed. We evaluated the proposed method and compared it to state-of-the-art methods by using the MICCAI 2015 Challenge dataset. In terms of the boundary-based metric 95HD, the proposed method ranked first in eight of all nine OARs and ranked second in the other OAR. In terms of the area-based metric DSC, the proposed method ranked first in six of the nine OARs and ranked second in the other three OARs with small difference with the first one.
Wavelet based edge feature enhancement for convolutional neural networks
Venue: arXiv cs.CV 2019
Year: 2019

Convolutional neural networks are able to perform a hierarchical learning process starting with local features. However, a limited attention is paid to enhancing such elementary level features like edges. We propose and evaluate two wavelet-based edge feature enhancement methods to preprocess the input images to convolutional neural networks. The first method develops feature enhanced representations by decomposing the input images using wavelet transform and limited reconstructing subsequently. The second method develops such feature enhanced inputs to the network using local modulus maxima of wavelet coefficients. For each method, we have developed a new preprocessing layer by implementing each purposed method and have appended to the network architecture. Our empirical evaluations demonstrate that the proposed methods are outperforming the baselines and previously published work with significant accuracy gains.