OpenRaiser/Intern-Atlas huggingface dataset:
Network Inference from Consensus Dynamics
Venue: arXiv cs.SI 2017
Year: 2017

We consider the problem of identifying the topology of a weighted, undirected network $\mathcal G$ from observing snapshots of multiple independent consensus dynamics. Specifically, we observe the opinion profiles of a group of agents for a set of $M$ independent topics and our goal is to recover the precise relationships between the agents, as specified by the unknown network $\mathcal G$. In order to overcome the under-determinacy of the problem at hand, we leverage concepts from spectral graph theory and convex optimization to unveil the underlying network structure. More precisely, we formulate the network inference problem as a convex optimization that seeks to endow the network with certain desired properties -- such as sparsity -- while being consistent with the spectral information extracted from the observed opinions. This is complemented with theoretical results proving consistency as the number $M$ of topics grows large. We further illustrate our method by numerical experiments, which showcase the effectiveness of the technique in recovering synthetic and real-world networks.
PixelNN: Example-based Image Synthesis
Venue: arXiv cs.CV 2017
Year: 2017

We present a simple nearest-neighbor (NN) approach that synthesizes high-frequency photorealistic images from an "incomplete" signal such as a low-resolution image, a surface normal map, or edges. Current state-of-the-art deep generative models designed for such conditional image synthesis lack two important things: (1) they are unable to generate a large set of diverse outputs, due to the mode collapse problem. (2) they are not interpretable, making it difficult to control the synthesized output. We demonstrate that NN approaches potentially address such limitations, but suffer in accuracy on small datasets. We design a simple pipeline that combines the best of both worlds: the first stage uses a convolutional neural network (CNN) to maps the input to a (overly-smoothed) image, and the second stage uses a pixel-wise nearest neighbor method to map the smoothed output to multiple high-quality, high-frequency outputs in a controllable manner. We demonstrate our approach for various input modalities, and for various domains ranging from human faces to cats-and-dogs to shoes and handbags.
Faculty citation measures are highly correlated with peer assessment of computer science doctoral programs
Venue: arXiv cs.DL 2017
Year: 2017

We study relationship between peer assessment of quality of U.S. Computer Science (CS) doctoral programs and objective measures of research strength of those programs. In Fall 2016 we collected Google Scholar citation data for 4,352 tenure-track CS faculty from 173 U.S. universities. The citations are measured by the t10 index, which represents the number of citations received by the 10th highest cited paper of a faculty. To measure the research strength of a CS doctoral program we use 2 groups of citation measures. The first group of measures averages t10 of faculty in a program. Pearson correlation of those measures with the peer assessment of U.S. CS doctoral programs published by the U.S. News in 2014 is as high as 0.890. The second group of measures counts the number of well cited faculty in a program. Pearson correlation of those measures with the peer assessment is as high as 0.909. By combining those two groups of measures using linear regression, we create the Scholar score whose Pearson correlation with the peer assessment is 0.933 and which explains 87.2% of the variance in the peer assessment. Our evaluation shows that the highest 62 ranked CS doctoral programs by the U.S. News peer assessment are much higher correlated with the Scholar score than the next 57 ranked programs, indicating the deficiencies of peer assessment of less-known CS programs. Our results also indicate that university reputation might have a sizeable impact on peer assessment of CS doctoral programs. To promote transparency, the raw data and the codes used in this study are made available to research community at http://www.dabi.temple.edu/~vucetic/CSranking/.
On Ensuring that Intelligent Machines Are Well-Behaved
Venue: arXiv cs.AI 2017
Year: 2017

