# MAGIC: Generating Self-Correction Guideline for In-Context Text-to-SQL

Arian Askari1 , Christian Poelitz2, Xinye Tang2
1Leiden University
2Microsoft

1Leiden University<EMAIL_ADDRESS>
2Microsoft {cpoelitz<EMAIL_ADDRESS>
Work done during an internship at Microsoft.

###### Abstract

Self-correction in text-to-SQL is the process of prompting large language
model (LLM) to revise its previously incorrectly generated SQL, and commonly
relies on manually crafted self-correction guidelines by human experts that
are not only labor-intensive to produce but also limited by the human ability
in identifying all potential error patterns in LLM responses. We introduce
MAGIC, a novel multi-agent method that automates the creation of the self-
correction guideline. MAGIC uses three specialized agents: a manager, a
correction, and a feedback agent. These agents collaborate on the failures of
an LLM-based method on the training set to iteratively generate and refine a
self-correction guideline tailored to LLM mistakes, mirroring human processes
but without human involvement. Our extensive experiments show that MAGIC’s
guideline outperforms expert human’s created ones. We empirically find out
that the guideline produced by MAGIC enhance the interpretability of the
corrections made, providing insights in analyzing the reason behind the
failures and successes of LLMs in self-correction. We make all agent
interactions publicly available to the research community, to foster further
research in this area, offering a synthetic dataset for future explorations
into automatic self-correction guideline generation.

##  1 Introduction

Converting natural language questions to SQL database queries, known as text-
to-SQL, serves as a pivotal component for empowering non-expert data analysts
in extracting desired information from relational databases using natural
language Qu et al. (2024). While large language models have shown a
significant improvement in text-to-SQL and serve as state-of-the methods
according to the leaderboards Li et al. (2024b), they are prone to mistakes
and even GPT4 has a notable accuracy gap of 30% within human Li et al. (2023).

A solution for resolving the mistakes of LLM is the emerging concept of ‘self-
correction’ Madaan et al. (2023) that defines as the ability of LLMs in
revising their previous mistakes under the hypothesis that recognizing errors
is easier than avoiding them Gou et al. (2024); Madaan et al. (2023). Self-
correction in context of text-to-SQL is the process of prompting an LLM to
revise its previously incorrectly generated SQL Zhang et al. (2024); Chen et
al. (2023).

Figure 1: Example of self-correction using automatically generated guidelines
by MAGIC

While self-correction for LLMs has been widely studied in variety of tasks
including code generation with GPT4 Shypula et al. (2024); Pan et al. (2023);
Kamoi et al. (2024), it has been relatively unexplored in text-to-SQL. The
common method for self-correcting in existing few-shot LLM based methods that
achieve state-of-the-art effectiveness is designing a self-correction
guideline by human and prompting it to GPT-4 together with its initial
generated SQL Pourreza et al. (2023). This self-correction guideline commonly
engineered based on the train set where an expert human analyzes common
mistakes of the LLM on the training data and design a guideline to prevent
common mistakes. This process is a time-consuming and challenging task that is
limited to the ability of humans in identifying all the mistake patterns that
exist in the LLM responses Pourreza et al. (2023); Wang et al. (2024a); Talaei
et al. (2024).

We propose MAGIC, a novel multi-agent self-correction guideline generation for
text-to-SQL, that generates an effective self-correction guideline that
outperforms human-written guidelines and yields to improving effectiveness of
strong few-shot LLM based text-to-SQL methods. Similar to humans who engineer
the self-correction guideline and apply it to LLMs during inference, with
MAGIC, we first tackle guideline generation and then utilize the generated
guideline during inference. By iterating over the incorrect generated SQLs by
the initial text-to-SQL method, MAGIC automatically generates the self-
correction guideline that is tailored to the mistakes of the initial system.
Next, in inference, the self-correction guideline of MAGIC will be integrated
to the initial text-to-SQL method, assisting it in preventing its common
mistakes.

Unlike previous studies that analyze self-correction on a simple method that
uses GPT4 as its backbone or a low-effective open-source language model Zhang
et al. (2024), we employ a strong and effective open-source method based on
GPT4, DIN-SQL Pourreza et al. (2023), as our initial text-to-SQL system aiming
to compare our automatically generated guideline with an effective expert
human-written guideline. Our experiments demonstrate that the generated
guideline by MAGIC leads to self-explanatory self-correction, where the LLM
asks itself questions before self-correcting. Figure 1 illustrates an example
of where the MAGIC guideline assisted GPT4 to self-correct its previously
incorrectly generated SQL. The process is interpretable as the LLM first
starts with asking itself and then perform self-correction.

Figure 2: Illustration of our proposed method, MAGIC.

Our contributions are as follows:

  * •

We establish the task of self-correction guideline generation for text-to-SQL,
and introduce MAGIC, a novel multi-agent method, that automates the generation
of self-correction guideline and outperforms human-written guideline; yielding
to improve effectiveness of a strong few-shot LLM based text-to-SQL method.

  * •

We systematically analyze the impact of ours and existing self-correction
methods to perform self-correction across different scenarios: Correcting
incorrect queries; non-executable queries; and all queries.

  * •

We reproduce all the baselines utilizing the same version of GPT-4 across all
the experiments, and provide a comprehensive comparable insight on self-
correction in text-to-SQL.

We found that there can be a significant gap in terms of effectiveness when
utilizing different versions of GPT-4. For instance, our replication of DIN-
SQL Pourreza et al. (2023) on development set of BIRD Li et al. (2023)
achieves 56.52 compared to the original report of 50.72 in the paper, which is
about 6 points higher than the reported number. This is our motivation for
replicating and reproducing all the reported baselines using same GPT-4 and
and avoid copying numbers from previous papers.

##  2 Related work

LLMs for Text-to-SQL. Converting natural language questions into SQL queries,
known as text-to-SQL, has been an active area of research within both the
natural language processing (NLP) and database communities for many years
Zelle and Mooney (1996); Guo et al. (2019). Recently, text-to-SQL has
benefited from the promising effectiveness of Large Language Models (LLMs)
Talaei et al. (2024); Pourreza et al. (2023). Early methods utilized the zero-
shot in-context learning capabilities of LLMs for SQL generation Rajkumar et
al. (2022). Building on this, subsequent models have improved LLM performance
through task decomposition and techniques such as Chain-of-Thought (CoT) Wei
et al. (2022), including but not limited to models like DAIL-SQL Gao et al.
(2023), MAC-SQL Wang et al. (2024a), C3 Dong et al. (2023), self-consistency
Wang et al. (2022), and least-to-most prompting Zhou et al. (2023). In
addition, there are studies focusing on fine-tuning LLMs for text-to-SQL Li et
al. (2024c); Gao et al. (2023); Li et al. (2024a). We choose DIN-SQL Pourreza
et al. (2023) as the initial text-to-SQL system due to two reasons: (i) high
effectiveness and available open-source code; (ii) its self-correction
component is a human expert written guideline based on prior mistakes of the
LLM making it a suitable baseline for comparing the automatically self-
correction guideline generated by MAGIC with expert human-written guideline.
However, we would emphasize that our method is independent of how the in-
context learning method is designed and is adaptable to the output of any
method, as we only require the predicted SQL of the initial text-to-SQL system
for tackling self-correction in MAGIC.

Self-correction in text-to-SQL. Pan et al. (2024) and Kamoi et al. (2024)
provide an extensive overview of research on self-correction in a variety of
domains up to 2024. Here, we focus on self-correction in Text-to-SQL, where
there has been relatively limited study. Self-debugging Chen et al. (2023)
generates additional explanations on the question and initial predicted SQL,
which are then provided to an LLM for self-correction. DIN-SQL Pourreza et al.
(2023) designs a human-written self-correction guideline and revises all the
initially generated SQLs according to this guideline. Self-consistency is
based on generating several candidates and employing a voting process, which
has been integrated into Text-to-SQL by DAIL-SQL Gao et al. (2023). The
refiner component of MAC-SQL Wang et al. (2024a) uses execution errors as
signals for revising the SQL. To the best of our knowledge, we are the first
study to address self-correction in Text-to-SQL by generating a self-
correction guideline.

LLM-based Agents. LLM-based agents have been a promising area of study in both
academic and industry communities for an extended period Wang et al. (2024b),
leading to extensive research exploring autonomous agents based on LLMs such
as AutoGPT Significant Gravitas , OpenAgents Xie et al. (2023), and AutoGen Wu
et al. (2023). However, there are limited studies leveraging this concept for
text-to-SQL, with MAC-SQL being the only multi-agent method focusing on
addressing the Text-to-SQL task through a new multi-agent collaborative
framework Wang et al. (2024a). Inspired by the literature on multi-agent LLMs,
in MAGIC, we employ a multi-agent collaborative framework that iteratively
analyzes the failures of predicted SQLs by a text-to-SQL method’s and
automatically generates a self-correction guideline tailored to the method’s
mistakes. To the best of our knowledge, there is no prior work in the
literature that employs multi-agent methods for designing a self-correction
guideline in text-to-SQL or other domains.

##  3 Self-correction Guideline Generation

Tasks definition. Given a set of questions in natural language alongside the
corresponding database schema and the initially generated incorrect SQL
queries by a text-to-SQL system, the task of self-correction guideline
generation is to generate a self-correction guideline that is tailored to the
LLM’s mistakes and prevents it from repeating them. This can be done by a
human expert, an LLM, or a collaboration between a human expert and an LLM.
The typical approach for self-correction involves writing a guideline for the
Large Language Model manually by humans based on the LLM’s common mistakes
Pourreza et al. (2023); Talaei et al. (2024). The data used for guideline
generation must not be shared with the evaluation data to prevent overfitting
the guidelines on the test errors.

###  3.1 MAGIC

We tackle the task of generating self-correction guideline for text-to-SQL
systems, focusing on the failures of an initial method, denoted as $M$, using
the training dataset. A failure for $M$ occurs when the predicted SQL is
either not executable or its execution result differs from that of the ground
truth SQL, denoted as $s^{gt}$. In this context, the predicted SQL that is
either not executable or has a differing execution result is called an
incorrect SQL, denoted as $s^{\prime}$.

Our method, MAGIC, consists of three agents illustrated in Figure 2: the
manager, feedback, and correction agents. These agents interact iteratively
over the failures to generate the self-correction guideline. We describe this
process in detail in the following.

Feedback-correction cycle. Given each question, $s^{gt}$, and $s^{\prime}$,
the manager agent starts a feedback-correction iteration cycle. At each
iteration of this cycle, the manager requests the feedback agent for an
explanation of the mistakes in $s^{\prime}$ by comparing it to $s^{gt}$ (steps
2 to 3 in Figure 2). Next, the manager agent integrates the feedback received
from the feedback agent to interact with the correction agent. The manager
requests the correction agent to revise $s^{\prime}$ according to the provided
feedback (step 3 to 4 in Figure 2). Subsequently, the correction agent
generates a new revised SQL. At this stage, the manager identifies whether the
revised SQL by the correction agent successfully leads to identical results
with $s^{gt}$. To do so, the manager uses its SQL executor tool to execute the
correction agent’s revised SQL (step 5 in Figure 2). The manager ends this
cycle if the stopping criteria are met. The stopping criteria are either
revising $s^{\prime}$ successfully by the correction agent or reaching the
maximum number of iterations. We set $5$ as maximum number of iteration in our
experiments.

Revising agents’ instruction. In the first iteration of the feedback-
correction cycle, the manager uses two predefined prompts designed for its
interactions with the feedback and correction agents, as illustrated in
Figures 5 and 6 respectively. If the correction agent cannot successfully
revise $s^{\prime}$ in the first iteration, the manager begins revising these
predefined prompts. The prompt template of manager for revising the predefined
prompts of feedback and correction agents are illustrated in Figures 7 and 8.
We found empirically that this step plays an important role for the manager to
adapt its interaction with agents. Manager revise the agent’s instruction
based on the previous response of the agent, previous prompt that is used for
interacting with the agent, question, $s^{\prime}$, and $s^{gt}$.

Guideline generation. Given each successful revision by the correction agent,
the manager stores the corresponding successful feedback that led to this in
its memory. The manager then aggregates these stored feedbacks to generate the
self-correction guideline batch-by-batch using a predefined prompt for
guideline generation (Figure 9). Each batch consist of $k$ feedbacks. In our
preliminary experiments, we determined that a feedback batch size of 10 is
optimal. In the first batch, the manager begins without any pre-existing
guideline and generate an initial guideline. For subsequent batches, the
manager updates the already generated guideline. This guideline generation
process is triggered at the end of a feedback-correction cycle if the manager
has accumulated a new batch of successful feedbacks that has not yet been
utilized for guideline generation. The self-correction guideline generated by
our proposed method, MAGIC, automatically and from scratch, is presented in
Figures 11, 12, 13, 14, 15, and 16 in appendix section.

Efficiency. Previous approaches to craft self-correction guidelines needed
extensive expert human work. With MAGIC, we can efficiently generate,
empirically shown better guideline, in less than 2 hour.

###  3.2 Agents access to information

Although the manager agent has access to all the available information during
generation of self-correction guideline, the agents has limited access to the
information about the task. During the iterations, the correction agent
consistently receives only $s^{\prime}$. This ensures that a successful self-
correction can indicate that the feedback could effectively cover the mistakes
that exist in the $s^{\prime}$. This is important since the goal is generating
a guideline that can prevent from initial text-to-SQL system errors. As the
result, the self-correction agent should focus on correcting the initial
system prediction.

| Scenario of Self-Correction Application
---|---
DIN-SQL | Correcting incorrect SQLs | SQLs with Exec error | All SQLs
S | M | C | T | S | M | C | T | S | M | C | T
W/o self-correction | 63.14 | 49.03 | 38.19 | 56.52 | 63.14 | 49.03 | 38.19 | 56.52 | 63.14 | 49.03 | 38.19 | 56.52
Self-correction w/o guideline
Self-Debugging Chen et al. (2023) | 63.57 | 50.11 | 39.67 | 57.24 | 63.35 | 49.03 | 39.58 | 56.78 | 63.03 | 49.25 | 38.89 | 56.58
Self-Consistency Wang et al. (2022) | 64.56 | 50.79 | 40.09 | 58.08 | 63.24 | 49.03 | 38.19 | 56.58 | 64.00 | 49.68 | 37.50 | 57.17
Multiple-Prompt Lee et al. (2024) | 64.22 | 50.75 | 40.02 | 57.86 | 63.35 | 49.03 | 38.19 | 56.65 | 63.68 | 50.11 | 39.58 | 57.30
Self-correction w/ guideline
Human Expert G Wang et al. (2024a) | 63.18 | 49.19 | 38.30 | 56.60 | 63.20 | 49.03 | 38.19 | 56.58 | 47.80 | 46.22 | 35.30 | 46.14
Human Expert G Pourreza et al. (2023) | 64.32 | 50.32 | 39.58 | 57.76 | 63.58 | 49.03 | 38.89 | 56.98 | 62.49 | 48.17 | 37.50 | 55.80
MAGIC G (ours) | 65.84 | 51.61 | 40.28 | 59.13 | 63.69 | 50.15 | 39.59 | 57.32 | 65.75 | 49.46 | 41.67 | 58.55

Table 1: Effectiveness results in terms of Execution Accuracy (EX) on the DEV
set of the BIRD dataset. All the experiments have been reproduced by us. ‘S’,
‘M’, ‘C’, and ‘T’ refer to different levels of difficulty: Simple, Medium,
Challenging, and Total, respectively. The baseline for Natural Language to SQL
conversion is DIN-SQL and ‘Human Expert G’ refers to self-correction guideline
(prompt) by Pourreza et al. (2023) and Wang et al. (2024a). ‘MAGIC refers to
the guideline that is automatically generated by our proposed method, MAGIC,
using the train set of BIRD dataset.

##  4 Experimental setup

Datasets. The Spider Yu et al. (2018) dataset is a collection of 10,181
questions and 5,693 unique complex SQL queries across 200 databases in 138
domains, with each domain featuring multiple tables. It is divided into
training, development, and test sets with 8,659, 1,034, and 2,147 examples,
respectively, across 146, 20, and 34 distinct databases, ensuring no overlap
between sets. Queries are classified into four difficulty levels based on
complexity factors such as SQL keywords, nested subqueries, and use of column
selections and aggregations. The BIRD dataset Li et al. (2023) comprises
12,751 unique question-SQL pairings across 95 relative large databases (33.4
GB) in 37 professional domains like blockchain and healthcare. BIRD introduces
external knowledge as an additional resource for generating accurate SQL
queries to bring more complexity into the task.

Metrics. We employ two key metrics from existing literature: Execution
Accuracy (EX) and Valid Efficiency Score (VES). Execution Accuracy measures
the correctness of a predicted SQL query by comparing its execution output
with that of the ground truth SQL query. A SQL query is deemed correct if its
execution results match those of the ground truth, allowing for a precise
assessment of the model’s performance given the possibility of multiple valid
SQL queries for a single question. The Valid Efficiency Score evaluates the
efficiency of executing the generated SQL queries, focusing on both their
accuracy and execution time, but only considers queries that produce correct
results, i.e., those whose execution outcomes are consistent with the
reference query. This dual-metric approach provides a comprehensive evaluation
of the model’s ability to generate both accurate and efficient SQL queries.

Baselines. We reproduce DIN-SQL using the publicly available original
implementation Pourreza et al. (2023). For self-correction, we employ an
extensive set of baselines categorized into guideline-dependent and guideline-
independent methods. For guideline-independent methods, we reproduce self-
debugging Chen et al. (2023) based on the written prompts in the paper. For
self-consistency Wang et al. (2022); Gao et al. (2023), we generate 20 SQL
queries given the SQL generation prompt of DIN-SQL instead of generating only
one SQL and select the final SQL based on voting. In voting, we execute all
SQL queries and select the most frequently returned result’s SQL. If one
result is produced by various SQL queries, we select the most efficient one by
comparing them against each other. For the Multiple-Prompt baseline, we follow
the approach in Lee et al. (2024) by re-ordering candidate tables in the
prompt and generating up to 20 different combinations, employing a voting
mechanism similar to our self-consistency implementation. For human-expert
baselines, we utilize the self-correction guideline from DIN-SQL Pourreza et
al. (2023), written by human experts, and the revision guideline from MAC-SQL
Wang et al. (2024a), that is also written by human experts and are designed
specifically for correcting SQL queries with execution errors. However, we
also adopt their approach for correcting incorrect SQL queries and for
correcting all initially predicted SQL queries, regardless of whether they are
correct, similar to the scenarios analyzed in Chen et al. (2023) and Pourreza
et al. (2023) respectively.

##  5 Results

This section addresses the following research questions (RQs):

  * •

RQ1: What is the effectiveness of MAGIC’s self-correction guideline compared
to the existing state-of-the-art baselines for self-correction in text-to-SQL,
particularly across different error scenarios and datasets?

  * •

RQ2: How is the effectiveness of generated guidelines influenced by the
quantity of feedback - is more feedback always better?

  * •

RQ3: What is the impact of manager agent intervention on reducing the number
of iterations and increasing the number of corrected SQLs?

Main results (RQ1). Table 1 and 2 present the results of self-correction with
the guidelines generated by MAGIC on the development set of BIRD and SPIDER,
respectively. Overall, the guidelines generated by our proposed method, MAGIC,
outperform all the baselines in terms of total effectiveness measured by
execution accuracy and demonstrate significant improvements in self-correction
performance across the BIRD and SPIDER datasets, outperforming self-correction
guidelines written by expert humans. For example, MAGIC’s guidelines improve
the DIN-SQL Pourreza et al. (2023) baseline from 56.52 to 59.13 in terms of
execution accuracy and outperform the self-correction guideline of Wang et al.
(2024a) as well, as presented in Tables 5 and 1 respectively.

We experiment with self-correction in three scenarios, as shown in Table 1:
(i) correcting incorrect SQLs, assuming the availability of a correctness
oracle. This setup is common in recent studies focusing on self-correction in
text-to-SQL Chen et al. (2023); Zhang et al. (2024). (ii) SQLs with execution
errors: this scenario is common in self-correction where there is no available
correctness oracle, but the goal is to avoid generating incorrect and non-
executable SQL Wang et al. (2024a). (iii) All SQLs: this setup is common in
methods where self-correction is part of a multi-step model, employing a self-
correction guideline on all predictions Pourreza et al. (2023).

Correction Method | EX
---|---
| w/o self-correction | 78.62
Self-correction w/o guideline
| Self-Consistency Wang et al. (2022) | 81.64
| Multiple-Prompt Lee et al. (2024) | 80.22
Self-correction w/ guideline
| Human’s G Wang et al. (2024a) | 81.15
| Human’s G Pourreza et al. (2023) | 80.35
| MAGIC’s G (Ours) | 85.66

Table 2: Effectiveness results for self-correcting incorrect SQL queries on
the SPIDER development set. We compared MAGIC’s generated guideline (MAGIC’s
G) against two top self-correction baselines: self-consistency and multiple-
prompt, as well as two expert human self-correction guidelines.

| # of aggregated batch of feedbacks
---|---
| 0 | 1 | 5 | 10 | 39 (All)
EX | 56.52 | 57.4 | 58.8 | 59.13 | 59.13

Table 3: Impact of number of aggregation levels of feedbacks on the
effectiveness of generated self-correction guideline on the development set of
BIRD dataset.

We find that applying self-correction to all predicted SQLs, as in the human-
expert written guideline for self-correction in Wang et al. (2024a), reduces
effectiveness. Intuitively, when self-correction is applied for all predicted
SQLs, there is a risk that the LLM changes its previously correct prediction
to an incorrect one, as suggested by previous work Li et al. (2024d).
Therefore, designing a proper self-correction guideline is crucial, or it is
safer to apply self-correction where a correctness oracle can identify whether
the initial response is correct or not. This oracle can be a human user who
minimally interacts with the system and only determines whether the executed
query results meet their expectations. Regarding the "SQLs with execution
errors" scenario, only 46 queries predicted by the initial text-to-SQL system
Pourreza et al. (2023) are non-executable, which limits the effectiveness of
self-correction for these cases, with several methods achieving the same
effectiveness (49.03) for medium query difficulty.

a) MAGIC w/ manager.

