Paper Group NANR 229
Bipartite Stochastic Block Models with Tiny Clusters. SoS-RSC: A Sum-of-Squares Polynomial Approach to Robustifying Subspace Clustering Algorithms. Step or Not: Discriminator for The Real Instructions in User-generated Recipes. Transductive Centroid Projection for Semi-supervised Large-scale Recognition. Augmented Translation: A New Approach to Com …
Bipartite Stochastic Block Models with Tiny Clusters
| Title | Bipartite Stochastic Block Models with Tiny Clusters |
| Authors | Stefan Neumann |
| Abstract | We study the problem of finding clusters in random bipartite graphs. We present a simple two-step algorithm which provably finds even tiny clusters of size $O(n^\epsilon)$, where $n$ is the number of vertices in the graph and $\epsilon > 0$. Previous algorithms were only able to identify clusters of size $\Omega(\sqrt{n})$. We evaluate the algorithm on synthetic and on real-world data; the experiments show that the algorithm can find extremely small clusters even in presence of high destructive noise. |
| Tasks | |
| Published | 2018-12-01 |
| URL | http://papers.nips.cc/paper/7643-bipartite-stochastic-block-models-with-tiny-clusters |
| http://papers.nips.cc/paper/7643-bipartite-stochastic-block-models-with-tiny-clusters.pdf | |
| PWC | https://paperswithcode.com/paper/bipartite-stochastic-block-models-with-tiny |
| Repo | |
| Framework | |
SoS-RSC: A Sum-of-Squares Polynomial Approach to Robustifying Subspace Clustering Algorithms
| Title | SoS-RSC: A Sum-of-Squares Polynomial Approach to Robustifying Subspace Clustering Algorithms |
| Authors | Mario Sznaier, Octavia Camps |
| Abstract | This paper addresses the problem of subspace clustering in the presence of outliers. Typically, this scenario is handled through a regularized optimization, whose computational complexity scales polynomially with the size of the data. Further, the regularization terms need to be manually tuned to achieve optimal performance. To circumvent these difficulties, in this paper we propose an outlier removal algorithm based on evaluating a suitable sum-ofsquares polynomial, computed directly from the data. This algorithm only requires performing two singular value decompositions of fixed size, and provides certificates on the probability of misclassifying outliers as inliers. |
| Tasks | |
| Published | 2018-06-01 |
| URL | http://openaccess.thecvf.com/content_cvpr_2018/html/Sznaier_SoS-RSC_A_Sum-of-Squares_CVPR_2018_paper.html |
| http://openaccess.thecvf.com/content_cvpr_2018/papers/Sznaier_SoS-RSC_A_Sum-of-Squares_CVPR_2018_paper.pdf | |
| PWC | https://paperswithcode.com/paper/sos-rsc-a-sum-of-squares-polynomial-approach |
| Repo | |
| Framework | |
Step or Not: Discriminator for The Real Instructions in User-generated Recipes
| Title | Step or Not: Discriminator for The Real Instructions in User-generated Recipes |
| Authors | Shintaro Inuzuka, Takahiko Ito, Jun Harashima |
| Abstract | In a recipe sharing service, users publish recipe instructions in the form of a series of steps. However, some of the {}steps{''} are not actually part of the cooking process. Specifically, advertisements of recipes themselves (e.g., {}introduced on TV{''}) and comments (e.g., {``}Thanks for many messages{''}) may often be included in the step section of the recipe, like the recipe author{'}s communication tool. However, such \textit{fake} steps can cause problems when using recipe search indexing or when being spoken by devices such as smart speakers. As presented in this talk, we have constructed a discriminator that distinguishes between such a fake step and the step actually used for cooking. This project includes, but is not limited to, the creation of annotation data by classifying and analyzing recipe steps and the construction of identification models. Our models use only text information to identify the step. In our test, machine learning models achieved higher accuracy than rule-based methods that use manually chosen clue words. | |
| Tasks | |
| Published | 2018-11-01 |
| URL | https://www.aclweb.org/anthology/W18-6128/ |
| https://www.aclweb.org/anthology/W18-6128 | |
| PWC | https://paperswithcode.com/paper/step-or-not-discriminator-for-the-real |
| Repo | |
| Framework | |
Transductive Centroid Projection for Semi-supervised Large-scale Recognition
| Title | Transductive Centroid Projection for Semi-supervised Large-scale Recognition |
| Authors | Yu Liu, Guanglu Song, Jing Shao, Xiao Jin, Xiaogang Wang |
| Abstract | Conventional deep semi-supervised learning methods, such as recursive clustering and training process, suffer from cumulative error and high computational complexity when collaborating with Convolutional Neural Networks. To this end, we design a simple but effective learning mechanism that merely substitutes the last fully-connected layer with the proposed Transductive Centroid Projection (TCP) module. It is inspired by the observation of the weights in classification layer (called extit{anchors}) converge to the central direction of each class in hyperspace. Specifically, we design the TCP module by dynamically adding an extit{ad hoc anchor} for each cluster in one mini-batch. It essentially reduces the probability of the inter-class conflict and enables the unlabelled data functioning as labelled data. We inspect its effectiveness with elaborate ablation study on seven public face/person classification benchmarks. Without any bells and whistles, TCP can achieve significant performance gains over most state-of-the-art methods in both fully-supervised and semi-supervised manners. |
| Tasks | |
| Published | 2018-09-01 |
| URL | http://openaccess.thecvf.com/content_ECCV_2018/html/Yu_Liu_Transductive_Centroid_Projection_ECCV_2018_paper.html |
| http://openaccess.thecvf.com/content_ECCV_2018/papers/Yu_Liu_Transductive_Centroid_Projection_ECCV_2018_paper.pdf | |
| PWC | https://paperswithcode.com/paper/transductive-centroid-projection-for-semi |
| Repo | |
| Framework | |
Augmented Translation: A New Approach to Combining Human and Machine Capabilities
| Title | Augmented Translation: A New Approach to Combining Human and Machine Capabilities |
| Authors | Arle Lommel |
| Abstract | |
| Tasks | Common Sense Reasoning |
| Published | 2018-03-01 |
| URL | https://www.aclweb.org/anthology/W18-1905/ |
| https://www.aclweb.org/anthology/W18-1905 | |
| PWC | https://paperswithcode.com/paper/augmented-translation-a-new-approach-to |
| Repo | |
| Framework | |
Neural Edit Operations for Biological Sequences
| Title | Neural Edit Operations for Biological Sequences |
| Authors | Satoshi Koide, Keisuke Kawano, Takuro Kutsuna |
| Abstract | The evolution of biological sequences, such as proteins or DNAs, is driven by the three basic edit operations: substitution, insertion, and deletion. Motivated by the recent progress of neural network models for biological tasks, we implement two neural network architectures that can treat such edit operations. The first proposal is the edit invariant neural networks, based on differentiable Needleman-Wunsch algorithms. The second is the use of deep CNNs with concatenations. Our analysis shows that CNNs can recognize star-free regular expressions, and that deeper CNNs can recognize more complex regular expressions including the insertion/deletion of characters. The experimental results for the protein secondary structure prediction task suggest the importance of insertion/deletion. The test accuracy on the widely-used CB513 dataset is 71.5%, which is 1.2-points better than the current best result on non-ensemble models. |
| Tasks | Protein Secondary Structure Prediction |
| Published | 2018-12-01 |
| URL | http://papers.nips.cc/paper/7744-neural-edit-operations-for-biological-sequences |
| http://papers.nips.cc/paper/7744-neural-edit-operations-for-biological-sequences.pdf | |
| PWC | https://paperswithcode.com/paper/neural-edit-operations-for-biological |
| Repo | |
| Framework | |
Variational PDEs for Acceleration on Manifolds and Application to Diffeomorphisms
| Title | Variational PDEs for Acceleration on Manifolds and Application to Diffeomorphisms |
| Authors | Ganesh Sundaramoorthi, Anthony Yezzi |
| Abstract | We consider the optimization of cost functionals on manifolds and derive a variational approach to accelerated methods on manifolds. We demonstrate the methodology on the infinite-dimensional manifold of diffeomorphisms, motivated by registration problems in computer vision. We build on the variational approach to accelerated optimization by Wibisono, Wilson and Jordan, which applies in finite dimensions, and generalize that approach to infinite dimensional manifolds. We derive the continuum evolution equations, which are partial differential equations (PDE), and relate them to simple mechanical principles. Our approach can also be viewed as a generalization of the $L^2$ optimal mass transport problem. Our approach evolves an infinite number of particles endowed with mass, represented as a mass density. The density evolves with the optimization variable, and endows the particles with dynamics. This is different than current accelerated methods where only a single particle moves and hence the dynamics does not depend on the mass. We derive the theory, compute the PDEs for acceleration, and illustrate the behavior of this new accelerated optimization scheme. |
| Tasks | |
| Published | 2018-12-01 |
| URL | http://papers.nips.cc/paper/7636-variational-pdes-for-acceleration-on-manifolds-and-application-to-diffeomorphisms |
| http://papers.nips.cc/paper/7636-variational-pdes-for-acceleration-on-manifolds-and-application-to-diffeomorphisms.pdf | |
| PWC | https://paperswithcode.com/paper/variational-pdes-for-acceleration-on |
| Repo | |
| Framework | |
Stochastic Nested Variance Reduced Gradient Descent for Nonconvex Optimization
| Title | Stochastic Nested Variance Reduced Gradient Descent for Nonconvex Optimization |
| Authors | Dongruo Zhou, Pan Xu, Quanquan Gu |
| Abstract | We study finite-sum nonconvex optimization problems, where the objective function is an average of $n$ nonconvex functions. We propose a new stochastic gradient descent algorithm based on nested variance reduction. Compared with conventional stochastic variance reduced gradient (SVRG) algorithm that uses two reference points to construct a semi-stochastic gradient with diminishing variance in each epoch, our algorithm uses $K+1$ nested reference points to build an semi-stochastic gradient to further reduce its variance in each epoch. For smooth functions, the proposed algorithm converges to an approximate first order stationary point (i.e., $\nabla F(\xb)_2\leq \epsilon$) within $\tO(n\land \epsilon^{-2}+\epsilon^{-3}\land n^{1/2}\epsilon^{-2})$\footnote{$\tO(\cdot)$ hides the logarithmic factors} number of stochastic gradient evaluations, where $n$ is the number of component functions, and $\epsilon$ is the optimization error. This improves the best known gradient complexity of SVRG $O(n+n^{2/3}\epsilon^{-2})$ and the best gradient complexity of SCSG $O(\epsilon^{-5/3}\land n^{2/3}\epsilon^{-2})$. For gradient dominated functions, our algorithm achieves $\tO(n\land \tau\epsilon^{-1}+\tau\cdot (n^{1/2}\land (\tau\epsilon^{-1})^{1/2})$ gradient complexity, which again beats the existing best gradient complexity $\tO(n\land \tau\epsilon^{-1}+\tau\cdot (n^{1/2}\land (\tau\epsilon^{-1})^{2/3})$ achieved by SCSG. Thorough experimental results on different nonconvex optimization problems back up our theory. |
| Tasks | |
| Published | 2018-12-01 |
| URL | http://papers.nips.cc/paper/7648-stochastic-nested-variance-reduced-gradient-descent-for-nonconvex-optimization |
| http://papers.nips.cc/paper/7648-stochastic-nested-variance-reduced-gradient-descent-for-nonconvex-optimization.pdf | |
| PWC | https://paperswithcode.com/paper/stochastic-nested-variance-reduced-gradient |
| Repo | |
| Framework | |
IPS-WASEDA system at CoNLL–SIGMORPHON 2018 Shared Task on morphological inflection
| Title | IPS-WASEDA system at CoNLL–SIGMORPHON 2018 Shared Task on morphological inflection |
| Authors | Rashel Fam, Yves Lepage |
| Abstract | |
| Tasks | Data Augmentation, Machine Translation, Morphological Inflection |
| Published | 2018-10-01 |
| URL | https://www.aclweb.org/anthology/K18-3003/ |
| https://www.aclweb.org/anthology/K18-3003 | |
| PWC | https://paperswithcode.com/paper/ips-waseda-system-at-conll-sigmorphon-2018 |
| Repo | |
| Framework | |
A Dataset for Telling the Stories of Social Media Videos
| Title | A Dataset for Telling the Stories of Social Media Videos |
| Authors | Sp Gella, ana, Mike Lewis, Marcus Rohrbach |
| Abstract | Video content on social media platforms constitutes a major part of the communication between people, as it allows everyone to share their stories. However, if someone is unable to consume video, either due to a disability or network bandwidth, this severely limits their participation and communication. Automatically telling the stories using multi-sentence descriptions of videos would allow bridging this gap. To learn and evaluate such models, we introduce VideoStory a new large-scale dataset for video description as a new challenge for multi-sentence video description. Our VideoStory captions dataset is complementary to prior work and contains 20k videos posted publicly on a social media platform amounting to 396 hours of video with 123k sentences, temporally aligned to the video. |
| Tasks | Video Captioning, Video Description |
| Published | 2018-10-01 |
| URL | https://www.aclweb.org/anthology/D18-1117/ |
| https://www.aclweb.org/anthology/D18-1117 | |
| PWC | https://paperswithcode.com/paper/a-dataset-for-telling-the-stories-of-social |
| Repo | |
| Framework | |
Reinforcement Learning via Replica Stacking of Quantum Measurements for the Training of Quantum Boltzmann Machines
| Title | Reinforcement Learning via Replica Stacking of Quantum Measurements for the Training of Quantum Boltzmann Machines |
| Authors | Anna Levit, Daniel Crawford, Navid Ghadermarzy, Jaspreet S. Oberoi, Ehsan Zahedinejad, Pooya Ronagh |
| Abstract | Recent theoretical and experimental results suggest the possibility of using current and near-future quantum hardware in challenging sampling tasks. In this paper, we introduce free-energy-based reinforcement learning (FERL) as an application of quantum hardware. We propose a method for processing a quantum annealer’s measured qubit spin configurations in approximating the free energy of a quantum Boltzmann machine (QBM). We then apply this method to perform reinforcement learning on the grid-world problem using the D-Wave 2000Q quantum annealer. The experimental results show that our technique is a promising method for harnessing the power of quantum sampling in reinforcement learning tasks. |
| Tasks | |
| Published | 2018-01-01 |
| URL | https://openreview.net/forum?id=HkMhoDITb |
| https://openreview.net/pdf?id=HkMhoDITb | |
| PWC | https://paperswithcode.com/paper/reinforcement-learning-via-replica-stacking |
| Repo | |
| Framework | |
HeLI-based Experiments in Swiss German Dialect Identification
| Title | HeLI-based Experiments in Swiss German Dialect Identification |
| Authors | Tommi Jauhiainen, Heidi Jauhiainen, Krister Lind{'e}n |
| Abstract | In this paper we present the experiments and results by the SUKI team in the German Dialect Identification shared task of the VarDial 2018 Evaluation Campaign. Our submission using HeLI with adaptive language models obtained the best results in the shared task with a macro F1-score of 0.686, which is clearly higher than the other submitted results. Without some form of unsupervised adaptation on the test set, it might not be possible to reach as high an F1-score with the level of domain difference between the datasets of the shared task. We describe the methods used in detail, as well as some additional experiments carried out during the shared task. |
| Tasks | Language Identification |
| Published | 2018-08-01 |
| URL | https://www.aclweb.org/anthology/W18-3929/ |
| https://www.aclweb.org/anthology/W18-3929 | |
| PWC | https://paperswithcode.com/paper/heli-based-experiments-in-swiss-german |
| Repo | |
| Framework | |
Linguistic Cues to Deception and Perceived Deception in Interview Dialogues
| Title | Linguistic Cues to Deception and Perceived Deception in Interview Dialogues |
| Authors | Sarah Ita Levitan, Angel Maredia, Julia Hirschberg |
| Abstract | We explore deception detection in interview dialogues. We analyze a set of linguistic features in both truthful and deceptive responses to interview questions. We also study the perception of deception, identifying characteristics of statements that are perceived as truthful or deceptive by interviewers. Our analysis show significant differences between truthful and deceptive question responses, as well as variations in deception patterns across gender and native language. This analysis motivated our selection of features for machine learning experiments aimed at classifying globally deceptive speech. Our best classification performance is 72.74{%} F1-Score (about 17{%} better than human performance), which is achieved using a combination of linguistic features and individual traits. |
| Tasks | Deception Detection |
| Published | 2018-06-01 |
| URL | https://www.aclweb.org/anthology/N18-1176/ |
| https://www.aclweb.org/anthology/N18-1176 | |
| PWC | https://paperswithcode.com/paper/linguistic-cues-to-deception-and-perceived |
| Repo | |
| Framework | |
TETRIS: TilE-matching the TRemendous Irregular Sparsity
| Title | TETRIS: TilE-matching the TRemendous Irregular Sparsity |
| Authors | Yu Ji, Ling Liang, Lei Deng, Youyang Zhang, Youhui Zhang, Yuan Xie |
| Abstract | Compressing neural networks by pruning weights with small magnitudes can significantly reduce the computation and storage cost. Although pruning makes the model smaller, it is difficult to get practical speedup in modern computing platforms such as CPU and GPU due to the irregularity. Structural pruning has attract a lot of research interest to make sparsity hardware-friendly. Increasing the sparsity granularity can lead to better hardware utilization, but it will compromise the sparsity for maintaining accuracy. In this work, we propose a novel method, TETRIS, to achieve both better hardware utilization and higher sparsity. Just like a tile-matching game, we cluster the irregularly distributed weights with small value into structured groups by reordering the input/output dimension and structurally prune them. Results show that it can achieve comparable sparsity with the irregular element-wise pruning and demonstrate negligible accuracy loss. The experiments also shows ideal speedup, which is proportional to the sparsity, on GPU platforms. Our proposed method provides a new solution toward algorithm and architecture co-optimization for accuracy-efficiency trade-off. |
| Tasks | |
| Published | 2018-12-01 |
| URL | http://papers.nips.cc/paper/7666-tetris-tile-matching-the-tremendous-irregular-sparsity |
| http://papers.nips.cc/paper/7666-tetris-tile-matching-the-tremendous-irregular-sparsity.pdf | |
| PWC | https://paperswithcode.com/paper/tetris-tile-matching-the-tremendous-irregular |
| Repo | |
| Framework | |
Discovering the mechanics of hidden neurons
| Title | Discovering the mechanics of hidden neurons |
| Authors | Simon Carbonnelle, Christophe De Vleeschouwer |
| Abstract | Neural networks trained through stochastic gradient descent (SGD) have been around for more than 30 years, but they still escape our understanding. This paper takes an experimental approach, with a divide-and-conquer strategy in mind: we start by studying what happens in single neurons. While being the core building block of deep neural networks, the way they encode information about the inputs and how such encodings emerge is still unknown. We report experiments providing strong evidence that hidden neurons behave like binary classifiers during training and testing. During training, analysis of the gradients reveals that a neuron separates two categories of inputs, which are impressively constant across training. During testing, we show that the fuzzy, binary partition described above embeds the core information used by the network for its prediction. These observations bring to light some of the core internal mechanics of deep neural networks, and have the potential to guide the next theoretical and practical developments. |
| Tasks | |
| Published | 2018-01-01 |
| URL | https://openreview.net/forum?id=H1srNebAZ |
| https://openreview.net/pdf?id=H1srNebAZ | |
| PWC | https://paperswithcode.com/paper/discovering-the-mechanics-of-hidden-neurons |
| Repo | |
| Framework | |
