Research Re: search & Re-search

• URL: http://arxiv.org/abs/2403.13705v1
• Date: Wed, 20 Mar 2024 16:08:57 GMT
• Title: Research Re: search & Re-search
• Authors: Aske Plaat,
• Abstract summary: This study takes a closer look at a depth-first algorithm, AB, and a best-first algorithm, SSS. The prevailing opinion on these algorithms is that SSS offers the potential for a more efficient search, but that its complicated formulation and exponential memory requirements render it impractical.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Search algorithms are often categorized by their node expansion strategy. One option is the depth-first strategy, a simple backtracking strategy that traverses the search space in the order in which successor nodes are generated. An alternative is the best-first strategy, which was designed to make it possible to use domain-specific heuristic information. By exploring promising parts of the search space first, best-first algorithms are usually more efficient than depth-first algorithms. In programs that play minimax games such as chess and checkers, the efficiency of the search is of crucial importance. Given the success of best-first algorithms in other domains, one would expect them to be used for minimax games too. However, all high-performance game-playing programs are based on a depth-first algorithm. This study takes a closer look at a depth-first algorithm, AB, and a best-first algorithm, SSS. The prevailing opinion on these algorithms is that SSS offers the potential for a more efficient search, but that its complicated formulation and exponential memory requirements render it impractical. The theoretical part of this work shows that there is a surprisingly straightforward link between the two algorithms -- for all practical purposes, SSS is a special case of AB. Subsequent empirical evidence proves the prevailing opinion on SSS to be wrong: it is not a complicated algorithm, it does not need too much memory, and it is also not more efficient than depth-first search.

Related papers

• LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
  This study introduces a novel guided tree search algorithm with dynamic node selection and node-level exploration budget. Experiments conducted on the GSM8K and TabMWP datasets demonstrate that our approach enjoys significantly lower computational costs compared to baseline methods.
  arXiv  Detail & Related papers  (2024-06-29T05:14:04Z)
• SLOPE: Search with Learned Optimal Pruning-based Expansion [2.0618817976970103]
  We present the Search with Learned Optimal Pruning-based Expansion (SLOPE) It learns the distance of a node from a possible optimal path, which in turn reduces the size of the open list. This ensures that the search explores only the region close to optimal paths while lowering memory and computational costs.
  arXiv  Detail & Related papers  (2024-06-07T13:42:15Z)
• Branches: Efficiently Seeking Optimal Sparse Decision Trees with AO* [12.403737756721467]
  Decision Tree (DT) Learning is a fundamental problem in Interpretable Machine Learning, yet it poses a formidable challenge. We formulate the problem as an AND/OR graph search which we solve with a novel AO*-type algorithm called Branches. We prove both optimality and complexity guarantees for Branches and we show that it is more efficient than the state of the art theoretically and on a variety of experiments.
  arXiv  Detail & Related papers  (2024-06-04T10:11:46Z)
• An optimized quantum minimum searching algorithm with sure-success probability and its experiment simulation with Cirq [4.987556615430226]
  We propose an optimized quantum minimum searching algorithm with sure-success probability. The performance evaluation shows that our algorithm has higher accuracy and efficiency than DHA algorithm.
  arXiv  Detail & Related papers  (2023-09-25T14:07:27Z)
• HARRIS: Hybrid Ranking and Regression Forests for Algorithm Selection [75.84584400866254]
  We propose a new algorithm selector leveraging special forests, combining the strengths of both approaches while alleviating their weaknesses. HARRIS' decisions are based on a forest model, whose trees are created based on optimized on a hybrid ranking and regression loss function.
  arXiv  Detail & Related papers  (2022-10-31T14:06:11Z)
• The CLRS Algorithmic Reasoning Benchmark [28.789225199559834]
  Learning representations of algorithms is an emerging area of machine learning, seeking to bridge concepts from neural networks with classical algorithms. We propose the CLRS Algorithmic Reasoning Benchmark, covering classical algorithms from the Introduction to Algorithms textbook. Our benchmark spans a variety of algorithmic reasoning procedures, including sorting, searching, dynamic programming, graph algorithms, string algorithms and geometric algorithms.
  arXiv  Detail & Related papers  (2022-05-31T09:56:44Z)
• Practical, Provably-Correct Interactive Learning in the Realizable Setting: The Power of True Believers [12.09273192079783]
  We consider interactive learning in the realizable setting and develop a general framework to handle problems ranging from best arm identification to active classification. We design novel computationally efficient algorithms for the realizable setting that match the minimax lower bound up to logarithmic factors.
  arXiv  Detail & Related papers  (2021-11-09T02:33:36Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  Bilevel optimization has been widely applied in many important machine learning applications. We propose two new algorithms for bilevel optimization. We show that both algorithms achieve the complexity of $mathcalO(epsilon-1.5)$, which outperforms all existing algorithms by the order of magnitude.
  arXiv  Detail & Related papers  (2021-06-08T21:05:30Z)
• Waypoint Planning Networks [66.72790309889432]
  We propose a hybrid algorithm based on LSTMs with a local kernel - a classic algorithm such as A*, and a global kernel using a learned algorithm. We compare WPN against A*, as well as related works including motion planning networks (MPNet) and value networks (VIN) It is shown that WPN's search space is considerably less than A*, while being able to generate near optimal results.
  arXiv  Detail & Related papers  (2021-05-01T18:02:01Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• Best-First Beam Search [78.71330480725668]
  We show that the standard implementation of beam search can be made up to 10x faster in practice. We propose a memory-reduced variant of Best-First Beam Search, which has a similar beneficial search bias in terms of downstream performance.
  arXiv  Detail & Related papers  (2020-07-08T05:56:01Z)

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.