The Structured Weighted Violations Perceptron Algorithm
We present the Structured Weighted Violations Perceptron (SWVP) algorithm, a new structured prediction algorithm that generalizes the Collins Structured Perceptron (CSP). Unlike CSP, the update rule of SWVP explicitly exploits the internal structure of the predicted labels. We prove the convergence of SWVP for linearly separable training sets, provide mistake and generalization bounds, and show that in the general case these bounds are tighter than those of the CSP special case. In synthetic data experiments with data drawn from an HMM, various variants of SWVP substantially outperform its CSP special case. SWVP also provides encouraging initial dependency parsing results.
Code (0)
등록된 구현이 없습니다.
Tasks
Dependency ParsingGeneralization BoundsStructured PredictionSimilar Papers 제목 키워드 기반
The Structured Weighted Violations MIRA
We present the Structured Weighted Violation MIRA (SWVM), a new structured prediction algorithm that is based on an hybridization between MIRA (Crammer and Singer, 2003) and the structured weighted violations perceptron …
Chunkingnamed-entity-recognitionNamed Entity RecognitionNamed Entity Recognition (NER)+3Lock-Free Parallel Perceptron for Graph-based Dependency Parsing
Dependency parsing is an important NLP task. A popular approach for dependency parsing is structured perceptron. Still, graph-based dependency parsing has the time complexity of $O(n^3)$, and it suffers from slow trainin…
Dependency ParsingHeterogeneous Multilayer Generalized Operational Perceptron
The traditional Multilayer Perceptron (MLP) using McCulloch-Pitts neuron model is inherently limited to a set of neuronal activities, i.e., linear weighted sum followed by nonlinear thresholding step. Previously, General…
Simulation of a Variational Quantum Perceptron using Grover's Algorithm
The quantum perceptron, the variational circuit, and the Grover algorithm have been proposed as promising components for quantum machine learning. This paper presents a new quantum perceptron that combines the quantum va…
Quantum Machine LearningDual Coordinate Descent Algorithms for Efficient Large Margin Structured Prediction
Due to the nature of complex NLP problems, structured prediction algorithms have been important modeling tools for a wide range of tasks. While there exists evidence showing that linear Structural Support Vector Machine …
Dependency ParsingDocument Summarizationnamed-entity-recognitionNamed Entity Recognition+5