OpenRaiser/Intern-Atlas huggingface dataset:
Tight Bounds on the Round Complexity of the Distributed Maximum Coverage Problem
Venue: arXiv cs.DS 2018
Year: 2018

We study the maximum $k$-set coverage problem in the following distributed setting. A collection of sets $S_1,\ldots,S_m$ over a universe $[n]$ is partitioned across $p$ machines and the goal is to find $k$ sets whose union covers the most number of elements. The computation proceeds in synchronous rounds. In each round, all machines simultaneously send a message to a central coordinator who then communicates back to all machines a summary to guide the computation for the next round. At the end, the coordinator outputs the answer. The main measures of efficiency in this setting are the approximation ratio of the returned solution, the communication cost of each machine, and the number of rounds of computation. Our main result is an asymptotically tight bound on the tradeoff between these measures for the distributed maximum coverage problem. We first show that any $r$-round protocol for this problem either incurs a communication cost of $ k \cdot m^{Ω(1/r)}$ or only achieves an approximation factor of $k^{Ω(1/r)}$. This implies that any protocol that simultaneously achieves good approximation ratio ($O(1)$ approximation) and good communication cost ($\widetilde{O}(n)$ communication per machine), essentially requires logarithmic (in $k$) number of rounds. We complement our lower bound result by showing that there exist an $r$-round protocol that achieves an $\frac{e}{e-1}$-approximation (essentially best possible) with a communication cost of $k \cdot m^{O(1/r)}$ as well as an $r$-round protocol that achieves a $k^{O(1/r)}$-approximation with only $\widetilde{O}(n)$ communication per each machine (essentially best possible). We further use our results in this distributed setting to obtain new bounds for the maximum coverage problem in two other main models of computation for massive datasets, namely, the dynamic streaming model and the MapReduce model.
Lifelong Learning for Sentiment Classification
Venue: arXiv cs.CL 2018
Year: 2018

This paper proposes a novel lifelong learning (LL) approach to sentiment classification. LL mimics the human continuous learning process, i.e., retaining the knowledge learned from past tasks and use it to help future learning. In this paper, we first discuss LL in general and then LL for sentiment classification in particular. The proposed LL approach adopts a Bayesian optimization framework based on stochastic gradient descent. Our experimental results show that the proposed method outperforms baseline methods significantly, which demonstrates that lifelong learning is a promising research direction.
An enhanced Multipath Strategy in Mobile Ad hoc Routing Protocols
Venue: arXiv cs.NI 2018
Year: 2018

The various routing protocols in Mobile Ad hoc Networks follow different strategies to send the information from one node to another. The nodes in the network are non static and they move randomly and are prone to link failure which makes always to find new routes to the destination. This research mainly focused on the study of the characteristics of multipath routing protocols in MANETS. Two of the multipath routing protocols were investigated and a comparative study along with simulation using NS2 was done between DSR and AODV to propose an enhanced approach to reach the destination maintaining the QoS. A possible optimization to the DSR and AODV routing protocols was proposed to make no node to be overburdened by distributing the load after finding the alternate multipath routes which were discovered in the Route discovery process. The simulation shows that the differences in the protocol highlighted major differences with the protocol performance. These differences have been analyzed with various network size, mobility, and network load. A new search table named Search of Next Node Enquiry Table (SONNET) was proposed to find the best neighbor node. Using SONNET the node selects the neighbor which can be reached in less number of hops and with less time delay and maintaining the QoS.
Analysis of Massive MIMO and Base Station Cooperation in an Indoor Scenario
Venue: arXiv cs.IT 2018
Year: 2018

The performance of centralized and distributed massive MIMO deployments are analyzed for indoor office scenarios. The distributed deployments use one of the following precoding methods: (1) local precoding with local channel state information (CSI) to the user equipments (UEs) that it serves; (2) large-scale MIMO with local CSI to all UEs in the network; (3) network MIMO with global CSI. For the distributed deployments (2) and (3), it is shown that using twice as many base station antennas as data streams provides many of the massive MIMO benefits in terms of spectral efficiency and fairness. This is in contrast to the centralized deployment and the distributed deployment (1) where more antennas are needed. Two of the main conclusions are that distributing base stations helps to overcome wall penetration loss; however, a backhaul is required to mitigate inter-cell interference. The effect of estimation errors on the performance is also quantified.
CANDY: Conditional Adversarial Networks based Fully End-to-End System for Single Image Haze Removal
Venue: arXiv cs.CV 2018
Year: 2018

