This is hilarious because my teachers back in college used this exact formula with Gzip to calculate plagiarism between programming assignments. Guess some people knew that Gzip could do this 10 years ago, and we just forgot it worked.

this is my favorite genre of cs research right now, the fact that compression is a useful clustering metric is so funny but also makes so much sense. stuff like this makes me hopeful that one day we'll escape the "scale everything" model of ML research and lean into the information/learning theory side of AI research :))

Yes, it works because if X and Y are similar (have a bunch of words in common), their normalised compressed length will be small and if two texts are different, it will be large. Think about it as "more common words = smaller compressed representation".

Computing Kolmogorov's compelxity is not NP-hard. No, it's literally uncomputable. Not in polynomial, not in exponential, it's just not computable in any finite time. Wikipedia has more details as to why, but TL;DR you can't even bruteforce iterate through all possible programs, because some of them will never terminate and just figuring out whether a given program will terminate is already an uncomputable problem.

One point is that one of the reasons this works is THE KIND of compression algorithm that gzip is. There are programs that compress text BETTER than gzip does WHICH WOULD BE WORSE for measuring similarity between texts, because they're better at taking advantage of global properties of the text (for instance, recognizing the languages) and less focused on taking advantage of context within the text.

I am glad I came across your channel today. I am currently in research and development on a project which attempts to model Kolcom. I hope to see more of your journey as I go along with mine. One such approach I have decided to utilize, is compression by reference. Pointers are one implementation of this method. A word for example is comprised of letters, which are hex values, or a single byte value. A reference frame determines the level of compression possible. This is why GZip and K-NN are very successful. By caching the reference frame, you cache the reverse program to decompress the data.

Tsoding, I really love your content dude, so genuine and interesting, you're really inspiring! I've wanted to ask you if you're into signal processing and if yes, would be cool to see you do a nice tsoding session about Fourier transformation and even wavelets and how they're similar yet very different they're in the sense of how they give information about both time and frequency :D You could even demonstrate how wavelets can be used to analyze features in pictures like blood vessels in medical imaging and so on! I'd really find that interesting coming from you and the way you explain and talk about complex things in an understandable way. Much appreciated and continue doing what you're doing!

Knowledge is compression. Your mind creates a model in your head of the world that is a compressed version of the world.

WARNING, I have to warn anyone who believes in the papers description of this approach being better then AI - it's not. This papers code has been debunked and authors made critical mistake with metric calculations when comparing their method against BERT. Don't know if this is mentioned on stream, but felt like this is important.

Having a value of 2 for k is strange. It's going to cause lots of cases where two classes have the same score... Ideally, it shouldn't be a multiple of either 2 (or 4) or 3 to avoid these kinds of conflicts. Personally, I would pick some prime number bigger than the number of classes, for example 5

to optimize `deflate(a+b)` maybe you can save the state of deflator right after `a`, and continue from that checkpoint for every `b`?

24:21 One of your machine learning videos a while back inspired me to recreate a Kaggle contest. Not sure if it’s considered a contest but more of a preliminary challenge before moving to some of the more difficult ones. It’s the titanic prediction model. I solved it using python and immediately thought, wow that was stupid. All the functions I used were completely abstracted and I had no clue what they were doing under the hood. As a means to learning, and an excuse to not use python, I decided to cause immense pain to myself and reimplement the model using c! I spent a decent amount of time writing a csv parser for the training data. The way the data was structured really pissed me off. nested double quotes and all sorts of crazy shit they packed in a given string lmfao. I ended up using a stack based approach, and it worked perfectly. I’m still working on building the rest of the model, it’s been challenging but learning a lot. It’s videos like these that inspire me to dig a bit deeper.

I agree that Pascal is the only real potential substitute for C, and you mentioning that reminded me that Niklaus Wirth died on the first.

loved watching this live

you could get a large speed-up by caching the compressed samples - as you will only need to re-compress the combination of test+sample inside the loop, instead of all three each time

Is it possible to show the possibilities of the classes? or does it not calculate that

Hi! New subscriber here! You have one of the freaking best channel on YT. Your contents are beyond priceless! I'm speechless. BTW You really need a simple piece of software to display onscreen the number of "right" you say 😂. (no offense intended!) Greeting from Italy!

