[HN Gopher] Linear algebra for programmers
___________________________________________________________________
Linear algebra for programmers
Author : coffeemug
Score : 105 points
Date : 2023-09-01 17:59 UTC (5 hours ago)
(HTM) web link (coffeemug.github.io)
(TXT) w3m dump (coffeemug.github.io)
| robot_no_421 wrote:
| "In hight school your math teacher may have started a treatment
| of linear algebra by making you solve a system of linear
| equations, at which point you very sensibly zoned out because you
| knew you'd go on to program computers and never have to solve a
| system of linear equations again (don't worry, I won't be talking
| much about them here)."
|
| No offense but I stopped reading there. Too many software
| developers have this weird superiority complex when it comes to
| math. When they struggle with math, I've seen devs criticize
| everything from naming conventions to curricula to it being
| "useless". A lot of them seem unwilling to acknowledge that math
| is sometimes... simply hard.
|
| If your attitude to math is "I don't need any of this useless
| stuff, so I'll zone out", then I kindly suggest you first at
| least try to learn Linear algebra for mathematicians first.
| bbkane wrote:
| Many devs who "zone out" because they won't "need math" still
| manage to do just fine?
|
| Software is a big field and there's room for folks with
| different interests and talents.
| notsurenymore wrote:
| That's how I was in high school, and immediately regretted it
| the minute I found interest in a domain where strong math
| ability was required.
| nh23423fefe wrote:
| weird to talk about linear algebra and never invoke linearity.
|
| also, why say these 2 things?
|
| >If you forget how matrix-vector multiplication works, just
| remember that its definition flows out of the notation.
|
| >Another way to think of matrix-vector multiplication is by
| treating each row of a matrix as its own vector, and computing
| the dot products of these row vectors with the vector we're
| multiplying by. How on earth does that work?! What does vector
| similarity have to do with linear equations, or with matrix-
| vector multiplication?
|
| But you just told me to plug into the definition? Which is a dot
| product.
|
| Pretty incoherent.
| stOneskull wrote:
| i think it's a rushed draft
|
| it hasn't gone through a spell-checker, with words in there
| like hight and strage
| ak_111 wrote:
| IMO it is much clearer to justify something like matrix
| multiplication via a simple real life example like markov chain
| computations, it might add a bit of complexity in understanding
| the application but motivates the definition much better.
| adrian_b wrote:
| True.
|
| Moreover, here as in most other writings about linear algebra
| that I have seen, there is the very bad habit of describing the
| more complex operations as being composed from dot products.
|
| On modern CPUs, dot products must be avoided, because like all
| reduction operations they consist of one chain of dependent
| operations, so their speed is limited by the latency of the
| fused multiply-add operations, instead of being limited by the
| much higher throughput of the FMA operations.
|
| When vectors are multiplied with vectors, there is no
| alternative for dot products, so the only way to accelerate
| them is to reorder the operations into a tree, to be able to
| overlap a part of them, which are independent.
|
| When arrays with more dimensions are multiplied, e.g. matrices
| with vectors or matrices with matrices, the multiplications
| correspond with nested for loops, i.e. 2 nested loops for
| matrix-vector multiplication and 3 nested loops for matrix-
| matrix multiplication.
|
| The nested loops can be reordered arbitrarily. In each case,
| one of the possible loop orders has in the innermost loop the
| computation of a dot product.
|
| This is the only order mentioned in the parent article and in
| most other linear algebra manuals. However, this order is
| exactly the worst possible computationally.
|
| For 2 or more nested loops, there is always another order where
| the innermost operation is a so-called AXPY operation (the BLAS
| function name). AXPY means the scalar A multiplied by the
| vector X Plus the vector Y, with the result stored in Y. AXPY
| operations are always better than dot products, because the FMA
| operations are independent, so they can be pipelined, but for 3
| or more nested loops there are better orders, where the
| innermost loop needs much less load and store operations than
| for AXPY.
|
| For 3 or more nested loops, there is always an order where the
| innermost operation is a tensor product of 2 vectors. This is a
| more attractive operation than both AXPY and dot products. If
| the tensor product of 2 vectors with N elements is stored in
| registers, then its computation needs N+N loads from memory,
| but N*N FMA operations, so if there are enough registers so
| that N>2, there will be much more FMA than loads, allowing the
| full utilization of the execution units of a modern CPU.
|
| In conclusion, matrix-vector products must not be described as
| being composed of N dot products that are executed separately
| for each element of the result vector, but as being the sum of
| N AXPY operations, which are accumulated into the result
| vector.
|
| Similarly, a matrix-matrix product must not be described as
| being composed of N^2 dot products, one for each element of the
| result matrix, but as being the sum of N vector-vector tensor
| products, which are accumulated into the result matrix.
|
| Such descriptions would be much more useful in practice, where
| the definitions based on dot products are just a hindrance.
| Corsome wrote:
| > This is actually not so strange- you can think of many
| structures as functions. For example, you can think of a number 3
| as a function. When you multiply it by things, it makes them
| three times bigger.
|
| I don't see how 3 can be a function from this example. "3*"
| (partially applied multiplication by 3) looks more like it.
|
| Matrices and vectors as functions? Yeah, if the argument is
| within bounds. That makes it just an indexing operation.
|
| (I guess one can view 3 as a one element vector but that sounds
| like a degenerate case)
|
| Or maybe I'm missing something...?
| robot_no_421 wrote:
| 3 is the following function: 3 == lambda x: 3*x
|
| But I think that the technical, mathematical way to think about
| it is:
|
| The monoid of linear functions L:R->R is isomorphic to the
| monoid (R, *)
|
| Meaning, the structure of 1x1 matrices under multiplication is
| exactly the same as the structure of real numbers under
| multiplication.
| inimino wrote:
| Check out Peano arithmetic.
|
| Intuitively, natural numbers come from and are defined by
| counting, and that implies that "3" means inherently that
| something (could be anything) happened or was repeated three
| times. For example, if you have three apples, that means that
| you can identify one particular apple that you have, then do
| that again, then do that again.
|
| Adding a unit to a number is like adding further information on
| what it is that is being repeated. Three pairs of apples? You
| just invented the number six!
|
| The meaning of doing something three times (most abstractly:
| applying the successor function) is already inherent in the
| meaning of three, so multiplication isn't something that has to
| be added on top. It's already in there.
| ajtulloch wrote:
| I think the mathematical concept that you are looking for is
| that of the dual space. Essentially if you have a vector space
| V, you can construct a dual space V* where the elements of the
| dual space are functions taking elements of V to the underlying
| field F, and under certain conditions these spaces are
| isomorphic (the same) - so there is a 1:1 correspondence
| between elements of the vector space and the functions in the
| dual space.
| denial wrote:
| I take it as analogous to the association of a matrix to a
| linear transformation. This association is via multiplication.
| thewataccount wrote:
| Can anyone suggest a something that teaches Linear Algebra with a
| practical applications, especially for software engineering?
|
| I can sorta kinda get the theory, but every demonstration
| involves moving an arrow around which is.... not something I need
| to do frequently. So I'm not sure how I actually apply linear
| algebra to solve actual problems.
|
| I'm a software developer and I know it's useful I just don't get
| where to use it - and I'm struggling to actually understand the
| different operations, purpose of the dot product, etc. I have a
| decent base for basic stats and calc, both of which I can
| "conceptually apply" near daily for understanding how things
| work.
|
| 3Blue1Brown is helpful, but I just kinda go "yeah I guess that
| looks right" without knowing what to do with it.
|
| EDIT: Thank you!
| cratermoon wrote:
| Much of the use of linear algebra in programming is for machine
| learning. To a first approximation, ML is statistics on huge
| datasets, and linear algebra makes it possible because matrix
| operations are massively, if not embarrassingly, parallel.
| farrelle25 wrote:
| I found a lot of practical CS applications in this one:
|
| "Coding The Matrix: Linear Algebra Through Computer Science
| Applications" https://codingthematrix.com/
|
| It used to be on Coursera too, has video lectures and a book to
| go with it.
| gensym wrote:
| I endorse this as well. I worked through the course back when
| it was on Coursera, and thoroughly enjoyed it. I've also
| found what I learned applicable many times since - most
| recently when experimenting with some computer vision
| algorithms.
| nextos wrote:
| Boyd & Vandenberghe's new book:
| https://web.stanford.edu/~boyd/vmls
|
| It has companion code in Julia and Python, and addresses many
| important applications, such as convex optimization where the
| authors' previous book is really famous.
| latenightcoding wrote:
| Fast ai had a computational linear algebra class iirc
| ndriscoll wrote:
| I don't know a recommendation to make; probably it makes more
| sense to find a field your interested in (pretty much any STEM
| field will do), and learn the more math heavy version of that.
| Inevitably linear algebra will come up, giving some motivation
| for the pure theory.
|
| As for why it comes up so much, it concerns itself with solving
| systems that look like y = Ax + b, where the Ax term works
| similarly to multiplication in 1-D. The point is these simple
| equations are ones we can actually understand! Everything else
| is too hard.
|
| But there's a trick we have for everything else: if you have
| some y = f(x) where f is super complicated, you can
| differentiate. The derivative of f at a point x_0 is the best
| linear approximation to f. i.e. f'(x_0) is the best matrix A
| such that y ~= Ax + b near x_0. Now your problem is linear and
| you can understand it (locally)! Then you can integrate your
| local solutions into a global one.
|
| The purpose of dot products is that they let you talk about
| things like angles, lengths, and projections. The point is you
| learn how it works for arrows and shadows and stuff, and figure
| out some equations that hopefully make intuitive sense in 2-
| and 3-D, and then it turns out those equations work in higher
| (even infinite) dimensions too.
|
| Projections are useful because they let you break vectors down
| and build them back up, and hopefully the broken down version
| is easier to understand. Understanding projections in high or
| infinite dimensions gives some intuition for things like the
| Fourier transform, where you project a function onto simpler
| waves, maybe study how a system reacts to those waves, and then
| use that description to build back how up the system reacts to
| your original function.
|
| Angles give one way to measure closeness. If you have some
| machine learning model that figures out a way to map text into
| a 50,000 dimensional space, you might be able to do it in a way
| where two sentences are intuitively similar if they are mostly
| pointing off in the same directions, so if the angle between
| them is small.
|
| So tl;dr the idea is you learn some geometry with arrows and
| all that, you figure out some equations from that geometry, and
| then you realize that those equations and that geometric
| intuition work anytime you have a linear (i.e. f(ax+b) = af(x)
| + f(b)) system. Calculus gives you ways to turn non-linear
| problems into linear ones, so you will find examples of linear
| systems everywhere.
| ak_111 wrote:
| Look into making a Doom-like game, tons of linear algebra
| there.
| tptacek wrote:
| One place to start might be a tutorial on principal component
| analysis, which will take you through some of the intuitions
| for applying SVD.
|
| You can also go in the direction of cryptography; here's, for
| instance, a really excellent LLL tutorial that builds on
| Graham-Schmidt: https://kel.bz/post/lll/
| anon____ wrote:
| This is the PCA tutorial that worked for me:
| https://arxiv.org/abs/1404.1100.
| dlevine wrote:
| Imperial College has a pretty good course on Linear Algebra for
| Machine Learning on Coursera. It's part of their Mathematics
| for Machine Learning Specialization. Deep Learning also has a
| course that appears to be similar.
|
| The specialization as a whole starts simple, and works its way
| up to PCA.
|
| https://www.coursera.org/specializations/mathematics-for-mac...
| marginalia_nu wrote:
| I strongly suggest anyone getting into Linear Algebra to have a
| project to work on. It makes everything so much easier when you
| get to play with the stuff.
|
| My hint for something to play with is that basic linear algebra
| applies _very_ directly to graphics, rotation matrices and so on.
| If you know how to multiply a matrix with a vector, you basically
| know what you need to render basic line-art 3D graphics. May want
| to look into dot and cross products as well as vector projection,
| but it 's fairly basic all of this.
| [deleted]
| paulsmith wrote:
| Deep learning! It's all "just" (more or less) high school
| calculus (partial derivatives, chain rule) and matrix
| multiplication.
| thewataccount wrote:
| I feel like I saw one once but lost it -
|
| Is there a githubrepo/tutorial for how linear algebra is used
| for a very small model just to demonstrate how that allows it
| to "learn"?
|
| I've got the calc, I just don't understand what the matrix
| multiplication "does"
| tstrimple wrote:
| I cannot recommend Andrew Ng's courses on Machine Learning
| enough. Something like this seems like it would cover
| everything you're looking for.
|
| https://www.coursera.org/learn/machine-learning
|
| I cannot speak to the author of the content of this github
| repo, but it appears they have completed the course and
| included all of the solutions here. It might let you jump
| right to what you're looking for.
|
| https://github.com/greyhatguy007/Machine-Learning-
| Specializa...
| paulsmith wrote:
| Watch Karpathy's recent lectures. They're gold. Start
| here[1] with micrograd[2]. It doesn't use linear
| algebra/matrices to start, but the principles are the same.
| The matrix multiplication is how the weights of the
| connections between neurons and the input values are
| combined (to form an activation value that then may lead to
| that neuron "firing" or not, depending on whether it passes
| some threshold function). We use matrices to model the
| connections between neurons - each row is a connection, and
| each column is a weight corresponding to an input.
|
| [1] https://www.youtube.com/watch?v=VMj-3S1tku0 [2]
| https://github.com/karpathy/micrograd
| seanmcdirmid wrote:
| I did this awhile ago, but found myself simply copying and
| tweaking graphics algorithms, rather than gaining any intrinsic
| understanding of what linear algebra is really doing. I guess I
| just didn't have enough computer graphics background? Yes, I
| can use lighting equations to define a pixel shader, but I'm
| basically copying and translating the algorithm from a book.
| marginalia_nu wrote:
| No I mean do full software rendering, no shaders, no graphics
| card.
| SotCodeLaureate wrote:
| > No I mean do full software rendering, no shaders, no
| graphics card.
|
| But why?
|
| There doesn't seems to be a lot to learn about applied
| linear algebra (in the sense discussed here) by
| implementing a rasterizer.
|
| But there is plenty of LA above and below that (in the
| scene management, in the shaders).
| marginalia_nu wrote:
| Eh, it's basically a project consisting entirely of the
| parts of LA that the article is talking about.
| delusional wrote:
| I'm sorry if this comes across as curt, but can't you just
| decide to not do that? Decide to not look at the examples in
| the book, but write it from the explanation instead. You
| could even forego the book and just sit down with a piece of
| paper and do the work from first principles. You might not
| come up with the most efficient algorithm, but you'll have a
| foothold into understanding the one you can then go and look
| up.
| ivan_ah wrote:
| If anyone wants to try things hands-on, I highly recommend the
| SymPy (in particular the online live shell
| https://live.sympy.org/ ). The `Matrix` class can be used to
| create matrices (lists of lists of numbers) and vectors (lists of
| numbers). Here is a clickable link that demos the first example
| rotation:
| https://live.sympy.org/?evaluate=A%20%3D%20Matrix(%5B%5B0%2C...
|
| For more info about SymPy, see section "VI. Linear algebra" in
| the SymPy tutorial I wrote
| https://minireference.com/static/tutorials/sympy_tutorial.pd...
| (also available as notebook
| https://github.com/minireference/sympytut_notebooks/blob/mas... )
| ivan_ah wrote:
| Oh and for even more linear algebra stuff, here is a 30 min
| condensed video tutorial that introduced most of topics in a
| standard LA course, also using SymPy to show demonstrations:
| https://www.youtube.com/watch?v=2G3PmEZI6n8&list=PLGmu4KtWiH...
___________________________________________________________________
(page generated 2023-09-01 23:01 UTC)