OpenRaiser/Intern-Atlas huggingface dataset:
Generalized Alignment Chain: Improved Converse Results for Index Coding
Venue: arXiv cs.IT 2019
Year: 2019

In this paper, we study the information-theoretic converse for the index coding problem. We generalize the definition for the alignment chain, introduced by Maleki et al., to capture more flexible relations among interfering messages at each receiver. Based on this, we derive improved converse results for the single-server index coding problem. Compared to the maximum acyclic induced subgraph (MAIS) bound, the new bounds are always as tight and can strictly outperform the MAIS bound. They can also be useful for large problems, where the generally tighter polymatroidal bound is computationally impractical. We then extend these new bounds to the multi-server index coding problem. We also present a separate, but related result where we identify a smaller single-server index coding instance, compared to those identified in the literature, for which non-Shannon-type inequalities are necessary to give a tighter converse.
Majority and Minority Voted Redundancy for Safety-Critical Applications
Venue: arXiv cs.AR 2019
Year: 2019

A new majority and minority voted redundancy (MMR) scheme is proposed that can provide the same degree of fault tolerance as N-modular redundancy (NMR) but with fewer function units and a less sophisticated voting logic. Example NMR and MMR circuits were implemented using a 32/28nm CMOS process and compared. The results show that MMR circuits dissipate less power, occupy less area, and encounter less critical path delay than the corresponding NMR circuits while providing the same degree of fault tolerance. Hence the MMR is a promising alternative to the NMR to efficiently implement high levels of redundancy in safety-critical applications.
Monocular Depth Estimation: A Survey
Venue: arXiv cs.CV 2019
Year: 2019

Monocular depth estimation is often described as an ill-posed and inherently ambiguous problem. Estimating depth from 2D images is a crucial step in scene reconstruction, 3Dobject recognition, segmentation, and detection. The problem can be framed as: given a single RGB image as input, predict a dense depth map for each pixel. This problem is worsened by the fact that most scenes have large texture and structural variations, object occlusions, and rich geometric detailing. All these factors contribute to difficulty in accurate depth estimation. In this paper, we review five papers that attempt to solve the depth estimation problem with various techniques including supervised, weakly-supervised, and unsupervised learning techniques. We then compare these papers and understand the improvements made over one another. Finally, we explore potential improvements that can aid to better solve this problem.
Parameterized Complexity of Safe Set
Venue: arXiv cs.CC 2019
Year: 2019

In this paper we study the problem of finding a small safe set $S$ in a graph $G$, i.e. a non-empty set of vertices such that no connected component of $G[S]$ is adjacent to a larger component in $G - S$. We enhance our understanding of the problem from the viewpoint of parameterized complexity by showing that (1) the problem is W[2]-hard when parameterized by the pathwidth $pw$ and cannot be solved in time $n^{o(pw)}$ unless the ETH is false, (2) it admits no polynomial kernel parameterized by the vertex cover number $vc$ unless $\mathrm{PH} = Σ^{\mathrm{p}}_{3}$, but (3) it is fixed-parameter tractable (FPT) when parameterized by the neighborhood diversity $nd$, and (4) it can be solved in time $n^{f(cw)}$ for some double exponential function $f$ where $cw$ is the clique-width. We also present (5) a faster FPT algorithm when parameterized by solution size.
99% of Distributed Optimization is a Waste of Time: The Issue and How to Fix it
Venue: arXiv cs.LG 2019
Year: 2019