Single image haze removal is a very challenging and ill-posed problem. The existing haze removal methods in literature, including the recently introduced deep learning methods, model the problem of haze removal as that of estimating intermediate parameters, viz., scene transmission map and atmospheric light. These are used to compute the haze-free image from the hazy input image. Such an approach only focuses on accurate estimation of intermediate parameters, while the aesthetic quality of the haze-free image is unaccounted for in the optimization framework. Thus, errors in the estimation of intermediate parameters often lead to generation of inferior quality haze-free images. In this paper, we present CANDY (Conditional Adversarial Networks based Dehazing of hazY images), a fully end-to-end model which directly generates a clean haze-free image from a hazy input image. CANDY also incorporates the visual quality of haze-free image into the optimization function; thus, generating a superior quality haze-free image. To the best of our knowledge, this is the first work in literature to propose a fully end-to-end model for single image haze removal. Also, this is the first work to explore the newly introduced concept of generative adversarial networks for the problem of single image haze removal. The proposed model CANDY was trained on a synthetically created haze image dataset, while evaluation was performed on challenging synthetic as well as real haze image datasets. The extensive evaluation and comparison results of CANDY reveal that it significantly outperforms existing state-of-the-art haze removal methods in literature, both quantitatively as well as qualitatively.
Polarization of the Vaccination Debate on Facebook
Venue: arXiv cs.SI 2018
Year: 2018

Vaccine hesitancy has been recognized as a major global health threat. Having access to any type of information in social media has been suggested as a potential powerful influence factor to hesitancy. Recent studies in other fields than vaccination show that access to a wide amount of content through the Internet without intermediaries resolved into major segregation of the users in polarized groups. Users select the information adhering to theirs system of beliefs and tend to ignore dissenting information. In this paper we assess whether there is polarization in Social Media use in the field of vaccination. We perform a thorough quantitative analysis on Facebook analyzing 2.6M users interacting with 298.018 posts over a time span of seven years and 5 months. We used community detection algorithms to automatically detect the emergent communities from the users activity and to quantify the cohesiveness over time of the communities. Our findings show that content consumption about vaccines is dominated by the echo-chamber effect and that polarization increased over years. Communities emerge from the users consumption habits, i.e. the majority of users only consumes information in favor or against vaccines, not both. The existence of echo-chambers may explain why social-media campaigns providing accurate information may have limited reach, may be effective only in sub-groups and might even foment further polarization of opinions. The introduction of dissenting information into a sub-group is disregarded and can have a backfire effect, further reinforcing the existing opinions within the sub-group.
99\% Revenue via Enhanced Competition
Venue: arXiv cs.GT 2018
Year: 2018

A sequence of recent studies show that even in the simple setting of a single seller and a single buyer with additive, independent valuations over $m$ items, the revenue-maximizing mechanism is prohibitively complex. This problem has been addressed using two main approaches: (i) Approximation: the best of two simple mechanisms (sell each item separately, or sell all the items as one bundle) gives $1/6$ of the optimal revenue [BILW14]. (ii) Enhanced competition: running the simple VCG mechanism with additional $m$ buyers extracts at least the optimal revenue in the original market [EFFTW17]. Both approaches, however, suffer from severe drawbacks: On the one hand, losing $83\%$ of the revenue is hardly acceptable in any application. On the other hand, attracting a linear number of new buyers may be prohibitive. Our main result is that by combining the two approaches one can achieve the best of both worlds. Specifically, for any constant $ε$ one can obtain a $(1-ε)$ fraction of the optimal revenue by running simple mechanisms --- either selling each item separately or selling all items as a single bundle --- with substantially fewer additional buyers: logarithmic, constant, or even none in some cases.
SDN-enabled Tactical Ad Hoc Networks: Extending Programmable Control to the Edge
Venue: arXiv cs.NI 2018
Year: 2018

Modern tactical operations have complex communication and computing requirements, often involving different coalition teams, that cannot be supported by today's mobile ad hoc networks. To this end, the emerging Software Defined Networking (SDN) paradigm has the potential to enable the redesign and successful deployment of these systems. In this paper, we propose a set of novel architecture designs for SDN-enabled mobile ad hoc networks in the tactical field. We discuss in detail the challenges raised by the ad hoc and coalition network environment, and we present specific solutions to address them. The proposed approaches build on evidence from experimental evaluation of such architectures and leverage recent theoretical results from SDN deployments in large backbone networks.
Denotation Extraction for Interactive Learning in Dialogue Systems
Venue: arXiv cs.CL 2018
Year: 2018

This paper presents a novel task using real user data obtained in human-machine conversation. The task concerns with denotation extraction from answer hints collected interactively in a dialogue. The task is motivated by the need for large amounts of training data for question answering dialogue system development, where the data is often expensive and hard to collect. Being able to collect denotation interactively and directly from users, one could improve, for example, natural understanding components on-line and ease the collection of the training data. This paper also presents introductory results of evaluation of several denotation extraction models including attention-based neural network approaches.
Between collective intelligence and semantic web : hypermediating sites. Contribution to technologies of intelligence
Venue: arXiv cs.AI 2018
Year: 2018