To get an intuition for setting k, I would look at the sorted NCD table for the first n records. If the klassifier is good, the klasses for the examples at the top of the sorted NCD table should be often aligned with the test example.

When k=2 and neighbors are different, selecting predicted klass will be pick based on order of classes (which I think is the problem). so I would say k=nklass+1 should be better

CPU cycles have never been utilized more efficiently. Take that Sam Altman!

Maybe it wont matter but at 45:24 you were measuring the performance of the whole application (reading the file to memory and then counting the lines) so i thought maybe counting the lines takes more time that opening the file hence you cannot decide if reading the whole file into memory is faster than reading it in chunks of 32k bytes, unless maybe the OS is also reading the file into memory using 32k byte chunks ? or maybe the allocator allocates pages of 32k bytes at a time and handles the page faults ? IDK but what i'm saying is maybe the measurment was flawed, maybe i'm wrong i am just curious and please correct me if so

This paper is a beautiful troll. I love how you think about how something works and turning the paper into a sort of puzzle. I'm stealing this technique without shame 😂 "Why the fuck would this even work?" is a question that really needs to be asked more by deep learning cool aid kids. (let's be honest - we use these models when we lack the capacity to explain whatever system we're..."modelling")

11:04 Is this true, does the ideal compression of a piece of text for example necessarily have the same entropy as the smallest program (in a specific language) to generate that text?

wow this is cool shit, i heard geohot talking about that ai is basically compression :D And here it is cleary demonstrated.

Regarding annoyance with custom printers, you can give them your compier's printf attribute so you get nice warnings.

I love how I get exposed to different papers by watching Tsoding. It feels like I'm back at college (but without the stress of tests, etc).

Could maybe also speed up the calculation of C(ab) by feeding the test sample into a deflate stream and then making a full copy of the state of that deflate stream before feeding the other sample into it. And then copy that backup again to get back to the state where the test sample was already deflated.

What a hilarious paper, love it!

That's freaking brilliant! I wonder if this would work for handwritten character recognition, like with the MNIST dataset or similar?

try implementing hnsw for this to speed up your classification? probably be a lot of fun to implement

I guess with k = 2 its hard to show the "confidence" of the system but that would have been a cool addition so that you can evaluate the output better

43:20 - Pascal WAS a competitor to C, and it almost won, it didn't win because: a) arrays start from 1 b) lack of macros (it was considered as uber-feature at the time) c) C was available out-of-the-box in Unix Zig is a good candidate to fill C niche because it DOES focus on simplicity, but it wouldn't take off because its too focused on it's own ideal (not until there would be c-style for loop, and some of 'errors' wouldn't be categorized as warnings instead (for example unused variable is an error)) 44:00 it doesn't matter because fread (and OS) does caching for you, and realloc takes some extra capacity

By the same analogy, the brain is an interpreter that uses body's sensory systems as IO. Fascinating!

another idea... could you preprocess the train data and find the centroid of each class, maybe 10 or so samples for class, that maximizes the distance from other classes while minimizing distance to other elements of their class, then classify on this reduced set? though at that point maybe you just get the most common words per each class... idk

It's interesting. I started getting really good at learning fast recently. I think it has to do with my ability to find a good enough "compression algorithm" and then compress the topic I want to learn. And yes, I first have to understand the concept, but I didn't really had a problem with that at school. What I did have a problem with was to remember a semester of detailed literature verbatim (times the ammount of courses I attended that semester), so I could do well on exams. (Stupid really) But in the end the process became: Parse and index the issue for common concepts, generalize the differences as much as possible, remember the general concept once, remember the few variables to bend the concept to my will. Which, if you think about it, is like a compression algorithm. Find common subsets, encode them by "keywords", remember the common keywords once (like a dictionary), remember the variables (the keys into the dictionary)

