DEV Community: aruna-x

Sometimes Stochastic Parrots Lie: How to Minimize LLM Hallucinations

aruna-x — Thu, 08 Jun 2023 07:32:33 +0000

Introduction
Examples of LLM Hallucinations
Why Do LLMs Hallucinate?
Strategies to Mitigate Hallucinations
- Steerability
- Retrieval Data Augmentation
- Completion Parameters / Hyperparameters
- Chain-of-Thought (CoT) Prompting

This week I prompted ChatGPT to educate me about LLM hallucinations. Hilariously, it hallucinated.

Late-life migraine accompaniments exist, however 'LLM' is not a valid acronym referencing them.

(Various permutations of this query were similarly fruitless.)

Despite its penchant for false facts, ChatGPT is not a malignant sociopath poised to betray us all. (I'm looking at you, Hal.) LLMs don't have intent. They produce outputs, and we label those offerings acceptable or hallucinatory based on our own valence toward them.

Examples of LLM Hallucinations

Have you heard that ChatGPT taught itself advanced Chemistry? Turns out, it didn't. It can simply double-talk advanced Chemistry convincingly enough to impress a layperson.
Watch ChatGPT 'gaslight' a user about the date.
In March of 2023 Stanford researchers published a LLaMa-based chatbot, only to quickly take it down due to hallucination.

A lovely kaleidoscope of fever dreams.

Why Do LLMs Hallucinate?

There are two reasons:

Lack of information.
A surface level, statistical model of language, rather than a modicum of true semantic understanding.

An LLM is liable to hallucinate when it lacks sufficient, domain-specific data during the training phase. Every LLM must be trained on a large corpus of knowledge long before it is made available to an end user. ChatGPT, for example, had access to the internet until its 'knowledge cutoff' in September 2021. (Although confusingly it seems to know about events that occurred after then. Mystery.)

As of September 2021, LLM hallucinations were not widely discussed online.

Whether or not it has enough subject material, LLMs are designed to complete what a human is likely to say, not necessarily what's correct. The use of statistical likelihood in Natural Language and text generation is nothing new. Markov chains, for instance, have been helpful in this domain for years. Natural Language Processing (NLP) and AI experts often call LLMs 'stochastic parrots'. Somewhat hilariously diminutive, given that LLMs can have billions of parameters - but totally fair.

Note that probabilities are calculated for tokens not words. Distinct tokens represent 'jumped' and ' jumped' (with a space). In this case, the probability of "jumped" is 82.14%.

In the second, deterministically repeated sentence, "jumped" occurs with 100% probability. Of course.

If we can make a leap from here, the point is: In a very general sense the sentence "The cow jumped over the moon" is as correct to an LLM as "Water boils at 100 degrees Celsius or 212 degrees Fahrenheit" - even though one is fantasy and the other is factual.

Now let's put the two pieces together. If ChatGPT doesn't know current events, it doesn't have information about LLM hallucinations. And if it is trained to spit out statistically likely phrases regardless of whether it has the facts, we get fabrications.

According to Ed Targett in this compelling article on LLM Hallucinations, "an eagerness to ascribe intelligence to LLMs comes with the risk that we start consuming convincing black box outputs as gospel without rigorous diligence." To that I say: Amen.

Strategies to Mitigate Hallucinations

As of writing this article, these post-training user strategies have proven effective:

Steerability via prompting
Retrieval data augmentation
Completion parameters / hyperparameters
Chain-of-Thought (CoT) prompting

Steerability

Steerability is the ability to guide an LLM's behavior. The LLM can take on a role: "You are a chemistry teacher." Or it can follow instructions: "Make a list of the 5 best places to vacation if you are allergic to the sun." (True story. I have two sun allergies.)

It can also adopt a persona or tone: "Summarize Edgar Allen Poe's The Tell-Tale Heart in the tone of Cardi B."

Thanks Cardi, that ending really turned it into an upper.

Note that currently ChatGPT uses GPT-3.5 under the hood. GPT-4 however is much more amenable to steerability. After the initial self-reinforcement training phase, it was fine-tuned via RLHF: Reinforcement Learning from Human Feedback.

While they may seem simple, these steering phrases have proven powerful to reduce hallucination:

"Stick to the facts."
"It's okay to say 'I don't know.'"
"Ask the user for information you may need to complete this task."

(These seem like great advice for humans too.)

Steerability is a viable strategy in the format of chat conversations as well. LangChain has a great example here of feeding the chat history back into the prompt with each turn to keep context fresh. Otherwise the LLM can forget context given enough further interaction, and (you guessed it) hallucinate.

Retrieval Data Augmentation

Retrieval data augmentation involves feeding data sourced by the end user to the LLM during prompting. Sources can include APIs, private data stores (smaller amounts of data, like documents or images on your own machine), databases (for larger amounts of data), or anything found on the internet itself.

I recently whipped up a React-Flask app called Weather to Wear as a basic example of retrieval data augmentation. It queries the user for a location, calls WeatherAPI to get the current day's weather, then embeds the resulting data in a prompt for gpt-3.5-turbo.

More often than not, the completion sounds reasonable:

In the first iteration of this app, occasionally the completion included recommendations like, “Don't forget to wear sunscreen and a hat or sunglasses if necessary, as the UV index is at 1.0.” That isn't accurate. UV between 0 and 2 is considered extremely low. In fact, some experts suggest that sunscreen is unnecessary in this range.

Simple fix: I augmented the prompt with a brief list of uv ranges and their associated UV severities.

Of course, this sort of simple method breaks down if we needs lots of data, partially because there is a limit to the amount of data you can stuff into a prompt, depending on the model. Imagine a law firm that wants a custom LLM-based app, augmented with an extensive digital library of court cases. For such situations, there are more powerful ways of architecting data retrieval augmentation.

Here's what that might look like: Because of the limits mentioned above, we'll break up the library into more manageable chunks. Next we calculate a numerical representation (a scored vector) for each chunk through a process called embedding, making the information significantly more compact. Store the results.

When a lawyer enters a query in search of cases related to a specific topic, we'll calculate the query's embedding. Using this new query vector we search the stored results from above. Best matches will be semantically relevant to the user's query.

We'll add the relevant chunks to our prompt like so:

"Document 1:" + chunk1 + "Document 2:" + chunk2 + "Document 3:" + chunk3 + ...

There's no need to build architecture like this from scratch though. Tools like LangChain and LlamaIndex have embedding features. Use them and make merry.

Now our LLM can effectively have fast access to a wide store of information for augmentation purposes, without hitting the token limit for the prompt/completion or having to scour the internet on the fly. As a general rule, the more salient information we have, the better hallucinations are managed.

Completion Parameters / Hyperparameters

Completion parameters (often mistakenly called hyperparameters) are post-training inputs we can adjust via the OpenAI Playground or by using the OpenAI Completions API. (I've noticed that some SWEs include completion parameters in the prompt itself! "Temperature: 0")

While we know approximately what each does, the real fun is in playing mix-and-match.

1. temperature (range: 0-2, default: 1)

Controls randomness. Low values are more deterministic. Use high values to get whacky.

2. top_p (range: 0-1, default: 1)

Also called nucleus sampling. Controls the pool of results from which a completion can be created. When top_p = 0.1, the model considers only the top 10% of the probability mass of tokens.

Note: OpenAI docs suggest using either temperature or top_p but not both. However, engineers working for OpenAI say to have at it. Press all the buttons.

3. presence_penalty (range: -2 to 2, default: 0)

Adjusts the bias of the model to choose novel tokens. Low values allow repeated tokens. High values encourage token novelty in the completion (in both diction and subject matter). This is a one-time adjustment applied to all tokens used at least once.

4. frequency_penalty (range: -2 to 2, default: 0)

Adjusts the bias of the model to limit token repetition in proportion to each token's frequency. Low values allow for more repetition. High values penalize repetition.

Note: On the surface presence and frequency penalties might look similar. They are not. Presence is a one-time adjustment applied to all tokens. Frequency is proportionally applied to each and every token.

5. logit bias (range: -100 to 100, requires: JSON object mapping specific tokens)

Controls the likelihood of tokens appearing in the completion at all. Use token IDs to specify which token likelihoods to modify. (e.g. {"31373": -100} will ensure that 'hello' will not appear.)

Assessing steerability vs fine-tuning with completion parameters feels like taking a lateral walk through language itself. With so many variables, exploring this space is equal parts compelling and confusing. But also, completely fun.

But for the purposes of limiting LLM hallucinations, the trick is to find the sweet spot where the completions are predictable enough to sound sane, but unpredictable enough to sound unlike a machine (if that's what you're after).

Chain-of-Thought (CoT) Prompting

Chain-of-thought prompting extends the concept of few-shot prompting to enable the LLM to model a certain flavor of reasoning, as in sufficiently complex math problems. It's also useful when we want output to conform to a specified format.

One-shot prompting:

"This is wonderful!"

I'm glad to hear that you're enjoying our conversation! I'm here to help and provide information to the best of my abilities. If there's anything specific you'd like to discuss or any questions you have, feel free to let me know. I'm here to assist you!

Aww, wholesome.

Few-shot prompting:

What if we wanted ChatGPT to indicate whether the sentence was positive or negative in tone? Let's feed it some formatted examples with few-shot prompting.

"This is awesome! // Negative
This is bad! // Positive
Wow that movie was rad! // Positive
What a horrible show! // "

Negative

For more complicated tasks we'll need to expose the LLM to intermediate steps of reasoning (a chain-of-thought if you will). Note that chain-of-thought prompting works especially well for 100+ billion parameter models. Also, ChatGPT has already evolved enough to automatically achieve and share CoT on its own for a variety of tasks. Basic uses of this strategy may become obsolete soon.

In some cases, you can approximate CoT prompting simply by adding this to your prompt: "Let's think step-by-step." Or, even better: "State each step and then show your work for performing that step." According to stevenic on the OpenAI forum, the latter phrasing improved hallucinations significantly, when used at the end of his prompts.

Here's a toy example of CoT prompting offered by this Google research article:

If you're anything like me, you don't find toy examples satisfying. Besides, this example (and most of the others I can find online) are already obsolete. ChatGPT definitely exposes reasoning in response to the standard prompt above.

I recommend reading this thread on the OpenAI forum, in which stevenic shares how he crafted a prompt that taught GPT-4 how to play risk with a human user. This thread has further discussion about his CoT format: Building Hallucination Resistant Prompts. It's the most compelling example of chain-of-thought prompting I've been able to find. Seriously, Steve has a fan over here.

I would love to hear your thoughts on LLM hallucinations in the comments. What strategies have you found most effective?

Stay tuned for my next project: a static single-page React chat app incorporating ChatGPT and information on my professional background, for my portfolio site. A user should be able to dictate the chat entity's personality and professional demeanor. Who says work can't be fun?

Addendum: for creatives and the curious in the mood to lean in to the hallucinations, try DreamGPT.

Cover image by Steve Johnson

The Wacky World of Closures & What Makes Them Useful

aruna-x — Thu, 16 Dec 2021 02:18:43 +0000

Can you guess what this prints out?

for (var i=0; i<3; i++) {
  setTimeout(() => console.log(i), 2000)
}

... Are you sure? There's a gotcha here, and if you're not aware of it already, I'd wager this blog post is worth your time. (Hint: 0, 1, 2 is incorrect.)

Getting Closure With Javascript

To understand what's happening in the above code snippet, we have to understand closures. If you're looking for practical applications of closures, you can jump ahead.

A closure has a surprisingly simple definition: a function with access to information outside of itself, otherwise known as its "lexical environment". function addTwo() is a closure:

let x = 5;
function addTwo() {
    return x+2;
}

And let x = 5 is in its lexical environment.

All functions in Javascript can be closures, because they automatically gain access to outer scope.

By contrast, pure functions are not closures:

function addNums(a,b) {
    return a+b;
}

addNums does not reference any data outside of its own scope. Its data is kept in your computer's short term memory. It gets pushed onto the "call stack", executed, and then popped off the stack again. Clean, simple, easy.

On the other hand, when a function references information outside of its own scope (as with a closure), its data becomes packaged (or "enclosed") with references to all of its lexical info, and the entire package gets placed in longer term memory, called the heap. We can thank a memory management process called garbage collection for keeping the heap clear of information we no longer need in long term memory.

Despite closures needing more memory and computational power, there are some great reasons to use them (which I'll cover in a moment below).

Not All Closures Are Made The Same

Closures are particularly easy in Javascript.

You can use let over lambda to create a closure in Lisp (the second oldest higher-level programming language).

The nonlocal keyword is helpful to gain access to variables normally outside of scope in python closures.

In C# however, closures must explicitly be enclosed with its lexical environment, through "binding" variables.

You get the idea. For now, we'll continue to use Javascript.

What Makes Closures Uniquely Useful?

There is surprisingly sparse info online about uses for closures. It's odd! While I'm sure there are many more uses, there seem to be at least two compelling ones I'd like to discuss:

Function factories
Namespacing private functions

Function Factories

Function factories are functions that return other functions based on various conditions. I'd like to share how I used a function factory in a recent project. But first, let's look at a simple example.

function factory(num) {
    switch(num){
      case 3:
        return (b) => num - b
      case 4:
        return (b) => num % b
      case 5:
        return (b) => num + b
      default:
        break;
    }
}

If we call factory(5), it returns (b) => 5 % b.
If we call factory(4) it returns (b) => 4 + b.
And if we call factory(4)(2) we can see that:

factory(4) = (b) => 4 + b

So factory(4)(2) becomes ((b) => 4 + b)(2)

Resulting in (2) => 4 + 2. Which returns 6.

The important note here is that function factories return functions that can accept even more info.

A Closure Function Factory In Use

I recently built a notes app with a react front end using semantic-ui-react. The new note form included a dropdown menu. (Bear with me here.)

semantic-ui-react's dropdown menu requires an array of options. Once I fetched data from my database and generated the options array, it looked something like this:

let options = [
    {value: 1, key: 1, text: option1}
    {value: 2, key: 2, text: option2}
    ...
]

You can feed this array to the dropdown like so:

<Dropdown
    name="dropdown"
    multiple
    search
    selection
    options={options}
/>

(I've simplified all of these snippets of code for readability.)

This dropdown will allow you to make multiple selections. It turns out the value attribute of semanitic-ui-react's dropdown menu is an array of values from the objects in options. I wanted to store whole objects from options in state instead.

I wanted just one change handler function for all form elements. Closure to the rescue.

Every form element executes the same function on change, like this:

onChange={(e) => handleMaker("name")(e)}

"name" matches the name attribute of the form element it's associated with for style reasons.

handleMaker is a function factory that returns a different function based on which form element name is passed in. The function returned from handleMaker accepts the onChange event as an argument.

Here is a simplified version of the function factory I use in the app:

function handleMaker(name){
  switch (name) {
    case "note":
      return (e, {value}) => setFormData({...formData, [name]: value});
    case "collections":
      return (e, {value}) => {
        setFormData({...formData, [name]: value.split(",").map(w=>w.trim())});
      }
    case "dropdown":
      return (e, {value}) => {
        setFormData({...formData, [name]: options.filter(o => {
          for (v in value) {
            return (v === o.id) ? true : false
          }
        })})
      };
    default:
      console.error("Oops, something went wrong!");
      break;
  }
}

There are other cases here, showing how a function factory can help handle all sorts of special cases.

Namespacing private functions

Private functions make apps more secure, disallowing ill-intentioned users from calling functions or methods that can mutate the app's state unhelpfully (or, in some cases, even inject code).

Ruby has a private keyword to make methods private. Javascript didn't until recently. But that applies to classes. When we're not inside classes (or running on IE, lol), we can still namespace private javascript functions with closures:

const namespacer = (function() {
    let num = 100;
    function changer(amt) {
      return num += amt;
    }

    return {
      public1: function() {
        return changer(100);
      },
      public2: function() {
        return changer(-100);
      },
      public3: function() {
        return num;
      }
    };
})()

Here, we can see that namespacer is actually an object with closures as keys, since the anonymous function on line 1 is immediately invoked on the last line.

We can call the public functions like this:

namespacer.public1(); // 200
namespacer.public2(); // 100
namespacer.public3(); // 100

But we would be unable to call changer directly:

namespacer.changer(); // TypeError: undefined is not a function

Or access num:

namespacer.num; // undefined

Presto! Private functions.

Closures In Interviews

If you are new to web dev and preparing for interviews, it may interest you to know that there is a common interview question involving closures:

for (var i=0; i<3; i++) {
  setTimeout(() => console.log(i), 2000)
}

Can you guess what console.logs here?

If you guessed

3
3
3

... you'd be right! We might expect 0, 1, 2 but that won't happen here. Each time we go through the loop, setTimeout waits a whole 2 seconds before running. The i inside of the setTimeout callback function refers to the i from the loop. Instantiating it with var gives us access to that variable even after it's done running. In 2 seconds, the loop will have run 4 times. Once i is assigned 3, it fails the condition and exits the for loop, leaving i at 3 when all three setTimeouts eventually run.

There are a number of ways we can fix this. One way is to wrap the callback function inside of setTimeout in an immediately invoked function that accepts i as its argument:

for (var i=0; i<3; i++) {
  setTimeout(((i) => (() => console.log(i)))(i), 2000)
}

What does this accomplish? Wrapping the callback function in an immediately invoked function ensures that the current value of i is passed in and kept in the state of the setTimeout function. It is stored there for later use.

Another way we can do this involves wrapping the entirety of the setTimeout in the same immediately invoked function:

for (var i=0; i<3; i++) {
  ((i) => setTimeout(() => console.log(i), 2000))(i)
}

This accomplishes the same result.

A Final Musing:

I'm curious to know whether there is a language in which creating a closure is impossible. So far my Googling efforts haven't gotten me far. I'd be grateful for your thoughts on the topic.

Abstract Syntax Trees: They're Actually Used Everywhere -- But What Are They?

aruna-x — Wed, 17 Nov 2021 21:02:00 +0000

Isn't it wonderful how VS Code grays out obsolete lines of code? Oops, my return statement is on line 3. Line 4 won't run... But I haven't called the function yet. So how in the world does VS Code know which lines of code won't be used in the future, when the code finally does run?

If we have a conditional statement, VS Code accurately evaluates the potential for us to hit the code outside of it:

bool could turn out to be false after all. But if we change the condition to true VS Code knows we will always run that block and (if there is an inevitable return inside) never reach the final line:

It's almost as if VS Code has the ability to understand the semantics of code. But under the hood VS Code uses code to do this! How?

Enter: Abstract Syntax Trees (ASTs)

An AST is a data structure that encodes abstract information about a piece of code.

This one is specifically for the above sample code declaring function foo(bool).

An AST is a "tree", which is a kind of graph. And a graph is a very useful type of data structure, ubiquitous in software engineering. In order to understand ASTs we have to understand graphs. (You can also skip ahead to learn more about ASTs or look at these tools to make and use an AST yourself.)

How Do Graphs Work?

Graphs consist of "nodes" and "edges", and can be represented by (often nested) objects or arrays. A graph can mix objects and arrays as well, nesting one kind within the other to whatever degree of complexity.

Each node and edge can contain information. You can travel from one node to another via the edge between them. Edges have direction as well. Here's a simple graph connecting node A to node B:

At a very basic level, if you were to write this in Javascript, it could look like this:

[ ["A", ["B"] ], [ "B", [] ] ]

{ 
   A: { value: data_set1, children: ["B"] }, 
   B: { value: data_set2, children: [] }
}

You can flip the direction

Resulting in code like this:

[ ["A", [] ], [ "B", ["A"] ] ]

or this

{ 
   A: { value: data_set1, children: [] }, 
   B: { value: data_set2, children: ["A"] }
}

And you can make the edge bidirectional, usually represented with a plain line with no arrows.

With code that does something like this

[ ["A", ["B"] ], [ "B", ["A"] ] ]

or this

{ 
   A: { value: data_set1, children: ["B"] }, 
   B: { value: data_set2, children: ["A"] }
}

These are simple examples, and in practice graphs can encode large amounts of data. Google displays search results with the help of a page rank graph, for example. This is a simplified representation of one:

Graphs can also have certain constraints. We can say: "The graph will start with exactly one node and every node except the first will have exactly one parent. Nodes can have multiple children though."

This is an example of one kind of tree. In general, a tree branches out. Every node after the first (root node) has exactly one parent. Trees are hierarchical and do not contain loops. (Graphs can have loops, and do not necessarily have a root node.)

But for now we'll focus on trees. Because when we build an AST, we take abstract syntactical data from code and encode it into a tree.

AST Design Standards & Traversal Functions

Because ASTs are often used in the process of compiling code (which happens all the time - every time you try to run any code), AST design standards are fairly robust. Compilers (and interpreters) essentially take the code we write (in Javascript, Python, Ruby, or C++) and turn it into machine-language instructions that a computer's CPU can run.

AST design standards include:

variables (and their declaration locations in the source code) must be preserved
the order in which statements get executed is well defined and preserved
in the case of binary operations, left and right positioning is preserved
identifiers and their values are stored

Ultimately, broken code cannot be turned into an AST. In the process of building the AST, we might come across errors like missing brackets, untyped variables (as in Typescript), or other syntactic mistakes. Instead of proceeding, we can flag these errors and display them to users for correction.

But once we successfully build an AST, it should be possible to unparse an it into something very similar to the original code, using a code generator. And the resulting code should definitely function exactly the same as the original code.

For example, using an AST like this ...

We could rebuild code that would look something like this:

function euclid(a,b) {
   while (b !== 0) {
      if (a > b) { a = a - b; } 
      else { b = b - a; }
   } 
   return a;
}

So we can take a piece of code, turn it into an AST, and eventually turn that back into code. But wait ... there's more: The function we use to step through the AST (called an AST traversal function) is intelligent enough to make sense of the semantic encodings and help us do useful things with that information.

We can use an AST traversal function to walk along the structure to discover "dead branches" (pieces of code that will never run).

Tree Shaking & More

Tree shaking refers to dead-code elimination in Javascript. In order to tree shake, we would combine the use of an AST and an AST traversal function to find which "branches" of code are "dead". This is how VS Code grays out unused lines of code. Tree shaking then eliminates those unused lines of code, for a cleaner, leaner code base.

When a code base is sufficiently large, dead-code elimination is necessary. Dead ends become dead weight, potentially causing worse performance if the product is shipped and bloated code in much need of pruning. (Amusingly, that's not a pun. That's what they call it! I came across many articles on tree pruning in writing this post though.)

There's incentive on both ends, as wet code is more confusing for developers as well.

The same traversal function can, interestingly, help us inject our own code into a given chunk of code according to preset rules if we wanted. (More about this in the follow up below.)

Tools To Make And Use An AST

Create an AST: Esprima

Traverse that AST and replace or inject code: Extraverse

Unparse the modified AST back into Javascript: Escodegen

ASTs vs CPTs

I mentioned earlier that ASTs are used in the process of compiling or interpreting. There is an alternative: Concrete Parse Tree. Unlike ASTs, CPTs include much more granular (potentially unnecessary) information. ASTs can omit some syntactic information like grouping parentheses, because of the way in which the structure of an AST already encodes that information.

CSTs are much bigger than ASTs. But the tradeoff is that they can aid in more efficient compiling. In practice, both are used.

Follow Up

My fascination with ASTs was inspired by an app I'm working on: a Big O (time complexity) calculator.

In my research on Big O approximation, I found that most tools calculate the amount of time a machine takes to run a function on different sized data sets. They use the resulting amounts of time to determine whether the rate of growth of time is sublinear, linear, exponential, etc.

I hope to create a tool that will count the number of actions taken (rather than the amount of time for a specific machine), so that for any snippet of code I can point to the most costly lines and indicate how many times they ran. This can help students learn Big O with a more concrete understanding of what's happening with their code.

The Halting Problem

Slightly outside the scope of this article, but cool enough to include: In 1936, Alan Turing (pictured at age 16, below) proved that it is impossible to write code that can examine another piece of code and its input, and tell whether or not it will ever terminate. This is called the halting problem.

For this reason, code entered into the Big O calculator can run too long in an infinite loop, and lock up a user's computer. I plan to bake in a fail-safe for that.

We'll See What's Possible

I'd eventually like to expand the project into a more comprehensive teaching tool. For now, I've scoped the project to the calculator to see if it's viable.

String Matching Algorithm Uses, Interactive Implementations, & Free Source Code

aruna-x — Thu, 04 Nov 2021 06:30:28 +0000

Ahhh autocorrect. How many times has it changed a four-letter expletive to "duck"? Though when autocorrect works as planned, it enables us to have smoother, more intuitive experiences with technology rather than hindering our free expression. At the heart of autocorrect is a well-intentioned string matching algorithm. There are many such tools, including:

username and password hash matching
search engines
autocorrect
spell checkers
email spam filters
plagiarism detection software
bioinformatics and DNA sequencing tools
quiz games!

Exact String Matching

There are two types of string matching: exact and fuzzy. Exact string matching is precisely as it sounds. Only identical strings pass the test, so to speak.

Something similar to this simple implementation seems useful for username and password hash matching. (Note: I've made this case sensitive for simplicity.)

Click the green play button to run this code. To edit code, create a replit account, fork this code, and have at it.

After pressing the green play button, you can feed the function your own strings in this console! Try entering: isExactMatch("string", "ring")

But perhaps we don't want to match whole strings. If we wanted to search large data for some exact substring query, we could redefine our criteria: exact common substring matches of length 4 or more found anywhere within either string, let's say. Then "apple" and "grappled" would pass.

The below implementation is called Longest Common Substring. Let's make it case insensitive. And if you've found this blog looking for a version that won't just check the first n characters (mystifyingly abundant online), but will return a match for any substring found anywhere within either string (way more useful imho), you're in luck:

Replace "4" on line 4 in the expression "end - beg > 4" with any number that allows your test data to succeed robustly.

Common substring has its limitations. For example, it fails "receipt vs reciept", a common typo. We'll circle back to this a bit later in this article.

There are indeed more powerful algorithms like the Boyer–Moore string-search algorithm, which avoids searching strings one character at a time. Instead, to increase efficiency, it explores the string being searched by jumping past ranges of characters and performs tail-first matching on the query string itself (which is assumed to be shorter). Fancy.

There's also the Meyers diff algorithm, used to highlight diffs in Github!

But for now, we'll move on to fuzzy string matching. Maybe I'll circle back to follow up on the Boyer–Moore string-search algorithm and the Meyer's diff algorithm in future updates.

Fuzzy String Matching

Google search queries often include typos.

Autocorrect can helpfully suggest adding back the "f" in "shift" in a work email. Bioinformatics tools can find gene mutations by detecting slight changes from original sequences. And spam filters can catch variations of common red flag phrases, despite spammers' best attempts at obfuscation.

Fuzzy string matching does some heavy lifting here. With fuzzy string matching (also referred to as inexact string matching or approximate string matching) we can probabilistically and algorithmically find most likely matches.

Here I've chosen to implement Levenshtein distance, the most common example of Edit distance. People often use these terms interchangeably, though there are other Edit distances.

Levenshtein Distance is in essence quite simple. It represents the minimum number of insertions, deletions, and substitutions it takes to make one string match another. To calculate the distance we use a matrix encoded with all possible operations on all possible substrings starting from the beginnings. This allows us to find and use the minimums on each operation dynamically.

This implementation uses a threshold of < 3. You can change that on line 25 after forking or copying.

According to my research, Levenshtein distance is considered the gold standard for fuzzy string matching. It hasn't been improved in about 50 years. For a comprehensive explanation, I highly recommend Understanding the Levenshtein Distance Equation for Beginners by Ethan Nam.

Even given its cachet, Levenshtein distance also has limitations. Unlike common substring it will pass "receipt vs reciept", but it will fail "Mt Whitney vs Mount Whitney" which common substring handles beautifully. Let's talk about that below.

Final Thoughts

A few weeks ago I co-created a kawaii-style quiz game called "Cookie-Loving Monster In Danger!" that uses the tech mentioned above. (No affiliation with Sesame Street or Jeopardy!) In order to get a functional version of string matching, I used all of these:

removal of special characters using regex
some simple logic to handle the edge case of query strings less than 3 characters
longest common substring (at a threshold of >4)
Levenshtein distance (at a threshold of <3)

Here is the final code. Try running it to see the test output, then test your own cases using the format stringAnalysis("string1", "string2"):

There are ways in which the above fails. It doesn't work with absolute accuracy.

However, this code worked well enough to make "Cookie-Loving Monster In Danger!" playable. So if you're curious to see it in action, hop over and play a game. If you win, there's a fun surprise in store. Or you can watch my walkthrough video here.

Follow Up

In the future, I'd be interested in creating my own implementations of the Boyer–Moore string-search algorithm and the Meyers diff algorithm, as I did with all of the above code snippets. I'd also be interested in improving the final code snippet by refactoring and further optimizing time and space complexity. I'd include a dictionary of common reasonable substitutions (like "2" and "two"). Then I'd take into account the probability of the occurrence of letters, common misspellings, and words in context (given actual usage).

Inspiration for the latter of these improvements comes from How to Write a Spelling Corrector by Peter Norvig. Well worth the read.

DEV Community: aruna-x

Sometimes Stochastic Parrots Lie: How to Minimize LLM Hallucinations

Table Of Contents

Examples of LLM Hallucinations

Why Do LLMs Hallucinate?

Strategies to Mitigate Hallucinations

Steerability

Retrieval Data Augmentation

Completion Parameters / Hyperparameters

1. temperature (range: 0-2, default: 1)

2. top_p (range: 0-1, default: 1)

3. presence_penalty (range: -2 to 2, default: 0)

4. frequency_penalty (range: -2 to 2, default: 0)

5. logit bias (range: -100 to 100, requires: JSON object mapping specific tokens)

Chain-of-Thought (CoT) Prompting

The Wacky World of Closures & What Makes Them Useful

Getting Closure With Javascript

Not All Closures Are Made The Same

What Makes Closures Uniquely Useful?

Function Factories

A Closure Function Factory In Use

Namespacing private functions

Closures In Interviews

A Final Musing:

Abstract Syntax Trees: They're Actually Used Everywhere -- But What Are They?

Enter: Abstract Syntax Trees (ASTs)

How Do Graphs Work?

AST Design Standards & Traversal Functions

Tree Shaking & More

Tools To Make And Use An AST

ASTs vs CPTs

Follow Up

The Halting Problem

We'll See What's Possible

String Matching Algorithm Uses, Interactive Implementations, & Free Source Code

Exact String Matching

Fuzzy String Matching

Final Thoughts

Follow Up