topos 0.13.0

An autodiff compiler stack in Rust.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

use smallvec::smallvec;

use crate::{Element, Recordable, Shape, Tensor};

use super::{Cotangents, Operation, Reads, binary};

/// The rows of a gradient scatter-added into a table by a one-hot
/// selection, with operands `[gradient, selection]`:
/// [`Gather`](super::Gather)'s adjoint, [`Recordable::scatter`] as a
/// node. The result's row count is the selection's vocabulary — its
/// second axis — so the operation carries no parameters.
///
/// It exists as an opcode because `gather`'s derivative rule speaks
/// `scatter`, so recorded gradients of embedding lookups need it on
/// the tape. The compact form is deliberate: composing the same map
/// as `matmul(transpose(selection), gradient)` is exact mathematics
/// but densifies the one-hot at embedding scale. The gradient of the
/// scattered operand is the incoming gradient gathered back by the
/// same selection — the pair is adjoint in both directions — and the
/// selection is data, not a differentiable dependency.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) struct Scatter;

impl Scatter {
    /// Returns the arity: two operands.
    pub(crate) fn arity(&self) -> usize {
        2
    }

    /// Returns the read set of the derivative rule below.
    /// It reads the selection payload (the gather needs its indices);
    /// the gradient contributes nothing.
    pub(crate) fn reads(&self) -> Reads {
        Reads {
            operands: [false, true],
            output: false,
        }
    }

    /// Infers the result shape `[vocab, ...gradient.shape[1..]]`,
    /// requiring the selection to be rank 2 with one row per gradient
    /// row.
    pub(crate) fn infer_shape(&self, operands: &[Shape]) -> Shape {
        let (gradient, selection) = binary(operands);
        assert!(
            gradient.rank() >= 1,
            "scatter needs a gradient with a leading selection axis, got {gradient}"
        );
        assert_eq!(
            selection.rank(),
            2,
            "scatter selection must be rank 2 [count, vocab], got {selection}"
        );
        assert_eq!(
            selection.axes()[0],
            gradient.axes()[0],
            "scatter gradient rows {} disagree with the selection count {}",
            gradient.axes()[0],
            selection.axes()[0]
        );
        Shape::new(std::iter::once(selection.axes()[1]).chain(gradient.axes()[1..].iter().copied()))
    }
}

impl Scatter {
    pub(crate) fn forward<E: Element>(&self, operands: &[&Tensor<E>]) -> Tensor<E> {
        let (&gradient, &selection) = binary(operands);
        gradient.scatter(selection)
    }
}

impl<Rule: Recordable> Operation<Rule> for Scatter {
    fn backward(&self, operands: &[&Rule], _output: &Rule, gradient: &Rule) -> Cotangents<Rule> {
        let (_, &selection) = binary(operands);
        smallvec![Some(gradient.gather(selection)), None]
    }
}

#[cfg(test)]
#[path = "tests/scatter_tests.rs"]
mod tests;