Machine learning algorithms are everywhere, ranging from simple data analysis and pattern recognition tools used across the sciences to complex systems that achieve super-human performance on various tasks. Ensuring that they are well-behaved---that they do not, for example, cause harm to humans or act in a racist or sexist way---is therefore not a hypothetical problem to be dealt with in the future, but a pressing one that we address here. We propose a new framework for designing machine learning algorithms that simplifies the problem of specifying and regulating undesirable behaviors. To show the viability of this new framework, we use it to create new machine learning algorithms that preclude the sexist and harmful behaviors exhibited by standard machine learning algorithms in our experiments. Our framework for designing machine learning algorithms simplifies the safe and responsible application of machine learning.
Simultaneous Detection and Quantification of Retinal Fluid with Deep Learning
Venue: arXiv cs.CV 2017
Year: 2017

We propose a new deep learning approach for automatic detection and segmentation of fluid within retinal OCT images. The proposed framework utilizes both ResNet and Encoder-Decoder neural network architectures. When training the network, we apply a novel data augmentation method called myopic warping together with standard rotation-based augmentation to increase the training set size to 45 times the original amount. Finally, the network output is post-processed with an energy minimization algorithm (graph cut) along with a few other knowledge guided morphological operations to finalize the segmentation process. Based on OCT imaging data and its ground truth from the RETOUCH challenge, the proposed system achieves dice indices of 0.522, 0.682, and 0.612, and average absolute volume differences of 0.285, 0.115, and 0.156 mm$^3$ for intaretinal fluid, subretinal fluid, and pigment epithelial detachment respectively.
Dilated Deep Residual Network for Image Denoising
Venue: arXiv cs.CV 2017
Year: 2017

Variations of deep neural networks such as convolutional neural network (CNN) have been successfully applied to image denoising. The goal is to automatically learn a mapping from a noisy image to a clean image given training data consisting of pairs of noisy and clean images. Most existing CNN models for image denoising have many layers. In such cases, the models involve a large amount of parameters and are computationally expensive to train. In this paper, we develop a dilated residual CNN for Gaussian image denoising. Compared with the recently proposed residual denoiser, our method can achieve comparable performance with less computational cost. Specifically, we enlarge receptive field by adopting dilated convolution in residual network, and the dilation factor is set to a certain value. We utilize appropriate zero padding to make the dimension of the output the same as the input. It has been proven that the expansion of receptive field can boost the CNN performance in image classification, and we further demonstrate that it can also lead to competitive performance for denoising problem. Moreover, we present a formula to calculate receptive field size when dilated convolution is incorporated. Thus, the change of receptive field can be interpreted mathematically. To validate the efficacy of our approach, we conduct extensive experiments for both gray and color image denoising with specific or randomized noise levels. Both of the quantitative measurements and the visual results of denoising are promising comparing with state-of-the-art baselines.
Towards the Automatic Anime Characters Creation with Generative Adversarial Networks
Venue: arXiv cs.CV 2017
Year: 2017