b) MAGIC w/o manager.

Figure 3: Analyzing impact of maximum number of iterations on the total number
of corrected SQLs, that were initially incorrect, with and without manager
being involved in MAGIC. The analysis is conducted on the train set of the
BIRD dataset.

It is noteworthy that although we have not attempted to combine MAGIC with
other baselines, as our focus is on analyzing different self-correction
methods rather than integrating them, some baselines could potentially enhance
MAGIC if combined, such as Self-consistency Wang et al. (2022) and Multiple-
Prompt Lee et al. (2024).

Impact of Feedback Quantity (RQ2). Table 3 presents the results of the
generated self-correction guideline effectiveness by MAGIC, where different
numbers of batches of feedback are aggregated for generating the guideline. We
found that after aggregating 10 batches of feedback, each batch consist of 10
feedbacks, the generated guideline by MAGIC outperforms existing self-
correction baselines, including those with guidelines written by humans. This
shows the efficiency of process of MAGIC for self-correction guideline
generation. Furthermore, we found that questions for which MAGIC cannot
provide feedback to self-correct are often controversial. For example, when an
additional aggregation function column is reported alongside the main column
name that should be reported, such as ’SELECT city, MAX(population) FROM
cities‘ where the MAX(population) should not be included in the predicted
query according to the ground truth.

