Paper Group ANR 754
Perturb and Combine to Identify Influential Spreaders in Real-World Networks. Recovery guarantees for polynomial approximation from dependent data with outliers. Object-sensitive Deep Reinforcement Learning. Homocentric Hypersphere Feature Embedding for Person Re-identification. Skeleton-to-Response: Dialogue Generation Guided by Retrieval Memory. …
Perturb and Combine to Identify Influential Spreaders in Real-World Networks
| Title | Perturb and Combine to Identify Influential Spreaders in Real-World Networks |
| Authors | Antoine J. -P. Tixier, Maria-Evgenia G. Rossi, Fragkiskos D. Malliaros, Jesse Read, Michalis Vazirgiannis |
| Abstract | Some of the most effective influential spreader detection algorithms are unstable to small perturbations of the network structure. Inspired by bagging in Machine Learning, we propose the first Perturb and Combine (P&C) procedure for networks. It (1) creates many perturbed versions of a given graph, (2) applies a node scoring function separately to each graph, and (3) combines the results. Experiments conducted on real-world networks of various sizes with the k-core, generalized k-core, and PageRank algorithms reveal that P&C brings substantial improvements. Moreover, this performance boost can be obtained at almost no extra cost through parallelization. Finally, a bias-variance analysis suggests that P&C works mainly by reducing bias, and that therefore, it should be capable of improving the performance of all vertex scoring functions, including stable ones. |
| Tasks | |
| Published | 2018-07-13 |
| URL | https://arxiv.org/abs/1807.09586v3 |
| https://arxiv.org/pdf/1807.09586v3.pdf | |
| PWC | https://paperswithcode.com/paper/perturb-and-combine-to-identify-influential |
| Repo | |
| Framework | |
Recovery guarantees for polynomial approximation from dependent data with outliers
| Title | Recovery guarantees for polynomial approximation from dependent data with outliers |
| Authors | Lam Si Tung Ho, Hayden Schaeffer, Giang Tran, Rachel Ward |
| Abstract | Learning non-linear systems from noisy, limited, and/or dependent data is an important task across various scientific fields including statistics, engineering, computer science, mathematics, and many more. In general, this learning task is ill-posed; however, additional information about the data’s structure or on the behavior of the unknown function can make the task well-posed. In this work, we study the problem of learning nonlinear functions from corrupted and dependent data. The learning problem is recast as a sparse robust linear regression problem where we incorporate both the unknown coefficients and the corruptions in a basis pursuit framework. The main contribution of our paper is to provide a reconstruction guarantee for the associated $\ell_1$-optimization problem where the sampling matrix is formed from dependent data. Specifically, we prove that the sampling matrix satisfies the null space property and the stable null space property, provided that the data is compact and satisfies a suitable concentration inequality. We show that our recovery results are applicable to various types of dependent data such as exponentially strongly $\alpha$-mixing data, geometrically $\mathcal{C}$-mixing data, and uniformly ergodic Markov chain. Our theoretical results are verified via several numerical simulations. |
| Tasks | |
| Published | 2018-11-25 |
| URL | http://arxiv.org/abs/1811.10115v1 |
| http://arxiv.org/pdf/1811.10115v1.pdf | |
| PWC | https://paperswithcode.com/paper/recovery-guarantees-for-polynomial |
| Repo | |
| Framework | |
Object-sensitive Deep Reinforcement Learning
| Title | Object-sensitive Deep Reinforcement Learning |
| Authors | Yuezhang Li, Katia Sycara, Rahul Iyer |
| Abstract | Deep reinforcement learning has become popular over recent years, showing superiority on different visual-input tasks such as playing Atari games and robot navigation. Although objects are important image elements, few work considers enhancing deep reinforcement learning with object characteristics. In this paper, we propose a novel method that can incorporate object recognition processing to deep reinforcement learning models. This approach can be adapted to any existing deep reinforcement learning frameworks. State-of-the-art results are shown in experiments on Atari games. We also propose a new approach called “object saliency maps” to visually explain the actions made by deep reinforcement learning agents. |
| Tasks | Atari Games, Object Recognition, Robot Navigation |
| Published | 2018-09-17 |
| URL | http://arxiv.org/abs/1809.06064v1 |
| http://arxiv.org/pdf/1809.06064v1.pdf | |
| PWC | https://paperswithcode.com/paper/object-sensitive-deep-reinforcement-learning |
| Repo | |
| Framework | |
Homocentric Hypersphere Feature Embedding for Person Re-identification
| Title | Homocentric Hypersphere Feature Embedding for Person Re-identification |
| Authors | Wangmeng Xiang, Jianqiang Huang, Xianbiao Qi, Xiansheng Hua, Lei Zhang |
| Abstract | Person re-identification (Person ReID) is a challenging task due to the large variations in camera viewpoint, lighting, resolution, and human pose. Recently, with the advancement of deep learning technologies, the performance of Person ReID has been improved swiftly. Feature extraction and feature matching are two crucial components in the training and deployment stages of Person ReID. However, many existing Person ReID methods have measure inconsistency between the training stage and the deployment stage, and they couple magnitude and orientation information of feature vectors in feature representation. Meanwhile, traditional triplet loss methods focus on samples within a mini-batch and lack knowledge of global feature distribution. To address these issues, we propose a novel homocentric hypersphere embedding scheme to decouple magnitude and orientation information for both feature and weight vectors, and reformulate classification loss and triplet loss to their angular versions and combine them into an angular discriminative loss. We evaluate our proposed method extensively on the widely used Person ReID benchmarks, including Market1501, CUHK03 and DukeMTMC-ReID. Our method demonstrates leading performance on all datasets. |
| Tasks | Person Re-Identification |
| Published | 2018-04-24 |
| URL | http://arxiv.org/abs/1804.08866v2 |
| http://arxiv.org/pdf/1804.08866v2.pdf | |
| PWC | https://paperswithcode.com/paper/homocentric-hypersphere-feature-embedding-for |
| Repo | |
| Framework | |
Skeleton-to-Response: Dialogue Generation Guided by Retrieval Memory
| Title | Skeleton-to-Response: Dialogue Generation Guided by Retrieval Memory |
| Authors | Deng Cai, Yan Wang, Victoria Bi, Zhaopeng Tu, Xiaojiang Liu, Wai Lam, Shuming Shi |
| Abstract | For dialogue response generation, traditional generative models generate responses solely from input queries. Such models rely on insufficient information for generating a specific response since a certain query could be answered in multiple ways. Consequentially, those models tend to output generic and dull responses, impeding the generation of informative utterances. Recently, researchers have attempted to fill the information gap by exploiting information retrieval techniques. When generating a response for a current query, similar dialogues retrieved from the entire training data are considered as an additional knowledge source. While this may harvest massive information, the generative models could be overwhelmed, leading to undesirable performance. In this paper, we propose a new framework which exploits retrieval results via a skeleton-then-response paradigm. At first, a skeleton is generated by revising the retrieved responses. Then, a novel generative model uses both the generated skeleton and the original query for response generation. Experimental results show that our approaches significantly improve the diversity and informativeness of the generated responses. |
| Tasks | Dialogue Generation, Information Retrieval |
| Published | 2018-09-14 |
| URL | https://arxiv.org/abs/1809.05296v5 |
| https://arxiv.org/pdf/1809.05296v5.pdf | |
| PWC | https://paperswithcode.com/paper/skeleton-to-response-dialogue-generation |
| Repo | |
| Framework | |
Low rank methods for multiple network alignment
| Title | Low rank methods for multiple network alignment |
| Authors | Huda Nassar, Georgios Kollias, Ananth Grama, David F. Gleich |
| Abstract | Multiple network alignment is the problem of identifying similar and related regions in a given set of networks. While there are a large number of effective techniques for pairwise problems with two networks that scale in terms of edges, these cannot be readily extended to align multiple networks as the computational complexity will tend to grow exponentially with the number of networks.In this paper we introduce a new multiple network alignment algorithm and framework that is effective at aligning thousands of networks with thousands of nodes. The key enabling technique of our algorithm is identifying an exact and easy to compute low-rank tensor structure inside of a principled heuristic procedure for pairwise network alignment called IsoRank. This can be combined with a new algorithm for $k$-dimensional matching problems on low-rank tensors to produce the alignment. We demonstrate results on synthetic and real-world problems that show our technique (i) is as good or better in terms of quality as existing methods, when they work on small problems, while running considerably faster and (ii) is able to scale to aligning a number of networks unreachable by current methods. We show in this paper that our method is the realistic choice for aligning multiple networks when no prior information is present. |
| Tasks | |
| Published | 2018-09-21 |
| URL | http://arxiv.org/abs/1809.08198v1 |
| http://arxiv.org/pdf/1809.08198v1.pdf | |
| PWC | https://paperswithcode.com/paper/low-rank-methods-for-multiple-network |
| Repo | |
| Framework | |
Efficient Stochastic Gradient Descent for Distributionally Robust Learning
| Title | Efficient Stochastic Gradient Descent for Distributionally Robust Learning |
| Authors | Soumyadip Ghosh, Mark Squillante, Ebisa Wollega |
| Abstract | We consider a new stochastic gradient descent algorithm for efficiently solving general min-max optimization problems that arise naturally in distributionally robust learning. By focusing on the entire dataset, current approaches do not scale well. We address this issue by initially focusing on a subset of the data and progressively increasing this support to statistically cover the entire dataset. |
| Tasks | |
| Published | 2018-05-22 |
| URL | http://arxiv.org/abs/1805.08728v1 |
| http://arxiv.org/pdf/1805.08728v1.pdf | |
| PWC | https://paperswithcode.com/paper/efficient-stochastic-gradient-descent-for |
| Repo | |
| Framework | |
Focal onset seizure prediction using convolutional networks
| Title | Focal onset seizure prediction using convolutional networks |
| Authors | Haidar Khan, Lara Marcuse, Madeline Fields, Kalina Swann, Bülent Yener |
| Abstract | Objective: This work investigates the hypothesis that focal seizures can be predicted using scalp electroencephalogram (EEG) data. Our first aim is to learn features that distinguish between the interictal and preictal regions. The second aim is to define a prediction horizon in which the prediction is as accurate and as early as possible, clearly two competing objectives. Methods: Convolutional filters on the wavelet transformation of the EEG signal are used to define and learn quantitative signatures for each period: interictal, preictal, and ictal. The optimal seizure prediction horizon is also learned from the data as opposed to making an a priori assumption. Results: Computational solutions to the optimization problem indicate a ten-minute seizure prediction horizon. This result is verified by measuring Kullback-Leibler divergence on the distributions of the automatically extracted features. Conclusion: The results on the EEG database of 204 recordings demonstrate that (i) the preictal phase transition occurs approximately ten minutes before seizure onset, and (ii) the prediction results on the test set are promising, with a sensitivity of 87.8% and a low false prediction rate of 0.142 FP/h. Our results significantly outperform a random predictor and other seizure prediction algorithms. Significance: We demonstrate that a robust set of features can be learned from scalp EEG that characterize the preictal state of focal seizures. |
| Tasks | EEG, Seizure prediction |
| Published | 2018-05-29 |
| URL | http://arxiv.org/abs/1805.11576v1 |
| http://arxiv.org/pdf/1805.11576v1.pdf | |
| PWC | https://paperswithcode.com/paper/focal-onset-seizure-prediction-using |
| Repo | |
| Framework | |
Influence-Directed Explanations for Deep Convolutional Networks
| Title | Influence-Directed Explanations for Deep Convolutional Networks |
| Authors | Klas Leino, Shayak Sen, Anupam Datta, Matt Fredrikson, Linyi Li |
| Abstract | We study the problem of explaining a rich class of behavioral properties of deep neural networks. Distinctively, our influence-directed explanations approach this problem by peering inside the network to identify neurons with high influence on a quantity and distribution of interest, using an axiomatically-justified influence measure, and then providing an interpretation for the concepts these neurons represent. We evaluate our approach by demonstrating a number of its unique capabilities on convolutional neural networks trained on ImageNet. Our evaluation demonstrates that influence-directed explanations (1) identify influential concepts that generalize across instances, (2) can be used to extract the “essence” of what the network learned about a class, and (3) isolate individual features the network uses to make decisions and distinguish related classes. |
| Tasks | |
| Published | 2018-02-11 |
| URL | http://arxiv.org/abs/1802.03788v2 |
| http://arxiv.org/pdf/1802.03788v2.pdf | |
| PWC | https://paperswithcode.com/paper/influence-directed-explanations-for-deep |
| Repo | |
| Framework | |
PURE: Scalable Phase Unwrapping with Spatial Redundant Arcs
| Title | PURE: Scalable Phase Unwrapping with Spatial Redundant Arcs |
| Authors | Ravi Lanka |
| Abstract | Phase unwrapping is a key problem in many coherent imaging systems, such as synthetic aperture radar (SAR) interferometry. A general formulation for redundant integration of finite differences for phase unwrapping (Costantini et al., 2010) was shown to produce a more reliable solution by exploiting redundant differential estimates. However, this technique requires a commercial linear programming solver for large-scale problems. For a linear cost function, we propose a method based on Dual Decomposition that breaks the given problem defined over a non-planar graph into tractable sub-problems over planar subgraphs. We also propose a decomposition technique that exploits the underlying graph structure for solving the sub-problems efficiently and guarantees asymptotic convergence to the globally optimal solution. The experimental results demonstrate that the proposed approach is comparable to the existing state-of-the-art methods in terms of the estimate with a better runtime and memory footprint. |
| Tasks | |
| Published | 2018-04-19 |
| URL | http://arxiv.org/abs/1805.00321v2 |
| http://arxiv.org/pdf/1805.00321v2.pdf | |
| PWC | https://paperswithcode.com/paper/pure-scalable-phase-unwrapping-with-spatial |
| Repo | |
| Framework | |
Argumentation for Explainable Scheduling (Full Paper with Proofs)
| Title | Argumentation for Explainable Scheduling (Full Paper with Proofs) |
| Authors | Kristijonas Čyras, Dimitrios Letsios, Ruth Misener, Francesca Toni |
| Abstract | Mathematical optimization offers highly-effective tools for finding solutions for problems with well-defined goals, notably scheduling. However, optimization solvers are often unexplainable black boxes whose solutions are inaccessible to users and which users cannot interact with. We define a novel paradigm using argumentation to empower the interaction between optimization solvers and users, supported by tractable explanations which certify or refute solutions. A solution can be from a solver or of interest to a user (in the context of ‘what-if’ scenarios). Specifically, we define argumentative and natural language explanations for why a schedule is (not) feasible, (not) efficient or (not) satisfying fixed user decisions, based on models of the fundamental makespan scheduling problem in terms of abstract argumentation frameworks (AFs). We define three types of AFs, whose stable extensions are in one-to-one correspondence with schedules that are feasible, efficient and satisfying fixed decisions, respectively. We extract the argumentative explanations from these AFs and the natural language explanations from the argumentative ones. |
| Tasks | Abstract Argumentation |
| Published | 2018-11-13 |
| URL | http://arxiv.org/abs/1811.05437v2 |
| http://arxiv.org/pdf/1811.05437v2.pdf | |
| PWC | https://paperswithcode.com/paper/argumentation-for-explainable-scheduling-full |
| Repo | |
| Framework | |
Effect of dilution in asymmetric recurrent neural networks
| Title | Effect of dilution in asymmetric recurrent neural networks |
| Authors | Viola Folli, Giorgio Gosti, Marco Leonetti, Giancarlo Ruocco |
| Abstract | We study with numerical simulation the possible limit behaviors of synchronous discrete-time deterministic recurrent neural networks composed of N binary neurons as a function of a network’s level of dilution and asymmetry. The network dilution measures the fraction of neuron couples that are connected, and the network asymmetry measures to what extent the underlying connectivity matrix is asymmetric. For each given neural network, we study the dynamical evolution of all the different initial conditions, thus characterizing the full dynamical landscape without imposing any learning rule. Because of the deterministic dynamics, each trajectory converges to an attractor, that can be either a fixed point or a limit cycle. These attractors form the set of all the possible limit behaviors of the neural network. For each network, we then determine the convergence times, the limit cycles’ length, the number of attractors, and the sizes of the attractors’ basin. We show that there are two network structures that maximize the number of possible limit behaviors. The first optimal network structure is fully-connected and symmetric. On the contrary, the second optimal network structure is highly sparse and asymmetric. The latter optimal is similar to what observed in different biological neuronal circuits. These observations lead us to hypothesize that independently from any given learning model, an efficient and effective biologic network that stores a number of limit behaviors close to its maximum capacity tends to develop a connectivity structure similar to one of the optimal networks we found. |
| Tasks | |
| Published | 2018-05-10 |
| URL | http://arxiv.org/abs/1805.03886v1 |
| http://arxiv.org/pdf/1805.03886v1.pdf | |
| PWC | https://paperswithcode.com/paper/effect-of-dilution-in-asymmetric-recurrent |
| Repo | |
| Framework | |
A Structured Perspective of Volumes on Active Learning
| Title | A Structured Perspective of Volumes on Active Learning |
| Authors | Xiaofeng Cao, Ivor W. Tsang, Guandong Xu |
| Abstract | Active Learning (AL) is a learning task that requires learners interactively query the labels of the sampled unlabeled instances to minimize the training outputs with human supervisions. In theoretical study, learners approximate the version space which covers all possible classification hypothesis into a bounded convex body and try to shrink the volume of it into a half-space by a given cut size. However, only the hypersphere with finite VC dimensions has obtained formal approximation guarantees that hold when the classes of Euclidean space are separable with a margin. In this paper, we approximate the version space to a structured {hypersphere} that covers most of the hypotheses, and then divide the available AL sampling approaches into two kinds of strategies: Outer Volume Sampling and Inner Volume Sampling. After providing provable guarantees for the performance of AL in version space, we aggregate the two kinds of volumes to eliminate their sampling biases via finding the optimal inscribed hyperspheres in the enclosing space of outer volume. To touch the version space from Euclidean space, we propose a theoretical bridge called Volume-based Model that increases the `sampling target-independent’. In non-linear feature space, spanned by kernel, we use sequential optimization to globally optimize the original space to a sparse space by halving the size of the kernel space. Then, the EM (Expectation Maximization) model which returns the local center helps us to find a local representation. To describe this process, we propose an easy-to-implement algorithm called Volume-based AL (VAL). | |
| Tasks | Active Learning |
| Published | 2018-07-24 |
| URL | http://arxiv.org/abs/1807.08904v1 |
| http://arxiv.org/pdf/1807.08904v1.pdf | |
| PWC | https://paperswithcode.com/paper/a-structured-perspective-of-volumes-on-active |
| Repo | |
| Framework | |
Accurate Deep Direct Geo-Localization from Ground Imagery and Phone-Grade GPS
| Title | Accurate Deep Direct Geo-Localization from Ground Imagery and Phone-Grade GPS |
| Authors | Shaohui Sun, Ramesh Sarukkai, Jack Kwok, Vinay Shet |
| Abstract | One of the most critical topics in autonomous driving or ride-sharing technology is to accurately localize vehicles in the world frame. In addition to common multi-view camera systems, it usually also relies on industrial grade sensors, such as LiDAR, differential GPS, high precision IMU, and etc. In this paper, we develop an approach to provide an effective solution to this problem. We propose a method to train a geo-spatial deep neural network (CNN+LSTM) to predict accurate geo-locations (latitude and longitude) using only ordinary ground imagery and low accuracy phone-grade GPS. We evaluate our approach on the open dataset released during ACM Multimedia 2017 Grand Challenge. Having ground truth locations for training, we are able to reach nearly lane-level accuracy. We also evaluate the proposed method on our own collected images in San Francisco downtown area often described as “downtown canyon” where consumer GPS signals are extremely inaccurate. The results show the model can predict quality locations that suffice in real business applications, such as ride-sharing, only using phone-grade GPS. Unlike classic visual localization or recent PoseNet-like methods that may work well in indoor environments or small-scale outdoor environments, we avoid using a map or an SFM (structure-from-motion) model at all. More importantly, the proposed method can be scaled up without concerns over the potential failure of 3D reconstruction. |
| Tasks | 3D Reconstruction, Autonomous Driving, Visual Localization |
| Published | 2018-04-20 |
| URL | http://arxiv.org/abs/1804.07470v1 |
| http://arxiv.org/pdf/1804.07470v1.pdf | |
| PWC | https://paperswithcode.com/paper/accurate-deep-direct-geo-localization-from |
| Repo | |
| Framework | |
Building Advanced Dialogue Managers for Goal-Oriented Dialogue Systems
| Title | Building Advanced Dialogue Managers for Goal-Oriented Dialogue Systems |
| Authors | Vladimir Ilievski |
| Abstract | Goal-Oriented (GO) Dialogue Systems, colloquially known as goal oriented chatbots, help users achieve a predefined goal (e.g. book a movie ticket) within a closed domain. A first step is to understand the user’s goal by using natural language understanding techniques. Once the goal is known, the bot must manage a dialogue to achieve that goal, which is conducted with respect to a learnt policy. The success of the dialogue system depends on the quality of the policy, which is in turn reliant on the availability of high-quality training data for the policy learning method, for instance Deep Reinforcement Learning. Due to the domain specificity, the amount of available data is typically too low to allow the training of good dialogue policies. In this master thesis we introduce a transfer learning method to mitigate the effects of the low in-domain data availability. Our transfer learning based approach improves the bot’s success rate by $20%$ in relative terms for distant domains and we more than double it for close domains, compared to the model without transfer learning. Moreover, the transfer learning chatbots learn the policy up to 5 to 10 times faster. Finally, as the transfer learning approach is complementary to additional processing such as warm-starting, we show that their joint application gives the best outcomes. |
| Tasks | Goal-Oriented Dialogue Systems, Transfer Learning |
| Published | 2018-06-03 |
| URL | http://arxiv.org/abs/1806.00780v1 |
| http://arxiv.org/pdf/1806.00780v1.pdf | |
| PWC | https://paperswithcode.com/paper/building-advanced-dialogue-managers-for-goal |
| Repo | |
| Framework | |