Automatic generation of facial images has been well studied after the Generative Adversarial Network (GAN) came out. There exists some attempts applying the GAN model to the problem of generating facial images of anime characters, but none of the existing work gives a promising result. In this work, we explore the training of GAN models specialized on an anime facial image dataset. We address the issue from both the data and the model aspect, by collecting a more clean, well-suited dataset and leverage proper, empirical application of DRAGAN. With quantitative analysis and case studies we demonstrate that our efforts lead to a stable and high-quality model. Moreover, to assist people with anime character design, we build a website (http://make.girls.moe) with our pre-trained model available online, which makes the model easily accessible to general public.
Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensor
Venue: arXiv cs.DS 2017
Year: 2017

In the past few years, successive improvements of the asymptotic complexity of square matrix multiplication have been obtained by developing novel methods to analyze the powers of the Coppersmith-Winograd tensor, a basic construction introduced thirty years ago. In this paper we show how to generalize this approach to make progress on the complexity of rectangular matrix multiplication as well, by developing a framework to analyze powers of tensors in an asymmetric way. By applying this methodology to the fourth power of the Coppersmith-Winograd tensor, we succeed in improving the complexity of rectangular matrix multiplication. Let $α$ denote the maximum value such that the product of an $n\times n^α$ matrix by an $n^α\times n$ matrix can be computed with $O(n^{2+ε})$ arithmetic operations for any $ε>0$. By analyzing the fourth power of the Coppersmith-Winograd tensor using our methods, we obtain the new lower bound $α>0.31389$, which improves the previous lower bound $α>0.30298$ obtained five years ago by Le Gall (FOCS'12) from the analysis of the second power of the Coppersmith-Winograd tensor. More generally, we give faster algorithms computing the product of an $n\times n^k$ matrix by an $n^k\times n$ matrix for any value $k\neq 1$. (In the case $k=1$, we recover the bounds recently obtained for square matrix multiplication). These improvements immediately lead to improvements in the complexity of a multitude of fundamental problems for which the bottleneck is rectangular matrix multiplication, such as computing the all-pair shortest paths in directed graphs with bounded weights.
Untangling Blockchain: A Data Processing View of Blockchain Systems
Venue: arXiv cs.DB 2017
Year: 2017

Blockchain technologies are gaining massive momentum in the last few years. Blockchains are distributed ledgers that enable parties who do not fully trust each other to maintain a set of global states. The parties agree on the existence, values and histories of the states. As the technology landscape is expanding rapidly, it is both important and challenging to have a firm grasp of what the core technologies have to offer, especially with respect to their data processing capabilities. In this paper, we first survey the state of the art, focusing on private blockchains (in which parties are authenticated). We analyze both in-production and research systems in four dimensions: distributed ledger, cryptography, consensus protocol and smart contract. We then present BLOCKBENCH, a benchmarking framework for understanding performance of private blockchains against data processing workloads. We conduct a comprehensive evaluation of three major blockchain systems based on BLOCKBENCH, namely Ethereum, Parity and Hyperledger Fabric. The results demonstrate several trade-offs in the design space, as well as big performance gaps between blockchain and database systems. Drawing from design principles of database systems, we discuss several research directions for bringing blockchain performance closer to the realm of databases.
Linear Symmetric Private Information Retrieval for MDS Coded Distributed Storage with Colluding Servers
Venue: arXiv cs.IT 2017
Year: 2017

The problem of symmetric private information retrieval (SPIR) from a coded database which is distributively stored among colluding servers is studied. Specifically, the database comprises $K$ files, which are stored among $N$ servers using an $(N,M)$-MDS storage code. A user wants to retrieve one file from the database by communicating with the $N$ servers, without revealing the identity of the desired file to any server. Furthermore, the user shall learn nothing about the other $K-1$ files in the database. In the $T$-colluding SPIR problem (hence called TSPIR), any $T$ out of $N$ servers may collude, that is, they may communicate their interactions with the user to guess the identity of the requested file. We show that for linear schemes, the information-theoretic capacity of the MDS-TSPIR problem, defined as the maximum number of information bits of the desired file retrieved per downloaded bit, equals $1-\frac{M+T-1}{N}$, if the servers share common randomness (unavailable at the user) with amount at least $\frac{M+T-1}{N-M-T+1}$ times the file size. Otherwise, the capacity equals zero. We conjecture that our capacity holds also for general MDS-TSPIR schemes.
Computer-aided position planning of miniplates to treat facial bone defects
Venue: arXiv cs.CV 2017
Year: 2017

In this contribution, a software system for computer-aided position planning of miniplates to treat facial bone defects is proposed. The intra-operatively used bone plates have to be passively adapted on the underlying bone contours for adequate bone fragment stabilization. However, this procedure can lead to frequent intra-operatively performed material readjustments especially in complex surgical cases. Our approach is able to fit a selection of common implant models on the surgeon's desired position in a 3D computer model. This happens with respect to the surrounding anatomical structures, always including the possibility of adjusting both the direction and the position of the used osteosynthesis material. By using the proposed software, surgeons are able to pre-plan the out coming implant in its form and morphology with the aid of a computer-visualized model within a few minutes. Further, the resulting model can be stored in STL file format, the commonly used format for 3D printing. Using this technology, surgeons are able to print the virtual generated implant, or create an individually designed bending tool. This method leads to adapted osteosynthesis materials according to the surrounding anatomy and requires further a minimum amount of money and time.
Deterministic coding theorems for blind sensing: optimal measurement rate and fractal dimension
Venue: arXiv cs.IT 2017
Year: 2017

Completely blind sensing is the problem of recovering bandlimited signals from measurements, without any spectral information beside an upper bound on the measure of the whole support set in the frequency domain. Determining the number of measurements necessary and sufficient for reconstruction has been an open problem, and usually partially blind sensing is performed, assuming to have some partial spectral information available a priori. In this paper, the minimum number of measurements that guarantees perfect recovery in the absence of measurement error, and robust recovery in the presence of measurement error, is determined in a completely blind setting. Results show that a factor of two in the measurement rate is the price pay for blindness, compared to reconstruction with full spectral knowledge. The minimum number of measurements is also related to the fractal (Minkowski-Bouligand) dimension of a discrete approximating set, defined in terms of the Kolmogorov $ε$-entropy. These results are analogous to a deterministic coding theorem, where an operational quantity defined in terms of minimum measurement rate is shown to be equal to an information-theoretic one. A comparison with parallel results in compressed sensing is illustrated, where the relevant dimensionality notion in a stochastic setting is the information (Rényi) dimension, defined in terms of the Shannon entropy.
Boolean Unateness Testing with $\widetilde{O}(n^{3/4})$ Adaptive Queries
Venue: arXiv cs.CC 2017
Year: 2017

We give an adaptive algorithm which tests whether an unknown Boolean function $f\colon \{0, 1\}^n \to\{0, 1\}$ is unate, i.e. every variable of $f$ is either non-decreasing or non-increasing, or $ε$-far from unate with one-sided error using $\widetilde{O}(n^{3/4}/ε^2)$ queries. This improves on the best adaptive $O(n/ε)$-query algorithm from Baleshzar, Chakrabarty, Pallavoor, Raskhodnikova and Seshadhri when $1/ε\ll n^{1/4}$. Combined with the $\widetildeΩ(n)$-query lower bound for non-adaptive algorithms with one-sided error of [CWX17, BCPRS17], we conclude that adaptivity helps for the testing of unateness with one-sided error. A crucial component of our algorithm is a new subroutine for finding bi-chromatic edges in the Boolean hypercube called adaptive edge search.
Discovery of Visual Semantics by Unsupervised and Self-Supervised Representation Learning
Venue: arXiv cs.CV 2017
Year: 2017

The success of deep learning in computer vision is rooted in the ability of deep networks to scale up model complexity as demanded by challenging visual tasks. As complexity is increased, so is the need for large amounts of labeled data to train the model. This is associated with a costly human annotation effort. To address this concern, with the long-term goal of leveraging the abundance of cheap unlabeled data, we explore methods of unsupervised "pre-training." In particular, we propose to use self-supervised automatic image colorization. We show that traditional methods for unsupervised learning, such as layer-wise clustering or autoencoders, remain inferior to supervised pre-training. In search for an alternative, we develop a fully automatic image colorization method. Our method sets a new state-of-the-art in revitalizing old black-and-white photography, without requiring human effort or expertise. Additionally, it gives us a method for self-supervised representation learning. In order for the model to appropriately re-color a grayscale object, it must first be able to identify it. This ability, learned entirely self-supervised, can be used to improve other visual tasks, such as classification and semantic segmentation. As a future direction for self-supervision, we investigate if multiple proxy tasks can be combined to improve generalization. This turns out to be a challenging open problem. We hope that our contributions to this endeavor will provide a foundation for future efforts in making self-supervision compete with supervised pre-training.
Outage Performance Analysis of Multicarrier Relay Selection for Cooperative Networks
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we analyze the outage performance of two multicarrier relay selection schemes, i.e. bulk and per-subcarrier selections, for two-hop orthogonal frequency-division multiplexing (OFDM) systems. To provide a comprehensive analysis, three forwarding protocols: decode-and-forward (DF), fixed-gain (FG) amplify-and-forward (AF) and variable-gain (VG) AF relay systems are considered. We obtain closed-form approximations for the outage probability and closed-form expressions for the asymptotic outage probability in the high signal-to-noise ratio (SNR) region for all cases. Our analysis is verified by Monte Carlo simulations, and provides an analytical framework for multicarrier systems with relay selection.
A novel agent-based simulation framework for sensing in complex adaptive environments
Venue: arXiv cs.NI 2017
Year: 2017

In this paper we present a novel Formal Agent-Based Simulation framework (FABS). FABS uses formal specification as a means of clear description of wireless sensor networks (WSN) sensing a Complex Adaptive Environment. This specification model is then used to develop an agent-based model of both the wireless sensor network as well as the environment. As proof of concept, we demonstrate the application of FABS to a boids model of self-organized flocking of animals monitored by a random deployment of proximity sensors.
Arabic Multi-Dialect Segmentation: bi-LSTM-CRF vs. SVM
Venue: arXiv cs.CL 2017
Year: 2017

Arabic word segmentation is essential for a variety of NLP applications such as machine translation and information retrieval. Segmentation entails breaking words into their constituent stems, affixes and clitics. In this paper, we compare two approaches for segmenting four major Arabic dialects using only several thousand training examples for each dialect. The two approaches involve posing the problem as a ranking problem, where an SVM ranker picks the best segmentation, and as a sequence labeling problem, where a bi-LSTM RNN coupled with CRF determines where best to segment words. We are able to achieve solid segmentation results for all dialects using rather limited training data. We also show that employing Modern Standard Arabic data for domain adaptation and assuming context independence improve overall results.
An FPT algorithm for planar multicuts with sources and sinks on the outer face
Venue: arXiv cs.DS 2017
Year: 2017

Given a list of k source-sink pairs in an edge-weighted graph G, the minimum multicut problem consists in selecting a set of edges of minimum total weight in G, such that removing these edges leaves no path from each source to its corresponding sink. To the best of our knowledge, no non-trivial FPT result for special cases of this problem, which is APX-hard in general graphs for any fixed k>2, is known with respect to k only. When the graph G is planar, this problem is known to be polynomial-time solvable if k=O(1), but cannot be FPT with respect to k under the Exponential Time Hypothesis. In this paper, we show that, if G is planar and in addition all sources and sinks lie on the outer face, then this problem does admit an FPT algorithm when parameterized by k (although it remains APX-hard when k is part of the input, even in stars). To do this, we provide a new characterization of optimal solutions in this case, and then use it to design a "divide-and-conquer" approach: namely, some edges that are part of any such solution actually define an optimal solution for a polynomial-time solvable multiterminal variant of the problem on some of the sources and sinks (which can be identified thanks to a reduced enumeration phase). Removing these edges from the graph cuts it into several smaller instances, which can then be solved recursively.
Solving a New 3D Bin Packing Problem with Deep Reinforcement Learning Method
Venue: arXiv cs.AI 2017
Year: 2017

In this paper, a new type of 3D bin packing problem (BPP) is proposed, in which a number of cuboid-shaped items must be put into a bin one by one orthogonally. The objective is to find a way to place these items that can minimize the surface area of the bin. This problem is based on the fact that there is no fixed-sized bin in many real business scenarios and the cost of a bin is proportional to its surface area. Our research shows that this problem is NP-hard. Based on previous research on 3D BPP, the surface area is determined by the sequence, spatial locations and orientations of items. Among these factors, the sequence of items plays a key role in minimizing the surface area. Inspired by recent achievements of deep reinforcement learning (DRL) techniques, especially Pointer Network, on combinatorial optimization problems such as TSP, a DRL-based method is applied to optimize the sequence of items to be packed into the bin. Numerical results show that the method proposed in this paper achieve about 5% improvement than heuristic method.