| BIRD | Spider
---|---|---
EX $\uparrow$ | VES $\uparrow$ | AVGi $\downarrow$ | EX $\uparrow$ | AVGi $\downarrow$
MAGIC${}_{\text{max}_{i}=2}$
w/o manager | 73.01 | 68.29 | 1.17 | 81.40 | 1.11
w/ manager | 78.94 | 80.22 | 1.12 | 86.52 | 1.05
MAGIC${}_{\text{max}_{i}=5}$
w/o manager | 78.60 | 79.58 | 2.87 | 83.28 | 2.22
w/ manager | 81.81 | 84.19 | 2.41 | 91.78 | 2.15

Table 4: The effectiveness for generating feedbacks on the train set of BIRD
dataset. The $max_{i}$ and $AVG_{i}$ refers to the maximum number of
iterations and average number of iterations till stopping criteria triggers
respectively.

Feedback generation effectiveness (RQ3). Figure 3 presents an analysis of the
number of corrected SQL queries with and without the inclusion of the manager
agent, by evaluating the performance of the MAGIC framework across a range of
maximum iteration counts used as stopping criteria, from one to five. When the
manager agent is excluded, the feedback agent controls the maximum iteration
count and utilizes the SQL executor tool to compare the execution results of
the revised SQL with the ground truth SQL. This comparison underscores the
significant role of the manager agent in correcting a larger number of
incorrect SQL queries within fewer iterations and ultimately correcting more
SQL queries when both setups reach the maximum of five iterations. It is
important to note that excluding the manager agent from MAGIC is equivalent to
the critic-refine cycle method Kamoi et al. (2024), that has been employed in
other tasks, such as code generation. However, unlike MAGIC, the critic-refine
Kamoi et al. (2024) does not produce any guidelines as a result of its
feedback generation process and has not been applied to text-to-SQL tasks to
the best of our knowledge.

Method | EX
---|---
Zero-shot GPT-4 OpenAI (2023b) | 40.18
Zero-shot GPT-4 + MAGIC G (Ours) | 48.19
Few-shot GPT-4 Li et al. (2023) | 45.66
Few-shot GPT-4 Li et al. (2023) \+ MAGIC G (Ours) | 50.38
DIN-SQL Pourreza et al. (2023) | 56.52
DIN-SQL Pourreza et al. (2023) \+ MAGIC G (Ours) | 59.13

Table 5: The effectiveness of self-correction guideline generated by our
proposed method, MAGIC, across different methods.

Figure 4: Analyzing impact of MAGIC’s correction guideline across different
databases of development set of BIRD dataset.

We further analyze the impact of manager agent in terms of overall performance
of self-correction considering all the queries. Table 4 measures the
effectiveness of MAGIC in terms of execution accuracy (EX) to determine how
many could be addressed correctly in total with the already corrected
predictions by LLM and self-corrected ones with MAGIC. We also measure Valid
Efficiency Score (VES) to determine whether the self-correction by MAGIC
results in optimized SQLs compared to the ground truth. As it can be observed,
MAGIC with the manager agent outperforms the exclusion of manager agent in all
setups in terms of all metrics across the BIRD and SPIDER datasets. Results
show that MAGIC with manager agent is able to generate more efficient SQLs
compared to exclusion of manager agent, e.g., 84.19 vs. 79.58 in terms of VES
for w/ manager and w/o manager on the BIRD dataset where the maximum numebr of
iteration is set to 5. We manually analyzed the revised prompt by manager
agent and found out during its interactions with the agents where it revises
the prompts, the manager agent tends add instructions for self-correction to
optimize the efficiency of SQL, which might be the reason behind generating
more efficient SQLs.

##  6 Discussion

Applicability to other methods. We analyze the applicability of the guideline
generated by MAGIC based on the mistakes of the DIN-SQL Pourreza et al. (2023)
method on two other methods that generate SQL in a single step: zero-shot
GPT-4 OpenAI (2023a) and few-shot GPT-4 Li et al. (2023) as shown in Table 5.
As we can observe, MAGIC’s guidelines improve the zero-shot GPT-4 baseline
from 40.18 to 48.19 and few-shot GPT-4 from 45.56 to 50.38 in terms of
execution accuracy, respectively.

Source of examples in guideline. We analyzed the relationship between the
generated guideline and the feedback that contributed to its creation.
Specifically, we examined whether any examples in the guideline directly
mirrored instances from the feedback or outputs of the correction agent. Our
findings indicate that no example was directly copied from the feedback to be
used in the guideline. Instead, our empirical observations reveal that the
manager agent tends to aggregate multiple pieces of feedback to construct new
examples into the self-correction guideline.

Database analysis. Figure 4 illustrates the impact of the self-correction
guidelines generated by MAGIC across different databases in the development
set of the BIRD dataset. We found that while self-correction improves
effectiveness across all databases, some databases benefit more from MAGIC’s
guidelines. This variability could be due to the capability of the LLM, the
differing levels of challenging information in the databases, or other
factors. This observation could motivate the development of guidelines that
are adapted to difficulty of database in the future.

##  7 Conclusions

This paper presents a new perspective on self-correction in in-context
learning for text-to-SQL translation. It proposes a novel method for
generating self-correction guidelines, called MAGIC. The motivation behind
this approach is to overcome the limitations of existing methods that generate
self-correction guidelines by hand, a time-consuming task. Additionally, it
addresses the important and costly task of automatically fixing incorrect SQL
generated by humans. This work showcases the potential of leveraging LLMs to
generate their own self-correction guidelines and highlights the significance
of guideline generation in text-to-SQL. We emphasize the importance of
improving self-correction methods in text-to-SQL and addressing them as a
separate task. The findings of this study contribute to advancing the state-
of-the-art in text-to-SQL translation, as our method can be applied to fix
issues in any method and provide valuable insights for future research in this
domain.

##  8 Limitations

In this paper, we have demonstrated that generative LLMs are capable of
generating their own self-correction guidelines even more effectively than
exsiting guidelines written by human experts in previous studies. However, it
is important to highlight that such training data might not be available for
the new query languages. Moreover, while our experiments illustrate the
superior effectiveness of our self-correction guidelines in comparison to
those developed by human experts, we have not conducted a systematic study to
quantify the potential generation of hallucinated data during this process and
its subsequent impact on the performance of the automatically generated
guidelines.

Additionally, despite the high effectiveness of the generated guidelines, we
wish to underscore that for large businesses, it may still be needed to have
humans review these guidelines. Nevertheless, given that the generated
guidelines tend not to be overly lengthy and can be generated under 2 hours
(presented in Figure 11 to Figure 16 in appendix section), we believe that the
effort required for reviewing the content of these guidelines is significantly
more efficient than manually analyzing all of the LLM’s errors and developing
self-correction guidelines from scratch.

