Safe Screening for Sparse Conditional Random Fields
- URL: http://arxiv.org/abs/2111.13958v1
- Date: Sat, 27 Nov 2021 18:38:57 GMT
- Title: Safe Screening for Sparse Conditional Random Fields
- Authors: Weizhong Zhang and Shuang Qiu
- Abstract summary: We propose a novel safe dynamic screening method to identify and remove irrelevant features during the training process.
Our method is also the first screening method in sparse CRFs and even structure prediction models.
Experimental results on both synthetic and real-world datasets demonstrate that the speedup gained by our method is significant.
- Score: 13.563686294946745
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Sparse Conditional Random Field (CRF) is a powerful technique in computer
vision and natural language processing for structured prediction. However,
solving sparse CRFs in large-scale applications remains challenging. In this
paper, we propose a novel safe dynamic screening method that exploits an
accurate dual optimum estimation to identify and remove the irrelevant features
during the training process. Thus, the problem size can be reduced
continuously, leading to great savings in the computational cost without
sacrificing any accuracy on the finally learned model. To the best of our
knowledge, this is the first screening method which introduces the dual optimum
estimation technique -- by carefully exploring and exploiting the strong
convexity and the complex structure of the dual problem -- in static screening
methods to dynamic screening. In this way, we can absorb the advantages of both
the static and dynamic screening methods and avoid their drawbacks. Our
estimation would be much more accurate than those developed based on the
duality gap, which contributes to a much stronger screening rule. Moreover, our
method is also the first screening method in sparse CRFs and even structure
prediction models. Experimental results on both synthetic and real-world
datasets demonstrate that the speedup gained by our method is significant.
Related papers
- The Stochastic Conjugate Subgradient Algorithm For Kernel Support Vector Machines [1.738375118265695]
This paper proposes an innovative method specifically designed for kernel support vector machines (SVMs)
It not only achieves faster iteration per iteration but also exhibits enhanced convergence when compared to conventional SFO techniques.
Our experimental results demonstrate that the proposed algorithm not only maintains but potentially exceeds the scalability of SFO methods.
arXiv Detail & Related papers (2024-07-30T17:03:19Z) - One-Shot Safety Alignment for Large Language Models via Optimal Dualization [64.52223677468861]
This paper presents a perspective of dualization that reduces constrained alignment to an equivalent unconstrained alignment problem.
We do so by pre-optimizing a smooth and convex dual function that has a closed form.
Our strategy leads to two practical algorithms in model-based and preference-based settings.
arXiv Detail & Related papers (2024-05-29T22:12:52Z) - Real-Time Adaptive Safety-Critical Control with Gaussian Processes in
High-Order Uncertain Models [14.790031018404942]
This paper presents an adaptive online learning framework for systems with uncertain parameters.
We first integrate a forgetting factor to refine a variational sparse GP algorithm.
In the second phase, we propose a safety filter based on high-order control barrier functions.
arXiv Detail & Related papers (2024-02-29T08:25:32Z) - Nonconvex Robust High-Order Tensor Completion Using Randomized Low-Rank
Approximation [29.486258609570545]
Two efficient low-rank approximation approaches are first devised under the order high-artd (d >= 3) T-SVD framework.
The proposed method outperforms other state-of-the-art approaches in terms of both computational efficiency and estimated precision.
arXiv Detail & Related papers (2023-05-19T07:51:36Z) - Log Barriers for Safe Black-box Optimization with Application to Safe
Reinforcement Learning [72.97229770329214]
We introduce a general approach for seeking high dimensional non-linear optimization problems in which maintaining safety during learning is crucial.
Our approach called LBSGD is based on applying a logarithmic barrier approximation with a carefully chosen step size.
We demonstrate the effectiveness of our approach on minimizing violation in policy tasks in safe reinforcement learning.
arXiv Detail & Related papers (2022-07-21T11:14:47Z) - Distributed Dynamic Safe Screening Algorithms for Sparse Regularization [73.85961005970222]
We propose a new distributed dynamic safe screening (DDSS) method for sparsity regularized models and apply it on shared-memory and distributed-memory architecture respectively.
We prove that the proposed method achieves the linear convergence rate with lower overall complexity and can eliminate almost all the inactive features in a finite number of iterations almost surely.
arXiv Detail & Related papers (2022-04-23T02:45:55Z) - High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
It is essential to theoretically guarantee that algorithms provide small objective residual with high probability.
Existing methods for non-smooth convex optimization have complexity bounds with dependence on confidence level.
We propose novel stepsize rules for two methods with gradient clipping.
arXiv Detail & Related papers (2021-06-10T17:54:21Z) - Probabilistic robust linear quadratic regulators with Gaussian processes [73.0364959221845]
Probabilistic models such as Gaussian processes (GPs) are powerful tools to learn unknown dynamical systems from data for subsequent use in control design.
We present a novel controller synthesis for linearized GP dynamics that yields robust controllers with respect to a probabilistic stability margin.
arXiv Detail & Related papers (2021-05-17T08:36:18Z) - Efficient falsification approach for autonomous vehicle validation using
a parameter optimisation technique based on reinforcement learning [6.198523595657983]
The widescale deployment of Autonomous Vehicles (AV) appears to be imminent despite many safety challenges that are yet to be resolved.
The uncertainties in the behaviour of the traffic participants and the dynamic world cause reactions in advanced autonomous systems.
This paper presents an efficient falsification method to evaluate the System Under Test.
arXiv Detail & Related papers (2020-11-16T02:56:13Z) - Hidden Cost of Randomized Smoothing [72.93630656906599]
In this paper, we point out the side effects of current randomized smoothing.
Specifically, we articulate and prove two major points: 1) the decision boundaries of smoothed classifiers will shrink, resulting in disparity in class-wise accuracy; 2) applying noise augmentation in the training process does not necessarily resolve the shrinking issue due to the inconsistent learning objectives.
arXiv Detail & Related papers (2020-03-02T23:37:42Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.