Just a stream of thoughts... Given the formula: NCD(x,y) = (C(xy) - min(C(x), C(y)) / max(C(x) , C(y)) I think it's quite educational to look at the minimal test case of samples: "aabb", "aa", "bbcc" Assuming a naive length based on dictionary size 2, entries D and dictionary lookups L "aa", "aabb" => (2D3L - min(1D1L, 2D2L)) / max(1D1L, 2D2L) = 1D2L / 2D2L "aa", "bbcc" => (3D3L - min(1D1L, 2D2L)) / max(1D1L, 2D2L) = 2D2L / 2D2L "aabb", "bbcc" => (3D4L - min(2D2L, 2D2L)) / max(2D2L, 2D2L) = 1D2L / 2D2L So, as expected, "aa" has as much in common with "aabb" as "aabb" does "bbcc". Of course, it's far from the complete picture but decent enough to illustrate a point. Not sure how useful it would be, but there's a parallel gzip called pigz. If nothing else, the concatenation process might be useful. You could store the compressed form of every entry and then, instead of doing C(xy) it might be enough to approximate by compressing y initialized with the dictionary from x. So halving the workload for the calculation for the given samples at least. k = 2 is probably used due to the short samples causing too much variability for larger neighbourhoods I would think? The moon landing being classified as sports isn't all that strange. At least I'm pretty sure I've heard such phrases as "landing (a goal)", "landing (a hit)", etc. Would be interesting if this also works for image classification, or maybe even face recognition, using jpeg.

You could try implementing the MDS algorithm using the NCD in order to plot the points to a lower dimnsion. Then you could use k-means and see if the data could be clustered correctly.

this program can be further optimized by pre-caching the gzip of the training (and test?) samples

Calculation of kolmogorov complexity is not only NP-hard, it's actually uncomputable (and even wikipedia contains proof for it)

44:30 stdio already reads in chunks. So it kinda reads a chunk then copies it into users read buffer. And yes it is inefficient, you could probably do it better with raw 'read' syscalls

I love our little rant about mathematicians giving stuff overly technical, complex names to make things seems complex. Mathematicians are really good at abstracting things to easier problems for themselves and really good at making it as complex as possible for others.

I am working on a DL projects and it's 4 am in the morning and I am fucking dying because I don't have enough computation on kaggle to run the models properly ..... and KZfaq recommends me this. These recommendation systems are getting out of hand man .

I started smiling already by reading the title 💪🏻😁

It seems that basically data compression mimics cognitive abstraction or how we form concepts. We find find the similarities among objects in order to classify them. For example, we call something a chair because it meets a certain criteria.

1:11:45 read all the data into memory and compressed it faster than github can load a single page

11:23 this remind me of a video I saw of george hotz, where he said exactly that, I think it was called "the days that changed my life" or something

I wonder if you could make a basic spam/phishing filter using this

Hello I'want to learn opencv but l have i5 cpu 8gb ram and intel hd 520 gpu is it Enough

so theoretically information compression is the emergence of awareness/understanding?

@00:12:31 they're code also contains syntax errors. (missing ')' after every use of ...`encoded()` ).

Interestingly, when you say "state of the art AI language models and shit like that", youtube auto-generated subtitles do not show the "shit"... KZfaq guys implemented a shit-collector... 😅

22:46 but github also needs to display stuff, not just load into memory

@ 27:30 and this is why im always using -Werror in my projects 😅😅

How does he beatbox so good

this video was awesome

PASCAL was a good competitor to C. I'm suprised people like us still exist. GG

good video