## References

  * Chen et al. (2023) Xinyun Chen, Maxwell Lin, Nathanael Schärli, and Denny Zhou. 2023.  Teaching large language models to self-debug.  _arXiv preprint arXiv:2304.05128_.
  * Dong et al. (2023) Xuemei Dong, Chao Zhang, Yuhang Ge, Yuren Mao, Yunjun Gao, Jinshu Lin, Dongfang Lou, et al. 2023.  C3: Zero-shot text-to-sql with chatgpt.  _arXiv preprint arXiv:2307.07306_.
  * Gao et al. (2023) Dawei Gao, Haibin Wang, Yaliang Li, Xiuyu Sun, Yichen Qian, Bolin Ding, and Jingren Zhou. 2023.  Text-to-sql empowered by large language models: A benchmark evaluation.  _arXiv preprint arXiv:2308.15363_.
  * Gou et al. (2024) Zhibin Gou, Zhihong Shao, Yeyun Gong, yelong shen, Yujiu Yang, Nan Duan, and Weizhu Chen. 2024.  CRITIC: Large language models can self-correct with tool-interactive critiquing.  In _The Twelfth International Conference on Learning Representations_.
  * Guo et al. (2019) Jiaqi Guo, Zecheng Zhan, Yan Gao, Yan Xiao, Jian-Guang Lou, Ting Liu, and Dongmei Zhang. 2019.  Towards complex text-to-sql in cross-domain database with intermediate representation.  _arXiv preprint arXiv:1905.08205_.
  * Kamoi et al. (2024) Ryo Kamoi, Yusen Zhang, Nan Zhang, Jiawei Han, and Rui Zhang. 2024.  When can llms actually correct their own mistakes? a critical survey of self-correction of llms.  _arXiv preprint arXiv:2406.01297_.
  * Lee et al. (2024) Dongjun Lee, Choongwon Park, Jaehyuk Kim, and Heesoo Park. 2024.  Mcs-sql: Leveraging multiple prompts and multiple-choice selection for text-to-sql generation.  _arXiv preprint arXiv:2405.07467_.
  * Li et al. (2024a) Haoyang Li, Jing Zhang, Hanbing Liu, Ju Fan, Xiaokang Zhang, Jun Zhu, Renjie Wei, Hongyan Pan, Cuiping Li, and Hong Chen. 2024a.  Codes: Towards building open-source language models for text-to-sql.  _arXiv preprint arXiv:2402.16347_.
  * Li et al. (2024b) Jinyang Li, Binyuan Hui, Ge Qu, Jiaxi Yang, Binhua Li, Bowen Li, Bailin Wang, Bowen Qin, Rongyu Cao, Ruiying Geng, Nan Huo, Xuanhe Zhou, Chenhao Ma, Guoliang Li, Kevin C. C. Chang, Fei Huang, Reynold Cheng, and Yongbin Li. 2024b.  Bird-sql leaderboard.
  * Li et al. (2023) Jinyang Li, Binyuan Hui, GE QU, Jiaxi Yang, Binhua Li, Bowen Li, Bailin Wang, Bowen Qin, Ruiying Geng, Nan Huo, Xuanhe Zhou, Chenhao Ma, Guoliang Li, Kevin Chang, Fei Huang, Reynold Cheng, and Yongbin Li. 2023.  Can LLM already serve as a database interface? a BIg bench for large-scale database grounded text-to-SQLs.  In _Thirty-seventh Conference on Neural Information Processing Systems Datasets and Benchmarks Track_.
  * Li et al. (2024c) Jinyang Li, Binyuan Hui, Ge Qu, Jiaxi Yang, Binhua Li, Bowen Li, Bailin Wang, Bowen Qin, Ruiying Geng, Nan Huo, et al. 2024c.  Can llm already serve as a database interface? a big bench for large-scale database grounded text-to-sqls.  _Advances in Neural Information Processing Systems_ , 36.
  * Li et al. (2024d) Loka Li, Guangyi Chen, Yusheng Su, Zhenhao Chen, Yixuan Zhang, Eric Xing, and Kun Zhang. 2024d.  Confidence matters: Revisiting intrinsic self-correction capabilities of large language models.  _CoRR_ , abs/2402.12563.
  * Madaan et al. (2023) Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, et al. 2023.  Self-refine: Iterative refinement with self-feedback.  _Advances in Neural Information Processing Systems_.
  * OpenAI (2023a) OpenAI. 2023a.  Gpt-4 technical report.
  * OpenAI (2023b) R OpenAI. 2023b.  Gpt-4 technical report. arxiv 2303.08774.  _View in Article_ , 2(5).
  * Pan et al. (2023) Liangming Pan, Michael Saxon, Wenda Xu, Deepak Nathani, Xinyi Wang, and William Yang Wang. 2023.  Automatically correcting large language models: Surveying the landscape of diverse self-correction strategies.  _arXiv preprint arXiv:2308.03188_.
  * Pan et al. (2024) Liangming Pan, Michael Saxon, Wenda Xu, Deepak Nathani, Xinyi Wang, and William Yang Wang. 2024.  Automatically correcting large language models: Surveying the landscape of diverse automated correction strategies.  _Transactions of the Association for Computational Linguistics_ , 11:484–506.
  * Pourreza et al. (2023) Mohammadreza Pourreza, , and Davood Rafiei. 2023.  Din-sql: Decomposed in-context learning of text-to-sql with self-correction.  In _Advances in Neural Information Processing Systems_ , volume 36, pages 36339–36348. Curran Associates, Inc.
  * Qu et al. (2024) Ge Qu, Jinyang Li, Bowen Li, Bowen Qin, Nan Huo, Chenhao Ma, and Reynold Cheng. 2024.  Before generation, align it! a novel and effective strategy for mitigating hallucinations in text-to-sql generation.  _arXiv preprint arXiv:2405.15307_.
  * Rajkumar et al. (2022) Nitarshan Rajkumar, Raymond Li, and Dzmitry Bahdanau. 2022.  Evaluating the text-to-sql capabilities of large language models.  _arXiv preprint arXiv:2204.00498_.
  * Shypula et al. (2024) Alexander G Shypula, Aman Madaan, Yimeng Zeng, Uri Alon, Jacob R. Gardner, Yiming Yang, Milad Hashemi, Graham Neubig, Parthasarathy Ranganathan, Osbert Bastani, and Amir Yazdanbakhsh. 2024.  Learning performance-improving code edits.  In _The Twelfth International Conference on Learning Representations_.
  * (22) Significant Gravitas.  AutoGPT.
  * Talaei et al. (2024) Shayan Talaei, Mohammadreza Pourreza, Yu-Chen Chang, Azalia Mirhoseini, and Amin Saberi. 2024.  Chess: Contextual harnessing for efficient sql synthesis.
  * Wang et al. (2024a) Bing Wang, Changyu Ren, Jian Yang, Xinnian Liang, Jiaqi Bai, Linzheng Chai, Zhao Yan, Qian-Wen Zhang, Di Yin, Xing Sun, and Zhoujun Li. 2024a.  Mac-sql: A multi-agent collaborative framework for text-to-sql.
  * Wang et al. (2024b) Lei Wang, Chen Ma, Xueyang Feng, Zeyu Zhang, Hao Yang, Jingsen Zhang, Zhiyuan Chen, Jiakai Tang, Xu Chen, Yankai Lin, et al. 2024b.  A survey on large language model based autonomous agents.  _Frontiers of Computer Science_ , 18(6):186345.
  * Wang et al. (2022) Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc V Le, Ed H Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. 2022.  Self-consistency improves chain of thought reasoning in language models.  In _The Eleventh International Conference on Learning Representations_.
  * Wei et al. (2022) Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al. 2022.  Chain-of-thought prompting elicits reasoning in large language models.  _Advances in Neural Information Processing Systems_ , 35:24824–24837.
  * Wu et al. (2023) Qingyun Wu, Gagan Bansal, Jieyu Zhang, Yiran Wu, Shaokun Zhang, Erkang Zhu, Beibin Li, Li Jiang, Xiaoyun Zhang, and Chi Wang. 2023.  Autogen: Enabling next-gen llm applications via multi-agent conversation framework.  _arXiv preprint arXiv:2308.08155_.
  * Xie et al. (2023) Tianbao Xie, Fan Zhou, Zhoujun Cheng, Peng Shi, Luoxuan Weng, Yitao Liu, Toh Jing Hua, Junning Zhao, Qian Liu, Che Liu, et al. 2023.  Openagents: An open platform for language agents in the wild.  _arXiv preprint arXiv:2310.10634_.
  * Yu et al. (2018) Tao Yu, Rui Zhang, Kai Yang, Michihiro Yasunaga, Dongxu Wang, Zifan Li, James Ma, Irene Li, Qingning Yao, Shanelle Roman, Zilin Zhang, and Dragomir Radev. 2018.  Spider: A large-scale human-labeled dataset for complex and cross-domain semantic parsing and text-to-SQL task.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 3911–3921, Brussels, Belgium. Association for Computational Linguistics.
  * Zelle and Mooney (1996) John M Zelle and Raymond J Mooney. 1996.  Learning to parse database queries using inductive logic programming.  In _Proceedings of the national conference on artificial intelligence_ , pages 1050–1055.
  * Zhang et al. (2024) Bin Zhang, Yuxiao Ye, Guoqing Du, Xiaoru Hu, Zhishuai Li, Sun Yang, Chi Harold Liu, Rui Zhao, Ziyue Li, and Hangyu Mao. 2024.  Benchmarking the text-to-sql capability of large language models: A comprehensive evaluation.  _arXiv preprint arXiv:2403.02951_.
  * Zhou et al. (2023) Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schuurmans, Claire Cui, Olivier Bousquet, Quoc V Le, et al. 2023.  Least-to-most prompting enables complex reasoning in large language models.  In _The Eleventh International Conference on Learning Representations_.

##  9 Appendix

###  9.1 Prompts

The prompts that are used are as follow:

  * •

The prompt for the predefined interaction of manager agent with feedback agent
can be seen in Figure 5, and the prompt with that the manager agent revises
its previous predefined prompt can be seen in Figure 7.

  * •

The prompt for the predefined interaction of manager agent with feedback agent
can be seen in Figure 6, and the prompt with that the manager agent revises
its previous predefined prompt can be seen in Figure 8.

  * •

The prompt for manager agent to generate the self-correction guideline can be
seen in Figure 9.

Furthermore, an example of last iteration of our proposed method, MAGIC, on a
question of BIRD dataset, that led to a successful self-correction can be seen
in Figure 10.

System role prompt:

