[HN Gopher] Graph Algorithms for Data Science
___________________________________________________________________
Graph Algorithms for Data Science
Author : Anon84
Score : 31 points
Date : 2021-01-10 15:05 UTC (7 hours ago)
(HTM) web link (graphs4sci.substack.com)
(TXT) w3m dump (graphs4sci.substack.com)
| dragontamer wrote:
| When 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 wrote:
| Substack author here. These sound interesting. Can you point me
| to them? I would be interested in taking a look
| dragontamer wrote:
| I'll try, but as noted earlier, I really don't understand
| what is going on yet.
|
| 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 wrote:
| Thank you. I'll check it out
| dragontamer wrote:
| You 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 wrote:
| I 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 wrote:
| Looking 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
|
| ------
|
| 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 wrote:
| I only read marketing here: promises and a need to leave your
| emailaddress.
| Anon84 wrote:
| True, 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
___________________________________________________________________
(page generated 2021-01-10 23:03 UTC)