feedback#
The free feedback category, i.e. diagrams with delayed feedback loops.
We follow the definition of Di Lavore et al. [DLdeFeliceRoman22] with some extra structure
for the head and tail of streams with the FollowedBy
generator.
The main example of a feedback category is given by discopy.stream
.
Summary#
A feedback object is an object with a time_step and an optional argument is_constant for whether the object is interpreted as a constant stream. |
|
The head of a feedback object, interpreted as the first element of a stream followed by the constant stream on the empty type. |
|
The tail of a non-constant feedback object, interpreted as the stream starting from the second time step. |
|
A feedback type is a monoidal type with delay, head and tail. |
|
A feedback layer is a monoidal layer with a delay method. |
|
A feedback diagram is a markov diagram with a |
|
A feedback box is a markov box in a feedback diagram. |
|
The swap of feedback types |
|
Feedback is a bubble that takes a diagram from dom @ mem.delay() to cod @ mem and returns a box from dom to cod. |
|
The isomorphism between x.head @ x.tail.delay() and x. |
|
The head of a feedback diagram, interpreted as the first element followed by the identity stream on the empty type. |
|
The tail of a feedback diagram, interpreted as the stream starting from the second time step with the identity on the empty type at the first step. |
|
A feedback category is a markov category with methods |
|
A feedback functor is a markov one that preserves delay and feedback. |
Axioms#
A feedback category is a symmetric monoidal category with a monoidal
endofunctor Diagram.delay()
, shortened to .d and a method
Diagram.feedback()
of the following shape:
>>> from discopy.drawing import Equation
>>> x, y, m = map(Ty, "xym")
>>> f = Box('f', x @ m.delay(), y @ m)
>>> Equation(f, f.feedback(), symbol="$\\mapsto$").draw(
... path="docs/_static/feedback/feedback-operator.png", figsize=(8, 4))
such that the following equations are satisfied:
Vanishing#
>>> assert Box('f', x, y).feedback(mem=Ty()) == Box('f', x, y)
Joining#
>>> f = Box('f', x @ (m @ m).delay(), y @ m @ m)
>>> assert f.feedback(mem=m @ m) == f.feedback().feedback()
Strength#
This can only be checked up to a functor into streams.
>>> from discopy import stream
>>> F0 = Functor(lambda x: stream.Ty.sequence(x.name), cod=stream.Category())
>>> F = Functor(
... F0, lambda f: stream.Stream.sequence(f.name, F0(f.dom), F0(f.cod)),
... cod=stream.Category())
>>> all_eq = lambda xs: len(set(xs)) == 1
>>> eq_up_to_F = lambda *fs, n=2: all_eq(F(f).unroll(2).now for f in fs)
>>> f, g = Box('f', x @ m.delay(), y @ m), Box('g', x, y)
>>> strength = Equation(g @ f.feedback(), (g @ f).feedback())
>>> assert eq_up_to_F(*strength.terms)
>>> strength.draw(
... path='docs/_static/feedback/strength.png', draw_type_labels=False)
Sliding#
This can only be checked up to extensional equivalence of streams.
>>> from discopy import symmetric
>>> n = Ty("n")
>>> h = Box('h', m, n) # assume h is an isomorphism
>>> f = Box('f', x @ n.d, y @ m)
>>> sliding = Equation((f >> y @ h).feedback(), (x @ h.d >> f).feedback())
>>> sliding.draw(
... path='docs/_static/feedback/sliding.png', draw_type_labels=False)
>>> LHS, RHS = sliding.terms
>>> eq = Equation(*map(lambda f: F(f).unroll(2).now, sliding.terms),
... symbol="$\\sim$").draw(path='docs/_static/feedback/slide-unroll.png')
>>> with symmetric.Diagram.hypergraph_equality:
... assert F(LHS).unroll(2).now == F(RHS).unroll(2).now\
... >> F(y).unroll(2).now @ F(h).later.later.now
Note
Every traced symmetric category is a feedback category with a trivial delay:
>>> from discopy import symmetric
>>> symmetric.Ty.delay = symmetric.Diagram.delay = lambda self: self
>>> symmetric.Diagram.feedback = lambda self, dom=None, cod=None, mem=None:\
... self.trace(len(mem))
>>> F0 = Functor(
... ob=lambda x: symmetric.Ty(x.name), ar={}, cod=symmetric.Category)
>>> assert F0(x.delay()) == F0(x)
>>> F = Functor(
... ob=F0, ar=lambda f: symmetric.Box(f.name, F0(f.dom), F0(f.cod)),
... cod=symmetric.Category)
>>> f = Box('f', x @ m.delay(), y @ m)
>>> assert F(f.delay()) == F(f) and F(f.feedback()) == F(f).trace()
Note
We also implement endofunctors Head
and Tail
together with an
isomorphism FollowedBy
between x and x.head @ x.tail.delay().
This satisfies the following equations:
>>> assert x.head.head == x.head
>>> assert x.head.tail == Ty()
>>> assert x.delay().head == Ty()
>>> assert x.delay().tail == x
In the category of streams, this is just the identity.