Complete the text in chat style like a database manager expert. Write in
simple present without using correct SQL. Accept what the user identifies as
correct or incorrect.

User role prompt:

"question": "{question}",
"evidence": "{evidence}",
"Correct SQL": "{Correct SQL}",
"Incorrect SQL": "{Incorrect SQL}",

Incorrect SQL mistakes are: Figure 5: The predefined prompt for interaction of
magic agent with feedback agent. System role prompt:
Your task is to correct the predicted SQL based on the provided feedback by
expert human.

1\. Input Information: You will receive a question, a database schema, a
predicted SQL query, and a human feedback.

2\. SQL format in your response:
\- You must ensure that your response contains a valid SQL.
\- The format of SQL in your response must be in the following format: “‘sql
SQL “‘.

User role prompt:

\- Schema Overview: {schema}
\- Columns Description: columns Description
\- Question: {question}

\- Predicted SQL: “‘sql {Incorrect SQL} “‘
\- Expert Human Feedback: {feedback} Figure 6: The predefined prompt for
interaction of magic agent with correction agent. System role prompt
You are a helpful AI assistant that manages other assistants.

User role prompt
Manager, please review the following prompt for the following agent and
generate a revised prompt.
So far you have revised the prompt for {iteration_number} times.
Agent description: This agent generates feedback based on the comparison
between predicted and ground truth SQL queries.
Previous output of agent that was not useful: {agent_outputs[-1]}
Previous prompt of agent that you should revise: {agent_prompts[-1]}

Revise prompt (Return the entire prompt so it can be directly pass to the
agent): Figure 7: The prompt template of manager for revising the predefined
prompts of feedback agent. System role prompt:
You are a helpful AI assistant that manages other assistants.

User role prompt:
Manager, please review the following prompt for the following agent and
generate a revised prompt.
So far you have revised the prompt for {iteration_number} times.
Agent description: This agent generates corrections for SQL queries based on
expert human feedback.
Previous output of agent that was not useful: {agent_outputs[-1]}
Previous prompt of agent that you should revise: {agent_prompts[-1]}

####
The ideal output of agent should be the following but we cannot directly give
the ideal output to the agent:
Ideal output of agent: {Correct SQL}
####

Revise prompt (Return the entire prompt so it can be directly pass to the
agent):
Figure 8: The prompt template of manager for revising the predefined prompts
of correction agent. # Guideline format:
number. Reminder of mistake
\- Question: "Question"
\- Incorrect SQL generated by me: “‘sql incorrect sql “‘
\- Corrected SQL generated by me: “‘sql corrected sql “‘
\- Negative and strict step-by-step ask-to-myself questions to prevent same
mistake again:

# Guideline so far:
{current_guideline} // current guideline variable is empty at first

# Recent mistakes that must be aggregate to Guideline:
{batch_of_successful_feedbacks}

# Updated Guideline (Return the entire of guideline): Figure 9: The prompt of
manager for self-correction guideline generation. Figure 10: Illustration of
last iteration of our proposed method, MAGIC, on a question of BIRD dataset,
that led to a successful self-correction.
---
Figure 11: Self-correction guideline that is generated by our method, MAGIC,
automatically. Page 1.
---
Figure 12: Self-correction guideline that is generated by our method, MAGIC,
automatically. Page 2.
---
Figure 13: Self-correction guideline that is generated by our method, MAGIC,
automatically. Page 3.
---
Figure 14: Self-correction guideline that is generated by our method, MAGIC,
automatically. Page 4.
---
Figure 15: Self-correction guideline that is generated by our method, MAGIC,
automatically. Page 5.
---
Figure 16: Self-correction guideline that is generated by our method, MAGIC,
automatically. Page 6.


# Relevance-aware Algorithmic Recourse

Dongwhi Kim  University of Notre Dame<EMAIL_ADDRESS>and  Nuno Moniz
University of Notre Dame<EMAIL_ADDRESS>
(2018; 20 February 2007; 12 March 2009; 5 June 2009)

###### Abstract.

As machine learning continues to gain prominence, transparency and
explainability are increasingly critical. Without an understanding of these
models, they can replicate and worsen human bias, adversely affecting
marginalized communities. Algorithmic recourse emerges as a tool for
clarifying decisions made by predictive models, providing actionable insights
to alter outcomes. They answer, “What do I have to change?” to achieve the
desired result. Despite their importance, current algorithmic recourse methods
treat all domain values equally, which is unrealistic in real-world settings.
In this paper, we propose a novel framework, Relevance-Aware Algorithmic
Recourse (RAAR), that leverages the concept of relevance in applying
algorithmic recourse to regression tasks. We conducted multiple experiments on
15 datasets to outline how relevance influences recourses. Results show that
relevance contributes algorithmic recourses comparable to well-known
baselines, with greater efficiency and lower relative costs.

Algorithmic Recourse, Bayesian Optimization, Regression, Counterfactual
Explanations

††copyright: acmlicensed††journalyear: 2018††doi: XXXXXXX.XXXXXXX††conference:
Make sure to enter the correct conference title from your rights confirmation
emai; June 03–05, 2018; Woodstock, NY††isbn: 978-1-4503-XXXX-X/18/06††ccs:
Computing methodologies Machine learning algorithms

##  1\. Introduction

The landscape of machine learning applications in decision-making has exploded
in the past decade, ranging from dynamic pricing algorithms in services like
Uber to pivotal decisions in areas such as bail and loan approvals (Wang et
al., 2020; Yan et al., 2020). The sheer volume of data generation highlights
the need for better ways to analyze and leverage data to provide quick and
accurate decision-making (Clissa et al., 2023; Eirinaki et al., 2016). In this
respect, machine learning has shown it can provide solutions capable of
rapidly analyzing data and benefiting society, although requiring human
monitoring to ensure a just experience.

Unsurprisingly, the increased adoption of machine learning has drawn attention
from governments and large organizations in regulation (Black and Murray,
2019). Evidenced by the “right to explanation” introduced by the EU General
Data Protection Regulation (GDPR), it seeks to safeguard individuals adversely
affected by semi-autonomous decisions, giving them the right to understand why
they were denied (eu_, 2018). Similarly, within the United States, the “right
to explanation” is enforced in credit scoring, ensuring that creditors explain
the key factors that influence an individual’s credit score (us_, [n. d.]).
Consequently, there is a growing emphasis on developing programs and analyses
that provide avenues for recourse to those impacted by semi-autonomous
decisions (Voigt and Bussche, 2017). Regulation is necessary to manage the
associated risks associated with AI while promoting its development.

Counterfactual explanations are excellent tools to mitigate risks, promote the
ethical use of AI, and abide by regulations (Sokol and Flach, 2019). They
outline the necessary conditions to achieve a desired outcome, offering
insights into complex models. In addition, they reduce the regulatory burden
by providing practical recourse options and align with the GDPR’s “right to
explanation” (Voigt and Bussche, 2017).

In recent literature, multiple approaches exist for algorithmic recourse,
i.e., counterfactuals, from gradient-based methods to integer programming-
based approaches and probabilistic optimizations (Wachter et al., 2017; Ustun
et al., 2019; Karimi et al., 2020b). Although different, each strategy offers
nuanced perspectives and techniques to address the challenges associated with
algorithmic decision-making.

##### Motivation

Suppose a person arrives at a bank seeking a $100,000 loan but is only allowed
$50,000. Algorithmic recourse will only be useful if it provides actionable
and realistic counterfactuals, conveying how the individual may effect small
changes to become eligible. As such, disregarding user preferences may lead to
useless explanations. This describes the main issue with current algorithmic
recourse methods. Current methods lack consideration for user preferences over
the domain, i.e., relevance, and generally assume all values in a domain are
equally important in obtaining an accurate prediction (Ribeiro and Moniz,
2020). In this context, relevance is the importance of obtaining an accurate
prediction from a user perspective.

##### Contribution.

In this paper, we introduce a new framework, Relevance-Aware Algorithmic
Recourse (RAAR) rooted in providing accurate and realistic recourses by
leveraging the concept of domain relevance (Ribeiro and Moniz, 2020). It
enhances the effectiveness of algorithmic recourse in decision-making
processes through counterfactual explanations that maximize one’s outcomes
relative to one’s situation. Our results show relevance contributes to
algorithmic recourses comparable to well-known baselines, with greater
efficiency and lower relative costs. As a result, we can provide more
actionable recourses for users, enabling them to take action more easily and
still obtain their desired outcome.

##  2\. Related Works

Algorithmic recourse provides actionable recourse to individuals affected by
semi-autonomous decisions (Karimi et al., 2020a). It answers: how can I change
my situation (Venkatasubramanian and Alfano, 2020; Joshi et al., 2019)?
Currently, there are several approaches that other papers have outlined to
tackle this same issue. In general, they fall into these categories: level of
accessibility to the predictive model (black box or gradient), the enforcement
of sparsity (changing the least features) in counterfactuals, research of the
underlying causal relationship, and more (Karimi et al., 2020a). Certain
models also use feature-highlighting explanations or add actionability and
plausibility constraints by setting features to be actionable and mutable,
non-actionable and mutable, or non-actionable and immutable (Barocas et al.,
2020; Karimi et al., 2021). There has also been work to make these models
robust to dataset shifts in the real world (Upadhyay et al., 2021). Yet, none
incorporate the use of domain preferences, i.e., relevance. In this paper, we
focus our contribution in the scope of Bayesian Optimization methods.

###  2.1. Bayesian Optimization

Bayesian optimization is a global optimization problem to solve:

(1) $x^{*}=\max_{x\epsilon X}f(x),$

where $f(x)$ is the objective function, $X$ is the set of features, $x$ is a
feature, and $x^{*}$ is the feature for the global maximum of the objective
function (Frazier, 2018). When $f(x)$ is unknown, Bayesian optimization treats
it as a black-box function, a scenario commonly encountered in algorithmic
recourse (Snoek et al., 2012). The methodology revolves around three primary
components: objective function (black box), surrogate model (Gaussian
process), and acquisition function (Schulz et al., 2018).

####  2.1.1. Pseudo Code of the Algorithm

Algorithm 1 Bayesian optimization pseudo code

function BayesOpt($f,M_{0},N,A$)

$H\leftarrow\phi$

for $n\leftarrow 1$ to $N$ do

$x^{*}\leftarrow max_{x}$ $A(x,M_{n-1})$,

