4 ms·
I've been running into the idea of computational graphs a lot recently. It's at the core of Tensorflow (and NN in general) but it also comes up for example in A
by adamnemecek 10y ago
I've been running into the idea of computational graphs a lot recently. It's at the core of Tensorflow (and NN in general) but it also comes up for example in Apple's AVFoundation where all audio processing happens in a graph of audio units. Does anyone know what's the theoretical foundation of computational graphs?
EDIT: I've created a wiki page for computational graphs. https://en.wikipedia.org/wiki/Computational_Graph https://en.wikipedia.org/wiki/Computational_Graph. Add your input.
- mtrn 10y agoThere is the biological analogue, which has inspired neural networks: > Recall that in our general definition a feed-forward neural network is a computational graph whose nodes are computing units and whose directed edges transmit numerical information from node to node. > Each computing unit is capable of evaluating a single primitive function of its input. In fact the network represents a chain of function compositions which transfor m an input to an output vector (called a pattern). From: https://page.mi.fu-berlin.de/rojas/neural/chapter/K7.pdf https://page.mi.fu-berlin.de/rojas/neural/chapter/K7.pdf (1996) Another ancestor would be the Data-Flow paradigm: > .. programming paradigm that internally represents applications as a directed graph, similarly to a dataflow diagram. Applications are represented as a set of nodes (also called blocks) with input and/or output ports in them. These nodes can either be sources, sinks or processing blocks to the information flowing in the system. Nodes are connected by directed edges that define the flow of information between them. From: https://paginas.fe.up.pt/~prodei/dsie12/papers/paper_17.pdf https://paginas.fe.up.pt/~prodei/dsie12/papers/paper_17.pdf (2012)
- adamnemecek 10y ago> There is the biological analogue, which has inspired neural network I'm somewhat aware but it seems like the idea of a computational graph is the most generic computational idea I can think of and I'm surprised it's not more explored. > Another ancestor would be the Data-Flow paradigm: Oh yeah, data flow is definitely another one.
- throwawayish 10y ago> I'm somewhat aware but it seems like the idea of a computational graph is the most generic computational idea I can think of and I'm surprised it's not more explored. ASTs?!
- adamnemecek 10y agoYeah, I think that ASTs are only a special case of computational graphs.
- Jasper_ 10y agoFunctional programming can be represented as a graph, where calls are directed edges. Flow control is often analyzed in graph form in real compilers: https://en.wikipedia.org/wiki/Control_flow_graph https://en.wikipedia.org/wiki/Control_flow_graph
- adamnemecek 10y agoIt's not just functional programming (but I do agree that it's better in functional programming). All the reverse engineering tools have some feature to represent assembly as a CFG which is super helpful.
- throwaway91111 10y agoI think an SSA DAG might apply here as well.
- YeGoblynQueenne 10y ago>> Does anyone know what's the theoretical foundation of computational graphs? Automata can be represented as graphs- that's the main idea. When you look at the typical automaton diagram with states and transitions- that's a graph (with states as vertices and transitions as edges). I think the confusion arises from the fact that, while automata can be represented as graphs, graphs can represent a much broader array of processes and objects (e.g. belief networks or semantic networks). I guess you can represent pretty much anything as a graph. So "computational graph" as I understand it, just stresses the point that what is represented is a unit of computation (a.k.a. an automaton a.k.a. a grammar a.k.a. a language etc. etc.) rather than some other kind of graph.
- adamnemecek 10y ago> So "computational graph" as I understand it, just stresses the point that what is represented is a unit of computation (a.k.a. an automaton a.k.a. a grammar a.k.a. a language etc. etc.) rather than some other kind of graph. Exactly. I think that the fact that the nodes represent a unit of computation is enough for it to be different from normal graphs I think.
- dluther 10y agoRelated: directed acrylic graphs. https://en.wikipedia.org/wiki/Directed_acyclic_graph https://en.wikipedia.org/wiki/Directed_acyclic_graph