Why Local Search Excels in Expression Simplification

2014-09-18 · Ben Ruijl, Aske Plaat, Jos Vermaseren, Jaap van den Herik

Simplifying expressions is important to make numerical integration of large expressions from High Energy Physics tractable. To this end, Horner's method can be used. Finding suitable Horner schemes is assumed to be hard, due to the lack of local heuristics. Recently, MCTS was reported to be able to find near optimal schemes. However, several parameters had to be fine-tuned manually. In this work, we investigate the state space properties of Horner schemes and find that the domain is relatively flat and contains only a few local minima. As a result, the Horner space is appropriate to be explored by Stochastic Local Search (SLS), which has only two parameters: the number of iterations (computation time) and the neighborhood structure. We found a suitable neighborhood structure, leaving only the allowed computation time as a parameter. We performed a range of experiments. The results obtained by SLS are similar or better than those obtained by MCTS. Furthermore, we show that SLS obtains the good results at least 10 times faster. Using SLS, we can speed up numerical integration of many real-world large expressions by at least a factor of 24. For High Energy Physics this means that numerical integrations that took weeks can now be done in hours.

📄 PDF Abstract BibTeX arXiv:1409.5223

Code (0)

등록된 구현이 없습니다.

Tasks

Numerical Integration

Methods 이 논문이 사용한 방법론

SPEED The monocular depth estimation (MDE) is the task of estimating depth from a single frame. This information is an essential knowledge in many computer vision tasks such as scene…

Inexact Simplification of Symbolic Regression Expressions with Locality-sensitive Hashing

2024-04-08 · Guilherme Seidyo Imai Aldeia, Fabricio Olivetti de Franca, William G. La Cava

Symbolic regression (SR) searches for parametric models that accurately fit a dataset, prioritizing simplicity and interpretability. Despite this secondary objective, studies point out that the models are often overly co…

regression Symbolic Regression

Learning to Perform Local Rewriting for Combinatorial Optimization

2018-09-30 · NeurIPS 2019 12 · Xinyun Chen, Yuandong Tian

Search-based methods for hard combinatorial optimization are often guided by heuristics. Tuning heuristics in various conditions and situations is often time-consuming. In this paper, we propose NeuRewriter that learns a…

Combinatorial Optimization Reinforcement Learning Reinforcement Learning (RL)Scheduling

Syntactic Simplification of OWL Class Expressions

2026-08-19 · Alkid Baci, N'Dah Jean Kouagou, Caglar Demir, Axel-Cyrille Ngonga Ngomo arxiv

Class expression learning often produces complex OWL class expressions that are difficult to interpret and reason over. However, by following theoretically grounded simplification principles, this complexity can be reduc…

Learning to Unscramble: Simplifying Symbolic Expressions via Self-Supervised Oracle Trajectories

2026-03-11 · David Shih arxiv

We present a new self-supervised machine learning approach for symbolic simplification of complex mathematical expressions. Training data is generated by scrambling simple expressions and recording the inverse operations…

Reinforcement Learning

Learning to Progressively Plan

2019-05-01 · ICLR 2019 5 · Xinyun Chen, Yuandong Tian

For problem solving, making reactive decisions based on problem description is fast but inaccurate, while search-based planning using heuristics gives better solutions but could be exponentially slow. In this paper, we p…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)Scheduling