evaluate $f(x^{*})$

$H\leftarrow H\cup(x^{*},f(x^{*}))$,

Fit a new model $M_{n}$ to $H$

end for

return $H$

end function

Where H is the observation history of the pair (feature, value), N is the max
number of iterations, f is the true objective function (black box), M is the
surrogate function (Gaussian process), A is the Acquisition function, $x^{*}$
is the next feature chosen to evaluate (Bergstra et al., 2011).

####  2.1.2. Surrogate Model (Gaussian Process)

It uses the model’s history to construct multivariate Gaussian distributions
to predict the objective function. The mean and covariance function decide
where to steer the acquisition function.

In our paper, we use the matern (covariance) kernel function along with this.
Matern kernels are a generalization of power exponential kernels where the
additional parameter $\nu$ controls the smoothness of the function. The larger
$\nu$ is the smoother the function until $\nu\rightarrow\infty$, where the
matern kernel becomes a power exponential kernel (Snoek et al., 2012). A 2.5
matern kernel has $\nu=2.5$ for twice differentiable functions. This kernel is
given by:

(2)
$k(x_{i},x_{j})=\frac{1}{\Gamma(\nu)2^{\nu-1}}\Bigg{(}\frac{\sqrt{2\nu}}{l}d(x_{i},x_{j})\Bigg{)}^{\nu}K_{\nu}\Bigg{(}\frac{\sqrt{2\nu}}{l}d(x_{i},x_{j})\Bigg{)},$

where $k$ is the kernel, $d(x_{i},x_{j})$ is the euclidean distance between
$x_{i}$ and $x_{j}$, $\nu$ is the smoothness of the function, $K_{\nu}()$ is
the modified Bessel function, and $\Gamma(\nu)$ is the gamma function (Schulz
et al., 2018).

####  2.1.3. Acquisition Function

This is optimized to balance the exploration and exploitation of the objective
function. The Upper Confidence Bound is simple, and what we use given by:

(3) $a(x;\lambda)=\mu(x)+\lambda\sigma(x),$

where $\mu(x)$ is the expected performance of our surrogate model, controlling
the exploration, and $\sigma=\sqrt{k(x_{i},x_{j}}$ adds uncertainty through
the standard deviation (root of the kernel), controlling the exploitation
(Schulz et al., 2018). The larger $\lambda$ is, the more this function is
rewarded for searching unknown spaces, leading to more exploration (Frazier,
2018).

###  2.2. Relevance

The concept of relevance is defined by Ribeiro and Moniz (Ribeiro and Moniz,
2020) as a function given by:

(4) $\phi(Y):{\mathcal{Y}}\rightarrow[0,1],$

where $\phi$ is the continuous relevance function, displaying the bias of
domain $\mathcal{Y}$ by mapping it to the continuous range $[0,1]$ with 0
being the minimum and 1 being the maximum relevance (Torgo et al., 2015). To
calculate the relevance of all points, we require:

  1. a)

control points which are points with a known relevance

  2. b)

interpolation function that can determine the relevance of other points
(Ribeiro and Moniz, 2020).

Control points are required for interpolation, with a minimum of three: the
minimum, median, and maximum points for relevance. The control points can be
defined by the equation given by:

(5) $S=\left\\{\langle
y_{k},\varphi(y_{k}),\varphi^{\prime}(y_{k})\rangle\right\\}_{k=1}^{s},$

where $y_{k}$ is the control point, $\varphi(y_{k})$ is the relevance at
$y_{k}$, and $\varphi^{\prime}(y_{k})$ is the derivative of the relevance
function at that point. By default, $\varphi^{\prime}(y_{k})$ will be 0
because the control points are assumed to be the minimums and maximums of the
function (Ribeiro and Moniz, 2020). Automatic generation of a relevance
function makes common values less relevant and rarer points more relevant. We
can also manually set the relevance of control points to reflect their real-
world significance. Concerning interpolation, (Ribeiro and Moniz, 2020)
proposes the use of pchip (Piecewise Cubic Hermite Interpolating Polynomials)
to achieve the desirable conditions, such as continuity in generated points.

##  3\. Our Framework: Relevance-Aware Algorithmic Recourse

In this section, we detail our framework, Relevance-Aware Algorithmic Recourse
(RAAR). First, we introduce background information and details about our
algorithmic recourse problem. Then, we introduce our objective function and
how to optimize it.

###  3.1. Preliminaries

Through Bayesian optimization, we optimize for a particular outcome by
applying changes to $x$, where $f(x+\epsilon)$ is the new outcome with a cost
of $\epsilon$. We explore the solution space through the Gaussian process,
generating a counterfactual distribution. Formally, we have a regression model
$f:\chi\rightarrow{\rm I\\!R}$ with the Gaussian Process surrogate Model,
$GP(\mu_{n},K_{n})$. This surrogate model accepts a mean function
$\mu_{n}:\chi\rightarrow{\rm I\\!R}$ and a covariance function
$K_{n}:\chi*\chi\rightarrow{\rm I\\!R}$, with an Upper Confidence Bound
acquisition function (Snoek et al., 2012; Spooner et al., 2021).

###  3.2. Formulating and Optimizing our Objective

We have two types of objective functions, one for $y$, the target value, and
one for relevance, $\phi()$. We also have two optimization goals, one for
obtaining the maximum $y$ value possible and one for a specific target value
$y$. Additionally, we introduce bounds to either focus or expand their
exploration. For maximum value optimizations, we set bounds of $\pm$5% to
focus on recourses with small changes. For target value optimizations, we use
$\pm 100\%$ to focus on reaching the target value in both y and relevance
optimizations. This process compares the impact of relevance on recourses.

####  3.2.1. Y Optimization

For this, the maximum value optimization uses the objective function as
follows:

(6) $x^{*}=\max_{x\epsilon X}\frac{f(x^{*})-M(x)}{|M(x)|}$

For the target optimization, we optimize for the point that achieves the
closest value to our target value.

(7) $x^{*}=\max_{x\epsilon
X}\frac{-|f(x^{*})-y_{target}|}{|y_{target}-y_{orig}|}$

####  3.2.2. Relevance Optimization

We optimize for relevance through using $\phi(f(x))$ instead of $f(x)$, where
$\phi(y)$ is the relevance function. The relevance function further pseudo-
bounds the optimization process to provide a realistic and relevance-bound
recourse. We use the same equation for both maximum and target optimizations.

(8) $x^{*}=\max_{x\epsilon X}\phi(f(x^{*}))$

The above $\phi$ function can be generated in two main ways: changing whether
we optimize for a maximum relevance value or a target y value. We generate an
automated (distribution-based) relevance function with only the right extreme
for the maximum relevance value. We use the training set to optimize for its
most extreme values, investigating how using the relevance function for
optimization compares with target value optimizations. For target values, we
generate a unique relevance function with both extremes for every target value
we want to reach (local). To define a unique relevance function for a target
value, we define its control points as follows:

(9) $S=\left\\{\langle y_{min},0,0\rangle,\langle
y_{original},0.5,0\rangle,\langle y_{target},1,0\rangle,\langle
y_{max},0,0\rangle,\right\\}$

Setting these control points as above ensures that the optimization direction
is always at maximum relevance or $y_{target}$.

##  4\. Experiments

This paper aims to analyze if Relevance-Aware Algorithmic Recourse (RAAR)
generates better counterfactuals. Here, we discuss the experimental process of
evaluating our novel framework. We investigate through two methods of
generating a recourse, with two different optimization objectives and two
regression models each. The following describes how we leverage the well-known
learning algorithms Random Forest and LGBM in our optimization (Rigatti, 2017;
Sibindi et al., 2023).

Figure 1. Experimental Process

###  4.1. Experimental Setup

We compiled 15 datasets to run the process above, ranging from insurance
expenses and mortgages to wine ratings. During every optimization process, we
use Bayesian optimization to reach our target. For (1), the target is the
maximum positive difference we can reach while minimizing the cost. For (2),
the target is any value we provide, and we used four different percentage
increases to analyze how close we can get to that target value. The results of
these experiments answer how relevance affects recourses and how the two
methods compare.

###  4.2. Maximum Optimization Results

For the maximum optimization, we can break this method down further into two
more: 1) context-free, which finds the maximum y, and 2) contextual, which
finds the maximum relevance. By optimizing for a maximum y, we try to get as
large (within bounds of $\pm$5%) as possible without looking at the practical
and real-world settings. However, by incorporating relevance, we introduce a
further pseudo-bound by trying to get the largest y within the person’s
situation, providing a more realistic recourse.

Table 1. Maximum Optimization Data Results— Model | Optimizes |  $\Delta y\%$ Mean |  $\Delta y\%$ SD |  $\phi$ Mean |  $\phi$ SD | $\Delta d$
---|---|---|---|---|---|---
RF | Y | 30.2 | 61.74 | 0.18 | 0.23 | -0.07%
| Relevance | 25.36 | 60.98 | 0.18 | 0.23 |
LGBM | Y | 41.23 | 65.37 | 0.24 | 0.26 | -0.12%
| Relevance | 36.62 | 63.8 | 0.24 | 0.26 |

In Table 1, $\Delta y\%$ is the average percent change in y, with its standard
deviation, $\phi$ mean and SD are the mean and standard deviation relevance
values, $\Delta d$ is the distance difference between the y and relevance
optimization models w.r.t. relevance. Recourses that leverage relevance have
smaller cost (distance) and smaller y percent change. Here, our goal is to
evaluate the recourses generated by the y-optimized and relevance-optimized
models. Overall, the y optimization model recourses obtain a larger change in
the outcome than relevance optimization models. However, they both reach the
same relevance, outlining that the relevance functions produced limit the
change in y. This is because we automatically generate it to favor larger,
rarer extreme cases without guidance.

###  4.3. Target Optimization Results

In many scenarios, people want to know what they can change to achieve a
specific outcome instead of a maximum. To replicate this, we optimized for a
target value instead of a maximum value. We compared the y difference model
against the relevance model when predicting values 10%, 20%, 50%, and 100%
greater than its original. For the relevance model, we manually created
relevance functions.