Many popular distributed optimization methods for training machine learning models fit the following template: a local gradient estimate is computed independently by each worker, then communicated to a master, which subsequently performs averaging. The average is broadcast back to the workers, which use it to perform a gradient-type step to update the local version of the model. It is also well known that many such methods, including SGD, SAGA, and accelerated SGD for over-parameterized models, do not scale well with the number of parallel workers. In this paper we observe that the above template is fundamentally inefficient in that too much data is unnecessarily communicated by the workers, which slows down the overall system. We propose a fix based on a new update-sparsification method we develop in this work, which we suggest be used on top of existing methods. Namely, we develop a new variant of parallel block coordinate descent based on independent sparsification of the local gradient estimates before communication. We demonstrate that with only $m/n$ blocks sent by each of $n$ workers, where $m$ is the total number of parameter blocks, the theoretical iteration complexity of the underlying distributed methods is essentially unaffected. As an illustration, this means that when $n=100$ parallel workers are used, the communication of $99\%$ blocks is redundant, and hence a waste of time. Our theoretical claims are supported through extensive numerical experiments which demonstrate an almost perfect match with our theory on a number of synthetic and real datasets.
Promoting Diversity for End-to-End Conversation Response Generation
Venue: arXiv cs.CL 2019
Year: 2019

We present our work on Track 2 in the Dialog System Technology Challenges 7 (DSTC7). The DSTC7-Track 2 aims to evaluate the response generation of fully data-driven conversation models in knowledge-grounded settings, which provides the contextual-relevant factual texts. The Sequenceto-Sequence models have been widely used for end-to-end generative conversation modelling and achieved impressive results. However, they tend to output dull and repeated responses in previous studies. Our work aims to promote the diversity for end-to-end conversation response generation, which follows a two-stage pipeline: 1) Generate multiple responses. At this stage, two different models are proposed, i.e., a variational generative (VariGen) model and a retrieval based (Retrieval) model. 2) Rank and return the most related response by training a topic coherence discrimination (TCD) model for the ranking process. According to the official evaluation results, our proposed Retrieval and VariGen systems ranked first and second respectively on objective diversity metrics, i.e., Entropy, among all participant systems. And the VariGen system ranked second on NIST and METEOR metrics.
Deconstructing Generative Adversarial Networks
Venue: arXiv cs.LG 2019
Year: 2019

We deconstruct the performance of GANs into three components: 1. Formulation: we propose a perturbation view of the population target of GANs. Building on this interpretation, we show that GANs can be viewed as a generalization of the robust statistics framework, and propose a novel GAN architecture, termed as Cascade GANs, to provably recover meaningful low-dimensional generator approximations when the real distribution is high-dimensional and corrupted by outliers. 2. Generalization: given a population target of GANs, we design a systematic principle, projection under admissible distance, to design GANs to meet the population requirement using finite samples. We implement our principle in three cases to achieve polynomial and sometimes near-optimal sample complexities: (1) learning an arbitrary generator under an arbitrary pseudonorm; (2) learning a Gaussian location family under TV distance, where we utilize our principle provide a new proof for the optimality of Tukey median viewed as GANs; (3) learning a low-dimensional Gaussian approximation of a high-dimensional arbitrary distribution under Wasserstein distance. We demonstrate a fundamental trade-off in the approximation error and statistical error in GANs, and show how to apply our principle with empirical samples to predict how many samples are sufficient for GANs in order not to suffer from the discriminator winning problem. 3. Optimization: we demonstrate alternating gradient descent is provably not locally asymptotically stable in optimizing the GAN formulation of PCA. We diagnose the problem as the minimax duality gap being non-zero, and propose a new GAN architecture whose duality gap is zero, where the value of the game is equal to the previous minimax value (not the maximin value). We prove the new GAN architecture is globally asymptotically stable in optimization under alternating gradient descent.
Do users talk about the software in my product? Analyzing user reviews on IoT products
Venue: arXiv cs.SE 2019
Year: 2019

