Paper Group ANR 396
Machine Learning for Combinatorial Optimization: a Methodological Tour d’Horizon. Towards a more efficient representation of imputation operators in TPOT. Differentiable Greedy Networks. CNN-Based Detection of Generic Constrast Adjustment with JPEG Post-processing. Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search. …
Machine Learning for Combinatorial Optimization: a Methodological Tour d’Horizon
| Title | Machine Learning for Combinatorial Optimization: a Methodological Tour d’Horizon |
| Authors | Yoshua Bengio, Andrea Lodi, Antoine Prouvost |
| Abstract | This paper surveys the recent attempts, both from the machine learning and operations research communities, at leveraging machine learning to solve combinatorial optimization problems. Given the hard nature of these problems, state-of-the-art algorithms rely on handcrafted heuristics for making decisions that are otherwise too expensive to compute or mathematically not well defined. Thus, machine learning looks like a natural candidate to make such decisions in a more principled and optimized way. We advocate for pushing further the integration of machine learning and combinatorial optimization and detail a methodology to do so. A main point of the paper is seeing generic optimization problems as data points and inquiring what is the relevant distribution of problems to use for learning on a given task. |
| Tasks | Combinatorial Optimization |
| Published | 2018-11-15 |
| URL | https://arxiv.org/abs/1811.06128v2 |
| https://arxiv.org/pdf/1811.06128v2.pdf | |
| PWC | https://paperswithcode.com/paper/machine-learning-for-combinatorial |
| Repo | |
| Framework | |
Towards a more efficient representation of imputation operators in TPOT
| Title | Towards a more efficient representation of imputation operators in TPOT |
| Authors | Unai Garciarena, Alexander Mendiburu, Roberto Santana |
| Abstract | Automated Machine Learning encompasses a set of meta-algorithms intended to design and apply machine learning techniques (e.g., model selection, hyperparameter tuning, model assessment, etc.). TPOT, a software for optimizing machine learning pipelines based on genetic programming (GP), is a novel example of this kind of applications. Recently we have proposed a way to introduce imputation methods as part of TPOT. While our approach was able to deal with problems with missing data, it can produce a high number of unfeasible pipelines. In this paper we propose a strongly-typed-GP based approach that enforces constraint satisfaction by GP solutions. The enhancement we introduce is based on the redefinition of the operators and implicit enforcement of constraints in the generation of the GP trees. We evaluate the method to introduce imputation methods as part of TPOT. We show that the method can notably increase the efficiency of the GP search for optimal pipelines. |
| Tasks | Imputation, Model Selection |
| Published | 2018-01-13 |
| URL | http://arxiv.org/abs/1801.04407v1 |
| http://arxiv.org/pdf/1801.04407v1.pdf | |
| PWC | https://paperswithcode.com/paper/towards-a-more-efficient-representation-of |
| Repo | |
| Framework | |
Differentiable Greedy Networks
| Title | Differentiable Greedy Networks |
| Authors | Thomas Powers, Rasool Fakoor, Siamak Shakeri, Abhinav Sethy, Amanjit Kainth, Abdel-rahman Mohamed, Ruhi Sarikaya |
| Abstract | Optimal selection of a subset of items from a given set is a hard problem that requires combinatorial optimization. In this paper, we propose a subset selection algorithm that is trainable with gradient-based methods yet achieves near-optimal performance via submodular optimization. We focus on the task of identifying a relevant set of sentences for claim verification in the context of the FEVER task. Conventional methods for this task look at sentences on their individual merit and thus do not optimize the informativeness of sentences as a set. We show that our proposed method which builds on the idea of unfolding a greedy algorithm into a computational graph allows both interpretability and gradient-based training. The proposed differentiable greedy network (DGN) outperforms discrete optimization algorithms as well as other baseline methods in terms of precision and recall. |
| Tasks | Combinatorial Optimization |
| Published | 2018-10-30 |
| URL | http://arxiv.org/abs/1810.12464v1 |
| http://arxiv.org/pdf/1810.12464v1.pdf | |
| PWC | https://paperswithcode.com/paper/differentiable-greedy-networks |
| Repo | |
| Framework | |
CNN-Based Detection of Generic Constrast Adjustment with JPEG Post-processing
| Title | CNN-Based Detection of Generic Constrast Adjustment with JPEG Post-processing |
| Authors | Mauro Barni, Andrea Costanzo, Ehsan Nowroozi, Benedetta Tondi |
| Abstract | Detection of contrast adjustments in the presence of JPEG postprocessing is known to be a challenging task. JPEG post processing is often applied innocently, as JPEG is the most common image format, or it may correspond to a laundering attack, when it is purposely applied to erase the traces of manipulation. In this paper, we propose a CNN-based detector for generic contrast adjustment, which is robust to JPEG compression. The proposed system relies on a patch-based Convolutional Neural Network (CNN), trained to distinguish pristine images from contrast adjusted images, for some selected adjustment operators of different nature. Robustness to JPEG compression is achieved by training the CNN with JPEG examples, compressed over a range of Quality Factors (QFs). Experimental results show that the detector works very well and scales well with respect to the adjustment type, yielding very good performance under a large variety of unseen tonal adjustments. |
| Tasks | |
| Published | 2018-05-29 |
| URL | http://arxiv.org/abs/1805.11318v1 |
| http://arxiv.org/pdf/1805.11318v1.pdf | |
| PWC | https://paperswithcode.com/paper/cnn-based-detection-of-generic-constrast |
| Repo | |
| Framework | |
Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search
| Title | Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search |
| Authors | Zhuwen Li, Qifeng Chen, Vladlen Koltun |
| Abstract | We present a learning-based approach to computing solutions for certain NP-hard problems. Our approach combines deep learning techniques with useful algorithmic elements from classic heuristics. The central component is a graph convolutional network that is trained to estimate the likelihood, for each vertex in a graph, of whether this vertex is part of the optimal solution. The network is designed and trained to synthesize a diverse set of solutions, which enables rapid exploration of the solution space via tree search. The presented approach is evaluated on four canonical NP-hard problems and five datasets, which include benchmark satisfiability problems and real social network graphs with up to a hundred thousand nodes. Experimental results demonstrate that the presented approach substantially outperforms recent deep learning work, and performs on par with highly optimized state-of-the-art heuristic solvers for some NP-hard problems. Experiments indicate that our approach generalizes across datasets, and scales to graphs that are orders of magnitude larger than those used during training. |
| Tasks | Combinatorial Optimization |
| Published | 2018-10-25 |
| URL | http://arxiv.org/abs/1810.10659v1 |
| http://arxiv.org/pdf/1810.10659v1.pdf | |
| PWC | https://paperswithcode.com/paper/combinatorial-optimization-with-graph |
| Repo | |
| Framework | |
Unsupervised Video-to-Video Translation
| Title | Unsupervised Video-to-Video Translation |
| Authors | Dina Bashkirova, Ben Usman, Kate Saenko |
| Abstract | Unsupervised image-to-image translation is a recently proposed task of translating an image to a different style or domain given only unpaired image examples at training time. In this paper, we formulate a new task of unsupervised video-to-video translation, which poses its own unique challenges. Translating video implies learning not only the appearance of objects and scenes but also realistic motion and transitions between consecutive frames.We investigate the performance of per-frame video-to-video translation using existing image-to-image translation networks, and propose a spatio-temporal 3D translator as an alternative solution to this problem. We evaluate our 3D method on multiple synthetic datasets, such as moving colorized digits, as well as the realistic segmentation-to-video GTA dataset and a new CT-to-MRI volumetric images translation dataset. Our results show that frame-wise translation produces realistic results on a single frame level but underperforms significantly on the scale of the whole video compared to our three-dimensional translation approach, which is better able to learn the complex structure of video and motion and continuity of object appearance. |
| Tasks | Image-to-Image Translation, Unsupervised Image-To-Image Translation |
| Published | 2018-06-10 |
| URL | http://arxiv.org/abs/1806.03698v1 |
| http://arxiv.org/pdf/1806.03698v1.pdf | |
| PWC | https://paperswithcode.com/paper/unsupervised-video-to-video-translation |
| Repo | |
| Framework | |
PersonLab: Person Pose Estimation and Instance Segmentation with a Bottom-Up, Part-Based, Geometric Embedding Model
| Title | PersonLab: Person Pose Estimation and Instance Segmentation with a Bottom-Up, Part-Based, Geometric Embedding Model |
| Authors | George Papandreou, Tyler Zhu, Liang-Chieh Chen, Spyros Gidaris, Jonathan Tompson, Kevin Murphy |
| Abstract | We present a box-free bottom-up approach for the tasks of pose estimation and instance segmentation of people in multi-person images using an efficient single-shot model. The proposed PersonLab model tackles both semantic-level reasoning and object-part associations using part-based modeling. Our model employs a convolutional network which learns to detect individual keypoints and predict their relative displacements, allowing us to group keypoints into person pose instances. Further, we propose a part-induced geometric embedding descriptor which allows us to associate semantic person pixels with their corresponding person instance, delivering instance-level person segmentations. Our system is based on a fully-convolutional architecture and allows for efficient inference, with runtime essentially independent of the number of people present in the scene. Trained on COCO data alone, our system achieves COCO test-dev keypoint average precision of 0.665 using single-scale inference and 0.687 using multi-scale inference, significantly outperforming all previous bottom-up pose estimation systems. We are also the first bottom-up method to report competitive results for the person class in the COCO instance segmentation task, achieving a person category average precision of 0.417. |
| Tasks | Instance Segmentation, Keypoint Detection, Pose Estimation, Semantic Segmentation |
| Published | 2018-03-22 |
| URL | http://arxiv.org/abs/1803.08225v1 |
| http://arxiv.org/pdf/1803.08225v1.pdf | |
| PWC | https://paperswithcode.com/paper/personlab-person-pose-estimation-and-instance |
| Repo | |
| Framework | |
RUN:Residual U-Net for Computer-Aided Detection of Pulmonary Nodules without Candidate Selection
| Title | RUN:Residual U-Net for Computer-Aided Detection of Pulmonary Nodules without Candidate Selection |
| Authors | Tian Lan, Yuanyuan Li, Jonah Kimani Murugi, Yi Ding, Zhiguang Qin |
| Abstract | The early detection and early diagnosis of lung cancer are crucial to improve the survival rate of lung cancer patients. Pulmonary nodules detection results have a significant impact on the later diagnosis. In this work, we propose a new network named RUN to complete nodule detection in a single step by bypassing the candidate selection. The system introduces the shortcut of the residual network to improve the traditional U-Net, thereby solving the disadvantage of poor results due to its lack of depth. Furthermore, we compare the experimental results with the traditional U-Net. We validate our method in LUng Nodule Analysis 2016 (LUNA16) Nodule Detection Challenge. We acquire a sensitivity of 90.90% at 2 false positives per scan and therefore achieve better performance than the current state-of-the-art approaches. |
| Tasks | |
| Published | 2018-05-30 |
| URL | http://arxiv.org/abs/1805.11856v1 |
| http://arxiv.org/pdf/1805.11856v1.pdf | |
| PWC | https://paperswithcode.com/paper/runresidual-u-net-for-computer-aided |
| Repo | |
| Framework | |
Fair Division Under Cardinality Constraints
| Title | Fair Division Under Cardinality Constraints |
| Authors | Siddharth Barman, Arpita Biswas |
| Abstract | We consider the problem of fairly allocating indivisible goods, among agents, under cardinality constraints and additive valuations. In this setting, we are given a partition of the entire set of goods—i.e., the goods are categorized—and a limit is specified on the number of goods that can be allocated from each category to any agent. The objective here is to find a fair allocation in which the subset of goods assigned to any agent satisfies the given cardinality constraints. This problem naturally captures a number of resource-allocation applications, and is a generalization of the well-studied (unconstrained) fair division problem. The two central notions of fairness, in the context of fair division of indivisible goods, are envy freeness up to one good (EF1) and the (approximate) maximin share guarantee (MMS). We show that the existence and algorithmic guarantees established for these solution concepts in the unconstrained setting can essentially be achieved under cardinality constraints. Specifically, we develop efficient algorithms which compute EF1 and approximately MMS allocations in the constrained setting. Furthermore, focusing on the case wherein all the agents have the same additive valuation, we establish that EF1 allocations exist and can be computed efficiently even under matroid constraints. |
| Tasks | |
| Published | 2018-04-25 |
| URL | http://arxiv.org/abs/1804.09521v2 |
| http://arxiv.org/pdf/1804.09521v2.pdf | |
| PWC | https://paperswithcode.com/paper/fair-division-under-cardinality-constraints |
| Repo | |
| Framework | |
Adversarial Classifier for Imbalanced Problems
| Title | Adversarial Classifier for Imbalanced Problems |
| Authors | Ehsan Montahaei, Mahsa Ghorbani, Mahdieh Soleymani Baghshah, Hamid R. Rabiee |
| Abstract | Adversarial approach has been widely used for data generation in the last few years. However, this approach has not been extensively utilized for classifier training. In this paper, we propose an adversarial framework for classifier training that can also handle imbalanced data. Indeed, a network is trained via an adversarial approach to give weights to samples of the majority class such that the obtained classification problem becomes more challenging for the discriminator and thus boosts its classification capability. In addition to the general imbalanced classification problems, the proposed method can also be used for problems such as graph representation learning in which it is desired to discriminate similar nodes from dissimilar nodes. Experimental results on imbalanced data classification and on the tasks like graph link prediction show the superiority of the proposed method compared to the state-of-the-art methods. |
| Tasks | Graph Representation Learning, Link Prediction, Representation Learning |
| Published | 2018-11-21 |
| URL | http://arxiv.org/abs/1811.08812v1 |
| http://arxiv.org/pdf/1811.08812v1.pdf | |
| PWC | https://paperswithcode.com/paper/adversarial-classifier-for-imbalanced |
| Repo | |
| Framework | |
Optimal Bounds on the VC-dimension
| Title | Optimal Bounds on the VC-dimension |
| Authors | Monika Csikos, Andrey Kupavskii, Nabil H. Mustafa |
| Abstract | The VC-dimension of a set system is a way to capture its complexity and has been a key parameter studied extensively in machine learning and geometry communities. In this paper, we resolve two longstanding open problems on bounding the VC-dimension of two fundamental set systems: $k$-fold unions/intersections of half-spaces, and the simplices set system. Among other implications, it settles an open question in machine learning that was first studied in the 1989 foundational paper of Blumer, Ehrenfeucht, Haussler and Warmuth as well as by Eisenstat and Angluin and Johnson. |
| Tasks | |
| Published | 2018-07-20 |
| URL | http://arxiv.org/abs/1807.07924v1 |
| http://arxiv.org/pdf/1807.07924v1.pdf | |
| PWC | https://paperswithcode.com/paper/optimal-bounds-on-the-vc-dimension |
| Repo | |
| Framework | |
Depth with Nonlinearity Creates No Bad Local Minima in ResNets
| Title | Depth with Nonlinearity Creates No Bad Local Minima in ResNets |
| Authors | Kenji Kawaguchi, Yoshua Bengio |
| Abstract | In this paper, we prove that depth with nonlinearity creates no bad local minima in a type of arbitrarily deep ResNets with arbitrary nonlinear activation functions, in the sense that the values of all local minima are no worse than the global minimum value of corresponding classical machine-learning models, and are guaranteed to further improve via residual representations. As a result, this paper provides an affirmative answer to an open question stated in a paper in the conference on Neural Information Processing Systems 2018. This paper advances the optimization theory of deep learning only for ResNets and not for other network architectures. |
| Tasks | |
| Published | 2018-10-21 |
| URL | https://arxiv.org/abs/1810.09038v3 |
| https://arxiv.org/pdf/1810.09038v3.pdf | |
| PWC | https://paperswithcode.com/paper/depth-with-nonlinearity-creates-no-bad-local |
| Repo | |
| Framework | |
Cluster Loss for Person Re-Identification
| Title | Cluster Loss for Person Re-Identification |
| Authors | Doney Alex, Zishan Sami, Sumandeep Banerjee, Subrat Panda |
| Abstract | Person re-identification (ReID) is an important problem in computer vision, especially for video surveillance applications. The problem focuses on identifying people across different cameras or across different frames of the same camera. The main challenge lies in identifying the similarity of the same person against large appearance and structure variations, while differentiating between individuals. Recently, deep learning networks with triplet loss have become a common framework for person ReID. However, triplet loss focuses on obtaining correct orders on the training set. We demonstrate that it performs inferior in a clustering task. In this paper, we design a cluster loss, which can lead to the model output with a larger inter-class variation and a smaller intra-class variation compared to the triplet loss. As a result, our model has a better generalization ability and can achieve higher accuracy on the test set especially for a clustering task. We also introduce a batch hard training mechanism for improving the results and faster convergence of training. |
| Tasks | Person Re-Identification |
| Published | 2018-12-21 |
| URL | http://arxiv.org/abs/1812.10325v1 |
| http://arxiv.org/pdf/1812.10325v1.pdf | |
| PWC | https://paperswithcode.com/paper/cluster-loss-for-person-re-identification |
| Repo | |
| Framework | |
Adversarial Black-Box Attacks on Automatic Speech Recognition Systems using Multi-Objective Evolutionary Optimization
| Title | Adversarial Black-Box Attacks on Automatic Speech Recognition Systems using Multi-Objective Evolutionary Optimization |
| Authors | Shreya Khare, Rahul Aralikatte, Senthil Mani |
| Abstract | Fooling deep neural networks with adversarial input have exposed a significant vulnerability in the current state-of-the-art systems in multiple domains. Both black-box and white-box approaches have been used to either replicate the model itself or to craft examples which cause the model to fail. In this work, we propose a framework which uses multi-objective evolutionary optimization to perform both targeted and un-targeted black-box attacks on Automatic Speech Recognition (ASR) systems. We apply this framework on two ASR systems: Deepspeech and Kaldi-ASR, which increases the Word Error Rates (WER) of these systems by upto 980%, indicating the potency of our approach. During both un-targeted and targeted attacks, the adversarial samples maintain a high acoustic similarity of 0.98 and 0.97 with the original audio. |
| Tasks | Speech Recognition |
| Published | 2018-11-04 |
| URL | https://arxiv.org/abs/1811.01312v2 |
| https://arxiv.org/pdf/1811.01312v2.pdf | |
| PWC | https://paperswithcode.com/paper/adversarial-black-box-attacks-for-automatic |
| Repo | |
| Framework | |
Spatial Coherence of Oriented White Matter Microstructure: Applications to White Matter Regions Associated with Genetic Similarity
| Title | Spatial Coherence of Oriented White Matter Microstructure: Applications to White Matter Regions Associated with Genetic Similarity |
| Authors | Haraldur T. Hallgrímsson, Matthew Cieslak, Luca Foschini, Scott T. Grafton, Ambuj K. Singh |
| Abstract | We present a method to discover differences between populations with respect to the spatial coherence of their oriented white matter microstructure in arbitrarily shaped white matter regions. This method is applied to diffusion MRI scans of a subset of the Human Connectome Project dataset: 57 pairs of monozygotic and 52 pairs of dizygotic twins. After controlling for morphological similarity between twins, we identify 3.7% of all white matter as being associated with genetic similarity (35.1k voxels, $p < 10^{-4}$, false discovery rate 1.5%), 75% of which spatially clusters into twenty-two contiguous white matter regions. Furthermore, we show that the orientation similarity within these regions generalizes to a subset of 47 pairs of non-twin siblings, and show that these siblings are on average as similar as dizygotic twins. The regions are located in deep white matter including the superior longitudinal fasciculus, the optic radiations, the middle cerebellar peduncle, the corticospinal tract, and within the anterior temporal lobe, as well as the cerebellum, brain stem, and amygdalae. These results extend previous work using undirected fractional anisotrophy for measuring putative heritable influences in white matter. Our multidirectional extension better accounts for crossing fiber connections within voxels. This bottom up approach has at its basis a novel measurement of coherence within neighboring voxel dyads between subjects, and avoids some of the fundamental ambiguities encountered with tractographic approaches to white matter analysis that estimate global connectivity. |
| Tasks | |
| Published | 2018-02-14 |
| URL | http://arxiv.org/abs/1802.05342v1 |
| http://arxiv.org/pdf/1802.05342v1.pdf | |
| PWC | https://paperswithcode.com/paper/spatial-coherence-of-oriented-white-matter |
| Repo | |
| Framework | |