Table 2. Target Optimization Data Results Model |  Target $\Delta y\%$ | Optimizes | $\Delta y\%$ | Y SD |  $\phi$ Mean |  $\phi$ SD | $\Delta It$ | $\Delta d$
---|---|---|---|---|---|---|---|---
| 10% | Y | 9.57% | 1.25 | 0.94 | 0.13 | -6.24% | -2.15%
|  | Relevance | 13.14% | 1.52 | 0.96 | 0.10 |  |
| 20% | Y | 18.02% | 0.74 | 0.90 | 0.17 | -3.48% | -1.13%
RF |  | Relevance | 20.78% | 0.89 | 0.93 | 0.13 |  |
| 50% | Y | 41.39% | 0.41 | 0.87 | 0.18 | -1.19% | -0.33%
|  | Relevance | 42.63% | 0.48 | 0.90 | 0.13 |  |
| 100% | Y | 55.87% | 0.27 | 0.65 | 0.19 | -5.71% | -0.82%
|  | Relevance | 48.83% | 0.31 | 0.74 | 0.12 |  |
| 10% | Y | 9.61% | 0.44 | 0.96 | 0.12 | -4.98% | -1.91%
|  | Relevance | 13.09% | 0.82 | 0.98 | 0.08 |  |
| 20% | Y | 18.71% | 0.27 | 0.94 | 0.13 | -5.89% | -2.17%
LGBM |  | Relevance | 21.08% | 0.50 | 0.96 | 0.10 |  |
| 50% | Y | 44.03% | 0.22 | 0.90 | 0.16 | -6.15% | -1.76%
|  | Relevance | 43.40% | 0.32 | 0.91 | 0.12 |  |
| 100% | Y | 64.12% | 0.2 | 0.66 | 0.18 | -8.38% | -2.04%
|  | Relevance | 53.32% | 0.24 | 0.76 | 0.12 |  |

Table 2: Target $\Delta y\%$ is the target percent change, $\Delta y\%$ is the
average percent change in y, with its standard deviation, $\phi$ mean and SD
are the mean and standard deviation relevance values, $\Delta It$ is the
difference in number iterations to reach their recourse w.r.t. relevance,
$\Delta d$ is the distance difference between the y and relevance optimization
models w.r.t. relevance. Recourses that leverage relevance are quicker and
cheaper, with outcomes similar to target optimization recourses.

Figure 2. Percentage Optimization Iteration Difference

Box plot showcasing the optimization iteration difference.

Figure 3. Percentage Optimization Distance Difference

Box plot showcasing the optimization distance difference.

Here, we evaluate how the two optimization processes compare for a target
value. In the table, the y optimization model finds recourses similar to the
target on average only 60% of the time. However, Table 2, Figure 2, and Figure
3 show that the iterations and distances for relevance optimization models
find it quicker and cheaper, as demonstrated by the negative percentage.
Moreover, LGBM provides quicker and closer recourses to the target value than
random forest regression. Overall, relevance optimizations achieve results
similar to y optimizations but with greater efficiency because of the reduced
optimization iterations required and lower costs since the recourses generated
are closer to the original points. This introduces a trade-off between greater
efficiency versus a small reduction in accuracy and precision.

##  5\. Conclusion & Future Work

In this paper, we proposed the novel framework for algorithmic recourse
(RAAR), to address the issue of treating all values equally which is
unrealistic in real-world settings. We introduced the notion of relevance that
assigns values with varying levels of importance, which the model optimizes
for. Through Bayesian optimization, we used objective functions, a Gaussian
process, and an acquisition function to generate recourses that optimize for
the maximum change with the smallest cost or target change. The 15 datasets
and results show that relevance recourses are quicker and more cost-efficient
than its y recourse methods. Furthermore, they can be similar sometimes,
making relevance-focused recourses more desirable in certain situations. Our
work also highlights future development on relevance-focused recourses. For
instance, how different shapes of a relevance function can improve the
accuracy and precision of such recourses or how different mean covariance and
acquisition functions influence recourse. Additionally, using relevance-
focused recourses with other approaches to recourse mentioned earlier, such as
integer programming, would be useful to understand how relevance can aid in
providing effective recourses.

## References

  * (1)
  * us_([n. d.]) [n. d.].  Code of Federal Regulation.  https://www.ecfr.gov/current/title-12/chapter-X/part-1002/subpart-A/section-1002.9.  [Accessed 28-01-2024].
  * eu_(2018) 2018\.  https://gdpr-info.eu/recitals/no-71/
  * Barocas et al. (2020) Solon Barocas, Andrew D. Selbst, and Manish Raghavan. 2020.  The hidden assumptions behind counterfactual explanations and principal reasons. In _Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency_ (Barcelona, Spain) _(FAT* ’20)_. Association for Computing Machinery, New York, NY, USA, 80–89.  https://doi.org/10.1145/3351095.3372830
  * Bergstra et al. (2011) James Bergstra, Rémi Bardenet, Yoshua Bengio, and Balázs Kégl. 2011.  Algorithms for hyper-parameter optimization.  _Advances in neural information processing systems_ 24 (2011).
  * Black and Murray (2019) Julia Black and Andrew Douglas Murray. 2019.  Regulating AI and machine learning: setting the regulatory agenda.  _European journal of law and technology_ 10, 3 (2019).
  * Clissa et al. (2023) Luca Clissa, Mario Lassnig, and Lorenzo Rinaldi. 2023.  How big is Big Data? A comprehensive survey of data production, storage, and streaming in science and industry.  _Frontiers in big Data_ 6 (2023).
  * Eirinaki et al. (2016) Magdalini Eirinaki, Nuno Moniz, and Katerina Potika. 2016.  Threshold-Bounded Influence Dominating Sets for Recommendations in Social Networks. In _2016 IEEE International Conferences on Big Data and Cloud Computing (BDCloud), Social Computing and Networking (SocialCom), Sustainable Computing and Communications (SustainCom) (BDCloud-SocialCom-SustainCom)_. 408–415.  https://doi.org/10.1109/BDCloud-SocialCom-SustainCom.2016.67
  * Frazier (2018) Peter I Frazier. 2018.  A tutorial on Bayesian optimization.  _arXiv preprint arXiv:1807.02811_ (2018).
  * Joshi et al. (2019) Shalmali Joshi, Oluwasanmi Koyejo, Warut Vijitbenjaronk, Been Kim, and Joydeep Ghosh. 2019.  Towards Realistic Individual Recourse and Actionable Explanations in Black-Box Decision Making Systems.  arXiv:1907.09615 [cs.LG]
  * Karimi et al. (2020a) Amir-Hossein Karimi, Gilles Barthe, Bernhard Schölkopf, and Isabel Valera. 2020a.  A survey of algorithmic recourse: definitions, formulations, solutions, and prospects.  _arXiv preprint arXiv:2010.04050_ (2020).
  * Karimi et al. (2021) Amir-Hossein Karimi, Bernhard Schölkopf, and Isabel Valera. 2021.  Algorithmic Recourse: from Counterfactual Explanations to Interventions.  , 10 pages.  https://doi.org/10.1145/3442188.3445899
  * Karimi et al. (2020b) Amir-Hossein Karimi, Julius Von Kügelgen, Bernhard Schölkopf, and Isabel Valera. 2020b.  Algorithmic recourse under imperfect causal knowledge: a probabilistic approach.  _Advances in neural information processing systems_ 33 (2020), 265–277.
  * Ribeiro and Moniz (2020) Rita P Ribeiro and Nuno Moniz. 2020.  Imbalanced regression and extreme value prediction.  _Machine Learning_ 109 (2020), 1803–1835.
  * Rigatti (2017) Steven J Rigatti. 2017.  Random forest.  _Journal of Insurance Medicine_ 47, 1 (2017), 31–39.
  * Schulz et al. (2018) Eric Schulz, Maarten Speekenbrink, and Andreas Krause. 2018.  A tutorial on Gaussian process regression: Modelling, exploring, and exploiting functions.  _Journal of Mathematical Psychology_ 85 (2018), 1–16.
  * Sibindi et al. (2023) Racheal Sibindi, Ronald Waweru Mwangi, and Anthony Gichuhi Waititu. 2023.  A boosting ensemble learning based hybrid light gradient boosting machine and extreme gradient boosting model for predicting house prices.  _Engineering Reports_ 5, 4 (2023), e12599.
  * Snoek et al. (2012) Jasper Snoek, Hugo Larochelle, and Ryan P Adams. 2012.  Practical bayesian optimization of machine learning algorithms.  _Advances in neural information processing systems_ 25 (2012).
  * Sokol and Flach (2019) Kacper Sokol and Peter Flach. 2019.  Counterfactual explanations of machine learning predictions: opportunities and challenges for AI safety. In _2019 AAAI Workshop on Artificial Intelligence Safety, SafeAI 2019_. CEUR Workshop Proceedings.
  * Spooner et al. (2021) Thomas Spooner, Danial Dervovic, Jason Long, Jon Shepard, Jiahao Chen, and Daniele Magazzeni. 2021.  Counterfactual explanations for arbitrary regression models.  _arXiv preprint arXiv:2106.15212_ (2021).
  * Torgo et al. (2015) Luís Torgo, Paula Branco, Rita P Ribeiro, and Bernhard Pfahringer. 2015.  Resampling strategies for regression.  _Expert Systems_ 32, 3 (2015), 465–476.
  * Upadhyay et al. (2021) Sohini Upadhyay, Shalmali Joshi, and Himabindu Lakkaraju. 2021.  Towards robust and reliable algorithmic recourse.  _Advances in Neural Information Processing Systems_ 34 (2021), 16926–16937.
  * Ustun et al. (2019) Berk Ustun, Alexander Spangher, and Yang Liu. 2019.  Actionable Recourse in Linear Classification. In _Proceedings of the Conference on Fairness, Accountability, and Transparency_ (Atlanta, GA, USA) _(FAT* ’19)_. Association for Computing Machinery, New York, NY, USA, 10–19.  https://doi.org/10.1145/3287560.3287566
  * Venkatasubramanian and Alfano (2020) Suresh Venkatasubramanian and Mark Alfano. 2020.  The philosophical basis of algorithmic recourse. In _Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency_ (Barcelona, Spain) _(FAT* ’20)_. Association for Computing Machinery, New York, NY, USA, 284–293.  https://doi.org/10.1145/3351095.3372876
  * Voigt and Bussche (2017) Paul Voigt and Axel Bussche. 2017.  _The EU General Data Protection Regulation (GDPR): A Practical Guide_.  https://doi.org/10.1007/978-3-319-57959-7
  * Wachter et al. (2017) Sandra Wachter, Brent D. Mittelstadt, and Chris Russell. 2017.  Counterfactual Explanations without Opening the Black Box: Automated Decisions and the GDPR.  _CoRR_ abs/1711.00399 (2017).  arXiv:1711.00399 http://arxiv.org/abs/1711.00399
  * Wang et al. (2020) Yuelin Wang, Yihan Zhang, Yan Lu, and Xinran Yu. 2020.  A Comparative Assessment of Credit Risk Model Based on Machine Learning——a case study of bank loan data.  _Procedia Computer Science_ 174 (2020), 141–149.
  * Yan et al. (2020) Chiwei Yan, Helin Zhu, Nikita Korolko, and Dawn Woodard. 2020.  Dynamic pricing and matching in ride-hailing platforms.  _Naval Research Logistics (NRL)_ 67, 8 (2020), 705–724.