Consumer product reviews are an invaluable source of data because they contain a wide range of information that could help requirement engineers to meet user needs. Recent studies have shown that tweets about software applications and reviews on App Stores contain useful information, which enable a more responsive software requirements elicitation. However, all of these studies' subjects are merely software applications. Information on system software, such as embedded software, operating systems, and firmware, are overlooked, unless reviews of a product using them are investigated. Challenges in investigating these reviews could come from the fact that there is a huge volume of data available, as well as the fact that reviews of such products are diverse in nature, meaning that they may contain information mostly on hardware components or broadly on the product as a whole. Motivated by these observations, we conduct an exploratory study using a dataset of 7198 review sentences from 6 Internet of Things (IoT) products. Our qualitative analysis demonstrates that a sufficient quantity of software related information exists in these reviews. In addition, we investigate the performance of two supervised machine learning techniques (Support Vector Machines and Convolutional Neural Networks) for classification of information contained in the reviews. Our results suggest that, with a certain setup, these two techniques can be used to classify the information automatically with high precision and recall.
ICLR Reproducibility Challenge Report (Padam : Closing The Generalization Gap Of Adaptive Gradient Methods in Training Deep Neural Networks)
Venue: arXiv cs.LG 2019
Year: 2019

This work is a part of ICLR Reproducibility Challenge 2019, we try to reproduce the results in the conference submission PADAM: Closing The Generalization Gap of Adaptive Gradient Methods In Training Deep Neural Networks. Adaptive gradient methods proposed in past demonstrate a degraded generalization performance than the stochastic gradient descent (SGD) with momentum. The authors try to address this problem by designing a new optimization algorithm that bridges the gap between the space of Adaptive Gradient algorithms and SGD with momentum. With this method a new tunable hyperparameter called partially adaptive parameter p is introduced that varies between [0, 0.5]. We build the proposed optimizer and use it to mirror the experiments performed by the authors. We review and comment on the empirical analysis performed by the authors. Finally, we also propose a future direction for further study of Padam. Our code is available at: https://github.com/yashkant/Padam-Tensorflow
CURE: Curvature Regularization For Missing Data Recovery
Venue: arXiv cs.CV 2019
Year: 2019

Missing data recovery is an important and yet challenging problem in imaging and data science. Successful models often adopt certain carefully chosen regularization. Recently, the low dimension manifold model (LDMM) was introduced by S.Osher et al. and shown effective in image inpainting. They observed that enforcing low dimensionality on image patch manifold serves as a good image regularizer. In this paper, we observe that having only the low dimension manifold regularization is not enough sometimes, and we need smoothness as well. For that, we introduce a new regularization by combining the low dimension manifold regularization with a higher order Curvature Regularization, and we call this new regularization CURE for short. The key step of solving CURE is to solve a biharmonic equation on a manifold. We further introduce a weighted version of CURE, called WeCURE, in a similar manner as the weighted nonlocal Laplacian (WNLL) method. Numerical experiments for image inpainting and semi-supervised learning show that the proposed CURE and WeCURE significantly outperform LDMM and WNLL respectively.
Hybrid Machine Learning Approach to Popularity Prediction of Newly Released Contents for Online Video Streaming Service
Venue: arXiv cs.LG 2019
Year: 2019

In the industry of video content providers such as VOD and IPTV, predicting the popularity of video contents in advance is critical not only from a marketing perspective but also from a network optimization perspective. By predicting whether the content will be successful or not in advance, the content file, which is large, is efficiently deployed in the proper service providing server, leading to network cost optimization. Many previous studies have done view count prediction research to do this. However, the studies have been making predictions based on historical view count data from users. In this case, the contents had been published to the users and already deployed on a service server. These approaches make possible to efficiently deploy a content already published but are impossible to use for a content that is not be published. To address the problems, this research proposes a hybrid machine learning approach to the classification model for the popularity prediction of newly video contents which is not published. In this paper, we create a new variable based on the related content of the specific content and divide entire dataset by the characteristics of the contents. Next, the prediction is performed using XGBoosting and deep neural net based model according to the data characteristics of the cluster. Our model uses metadata for contents for prediction, so we use categorical embedding techniques to solve the sparsity of categorical variables and make them learn efficiently for the deep neural net model. As well, we use the FTRL-proximal algorithm to solve the problem of the view-count volatility of video content. We achieve overall better performance than the previous standalone method with a dataset from one of the top streaming service company.
Neural eliminators and classifiers
Venue: arXiv cs.LG 2019
Year: 2019

