Talks
Not so Neo in the Matrix
Summarized using AI
Not so Neo in the Matrix
by Micah AdamsIn the talk titled "Not So Neo in the Matrix," Micah Adams presents an engaging overview of matrices, their applications, and implications in programming and real-life scenarios. The primary aim is to demystify matrices, illustrating their relevance beyond just advanced mathematical contexts.
Key points discussed include:
- The prevalence of matrices across various programming fields and everyday tasks, driven by Adams' own experiences, particularly in graphics programming and applications such as virtual reality.
- A personal journey of rediscovery highlighted how matrices are omnipresent in code yet often unnoticed until explicitly called out. Adams encourages awareness rather than just mastery of this data structure.
- Basic definition and structure of matrices; understanding how matrices are essentially multi-dimensional arrays, and their relational properties with vectors.
- Practical applications:
- Graphics programming: Adams explains how transformations of geometric shapes like triangles use matrices to scale, translate, and rotate through specific operations.
- Probability distributions: Matrices can represent probability states, exemplified with a Markov matrix demonstrating weather conditions.
- Cryptography: Basic ciphers utilizing matrices for transformations, stressing the need for modern approaches in security.
- Relational data: Social network analysis using force-directed graphs linked to matrices, showcasing how relationships can be depicted effectively.
- Introduction to fields and vectors, explaining their significance in structuring computations and solving mathematical problems, using Galois fields as a crucial example in computer science.
- Several coding examples, with a highlight on using matrices in Dungeons and Dragons (D&D) for character data organization and game mechanics, emphasizing practical application in game development.
- The importance of libraries like Ruby’s matrix library that facilitate complex matrix operations and the possibility to utilize them in algorithms like the Levenshtein distance for string analysis.
In conclusion, Adams emphasizes that matrices significantly simplify and enhance programming practices and could be used as foundational structures in various computing fields, urging programmers to recognize when matrices can benefit or hinder performance. The talk invites questions and discussion, reinforcing the community aspect of programming and learning. By the end of the presentation, attendees are encouraged to be more mindful of matrices in their coding practices and explore new ways to implement them effectively.
00:00:14.240
Hey, good morning everybody! I don't know if someone was supposed to introduce me, but it's 10:41, and I like to be punctual, so let's get started. I'm really excited to be here.
00:00:22.289
It's my first time at RubyConf and my first time speaking here, so it should be pretty cool. Plus, I've been listening to hip-hop all morning to get pumped up for this talk. My name is Micah Adams.
00:00:38.879
I work for Mode Set, which is a software consultancy based out of Denver. We focus on early-stage startups, doing development work for them with the goal of getting our startups from Series A to Series B funding. Most recently, we worked with Ello, which is an ad-free social network. If anyone's on that, pretty cool!
00:01:00.210
The title of my talk is 'Not So Neo in the Matrix.' You're probably wondering why I chose matrices. There are likely a few groups in this audience: some of you probably use matrices all the time and are great at it, so I ask that you be kind to me during the Q&A session and don’t grill me too hard.
00:01:26.340
Others of you might not use matrices at all; maybe you are newer to programming or don’t have a formal background in it. And some of you might be like me, having rediscovered how useful matrices are, especially after forgetting how often we use something like code.
00:01:51.660
For me, this reintroduction started during a brief foray into OpenGL programming on Android. I had a client who wanted us to develop a virtual reality application using Google's Cardboard headset and SDK. I completed it in just a couple of weeks, and as I worked, I started noticing matrices everywhere.
00:02:03.570
I began seeing matrices in my sleep, on the streets while walking, and in old code I had previously reviewed. It became a bit of an obsession for me, realizing how much I used them versus how aware I was of that usage.
00:02:26.760
I formulated a simple hypothesis: matrices are useful in a variety of situations, and not just in the OpenGL project I was working on. They are implemented everywhere and across many different domains. I wanted to explore this hypothesis through this talk.
00:02:58.630
What I found was that I had forgotten how prevalent this data structure is. I constantly use matrices, but I had never stopped to consider why I was using them. I have also deeply repressed memories of calculating the inverse of a 3 by 3 matrix by hand—something I might need therapy for! Has anyone else done this? Math majors, perhaps?
00:03:19.990
It is brutal—the amount of calculations needed! We have to be thankful that computers exist to handle these tasks for us. Another domain I found matrices useful in is Dungeons & Dragons, which I consider a great area to explore new programming patterns.
00:03:39.010
I am an ultra-mega Dungeons and Dragons nerd; I've been playing since I was seven years old and own every edition of the game. I have even considered getting a Gary Gygax tattoo! Given my domain expertise in D&D, I found that exploring new programming concepts through my knowledge in D&D would help me flush out those ideas.
00:04:16.180
In this talk, I hope you leave with a renewed interest in matrices. I want you to become more aware of when you use them in your code, and importantly, know when to remove them. In one of the code examples, I have a matrix that is just brute-forcing code, which is not always appropriate; there are instances where it is suitable.
00:04:39.490
But, as someone who gets obsessed with concepts, you might find yourself trying to insert matrices everywhere, even in places they don’t belong. So the caveat is that your mileage may vary depending on the code examples presented.
00:05:07.530
The aim of this talk is not to teach you how to use matrices, but rather to increase your awareness of them and how they might be used. If you don't need it, please, leave it out; there are times when it just isn't performing well.
00:05:31.260
For those who may be uninterested and need coffee, here’s the too-long-didn’t-read version: matrices are essentially just multi-dimensional arrays, while vectors are similar to arrays. I hope I just blew your mind with that revelation! However, the context surrounding them fleshes out this talk, and we will explore that in greater detail.
00:06:02.220
We will talk about fields and some mathematical concepts around them, vectors and matrices, and then we will go through three code examples to illustrate these points.
00:06:20.030
So, what the heck is a matrix, anyway? Simply put, it is an array of elements organized into rows and columns. We can think of a matrix as being composed of vectors. A column in a matrix is a vector, while a row in a matrix is also a vector. The elements of a matrix are considered to be over what we call a field.
00:06:56.990
This prompts the question: when should you actually use a matrix? The snarky, grumpy developer in me wants to say, 'It depends!' However, one way to determine when it's appropriate is to look at situations where matrices, vectors, and the math around them are used in programming.
00:07:30.480
The first example everyone thinks of when discussing matrices or matrix manipulation is graphics programming, where mathematical primitives like polygons are manipulated. While I don’t want to delve too deeply into three-dimensional programming, I will provide a brief overview of how vectors and matrix manipulation can be applied to two-dimensional shapes for an initial introduction.
00:08:10.910
What you’re seeing here is a little animation of a triangle scaling over time, effectively throbbing. How is this achieved? The triangle consists of vertices, which represent the three points of the triangle. We apply a transformation to make the triangle grow and shrink, which is done by multiplying the vertices of the polygon by a vector.
00:08:37.590
This scaling is multiplicative—we can increase the size of the triangle this way. Another transformation we can apply is translation, which involves moving the triangle around on the X and Y coordinates to position it in space. Additionally, we can rotate the triangle's vertices, where this transformation involves applying a matrix of sine and cosine to perform the rotation.
00:09:10.560
As I said, there’s so much more to discuss regarding three-dimensional programming and its scope. My purpose today is to simplify the concept of matrices, but if there are graphics enthusiasts in the audience, we can delve deeper during the Q&A session.
00:09:27.350
So, what are some other applications of matrices and vectors that we may not think about? One example is representing probability distributions in a matrix. Here’s a Markov matrix: the first row breaks down the probability distribution of whether it will be rainy or dry, and each row sums to one.
00:09:44.420
This essentially shows the state of a system. Matrices can also be used in cryptography, such as with ciphers. Here's an example of a Caesar cipher with a shift value of three. When using it, for the input 'a', I would shift that letter to 'D', and so forth.
00:10:07.430
This is quite primitive in comparison to modern ciphers. If you are storing passwords using this technique in a database, leave now! Furthermore, we can visualize or understand relational data with matrices. For instance, this is a force-directed graph used in social networking that depicts relationships between people.
00:10:30.870
In this graph, if note one has a connecting edge to note four, we can reference the relationships via a matrix as we would in a coordinate map. If I want to check the relationships for note four, I would look at the column denoted before and notice that it only contains a self-referential relationship.
00:10:54.740
These matrices are significant, and while we won’t dive too deeply into graph structures, understand that in many cases, you will store this data in a matrix format.
00:11:13.570
Now let's discuss more mathematical concepts related to fields. A field is a collection of numbers with properties defined by operations such as addition, subtraction, multiplication, and division. You can think of a field as a class that adheres to an interface defining these methods.
00:11:37.210
For instance, the field of real numbers can encompass rational and irrational numbers, be they positive, negative, or zero. These numbers implement the aforementioned methods, and in reality, there are infinite elements in this field. However, it can be challenging to conceptualize a matrix in terms of infinite elements.
00:12:02.680
Instead, we find a better example of a field commonly used in computing: the finite field or Galois field. This field contains a finite number of elements. Can anyone guess what finite field I'm alluding to? It consists of two integers: 0 and 1.
00:12:27.750
The finite field I am referring to is Galois field two, employed in binary representation. This field is useful in computations for its excellent properties as demonstrated in addition operations.
00:12:52.970
In fact, addition in Galois field two is represented as a matrix with a unique boolean property—exclusive or. With this, you can toggle bits; this fundamental operation serves as the basis for encryption. In this context, a plaintext bit is represented in one column, the key in another, and the output ciphered in a final column.
00:13:12.580
This leads to the observation that having a truly random key can achieve perfect secrecy, which is a theoretical concept because, in practical applications, things are often decrypted or reverse-engineered.
00:13:37.350
Now that we’ve meandered through finite fields, let’s move onto vectors. Knowing what we now understand of a field, we can define a vector as a list of scalars over the specific field, and they are also comprehended as components of matrices as we’ll soon see.
00:14:01.020
Here’s an example of a vector over the field of real numbers. In Ruby, that exists as an array. Below that, we can also illustrate a vector over Galois field two. Vectors can be referenced functionally in programming to retrieve items via their index, a concept that’s consistently utilized.
00:14:35.820
The Ruby matrix library includes a vector class for when you need to execute more intensive computations, allowing access to various matrix operations.
00:15:03.320
Earlier, we discussed fields and vectors, so what is a matrix? In coding, we frequently use multi-dimensional arrays to represent matrices, or alternatively, you can access the Ruby matrix library.
00:15:27.010
We will view an example in this talk to demonstrate how to employ the matrix library, which provides several additional methods to facilitate complex calculations. There are also various contributed and open-source libraries available like NMatrix that can assist in more complex math.
00:15:54.120
Now, let's transition into code examples. My favorite example, as you might expect, is Dungeons and Dragons, where using matrices and vectors for manipulating relational data is illustrated.
00:16:19.570
For those of you unfamiliar with D&D, think of it as a classic role-playing game akin to World of Warcraft, but played with pen and paper. In this game, you have a party of characters and a dungeon master who runs the session.
00:16:42.200
D&D comprises a lot of static data that contains inherent relationships. Throughout your adventure, you gain levels, enhancing your abilities based on the experience points you collect from slaying enemies and obtaining loot.
00:17:08.930
Depending on your character's class—like rogue or mage—your abilities differ, making your strengths in battle unique. For instance, a level 10 mage is far less skilled in melee combat than a level 10 warrior.
00:17:35.510
This relationship between experience points, character levels, and proficiency bonuses inspired me to create a character generation tool for D&D to help generate character sheets. This tool could provide snapshots of a character's abilities and attributes at different points along their career.
00:18:03.370
I wanted to avoid using full Rails stack or a persistent back-end; instead, I aimed at just creating a web form generating these character sheets. Much of the character data is static, giving it a structure suitable for organizing in a matrix.
00:18:30.650
For example, I was inspired to model the relationship between character levels, experience points, and proficiency bonuses. I created a matrix to represent this static data; it’s a multi-dimensional array that's not overly interesting mathematically but is very practical.
00:18:56.840
If I know the levels and the required experience points, I can zip these values together into a more complex array, establishing a look-up table. One downside of multi-dimensional arrays is that you must know the exact row and column numbers to retrieve specific data.
00:19:22.540
Alternatively, you can shift that table into a hash to make it more human-readable. Using a hash simplifies defining references, making it easier to iterate through data without worrying about column and row numbers.
00:19:50.450
While a mere table representation works, what if we seek to illustrate more complex data relationships? We may represent classes through a composite approach or break down character elements like abilities into vectors.
00:20:21.860
For D&D abilities, there are six key scores: strength, dexterity, constitution, intelligence, wisdom, and charisma. I decided to model those score vectors within Ruby as symbols per ability and vectorize the levels as well.
00:20:47.690
By utilizing these classes and vectors, I can create a comprehensive character advancement table, making it easier to refer to the level and experience points as part of character development.
00:21:16.370
This method provides a more complex data structure that can be referenced easily but does not offer the robust querying capabilities of a relational database.
00:21:40.480
Additionally, we can explore a more mathematical approach by solving systems of equations with matrices. This involves utilizing the Ruby matrix library to tackle linear equations, something many of us might have experienced in school.
00:22:04.560
If we were to solve a small system of equations, we start by creating a coefficient matrix from values such as 2, 10, and 8 for one equation, while possibly assigning 0 to represent a missing variable.
00:22:29.280
Following this, we collect the constant values for the equations in another matrix. Thanks to computers, we don’t have to go through the tedious calculations ourselves.
00:22:54.910
Working out the inverse of a matrix is quite complex and involves multiple steps. Thankfully, we can utilize library functions to perform these operations much more quickly than doing it manually.
00:23:18.470
Using the matrix operations available, we can multiply the inverted coefficient matrix by the constants matrix to yield our solutions cleanly. Such matrix operations can be handy when modeling problems.
00:23:43.810
Remember, these patterns appear whenever linear equations are employed, which can happen more frequently than expected, particularly when working with comparisons.
00:24:06.820
Next, we’ll explore using a matrix as an internal data structure in algorithms. Specifically, we will use matrices to calculate the edit distance between strings.
00:24:32.750
This algorithm, known as the Levenshtein distance algorithm, aims to transform a source string into a target string, calculating the score associated with deletions, insertions, or substitutions required for the transformation.
00:25:00.270
The core idea is that the greater the edit distance score, the more dissimilar the two strings are. The algorithm starts by creating a matrix using the lengths of the source and target strings.
00:25:28.810
This sets up the necessary rows and columns for comparison. By iterating through both strings, we can assign scores based on differences at the position determined by our matrix.
00:25:56.780
Interestingly, the essential scores build up along the diagonal of the matrix, following the iterations, so we can visualize the comparison process as it unfolds.
00:26:25.120
As we step through the pairs of characters from both strings, we determine the scores for those pairs and store them in the corresponding matrix position. The score computation considers the minimum from three potential paths: insertion, deletion, or substitution.
00:26:53.570
To illustrate this, let's assume our source string is 'Micah' and our target string is 'Elis'. We can initialize a matrix to hold the intermediate scores for each character position.
00:27:20.330
We begin filling the matrix, iterating character positions between the two strings until we end up with the final score for the edit distance computation.
00:27:49.460
While this method of calculating is not the most performant, it offers a simple entry point into understanding how matrices can be employed in algorithms to solve string-distance problems.
00:28:17.880
Wrapping up this exploration, we've discussed fields and the relational properties that matrices provide, learned how to model linear equations, and implemented algorithms like the Levenshtein distance.
00:28:53.380
In conclusion, matrices serve various purposes. They can structure data to clarify relationships, optimize solutions for systems of equations, and simplify transformations in graphical programming.
00:29:23.460
Furthermore, matrices sometimes serve as data structures in algorithms, which may initially seem brute-force but can yield results.
00:29:50.330
Now, I want to open the floor for questions. If anyone has inquiries about the talk or would prefer to discuss Dungeons and Dragons, that’s fine too!
00:30:14.850
I’ll repeat the questions for clarity. The first question is: Is the matrix library part of the standard library? Yes, it is! I initially struggled with some quirks in the matrix library, but overall, the documentation is quite reliable.
00:30:37.490
Another question was concerning the expected overall performance of matrix math versus solving systems of linear equations. Honestly, I currently don’t have that knowledge.
00:31:05.470
Furthermore, someone inquired about GPU acceleration for matrix manipulation, and while I haven't employed that, I remember OpenGL handling several operations behind the scenes.
00:31:25.220
Lastly, the final question revolved around predictive modeling using matrices, particularly for data analysis purposes—yes, matrices can be used effectively in machine learning algorithms or genomic data analysis.
00:31:51.760
Thank you all for your time and for being part of this talk today. Your engagement and questions are greatly appreciated!
Explore all talks recorded at RubyConf 2015
+75