3 ms·
Graph Algorithms for Data Science
- dragontamer 6y agoWhen I was studying Reed Solomon the other day, I came across an interesting graph algorithm for error correction codes. Turns out there are tons of graph ECC out there. Viterbi algorithm is one, and LDPC is another. I don't understand them, but clearly graphs can be used in many obscure situations.
- Anon84 6y agoSubstack author here. These sound interesting. Can you point me to them? I would be interested in taking a look
- dragontamer 6y agoI'll try, but as noted earlier, I really don't understand what is going on yet. http://ipsit.bu.edu/phdthesis_html/node8.html http://ipsit.bu.edu/phdthesis_html/node8.html The above PHd thesis explicitly talks about the Trellis graph constructed for the Vertibi algorithm based Error Correction. It's complicated, there are matrix representations of these graphs too. It seems like information theorists have many mental models of what is going on, and they just fluidly switch between their mental models without sweating. It makes for a frustrating read, to say the least. ------ Application wise: Vertibi ECC is used for earlier Wifi 802.11... while LDPC is newer like 802.11n or so. Really low level stuff, I'm curious about it but don't really have an application in mind. Just found it curious that it's technically a graph algorithm
- Anon84 6y agoThank you. I’ll check it out
- dragontamer 6y agoYou might have better luck consulting actual textbooks. I don't think what I've found on the internet is very clearly written. I'm seriously considering buying some textbooks on coding theory, but since this is just idle curiosity... I'm not sure if its worth the effort, lol.
- Anon84 6y agoI come from a very different background, so it’s mostly idle curiosity as well. I’ll take a look and if something looks interesting I might dig into it in a post or two
- dragontamer 6y agoLooking over those PH.D thesis pages... something to note: * codeword = data * generator_matrix * codeword * check_matrix = 0_vector * senseword = codeword + error_vector * senseword * check_matrix = syndrome_vector (Yeah, this field likes "horizontal" data vectors. Its weird but you get used to it...) ------ The job of error correction is usually to convert sensewords back into data. Sensewords represent "what the receiver sensed". If no errors occurred, its usually very easy to convert sensewords back into data... but if an error occurred, then you must calculate the syndromes and then figure out a methodology to correct the errors. Coding schemes set up the matrix in different ways. It seems like Vertibi Algorithm has a graphical representation of the matrix, or something... I still don't understand it but hopefully this post of mine can give you a leg up in understanding what's going on.
- MeteorMarc 6y agoI only read marketing here: promises and a need to leave your emailaddress.
- Anon84 6y agoTrue, there isn’t much there yet. It was just launched today, after all. If you want to check out something a bit more substantive, how about this: https://github.com/DataForScience/Causality https://github.com/DataForScience/Causality
- kinow 6y agoYeah, it could be very interesting, but without any preview of past issues, or of what kind of message/content I'd receive it's hard to subscribe. Good initiative though, hopefully author is reading this thread and will update it.
- Anon84 6y agoI’m the author, and definitely will. Aiming for a 2+ posts a month. In the GitHub repo above you have links to other blogposts by yours truly