coding trails

Paradigm Shift

October 10, 2024 by schildawg Leave a Comment

In order to keep things simple while covering the basics, up till now I’ve written as if there is a single mathematical model governing the relationship of all words to each other. This is certainly not the case. There are potential models for every person in the world. For every philosophy, every religion, and every viewpoint. There are even valid models for every combination and permutation of every existing model. If a single model is a universe, the set of all models is the multiverse!

In upcoming posts I will explore how different models can interact with each other, merging or clashing. Models are also not static, but are continuously changing. However, in this post we will look at how even using the same training data can result in different models.

Let’s say we have two models, one with 1,000 dimensions, and another with 150, and we train them both using the book War and Peace. Both models will contain around 20,000 words. But the model with fewer dimensions will be lower resolution, and the words will lack the nuances of the model with more dimensions. If you reduce the resolution too much, the model becomes worthless, like a blurry picture where you can’t make out the details.

Because of diminishing returns, the 850 extra dimensions do not make the model 5 – 6 times more accurate. But if you include or omit an important dimension, it can make a huge difference. A perfect example of this is looking up into the night sky, and seeing two stars which appear to be right next to each other. But because of their distances from earth (the dimension we can’t see) they might really be very far apart.

This is what is known as a “paradigm shift.” A paradigm shift is when a single bit of information fundamentally changes your view of a concept or situation. Similarly, in a model, a single dimension can fundamentally change the meaning of a word.

Let’s take for example the words “pepper” and “jalapeño.” The two words are very similar, and share many dimensions, clustering them close together in the model with other vegetables and fruits. But if you add the dimension “spiciness” they become much further apart. Though not as far apart as “jalapeño” and “strawberry”.

Without this dimension, the prompt “create a recipe for two alarm chili” might end up substituting “jalapeño” with “bell pepper”, resulting in some disappointing results!

LeetCode

October 7, 2024 by schildawg Leave a Comment

Disclaimer: I don’t believe LeetCode is a true judge of a software engineer’s ability in most cases, and do not endorse the use of it for interviewing. My main purpose is to showcase Algol-24, while at the same time proving to myself that my language can handle all these scenarios.

Index:

Two Sum – Easy
Add Two Numbers – Medium
Longest Substring Without Repeating Characters – Medium
Median of Two Sorted Arrays – In Progress – Hard

Longest Substring Without Repeating Characters

October 7, 2024 by schildawg Leave a Comment

Description

Given a string s, find the length of the longest substring without repeating characters.

Tests

As always, let’s start out with the tests:

/// The answer is 'abc', with the length of 3.
///
test 'Example 1';
begin
    AssertEqual(3, LongestSubstring('abcabcbb'));
end

/// The answer is 'b', with the length of 1.
///
test 'Example 2';
begin
    AssertEqual(1, LongestSubstring('bbbbb'));
end

/// The answer is 'wke', with the length of 3. Notice that 
/// the answer must be a substring, 'pwke' is a subsequence 
/// and not a substring.
///
test 'Example 3';
begin
    AssertEqual(3, LongestSubstring('pwwkew'));
end

Solution

This is a medium level LeetCode question. Coding it is simple if you know the concept of the “sliding window.”

function LongestSubstring(S : String) : Integer;
var
   Start, Finish, TheMax : Integer := 0;
   TheSet : Set := Set();

begin
    while Finish < Length(S) do
    begin
        if Not TheSet.Contains(S[Finish]) then
            begin
                TheSet.Add(S[Finish]);        
                Finish := Finish + 1;
                
                TheMax := Max(TheSet.Length, TheMax);
            end
        else
            begin
                TheSet.Remove(S[Start]);
                Start := Start + 1;
            end 
    end
    Exit TheMax;
end

Use a Set to keep track of the unique characters. Start out with the “window” start and finish at the beginning of the String, and loop until the finish is at the end of the String. If the character at the end of the window is not in the Set, add it and move the end by one. If not, remove the character at the start of the window from the Set and move the start by one.

