- 15
- 302 467
Concepts Illuminated
Приєднався 7 тра 2015
What do you get when a software engineer, an educator, and an animator join forces? Videos which explain topics in a way that focuses on being intuitive, yet detailed. You get: Concepts Illuminated.
The Verhoeff-Gumm Check Digit Algorithm #SoME3
Rediscover and explore the Verhoeff-Gumm algorithm, a check digit formula which is more resilient to common errors than the Luhn algorithm, which is widely used in credit card numbers, IMEI numbers and more.
Historical Notes:
"Error Detecting Decimal Codes" [1], a PhD thesis by J Verhoeff was published in 1969. It showed how the vast majority of digit typos were single digit or transposition errors, traditional "modulo 10" algorithms always missed some transposition errors, and introduced a novel class of algorithms based on "the dihedral group of order 10" (pentagon flips and rotations). In section 4.4, Verhoeff outlines using "search program" to find a permutation function that is optimal for detecting errors. A formal proof of the permutation's correctness is omitted. I found Verhoeff's writing to be difficult to approach, so I recommend a section in "Contemporary Abstract Algebra" (seventh edition) by Joseph A Gallian (pg 111-114) for a clearer write-up. A witty quote from Verhoeff in the introduction made me chuckle: "[I believe] that the codes explained in chapter 4 provide the first practical application of the dihedral group. This would illustrate the old saying that all beautiful mathematics will find an application, sooner or later."
In 1985, H. Peter Gumm published "A new class of check-digit methods for arbitrary number systems" [2]. It starts with a dense proof that "modulo 10" (indeed modulo 2k) formulas will always be flawed. The paper then justifies the use of the dihedral group, which to me sounded like a mathematician walking around a store looking for the right outfit ("needs cancellation", "should be associative", "finite members", "can generalize for any even number"). Gumm then *proves* an algorithm using D_s works, using the number pair notation and a permutation function tau.
Gumm claims to have been unaware of Verhoeff's work. Additionally, Gumm adds a proof and a way to scale it beyond 10 digits, so I decided to credit them both with discovering the algorithm in this video.
A variant of the algorithm saw use (an may still see use) on German Banknotes [4].
Felix Klein (same as the Klein bottle) was an important contributor to group theory [3], and was chosen to be the cardholder in the intro. Likewise, Évariste Galois coined the term "group" and was thus chosen to be the online vendor.
[1] ir.cwi.nl/pub/13046/13046D.pdf
[2] www.researchgate.net/publication/3084126_A_new_class_of_check-digit_methods_for_arbitrary_number_systems_Corresp
[3] archive.org/details/vergleichendebe00kleigoog/page/n20/mode/2up
[4] ocs.ef.jcu.cz/index.php/inproforum/INP2016/paper/viewFile/794/565
Expanding the Mathematical Toolbox:
A key concept in Group Theory is the idea of sets, which is covered very well in [4]. Groups are introduced well in [5] and I hope the author continues the series.
The Rubix cube can be analyzed using group theory [6] or with "graphs" [7], which are both useful when dealing with so many possible states.
[4] ua-cam.com/video/dKtsjQtigag/v-deo.html "What IS a Number? As Explained by a Mathematician" by Another Roof
[5] ua-cam.com/video/KufsL2VgELo/v-deo.html "Researchers Use Group Theory to Speed Up Algorithms - Introduction to Groups" by Nemean
[6] ua-cam.com/video/FW2Hvs5WaRY/v-deo.html "Group theory 101: How to play a Rubik’s Cube like a piano - Michael Staff" by TED-Ed
[7] ua-cam.com/video/wL3uWO-KLUE/v-deo.html "The algorithmic trick that solves Rubik’s Cubes and breaks ciphers" by polylog
Animations were made by Kaylee L with Manim Community edition (www.manim.community/) taking about 7k lines of Python code to make. Narration by James K.
Sound effects from UA-cam Audio Library
- Battle Crowd Celebrate Stutter
- Punchline Drum
This was an entry into Summer of Math Exposition 3 #SoME3
- some.3b1b.co/
0:00 Luhn Algorithm (and its flaw)
1:39 How could we fix the flaw?
2:21 Basic Integer Operations (how they don't help)
3:12 Rotating and Flipping Shapes is order dependent
4:16 Combining Pentagons (function composition)
5:30 "Packing the box" with pentagons (associativity/inverses)
6:56 Do our pentagons work for all transpositions? (Cayley Table)
8:29 Adding a preprocessing step (sigma function)
9:30 How to prove if sigma works (converting to integer pairs)
11:56 Proving Gumm's sigma function does work
13:12 Expanding sigma into digit permutation
13:38 Scaling up to 3 or more digits/pentagons
15:06 Summarizing the Verhoeff-Gumm Algorithm (and the variants)
16:00 Group theory is all about surprising symmetries
Historical Notes:
"Error Detecting Decimal Codes" [1], a PhD thesis by J Verhoeff was published in 1969. It showed how the vast majority of digit typos were single digit or transposition errors, traditional "modulo 10" algorithms always missed some transposition errors, and introduced a novel class of algorithms based on "the dihedral group of order 10" (pentagon flips and rotations). In section 4.4, Verhoeff outlines using "search program" to find a permutation function that is optimal for detecting errors. A formal proof of the permutation's correctness is omitted. I found Verhoeff's writing to be difficult to approach, so I recommend a section in "Contemporary Abstract Algebra" (seventh edition) by Joseph A Gallian (pg 111-114) for a clearer write-up. A witty quote from Verhoeff in the introduction made me chuckle: "[I believe] that the codes explained in chapter 4 provide the first practical application of the dihedral group. This would illustrate the old saying that all beautiful mathematics will find an application, sooner or later."
In 1985, H. Peter Gumm published "A new class of check-digit methods for arbitrary number systems" [2]. It starts with a dense proof that "modulo 10" (indeed modulo 2k) formulas will always be flawed. The paper then justifies the use of the dihedral group, which to me sounded like a mathematician walking around a store looking for the right outfit ("needs cancellation", "should be associative", "finite members", "can generalize for any even number"). Gumm then *proves* an algorithm using D_s works, using the number pair notation and a permutation function tau.
Gumm claims to have been unaware of Verhoeff's work. Additionally, Gumm adds a proof and a way to scale it beyond 10 digits, so I decided to credit them both with discovering the algorithm in this video.
A variant of the algorithm saw use (an may still see use) on German Banknotes [4].
Felix Klein (same as the Klein bottle) was an important contributor to group theory [3], and was chosen to be the cardholder in the intro. Likewise, Évariste Galois coined the term "group" and was thus chosen to be the online vendor.
[1] ir.cwi.nl/pub/13046/13046D.pdf
[2] www.researchgate.net/publication/3084126_A_new_class_of_check-digit_methods_for_arbitrary_number_systems_Corresp
[3] archive.org/details/vergleichendebe00kleigoog/page/n20/mode/2up
[4] ocs.ef.jcu.cz/index.php/inproforum/INP2016/paper/viewFile/794/565
Expanding the Mathematical Toolbox:
A key concept in Group Theory is the idea of sets, which is covered very well in [4]. Groups are introduced well in [5] and I hope the author continues the series.
The Rubix cube can be analyzed using group theory [6] or with "graphs" [7], which are both useful when dealing with so many possible states.
[4] ua-cam.com/video/dKtsjQtigag/v-deo.html "What IS a Number? As Explained by a Mathematician" by Another Roof
[5] ua-cam.com/video/KufsL2VgELo/v-deo.html "Researchers Use Group Theory to Speed Up Algorithms - Introduction to Groups" by Nemean
[6] ua-cam.com/video/FW2Hvs5WaRY/v-deo.html "Group theory 101: How to play a Rubik’s Cube like a piano - Michael Staff" by TED-Ed
[7] ua-cam.com/video/wL3uWO-KLUE/v-deo.html "The algorithmic trick that solves Rubik’s Cubes and breaks ciphers" by polylog
Animations were made by Kaylee L with Manim Community edition (www.manim.community/) taking about 7k lines of Python code to make. Narration by James K.
Sound effects from UA-cam Audio Library
- Battle Crowd Celebrate Stutter
- Punchline Drum
This was an entry into Summer of Math Exposition 3 #SoME3
- some.3b1b.co/
0:00 Luhn Algorithm (and its flaw)
1:39 How could we fix the flaw?
2:21 Basic Integer Operations (how they don't help)
3:12 Rotating and Flipping Shapes is order dependent
4:16 Combining Pentagons (function composition)
5:30 "Packing the box" with pentagons (associativity/inverses)
6:56 Do our pentagons work for all transpositions? (Cayley Table)
8:29 Adding a preprocessing step (sigma function)
9:30 How to prove if sigma works (converting to integer pairs)
11:56 Proving Gumm's sigma function does work
13:12 Expanding sigma into digit permutation
13:38 Scaling up to 3 or more digits/pentagons
15:06 Summarizing the Verhoeff-Gumm Algorithm (and the variants)
16:00 Group theory is all about surprising symmetries
Переглядів: 193 666
Відео
Animated Python: 2D Lists and Connect Four
Переглядів 2 тис.Рік тому
This video animates the execution of the Python functions which provide the core features of the game Connect Four. Viewers can see how the computer executes the code step by step and see the contents of the variables change as the computer executes the operations. The key components illustrated are two-dimensional lists, functions, conditionals, and variables. Another way to visualize code run...
Animated Python: Dictionaries and Most Common Elements
Переглядів 1 тис.Рік тому
This video animates the execution of a short Python program that finds the most common letter in a user-provided sentence. Viewers can see how the computer executes the code step by step and see the contents of the variables change as the computer executes the operations. The key components illustrated are for each loops, dictionaries, lists, conditionals, and variables. The code is broken down...
Animated Python: Functions and Blackjack
Переглядів 1,1 тис.Рік тому
This video animates the execution of a short Python program that simulates hands in the card game Blackjack. Viewers can see how the computer executes the code step by step and see the contents of the variables change as the computer evaluates the operations. The key components illustrated are functions, scope, while loops, for range loops, conditionals, lists, and variables. Another way to vis...
Animated Python: For Range Loops and Sales Tax
Переглядів 1,4 тис.2 роки тому
This video animates the execution of a short Python program that processes a list of sales data to compute the total cost, including tax on some of the items. Viewers can see how the computer executes the code step by step and see the contents of the variables change as the computer executes the operations. The key components illustrated are for range loops, functions, string methods, condition...
Animated Python: For Each Loops and Palindromes
Переглядів 2,1 тис.2 роки тому
This video animates the execution of a short Python program that identifies user input as being a palindrome or not. Viewers can see how the computer executes the code step by step and see the contents of the variables change as the computer executes the operations. The key components illustrated are for each loops, string methods, conditionals, and variables. Another way to visualize code runn...
The Expected Value of Pyramid Dice (Casino Game) #SoME2
Переглядів 11 тис.2 роки тому
A video that shows how to calculate the Expected Value of the Casino Game Pyramid Dice. This is an interesting, but not too complex combinatorics problem. Prior to this video (July 2022), there was no complete and publicly available analysis of Pyramid Dice. The analysis in this video is original research by Kaylee Lubick and shows Pyramid Dice has an Expected Value of -12.37% as originally des...
Using MuZero's Tree Search To Find Optimal Tic-Tac-Toe Strategy in a Spreadsheet
Переглядів 8 тис.2 роки тому
A video that explores how the MuZero algorithm combines aspects of Reinforcement Learning and Monte Carlo Tree Search to play efficiently. The animations in the video make use of a spreadsheet which acts as a worked example of the calculations involved in the algorithm. Formulas discussed include Upper Confidence Bounds (for Trees, also called UCB or UCT). MuZero Tree Search Spreadsheet: - bit....
Appendix to Building a ML Transformer in a Spreadsheet
Переглядів 1,6 тис.2 роки тому
This covers multi-headed attention, scaling/mask, residual connections Add & Normalization. These topics did not fit in the main video. Original Video: Building an ML Transformer in a Spreadsheet - ua-cam.com/video/S9eKuRVigjY/v-deo.html Some figures are from "Attention Is All You Need" - arxiv.org/pdf/1706.03762.pdf Filled out Machine Learning Transformer in a Spreadsheet: bit.ly/TransformerSh...
Building a ML Transformer in a Spreadsheet
Переглядів 9 тис.2 роки тому
We continue the theme of building neural networks in a spreadsheet, as a way to do a worked example of them. In this video, we build a Transformer (a type of Machine Learning model) which can encipher text using the Atbash cipher and reverse strings. It also introduces the topics of self-attention and positional encoding. Follow along by making a copy of bit.ly/TransformerSheet1 Three press rel...
Building a Recurrent Neural Network in a spreadsheet
Переглядів 7 тис.3 роки тому
We continue the theme of building neural networks in a spreadsheet, as a way to do a worked example of them. In this video, we build a Recurrent Neural Network (RNN) that can predict the next letter given what the user has typed so far. Building and Training a Traditional Neural Net in a spreadsheet: ua-cam.com/video/fjfZZ6S1ad4/v-deo.html ua-cam.com/video/1zwnPt73pow/v-deo.html Building a Conv...
An Image Detecting Spreadsheet: Implementing Convolutional Neural Networks From Scratch Part 2
Переглядів 2,6 тис.3 роки тому
This is Part 2 in a series in which we create a convolutional neural network (CNN) in a spreadsheet. In this video, we add a second layer to our worked example that can differentiate T, X, and L. Part 1: ua-cam.com/video/8QfFtUcuYCU/v-deo.html Building and Training a Traditional Neural Net in a spreadsheet: ua-cam.com/video/fjfZZ6S1ad4/v-deo.html ua-cam.com/video/1zwnPt73pow/v-deo.html Sheets T...
An Image Detecting Spreadsheet: Implementing Convolutional Neural Networks From Scratch Part 1
Переглядів 8 тис.3 роки тому
This is Part 1 in a series in which we create a convolutional neural network (CNN) in a spreadsheet. In this video, we teach the spreadsheet to differentiate a T from an X. We create and investigate a worked example of the formulas involved. Part 2: ua-cam.com/video/pH0s0e62GT8/v-deo.html Building and Training a Traditional Neural Net in a spreadsheet: ua-cam.com/video/fjfZZ6S1ad4/v-deo.html ua...
Training a Deep Neural Network in a Spreadsheet
Переглядів 15 тис.3 роки тому
This is Part 2 in a series in which we create and train a neural network in a spreadsheet. This covers Gradient Descent Backpropagation for a deep (2 layer) neural network that learns the XOR function. Part 1: ua-cam.com/video/fjfZZ6S1ad4/v-deo.html Sheets Template: bit.ly/NNsheet Geogebra plot: www.geogebra.org/3d/uzzwedjb More information on the Backpropagation Algorithm: ua-cam.com/video/tIe...
Training a Neural Network in a Spreadsheet
Переглядів 39 тис.3 роки тому
This is Part 1 in a series in which we create and train a neural network in a spreadsheet. This covers Gradient Descent Backpropagation for a simple (1 layer) neural network that learns the AND function. We create and investigate a worked example of the formulas involved. Part 2: ua-cam.com/video/1zwnPt73pow/v-deo.html Background information on Neural Nets: ua-cam.com/video/aircAruvnKk/v-deo.ht...
Hey, this is a great video! I noticed you made a mistake in the spreadsheet regarding UCB calculations. The parenthesis of the square root calculation are placed differently.
your entire explanation is exceptional! very intuitive yet retaining the details!
I absolutely lost it when you said to represent the pentagons we are using to represent numbers with numbers
This is amazing! Woooooo
❤😊😊
0:38 There is another major flaw with this system: It can't detect repeating digits. According to the rules, 1212 1212 1212 1210 is a valid credit card number. 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 0 = 30, which is divisible by 10.
Thank you 😊
Man that was an excellent video, but I have one question, if your column “L” is always 1, the. That would mean that that column is entirely unnecessary and can be eliminated, isn’t that correct?
Ok so I managed to play with this quite a bit and figured with a couple of these in series, you can create a macro to automate it and continually copy the weights generated after the correction back into the top of the model continuously. I’ve been running it for a few days and creating some good algorithms for some auto stock trading bots I’ve been tinkering with. What I need now is to figure out how to incorporate Fourier functions into this model. If you have any insight please chime in
I LOVE YOU
this was the best explanation on ANN i have ever seen in youtube
I am currently writing my bachelor thesis on check digit algorithms and just wanted to say: thank you so much! I just couldn't make any sense from Verhoeffs original work.
It's a dense paper for sure. Took me a few attempts to really understand it.
Smooth animations. Explains it well
Are you sure that the input to the dynamic network is the actual game state and not the representation network output?
How did I miss these vids 😮. They're amazing!
Thanks a lot for this explanation and example... Is there any way to access the excel template?... the link provided seems not to be working any longer :-( kindly, could you please either provide an updated link or send it by email? - thanks again, great video!
docs.google.com/spreadsheets/d/1wylBJWZud1R4wcSGdlMsNKRodjhs4KGkMPRK3Zt8hUA/copy
How do you use that for a demand function
Imagine someone with 0 knowledge about groupe theory watching this
Thanks Kevin. Great stuff! Makes it much more clear to see the numbers progress through the various stages of learning.
Now I will be haker , and I will be rich😊
This video is gold.
You made convolution clear, the best tutorial I found, highly recommended
Absolutely excellent tutorial, crystal clear, and many thanks for the accompanying excel sheets
A variation is used for Swedish social security number… But the difference eg between 70 and 67 in this case is the check digit!
This is EXACTLY what is needed - THANK YOU 🤟- The downloadable sheets are the icing on the cake - and ev erything becomes crystal clear - well done
This is way more crazier than building MLP from scratch with cuda.
I am a bit confused by the partial derivative of the cost with respect to the activation. In the video this partial derivative is 2(a-y). But the cost function is (y-a)^2 so the derivative should be 2(y-a)?
I think there is an extra negative sign folded in from wanting to go "downhill" towards the local minima.
@@ConceptsIlluminated Thank you for your answer. I have to admit, my calculus knowledge is poor. I think the partial derivative of cost with respect to the activation is correct in the video. I can't confirm it for myself because my lack of knowledge but I asked ChatGPT and it gave me the same result as in the video.
Great content ! underrated channel
Kevin, you are an excellent teacher!! Thank you for your efforts in making these incredible videos
After 10 hours of driving, i stumbled upon this video. Now i cant sleep as my mind engages in this topic 😅 nice video btw. I learnt something new here...
When I heard pentagons and group theory i for some reason thought youd be throwing the quintic at us
I much prefer the idea of just having two different checksum digits using different algorithms. The first checksum can check everything before the last digit, and the last digit can remain the luhn algorithm as present, this gives us extra security and since we're not using all the digits of the card number already(there's orders of magnitude less cards than possible card numbers) it's not going to cost us anything for the additional safety that'd remain backwards compatible. If you're going to go for a solution most people can't do in their heads though I suggest going all out and just use a traditional hashing algo, they munge the data each step in such a way that communitivity is lost making transpositions as obvious as a changed value(using SHA for example that uses a grid of numbers, then every time it applies a change(by bitmasking numbers together) it applies row/column shifts such that the next number would apply differently). This also requires the least effort to add to new services, every modern programming language has access to libraries that can provide access to a bunch of pre-existing hashing algorithms.
You have said only "mistyped" or other things but forgot that maybe i tried putting random fake card numbers and i juts didnt knew about these things 😂
My Lord, so cool and genius !
After reading so many blogs, papers which explained transformers, this video helped me understand the intuition behind the Query/Key and Value matrix.
This is the best video I’ve seen on this. 10/10 presentation. The genius is the simplicity but maybe bc i can comprehend spreadsheets over other ways. The mini charts were sweet, hadn’t seen hidden layers visualized like that👌
So if this is the formula to check if it is a correct number, then what is the initial formula that generates these numbers. And how do we not run out of valid numbers.
i wonder how many people went to check their credi card number after this video to see if the test works
haha. I was thinking this would be the next step to your other 2 spreadsheet videos!!! awesome!
that's Very cool! thanks! great demonstration; cool way to see all the details
Hexagons are bestagons.
Z is zet!
This video flows so well! You are an excellent storyteller!
This guy does the math
Great captioning, clarified the pronunciation of a the name of the algorithm. More content creators should act like this!
you saved my life, ty
What am I even watching that late at night, I should sleep
I’m unsure if you are taking requests but the game mastermind has logic to it that would be interesting to see in a video visualized.
These animations and game topics definitely seep in concepts effectively!
Great content and explanation! I always was looking for a channel like this!
Subscribed