"The internet feels increasingly smaller and smaller and smaller..." yes :(

What da thumbnail it is 😂😂😂

Holy phek... Here's me being an idiot using embeddings. This makes total sense how it works. I'm only 10mins in and I totally want to stop and try and implement myself. I suspect for simple query and passage problems this would be useless but for large bodies of text it would work a charm. Gives me an idea to use a thesaurus and/or terminologies to create domain specific querying without AI model

Nice thumbnail

23:00 thank JS for that

05:00 can NCD(x,y)!=NCD(y,x) happen?

I might have proof of being the first person to find this solution which was just to see if kNN can work in a zip compression. By the way... I am not at all a mathematician and I also might be the first to have replaced the Sigmoid to be the ReLu.

Today I used this trick in the puzzle game I'm making :)

Thank you....

Hmm should take a look at Oodle i guess?

Parsing complex cvs is easier than signing up in kaggle it seems 😂

It works because NNs a actually lossy compressors and with enough coefficients they approach losless compression state. And zip is just a losless compressor. That seems obvious.

You're fucking awesome.

43:21 c is still easier for dynamic linking than pascal

difference between compression and ai is the same difference as ALAC/FLAC/WAVPAK and AAC,MP3.VORBIS, , the first is obligated to reproduce the source material exactly , the second tries to create a new thing that is persieved as alike the original. i recently had a discussion about this with someone about something related, i claimed that nvidia in essense proclamated that they hit the ceiling of their abilities by pushing all in on AI , since if you take a step back and look at the process , they switched from increasiong gpu power for improving image quality and rate , to prerendering the games on ultra quality at their server farm and shipping the frames the cards cant generrate due to lack of power , in a highly compressed form disguised as AI to the customer , if they just gave you hard disks full of complete prerendered frames , and your pc only had to pick the rigth frames to match the actions you make in the game , youd be calling it a disgrase... because the AI only can do what it was trained to do, similar a compressed prerender can only aproximate its original source , making the x-thousand ai accelerators pretty useless on their own for anything other than image restoration , and defenetly for anything requiring accuracy.... and im thinking of doing fourrier transforms en mass parralell (soemthing gfx cards should be good at,and they are but they wont get better than they are now) or proteinfolding , possibly even emulating syncro systems (logic) or simulating old console hardware (similar to what they use fpga's for today (modern gameboy eg)

couldn't you define a macro to automatically create an array type of a struct, something like #define vector(T)\ typedef struct {\ T* data;\ uint16_t length,capacity;\ } T ## s

7:58 it's not NP-hard, it requires solving the halting problem

Can someone clarify what are the main fields of math and cs this man is interested in?

Wait for the day someone comes with AI idea called “hash is all you need” and it’s going to be more awesome than Cypto

Just a little reminder, if you divide the video into 120 parts, the division is useless because it doesn't tell a person anything. Perhaps it would be better to combine some parts and generalize

40:53 fread and ferror don't set errno, so it would log incorrect error message

I'd try to reproduce their results with their data.

tangent re text files it's so so so stupid how "hard" it is for text editors to open files in the megabytes range. it's a minuscule fractions of a fractions of RAM available in our modern systems, yet notepad++ for example lags so hard when you feed it files in the megabytes. while ed just chads through it.

Woah

Any time someone says "AI" it's like saying a generic term. "Peaches are better than fiber", "AI" is a generic term that can literally mean anything. I can make a garbage AI that, yes, "Zip will work better", however, a very well crafted ML compression system would then be better.

I can't help but notice that all these papers that detract from modern llms use models that pre-date gpt-3. Like, no one ever claimed OPT or text-davinci were exciting, revolutionary, or game changing. It wasn't until gpt-3/4, llama, mistral, yi, etc that llms started to feel magic. The ouroboros paper was the same thing. Finetuning OPT with OPT outputs makes for a dumber model. Finetuning llama with llama outputs makes a far smarter model. Pretty sure that's how wizardLM was trained. Likewise, I'm not surprised Gzip is smarter than BERT. Who is out here claiming BERT is the future?

42:50 true, I used to be a fanboy and it hurts but it's true

3:06 FACTS hahaha bothers me so much sometimes

it doesnt have anything to do with complexity. as you have also realized its about common parts of A and B. huffman coding will do the heavy lifting here, basically looking for common prefixes and reducing their occurrence.

Here's a crackpot idea: AI is lossy compression for text?

Omg, Tsoding are you learning portuguese ? “cinco” 👉🏼👈🏼

12:10 😀 me as AI Researcher: 100% needed to do worse to crush space to fit into max page length. We shall apologize to all engineers ❤️

I was watching your videos, and you said in the one of your previous stream that "You know less about a subject, you are better from the others. You make done the job quickly." And than I've just run accross that video: kzfaq.info/get/bejne/o6iTddJ4zazSlI0.html --> "I built an image search engine". You know what? you were right, is he really built an image search engine, is he? Nah he's not. But at the same time he is. without having a purely understanding of the billions and zibillions of shit under the hood. You were right...

I though gzip used Huffman. Or the most probably thing is I didn't understand a shit xD

24:59 Shell 76.5%

Yeah but it spends much more time and processing

Try Odin

AGI

1:21:54 !

IF THERE IS DISCORD SERVER, HOW TF CAN'T I FIND IT ANYWHERE!!!

No, no it isn't....dumb question.

58:15 how does multiply by 2 handle compressed data bigger than uncompressed data? hello.txt is 6 bytes and hello.txt.gz is 36 bytes and 6*2=12 and 12