When the end of the window is at the end of window, return the largest number of characters the Set contained. (Every time you add a character, set the max to the length of the Set, if it is larger than the previous max.

The Big Bang

September 25, 2024 by schildawg Leave a Comment

“We don’t need no education” — The Wall

In The Word we see that the words in a language models can be visualized as constellations with precise mathematical relations between each other. And each constellation can also be thought of as a “thinking” entity which takes in other “context” words and redirects to the next word. (Adding itself to the context)

The code to navigate the model and generate content is pretty straightforward, and is not very difficult to develop or run, but the model itself is nothing short of amazing! It is something that a thousand programmers could not have programmed in a thousand years. We haven’t even begun to scratch the surface of understanding what is contained in it. So how did we manage to make these language models?

If you have a clear idea of the result you want, but have no training data, you can use “evolution” to teach neural networks. This is the method used for creating bots to beat Super Mario Brothers. The screen is the input, and controller actions are the output. The “hidden” layer is treated as DNA. The DNA is mutated, bred together, and divided into species. Over many generations, only the fittest DNA is kept, and the rest go extinct. The same principle can be used for evolving computer programs. I plan on using my BrainF*ck interpreter to create a laboratory to play around with this concept in PRISM, and I will write about it in depth.

Fortunately, with many zetabytes of content on the Internet, there is no shortage of content to train our model. Where do we start? First you create an hyper-dimensional void, and add all your words. At this point we don’t have the faintest clue where the words should go, however. And we don’t want to place them all at the origin, because that will introduce a bias towards the origin point. So we “explode” the words out, selecting a random hyper-dimensional point for each word.

Next we start working our way through the entire Internet! For every book ever written, every blog post, and every angry rant posted on a forum, we run it through our model nudging the stars to their correct place in the universe. This is where the hard part comes into play. You provide the inputs and the outputs, and use “backpropogation” to turn the knobs in the hidden layer of the neural network. This involves complex coding and advanced mathematics to pull off—people have written thesis papers on the topic, so I won’t be writing about it 😀

So, 64 ZB and a billion dollars later, you get ChatGPT-5. I said we don’t know what’s in it, but we actually do. It is the synthesis of the entirety of human knowledge, organized into a nice, compact mathematical formula.

With this massive undertaking accomplished, the doors are now open to a new form of training. There is no need to start back from the beginning. AI can be tasked with training other AI, which can in turn train other AI… and on and on. What took years to accomplish can now be done in a matter of hours.

Solutions such as OpenAI have thousands of dimensions, vastly exceeding the point of diminishing returns. Reducing dimensions down to several hundred can be 90% as effective, allowing it to run on inexpensive hardware. Stanford’s Alpaca can be trained in an hour and a half and run on a $300 computer! Llama 7B has even been successfully installed and run on a Raspberry Pi!

Add Two Numbers

September 4, 2024 by schildawg Leave a Comment

Description

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Setup

In LeetCode, the linked list is provided for you. We’ll have to add that ourselves. To make the test cases more readable, we will also add a ToString to print it out, and a factory to easily create it from an array of integers.

class ListNode;
begin
    constructor Init(Value : Integer, Next : ListNode := Nil);
    begin
       this.Value := Value;
       this.Next  := Next;
    end

    function ToString() : String;
    begin
        var ToString := Str('[') + Value;
        
        var Current := Next;
        while Current <> Nil do
        begin
           ToString := ToString + ', ' + Current.Value;
           Current := Current.Next;
        end
        ToString := ToString + ']';

        Exit ToString;
    end
end

function LinkedList(Values : Array of Integer) : ListNode;
var 
   Head, Current : ListNode;

begin
    if Values.Length = 0 then raise 'Must contain at least one node!'; 

    Head := ListNode(0);
    Current := Head;

    for var I := Iterator(Values); I.HasNext() do
    begin
        Current.Next := ListNode(I.Next());
        Current := Current.Next;
    end
    Exit Head.Next;
end

Tests

With that taken care of, we can add the 3 example scenarios as test cases:

test 'Case #1';
begin
    var Sum := AddTwoNumbers([2, 4, 3], [5, 6, 4]);

    AssertEqual('[7, 0, 8]', Sum.ToString());
end

test 'Case #2';
begin
    var Sum := AddTwoNumbers([0], [0]);

    AssertEqual('[0]', Sum.ToString());
end

test 'Case #3';
begin
    var Sum := AddTwoNumbers([9, 9, 9, 9, 9, 9, 9], [9, 9, 9, 9]);

    AssertEqual('[8, 9, 9, 9, 0, 0, 0, 1]', Sum.ToString());
end

Solution

To get a O(n) solution, you just loop through the two linked lists at the same time, and add the two together. If the first or second node is Nil you set that value to 0.

Probably the hardest part of this problem is carrying to 10’s place. You can use division to get the value, and the mod operator to get the carry. The tricky part comes in modifying the while loop to make sure you continue till carry value is gone, even if it goes beyond both linked lists.

Note: it makes the solution easier by creating a dummy head, and just returning the Next property.

function AddTwoNumbers(List1, List2: ListNode) : ListNode;
var 
   Head, Current : ListNode;
   
   First, Second : Integer;
   Sum, Carry    : Integer := 0;

begin
    Head := ListNode(0, Nil);
    Current := Head;

    while List1 <> Nil Or List2 <> Nil Or Carry <> 0 do
    begin
       First  := List1 = Nil ? 0 : List1.Value;
       Second := List2 = Nil ? 0 : List2.Value;

       Sum := First + Second + Carry;
       Carry := Sum / 10;

       Current.Next := ListNode(Sum % 10);
       Current := Current.Next;

       List1 := List1?.Next;
       List2 := List2?.Next;
    end
    Exit Head.Next;
end

**********

Bonus

Using operator overloading the code becomes more readable:

operator + (Other : ListNode) : ListNode;
begin
   Exit AddTwoNumbers (this, Other);
end

Now the code looks like LinkedList([1, 2, 3]) + LinkedList([4, 5, 6]).

Bonus #2

In an interview the other day I had the good old “reverse a linked list” coding question, in Java of course, but here is the equivalent in Algol-24 😀

/// Add to ListNode class.
///
function Reverse() : ListNode;
var
    Current, Previous, Next : LinkedNode := Nil;

begin
    Current := this;

    while Current <> Nil do
    begin
        Next := Current.Next;
        Current.Next := Previous;
            
        Previous := Current;
        Current := Next;
    end
    Exit Previous;
end 

test 'Reverse a linked list';
begin
    var TheList := LinkedList([2, 4, 3]);

    var Sum := TheList.Reverse();
    AssertEqual('[3, 4, 2]', Sum.ToString());
end

The Word

August 31, 2024 by schildawg Leave a Comment

ἐν ἀρχῇ ἦν ὁ λόγος — Ιωάννης ο αγαπημένος

To understand artificial intelligence, you have to start at the beginning—the word. If you look up a word in a dictionary, it is defined by other words, which are in turn defined by even more words. If you keep repeating this process, you end up with a network consisting of all of the words in a language. You can start at any word in that language and plot a course to any other word.

We tend to think of the relationship between words as being vague or fuzzy, but in fact a language is a precise mathematical model in which distances between words can be measured, angles calculated, and relationships derived using trigonometry and calculus.

A word is a singular point in a hyper-dimensional field. The number of dimensions determine the semantic preciseness of the word. Less than a hundred dimensions and the word loses its precision, like a picture out of focus. If you have more than several hundred dimensions, you start to experience diminishing returns. Three hundred dimensions is sufficient for general purposes, but models exist with several thousand dimensions.

You could think of words as being stars in a vast hyper-dimensional universe. It is possible to conceive of time being the fourth dimension and the multiverse as being the fifth, but if you go beyond that it quickly becomes incomprehensible. But there is a way to visualize it that is easily understandable. A three dimensional object can be drawn on a mostly two dimensional piece of paper. A four dimensional being would appear to us as three dimensional with movement.

If you take the dimensions of a word and divide it into three-dimensional slices and superimpose them on top of each other, you have a constellation of dozens of bright stars and hundreds of faint ones. At the center of gravity of this constellation there is a world, where you can look up into the sky and see millions of other stars, both bright and dim.

If you stand on world “Man” and look up and find the star “King” you can teleport to the same place on world “Woman” and in the exact same place in the sky will be the star “Queen.” Similarly, looking at “Queen” from “King” is the exact same relationship as “Woman” from “Man.” There are profound implications and insights that can be derived from this relationship, which we will explore in future posts.

If you break down a word even further into one-dimension points, we now have hundreds or even thousands of sliders or knobs which can be adjusted from off to completely on. This is the definition of a neuron in a neural network. With this paradigm, we can conceive of a word as being a “brain” which takes in a phrase of words and calculates the next word.

Returning to the analogy of a galaxy of stars, a word is a sector of space into which a space ship enters and the gravitational pull of each of the stars redirects and forwards the ship to the next sector in space. The ship starts out with a prompt, and bounces from word to word until it reaches the end of its journal with a complete response.

You see, a language model is a formula, or a condensed mathematical model of the entirety of human knowledge. The coding necessary to build this model is not complex or even particularly sophisticated. It just required the Internet to exist, and a great deal of time, and a lot of money to train it.

Now that we have the model, it’s easy and relatively inexpensive to copy it in high and low definition. But we don’t know what’s in it. We don’t even understand what all the higher dimensions are. This is, in my opinion “the final frontier.” There are insights to be gleaned in linguistics, psychology, and philosophy. A whole new universe exists which is waiting to be discovered and explored!