Classification may not be reliable for several reasons: noise in the data, insufficient input information, overlapping distributions and sharp definition of classes. Faced with several possibilities neural network may in such cases still be useful if instead of a classification elimination of improbable classes is done. Eliminators may be constructed using classifiers assigning new cases to a pool of several classes instead of just one winning class. Elimination may be done with the help of several classifiers using modified error functions. A real life medical application of neural network is presented illustrating the usefulness of elimination.
ErasureHead: Distributed Gradient Descent without Delays Using Approximate Gradient Coding
Venue: arXiv cs.LG 2019
Year: 2019

We present ErasureHead, a new approach for distributed gradient descent (GD) that mitigates system delays by employing approximate gradient coding. Gradient coded distributed GD uses redundancy to exactly recover the gradient at each iteration from a subset of compute nodes. ErasureHead instead uses approximate gradient codes to recover an inexact gradient at each iteration, but with higher delay tolerance. Unlike prior work on gradient coding, we provide a performance analysis that combines both delay and convergence guarantees. We establish that down to a small noise floor, ErasureHead converges as quickly as distributed GD and has faster overall runtime under a probabilistic delay model. We conduct extensive experiments on real world datasets and distributed clusters and demonstrate that our method can lead to significant speedups over both standard and gradient coded GD.
Language Independent Sequence Labelling for Opinion Target Extraction
Venue: arXiv cs.CL 2019
Year: 2019

In this research note we present a language independent system to model Opinion Target Extraction (OTE) as a sequence labelling task. The system consists of a combination of clustering features implemented on top of a simple set of shallow local features. Experiments on the well known Aspect Based Sentiment Analysis (ABSA) benchmarks show that our approach is very competitive across languages, obtaining best results for six languages in seven different datasets. Furthermore, the results provide further insights into the behaviour of clustering features for sequence labelling tasks. The system and models generated in this work are available for public use and to facilitate reproducibility of results.
SimBlock: A Blockchain Network Simulator
Venue: arXiv cs.DC 2019
Year: 2019

Blockchain, which is a technology for distributedly managing ledger information over multiple nodes without a centralized system, has elicited increasing attention. Performing experiments on actual blockchains are difficult because a large number of nodes in wide areas are necessary. In this study, we developed a blockchain network simulator SimBlock for such experiments. Unlike the existing simulators, SimBlock can easily change behavior of node, so that it enables to investigate the influence of nodes' behavior on blockchains. We compared some simulation results with the measured values in actual blockchains to demonstrate the validity of this simulator. Furthermore, to show practical usage, we conducted two experiments which clarify the influence of neighbor node selection algorithms and relay networks on the block propagation time. The simulator could depict the effects of the two techniques on block propagation time. The simulator will be publicly available in a few months.
OWA aggregation of multi-criteria with mixed uncertain fuzzy satisfactions
Venue: arXiv cs.AI 2019
Year: 2019

We apply the Ordered Weighted Averaging (OWA) operator in multi-criteria decision-making. To satisfy different kinds of uncertainty, measure based dominance has been presented to gain the order of different criterion. However, this idea has not been applied in fuzzy system until now. In this paper, we focus on the situation where the linguistic satisfactions are fuzzy measures instead of the exact values. We review the concept of OWA operator and discuss the order mechanism of fuzzy number. Then we combine with measure-based dominance to give an overall score of each alternatives. An example is illustrated to show the whole procedure.
AlteregoNets: a way to human augmentation
Venue: arXiv cs.AI 2019
Year: 2019