In this paper we present a new form of access to knowledge through what we call "hypermediator websites". These hypermediator sites are intermediate between information devices that just scan the book culture and a "real" hypertext writing format.
EBIC: an evolutionary-based parallel biclustering algorithm for pattern discover
Venue: arXiv cs.LG 2018
Year: 2018

In this paper a novel biclustering algorithm based on artificial intelligence (AI) is introduced. The method called EBIC aims to detect biologically meaningful, order-preserving patterns in complex data. The proposed algorithm is probably the first one capable of discovering with accuracy exceeding 50% multiple complex patterns in real gene expression datasets. It is also one of the very few biclustering methods designed for parallel environments with multiple graphics processing units (GPUs). We demonstrate that EBIC outperforms state-of-the-art biclustering methods, in terms of recovery and relevance, on both synthetic and genetic datasets. EBIC also yields results over 12 times faster than the most accurate reference algorithms. The proposed algorithm is anticipated to be added to the repertoire of unsupervised machine learning algorithms for the analysis of datasets, including those from large-scale genomic studies.
Secure Communication over 1-2-1 Networks
Venue: arXiv cs.IT 2018
Year: 2018

This paper starts by assuming a 1-2-1 network, the abstracted noiseless model of mmWave networks that was shown to closely approximate the Gaussian capacity in [1], and studies secure communication. First, the secure capacity is derived for 1-2-1 networks where a source is connected to a destination through a network of unit capacity links. Then, lower and upper bounds on the secure capacity are derived for the case when source and destination have more than one beam, which allow them to transmit and receive in multiple directions at a time. Finally, secure capacity results are presented for diamond 1-2-1 networks when edges have different capacities.
Open-Access Full-Duplex Wireless in the ORBIT Testbed
Venue: arXiv cs.NI 2018
Year: 2018

In order to support experimentation with full-duplex (FD) wireless, we recently integrated an open-access FD transceiver in the ORBIT testbed. In this report, we present the design and implementation of the FD transceiver and interfaces, and provide examples and guidelines for experimentation. In particular, an ORBIT node with a National Instruments (NI)/Ettus Research Universal Software Radio Peripheral (USRP) N210 software-defined radio (SDR) was equipped with the Columbia FlexICoN Gen-1 customized RF self-interference (SI) canceller box. The RF canceller box includes an RF SI canceller that is implemented using discrete components on a printed circuit board (PCB) and achieves 40dB RF SI cancellation across 5MHz bandwidth. We provide an FD transceiver baseline program and present two example FD experiments where 90dB and 85dB overall SI cancellation is achieved for a simple waveform and PSK modulated signals across both the RF and digital domains. We also discuss potential FD wireless experiments that can be conducted based on the implemented open-access FD transceiver and baseline program.
Convergence Analysis of Gradient Descent Algorithms with Proportional Updates
Venue: arXiv cs.LG 2018
Year: 2018

The rise of deep learning in recent years has brought with it increasingly clever optimization methods to deal with complex, non-linear loss functions. These methods are often designed with convex optimization in mind, but have been shown to work well in practice even for the highly non-convex optimization associated with neural networks. However, one significant drawback of these methods when they are applied to deep learning is that the magnitude of the update step is sometimes disproportionate to the magnitude of the weights (much smaller or larger), leading to training instabilities such as vanishing and exploding gradients. An idea to combat this issue is gradient descent with proportional updates. Gradient descent with proportional updates was introduced in 2017. It was independently developed by You et al (Layer-wise Adaptive Rate Scaling (LARS) algorithm) and by Abu-El-Haija (PercentDelta algorithm). The basic idea of both of these algorithms is to make each step of the gradient descent proportional to the current weight norm and independent of the gradient magnitude. It is common in the context of new optimization methods to prove convergence or derive regret bounds under the assumption of Lipschitz continuity and convexity. However, even though LARS and PercentDelta were shown to work well in practice, there is no theoretical analysis of the convergence properties of these algorithms. Thus it is not clear if the idea of gradient descent with proportional updates is used in the optimal way, or if it could be improved by using a different norm or specific learning rate schedule, for example. Moreover, it is not clear if these algorithms can be extended to other problems, besides neural networks. We attempt to answer these questions by establishing the theoretical analysis of gradient descent with proportional updates, and verifying this analysis with empirical examples.
An overview of deep learning based methods for unsupervised and semi-supervised anomaly detection in videos
Venue: arXiv cs.CV 2018
Year: 2018

Videos represent the primary source of information for surveillance applications and are available in large amounts but in most cases contain little or no annotation for supervised learning. This article reviews the state-of-the-art deep learning based methods for video anomaly detection and categorizes them based on the type of model and criteria of detection. We also perform simple studies to understand the different approaches and provide the criteria of evaluation for spatio-temporal anomaly detection.
Sufficient Conditions for the Tightness of Shannon's Capacity Bounds for Two-Way Channels
Venue: arXiv cs.IT 2018
Year: 2018

