Re: [agtk-devel] topological sorting of anchors

[Steven B. <sb...@un...>]

Matthias,

> I assume that all annotations are based on the word sequence, so that
> there are no other anchors than the ones that mark word boundaries. I
> have one AG per utterance. All AGs are linear and connected with respect
> to the word sequence.

I guess you would permit coterminous annotations, and annotations that span
multiple words.  Thus the anchors form a linear order, but the annotations
themselves do not.

> I am now circumventing the problem by assigning offsets to the
> within-utterance anchors as well, so that the temporal sorting is
> possible, by I am not very happy with this.

Agreed, you shouldn't be forced to do this in order to get our API to do
what you want.

> Why not combine topological and temporal sorting? Is it possible to have
> an AG whose topological and temporal sortings contradict each other?

No, by definition, the AG arrows go forward in time.  If we have an
annotation from anchor a to anchor b, then t(a) <= t(b).

> (e.g. consider (anchor1, offset 2 sec. -> anchor2, offset 1 sec.))
> If this is not allowed anyway, I could imagine somthing like this:
> 
> As a first step, a topsort (maybe restricted to some type) could
> indentify the ambiguities:
> - disjoint sections of an AG
> - sets of anchors of the same topological 'grade', i.e. where the
> relative ordering cannot be determined from the topology alone
> 
> In a second step, a temporal sort could resolve (some of) the
> ambiguities left from the topsort and at the same time check if any
> violations (see example above) exist. If there are still ambiguities
> left these may be made aware to the user of the AG library.

Actually, the B&L paper defines prec_s (structural precedence) and prec_t
(temporal precedence), and prec, an ordering which is the transitive
closure prec_s and prec_t.

> By the way, wouldn't it be possible to sort an AGSet on a temporal basis
> just like the disjoint sections of an AG?

Only if there is a common timeline.

>  > At some point in the future we may decide that particular kinds of AG
>  > need special treatment (e.g. connected AGs, totally anchored AGs,
>  > linear AGs).  There's two approaches available: enriching the class
>  > structure or creating new high-level APIs.  We could subclass our AG
>  > class and add extra methods (e.g. a getAnchorSeq method which did a
>  > topological sort on ConnectedAGs and a temporal sort on TotalAGs.)
>  > Some existing functions can be written more efficiently when we can
>  > make safe assumptions about the topology of the AG.  The other
>  > approach is to build a new API on top of the AG API which exposes a
>  > subset of the AG functions and adds some new ones which can be
>  > implemented using the existing API (cf our treebank API).
> 
> I'd tend to the first approach, only because I think the topological and
> temporal sort is a basic feature that should be integrated closely with
> the library.

Yes, but that unfortunately makes the closed-world assumption.  You tool
would only be able to add its kind of annotation to existing AGs that
behave the same constraints.  It seems strange to require that you cannot
add connected annotations to an AG which happens to be disconnected.

>  > Anyway, to sum up, before adding new sort functions we should first
>  > analyze the stated needs carefully...
> 
> I hope I could contribute to clarifying some needs :)

You'd be very welcome to.  In the fall I'd like to redesign the API a
little (stronger typing) and add better support for sorting, and we'll
need to work through the details on this list...

-Steven