A person dependent network, called an AlterEgo net, is proposed for development. The networks are created per person. It receives at input an object descriptions and outputs a simulation of the internal person's representation of the objects. The network generates a textual stream resembling the narrative stream of consciousness depicting multitudinous thoughts and feelings related to a perceived object. In this way, the object is described not by a 'static' set of its properties, like a dictionary, but by the stream of words and word combinations referring to the object. The network simulates a person's dialogue with a representation of the object. It is based on an introduced algorithmic scheme, where perception is modeled by two interacting iterative cycles, reminding one respectively the forward and backward propagation executed at training convolution neural networks. The 'forward' iterations generate a stream representing the 'internal world' of a human. The 'backward' iterations generate a stream representing an internal representation of the object. People perceive the world differently. Tuning AlterEgo nets to a specific person or group of persons, will allow simulation of their thoughts and feelings. Thereby these nets is potentially a new human augmentation technology for various applications.
On the effects of firing memory in the dynamics of conjunctive networks
Venue: arXiv cs.FL 2019
Year: 2019

Boolean networks are one of the most studied discrete models in the context of the study of gene expression. In order to define the dynamics associated to a Boolean network, there are several \emph{update schemes} that range from parallel or \emph{synchronous} to \emph{asynchronous.} However, studying each possible dynamics defined by different update schemes might not be efficient. In this context, considering some type of temporal delay in the dynamics of Boolean networks emerges as an alternative approach. In this paper, we focus in studying the effect of a particular type of delay called \emph{firing memory} in the dynamics of Boolean networks. Particularly, we focus in symmetric (non-directed) conjunctive networks and we show that there exist examples that exhibit attractors of non-polynomial period. In addition, we study the prediction problem consisting in determinate if some vertex will eventually change its state, given an initial condition. We prove that this problem is {\bf PSPACE}-complete.
Capacity-Achieving MIMO-NOMA: Iterative LMMSE Detection
Venue: arXiv cs.IT 2019
Year: 2019

This paper considers a low-complexity iterative Linear Minimum Mean Square Error (LMMSE) multi-user detector for the Multiple-Input and Multiple-Output system with Non-Orthogonal Multiple Access (MIMO-NOMA), where multiple single-antenna users simultaneously communicate with a multiple-antenna base station (BS). While LMMSE being a linear detector has a low complexity, it has suboptimal performance in multi-user detection scenario due to the mismatch between LMMSE detection and multi-user decoding. Therefore, in this paper, we provide the matching conditions between the detector and decoders for MIMO-NOMA, which are then used to derive the achievable rate of the iterative detection. We prove that a matched iterative LMMSE detector can achieve (i) the optimal capacity of symmetric MIMO-NOMA with any number of users, (ii) the optimal sum capacity of asymmetric MIMO-NOMA with any number of users, (iii) all the maximal extreme points in the capacity region of asymmetric MIMO-NOMA with any number of users, (iv) all points in the capacity region of two-user and three-user asymmetric MIMO-NOMA systems. In addition, a kind of practical low-complexity error-correcting multiuser code, called irregular repeat-accumulate code, is designed to match the LMMSE detector. Numerical results shows that the bit error rate performance of the proposed iterative LMMSE detection outperforms the state-of-art methods and is within 0.8dB from the associated capacity limit.
Intuitionistic Non-Normal Modal Logics: A general framework
Venue: arXiv cs.LO 2019
Year: 2019

We define a family of intuitionistic non-normal modal logics; they can bee seen as intuitionistic counterparts of classical ones. We first consider monomodal logics, which contain only one between Necessity and Possibility. We then consider the more important case of bimodal logics, which contain both modal operators. In this case we define several interactions between Necessity and Possibility of increasing strength, although weaker than duality. For all logics we provide both a Hilbert axiomatisation and a cut-free sequent calculus, on its basis we also prove their decidability. We then give a semantic characterisation of our logics in terms of neighbourhood models. Our semantic framework captures modularly not only our systems but also already known intuitionistic non-normal modal logics such as Constructive K (CK) and the propositional fragment of Wijesekera's Constructive Concurrent Dynamic Logic.