New sufficient conditions for determining in closed form the capacity region of point-to-point memoryless two-way channels (TWCs) are derived. The proposed conditions not only relax Shannon's condition which can identify only TWCs with a certain symmetry property but also generalize other existing results. Examples are given to demonstrate the advantages of the proposed conditions.
An Entropy Lower Bound for Non-Malleable Extractors
Venue: arXiv cs.CC 2018
Year: 2018

A $(k,\varepsilon)$-non-malleable extractor is a function ${\sf nmExt} : \{0,1\}^n \times \{0,1\}^d \to \{0,1\}$ that takes two inputs, a weak source $X \sim \{0,1\}^n$ of min-entropy $k$ and an independent uniform seed $s \in \{0,1\}^d$, and outputs a bit ${\sf nmExt}(X, s)$ that is $\varepsilon$-close to uniform, even given the seed $s$ and the value ${\sf nmExt}(X, s')$ for an adversarially chosen seed $s' \neq s$. Dodis and Wichs~(STOC 2009) showed the existence of $(k, \varepsilon)$-non-malleable extractors with seed length $d = \log(n-k-1) + 2\log(1/\varepsilon) + 6$ that support sources of entropy $k > \log(d) + 2 \log(1/\varepsilon) + 8$. We show that the foregoing bound is essentially tight, by proving that any $(k,\varepsilon)$-non-malleable extractor must satisfy the entropy bound $k > \log(d) + 2 \log(1/\varepsilon) - \log\log(1/\varepsilon) - C$ for an absolute constant $C$. In particular, this implies that non-malleable extractors require min-entropy at least $Ω(\log\log(n))$. This is in stark contrast to the existence of strong seeded extractors that support sources of entropy $k = O(\log(1/\varepsilon))$. Our techniques strongly rely on coding theory. In particular, we reveal an inherent connection between non-malleable extractors and error correcting codes, by proving a new lemma which shows that any $(k,\varepsilon)$-non-malleable extractor with seed length $d$ induces a code $C \subseteq \{0,1\}^{2^k}$ with relative distance $0.5 - 2\varepsilon$ and rate $\frac{d-1}{2^k}$.
Eliciting Worker Preference for Task Completion
Venue: arXiv cs.DB 2018
Year: 2018

Current crowdsourcing platforms provide little support for worker feedback. Workers are sometimes invited to post free text describing their experience and preferences in completing tasks. They can also use forums such as Turker Nation1 to exchange preferences on tasks and requesters. In fact, crowdsourcing platforms rely heavily on observing workers and inferring their preferences implicitly. In this work, we believe that asking workers to indicate their preferences explicitly improve their experience in task completion and hence, the quality of their contributions. Explicit elicitation can indeed help to build more accurate worker models for task completion that captures the evolving nature of worker preferences. We design a worker model whose accuracy is improved iteratively by requesting preferences for task factors such as required skills, task payment, and task relevance. We propose a generic framework, develop efficient solutions in realistic scenarios, and run extensive experiments that show the benefit of explicit preference elicitation over implicit ones with statistical significance.
Instance Map based Image Synthesis with a Denoising Generative Adversarial Network
Venue: arXiv cs.CV 2018
Year: 2018

Semantic layouts based Image synthesizing, which has benefited from the success of Generative Adversarial Network (GAN), has drawn much attention in these days. How to enhance the synthesis image equality while keeping the stochasticity of the GAN is still a challenge. We propose a novel denoising framework to handle this problem. The overlapped objects generation is another challenging task when synthesizing images from a semantic layout to a realistic RGB photo. To overcome this deficiency, we include a one-hot semantic label map to force the generator paying more attention on the overlapped objects generation. Furthermore, we improve the loss function of the discriminator by considering perturb loss and cascade layer loss to guide the generation process. We applied our methods on the Cityscapes, Facades and NYU datasets and demonstrate the image generation ability of our model.
When Exploiting Individual User Preference Is Beneficial for Caching at Base Stations
Venue: arXiv cs.IT 2018
Year: 2018

Most of prior works optimize caching policies based on the following assumptions: 1) every user initiates request according to content popularity, 2) all users are with the same active level, and 3) users are uniformly located in the considered region. In practice, these assumptions are often not true. In this paper, we explore the benefit of optimizing caching policies for base stations by exploiting user preference considering the spatial locality and different active level of users. We obtain optimal caching policies, respectively minimizing the download delay averaged over all file requests and user locations in the network (namely network average delay), and minimizing the maximal weighted download delay averaged over the file requests and location of each user (namely maximal weighted user average delay), as well as minimizing the weighted sum of both. The analysis and simulation results show that exploiting heterogeneous user preference and active level can improve user fairness, and can also improve network performance when users are with spatial locality.