# Automated Learning: An Implementation of The A* Search Algorithm over The
Random Base Functions

Nima Tatari
Washington University in St. Louis, Department of Physics
<EMAIL_ADDRESS>
##  1 Introduction

The presented idea resembles the asymptotic series representation of a target
function as opposed to the convergent series representation, such as the
Taylor series. In the asymptotic expansion, the first few terms of the series
represent the target function behavior with the desired accuracy in the
asymptotic regime [1]. On the other hand, expressing the function by a
convergent series would require a large number of terms to get the same
accuracy, moreover, the convergent series is a valid representation only
inside the disk of convergence on the complex plane. In this method, we reduce
the rigor of the analysis and let the algorithm find the leading behavior of
the data and its corrections layer by layer. In this sense, the method looks
like an asymptotic analysis. However, there exist major differences between
the two approaches. We try to develop a link between asymptotic analysis, a
search method in artificial intelligence, and pattern recognition in machine
learning.

##  2 A-star Algorithm

A-star algorithm, as a search strategy, finds the optimal path between two
points on a graph. [2, 3] Providing geometric information on the graph helps
A-star reduce the number of trials and errors in the search. Such a structure
yields the distance between two successive nodes, h(m,n), and the lower limit
for the cost between any node n and a goal node f, h(n). As depicted in the
graph below, starting from node “i” to find the optimal path to node “f”, as
the algorithm explores the node m in the middle, it finds the cost of
transitions from m to all its children, h(m,n). In addition, it will calculate
h(n) for all the children. We emphasize that if g(m) is the cost spent to
reach m, then:

$\centering g(m)+h(m,n)+h(n)=g(n)+h(n)=f(n)\@add@centering$ (1)

f(n) is the least cost that a path could take to connect i to f while passing
through n.

Figure 1: Paths to the goal node, h(n): lower bound on the cost from n to f,
g(m): cost spent to reach m, h(m,n): exact cost of exploring n from m. Each
path from “i” to “f” corresponds to a model.

After evaluating f(n) for all the children of m, they are stored in a set
called fringe, which contains all the nodes ready for exploration (e.g. n’s
and q’s in the diagram above). Then it will choose the node with the least
f(n) to explore.

In order to provide a visualization of the algorithm, let us consider a set of
nodes, as shown above. We assign a random function with undetermined
parameters (e.g. sine, cosine, tanh, etc.) to each node. The algorithm will
find the path that connects a subset of these nodes. This path will correspond
to a set of base functions to expand the data on that set. While A-star
chooses a node among the children, gradient descent optimizes the functions’
parameters at each node exploration.

The algorithm begins by exploring the initial node, which contains the
constant function. If the branching is four, there will be four children nodes
containing a random function, or product of two or three functions. In the
next step, it analyzes each child. Consider the instance where a child is a
cosine. The assigned random parameters $\alpha$, $\beta$ in $cos(\alpha
x+\beta)$ are subject to optimization by gradient descent so that
$c_{0}+c_{1}cos(\alpha x+\beta)$ produces the best fit to the data points.
Note that this function corresponds to a path that connects two nodes, the
initial node that contains the constant function, and its child node that
contains cosine.

The next step stores the child nodes with optimized parameters in a
prioritized order. The error they render while fitting the training and
validation(unseen) data determines the priority in exploration.

The subsequent step picks the child node with the least error, among the other
nodes stored in the fringe set described earlier.

The presented approach for modeling the data using a few well-known functions
considers an ideal path in the graph that would exactly match the data source.
Recall that paths in the graph correspond to models, which could describe the
data source. Finding the ideal model might remain impossible; nevertheless, a
graph endowed with a geometric property, the norm of the difference of two
functions as their distance, will navigate A-star towards a perfect model.

##  3 Geometry of The Graph

All the step costs along an optimal path add up to g(n). As a result, finding
how to calculate each step cost in the search completes the A-star
requirements. The Hilbert space where the paths, which correspond to the
functions, live in, equips the graph with geometry because the norm of the
difference between any pair of functions serves as the definition for the
distance between the corresponding nodes. In addition, the existence of the
inner product of the functions validates that the graph contains the elements
of a Hilbert space. This leads to the definition of the step cost from the
node m to its child n: $h(m,n)=\varphi m(x)-\varphi n(x)$

Figure 2: The diagram depicts an optimal path from i to n. The heuristics at m
and n estimate the cost from these nodes to f, the goal node. The step cost
from m to n defines the distance, hence the geometry on the graph. The sum of
all the step costs h(p,q) on the path to n adds up to g(n); moreover, the sum
of g(n) and h(n) results in f(n) which sets the priority of this path to be
chosen or not, for the next exploration at n.

##  4 Results Without Gradient Descent

Elimination of the gradient descent at each node expansion requires defining
the functions with known, fixed parameters. Since randomness sits at the core
of the method, a huge number of functions with random parameters must be
generated at each node exploration.

This results in large time complexities. Nevertheless, the first attempts for
developing the algorithm utilized this approach, which led to fulfilling
results by finding approximately true patterns from the training data set (the
red dots in the plots), such as varying oscillation frequencies and
amplitudes, as the following diagrams demonstrate. (The term poolSize above
the plots shows the number of random functions used in each run, and the term
replica means the number of runs to find the paths that each plotted curve
shows their weighted sum).

Figure 3: Search results with 100 functions in the random set. The models
found poorly represent the data trend on the unseen region. Figure 4: The
models show better correlations as the random set size increases to 500.
However, they fail in predicting the unseen data accurately. Figure 5:
Increasing the pool size to 5000.

The three diagrams above manifest a shift in the accuracy of predicting the
future behavior of the time series, as the number of random functions
increases. On the other hand, as this number takes the values of 100, 500, and
5000 respectively, the calculation time for finding five runs takes the trend
of 2s, 141s, and 2367s (Recall that each run in these plots corresponds to two
replicas, and each replica means a path in the graph. In each run the two
paths are weighted by their inverse error on the data).

The next three plots show the results for finding the oscillatory behavior
multiplied by polynomial terms $cos(x)(1+(x-5)2)$. With a pool size of 100 it
looks poor in extrapolation, however increasing the size of the random
function set to 10000 enables the algorithm to find a model that can predict a
part of the unseen data, yet the computation time increases largely.

Figure 6: Each continuous line shows the result of finding the base functions
used to model the data. The models are similar but lack the ability to capture
the patterns. Figure 7: Accuracy in prediction improves as the random set size
increases. Figure 8: Few models are able to extrapolate the data partially, as
the random set becomes extremely large.

##  5 Results Using Gradient Descent

The examples of the current section correspond to the algorithm armed with
gradient descent. The steps of the algorithm follow the procedures described
below:

1\. Defining the root node in the graph as a constant function, finding its
deviation from the training and validation data as $\vec{V}$.

2\. Generating a set of random functions with the size of the branching
parameter. This set will be used to generate successor nodes.

3\. For loop in the random set, analyze each element as a successor of the
current node.

4\. Given the parent node and a child, optimize the child function(s)
parameters using gradient descent. Fitting the resulting base functions to the
data, and returning their deviation vectors $\vec{V}$.

5\. Exploring the successor with the smallest distance from the goal node
$h(n)=|\vec{V}|$.

6\. Returning to step 2, if the iteration is smaller than its limit.
Otherwise, return the current base set model.

The following figures show the results of the main algorithm. Patterns, such
as oscillations, variations in amplitudes, and changes in frequencies are
detected by the search scheme.

Figure 9: Modeling the data behavior after 10 node expansions. Figure 10:
Modelling an interval of gravitational wave data detected by LIGO.

##  6 Time Complexity

In this section, we evaluate the computation time as a function of different
parameters on one of the generated data sets (figure 9). The time complexity
with respect to the number of the explored nodes (path length in the graph)
with fixed branching number is plotted in figure 11. The plot suggests a
polynomial behavior for the time complexity.

Figure 11: Calculation time as the number of explored nodes increases. The
number of successors (branching) is set to 8.

The next plot investigates the behavior of the complexity in terms of
increasing the branching number, which is the number of children of any node,
with a fixed number of the total explored nodes.

Figure 12: Calculation time as the number of successors increases, with the
number of totals, explored nodes (path length) set to 6.

##  7 Further Discussion and Possible Applications

It remains an important question that how the algorithm applies to real-world
problems, in terms of scalability and computational efficiency. It is a true
fact that collecting the data sets is the leading factor to train models,
regardless of the model complexity. This work forms a platform for future
works toward integrating methods from applied mathematics and artificial
intelligence and machine learning. For example, in neural networks, one may
use A-star to first choose a better set of nonlinear functions. The result can
lead to faster pattern recognition, with smaller input data.

##  8 Acknowledgement

The author warmly acknowledges Prof. Zohar Nussinov and Prof. Roman Garnett
for their discussions and for providing feedback on this work.

## References

  * [1] Carl M. Bender and Steven A. Orszag  “Advanced Mathematical Methods for Scientists and Engineers”  In _Springer_ , (1978)
  * [2] Peter E. Hart and Nils J. Nilsson  “A Formal Basis for The Heuristic Determination of Minimum Cost Paths”, (1968)
  * [3] Stuart Russell and Peter Norvig  “Artificial Intelligence A Modern Approach”  In _Pearson Inc_ , (2010)