Sharing cache between adaptive learners and equivalence oracles

[stateMachinist]

In LearnLib 0.17, there was a SULSymbolQueryOracle which extended MembershipOracle and it was possible to share a cache between an ADTLearner and an equivalence oracle by using SymbolQueryCache. I just saw that this cache does not exist anymore. And instead of SULSymbolQueryOracle, there is now a SULAdaptiveOracle which does not extend MembershipOracle. I am confused by these changes. Is it still possible to have cache sharing for adaptive learners without resorting to custom implementations?

[mtf90]

Dear @stateMachinist, recently the ADT learner has been switched to AdaptiveQuerys/AdaptiveMembershipOracles which are incompatible with regular queries/oracles. This was to support batching/query parallelization for the ADT learner. However, the underlying semantics of symbol-wise processing remained the same, so you should be able to share information on the SUL level rather than the oracle level.

SULCaches should give you the implementations needed that can be wrapped in adaptive/regular membership oracles for the learner/equivalence oracle.

[mtf90]

That's exactly what I had in mind. I think you don't need the Observable versions (unless you want to do something with the LTSmin model checker) but they probably don't hurt either, as they share a lot of code. The split counters are indeed a little bit verbose. We could merge them for the upcoming release.

[stateMachinist]

Alright, thank you. Merging the counters seems like a good idea to me.

There's another thing I've noticed while building my benchmark: When I replaced the regular MealyCacheOracle with a SymbolQueryCache for non-adaptive learners, I would sometimes get slightly different performance results. Then I noticed that processQueries in MealyCacheOracle sorts queries descending by length to exploit prefix-closedness (see here). The SymbolQueryCache did not do this (see here). I think this is a bug, because there is no necessity for this difference in performance and it potentially introduces bias when comparing adaptive and non-adaptive learners.

Again, I found this issue in version 0.17. I haven't tested it with the latest development version yet, but from a quick glance at the code, it seems to me that this issue may still be present. Furthermore, I am mentioning this because it may also affect other specialized oracles/caches that I haven't looked into.

[mtf90]

This is not a bug but a disadvantage of adaptive queries. The normal Mealy queries are preset, meaning that you know all the input symbols that will be posed to the oracle beforehand so that you can sort them intelligently. With adaptive queries this is not the case. You would have to already provide system outputs in order to obtain the next input symbols of the query which makes sorting them ahead-of-time impossible.

[stateMachinist]

I think there was a misunderstanding. I understand that there are natural limitations with adaptive queries. However, the SymbolQueryCache was also capable of processing preset queries via processQueries, but did not employ sorting for these. And since it could be used as a cache for preset queries, I would also expect it to have this generic optimization for preset queries. But since there seems to be a stronger separation between adaptive and preset views on the SUL now, I am not sure if it is still possible to run into such a scenario.

[mtf90]

Ah, I see. You are right, the previous implementation did not support reordering. I think this specific use-case was never really considered (although it sounds fairly reasonable). The processQueries method was just a convenience method to re-use the same oracle instance.

If you want to optimize the query order for the EQ part, you probably need to set up a second (duplicate) query cache for the membership oracle view (which internally delegates to the SUL cache then). This should also work for the current version with adaptive queries. However, note that you need to specify a batch size for the EQ oracle, since you can't really re-order singleton test queries.

It might be worthwhile to think about extracting this feature into a separate query filter. This way you could save on the duplicate memory consumption and it may also be used for de-duplicating some functionality in the current Mealy/Moore caches.

[stateMachinist]

I've taken another look at the new class hierarchy. In my example, it is the SULAdaptiveOracle wrapping the cache. I saw that SULAdaptiveOracle implements SingleAdaptiveMembershipOracle, which also has processQueries, but does not perform query sorting. Wouldn't the simplest solution be to always perform query sorting in the default implementation of processQueries for Mealy machine oracles? This way, oracle setup would remain the same and you would never lose performance by accident if you forgot to plug in that sorting filter.

[mtf90]

Maybe I'm mixing things up again, but don't the current classes run into the aforementioned problem? SingleAdaptiveMembershipOracle#processQueries takes AdaptiveQuerys which can't be sorted because the inputs aren't clear before actually processing the query (i.e., it is not a regular membership oracle anymore).

(Just following that line of thought: We could think about making something like Adaptive2MembershipWrapper public to make adaptive oracles compatible with preset environments again, but typically you interface your systems via the SUL class anyway for which the respective wrappers already exist.)

As for ordering (preset) queries by default: I think this somewhat muddies the water with algorithmic performance/comparisons because strategies like closing order, etc. which highlight certain algorithms will be affected. I would even argue that the current cache implementation is not that great in this regard either because it doesn't only cache queries (the unique query performance is affected as well). Sure, it would require one additional step if all you care about is performance, but it would also allow for more flexibility.

(Unfortunately, a prefix-closed DFA filter isn't that straightforward to realize, so a clean implementation might require some more time to think about. Nothing to stress about for the next release.)

[stateMachinist]

You are right! Sorry, it was me who mixed things up.

But I don't fully understand your point about interfering with learning performance. As you've explained, the only scenario where query sorting matters is when queries are posed in batches. Since from the perspective of the caller, the batch is processed atomically, how could query processing order ever affect a learner's future actions? How could it interfere with things like closing strategies? (Same reasoning applies to EQ oracles using batch processing)

I guess it boils down to what contract batch processing uses. If the callee guarantees sequential processing, reordering would not be acceptable. But then, why should a caller use batches in the first place?

[mtf90]

You are right in that the order of queries does not impact the future behavior of the algorithm but its measurable performance in comparison with other configurations/algorithms. Maybe closing strategies wasn't a good example.

Let's take the L* algorithm. When refining the hypothesis, the algorithm adds all prefixes of the counterexample as new rows to the observation table. In case of Moore learning, this would result in n queries for the epsilon column (which is used to determine state outputs). With the re-ordering, it would only result in 1 query. So the impact of techniques such as the Rivest & Schapire-style counterexample analysis (which requires log n queries) would get masked by an external influence.

Sure, it's a little bit of a constructed use-case, but in practice you can't really tell what queries have a prefix relationship. Given that there is a chance that these might mask the algorithmic properties, I'd rather be on the safe side and make it opt-in via an explicit filter.

As for batches, you are correct in that they are expected to be processed atomically (Collection doesn't give you any guarantees for the iteration order). In my opinion, the main appeal is parallelization. If you know that you are going to pose n queries, you can delegate them to multiple SUL instances to answer them faster.

[stateMachinist]

That's a good example of how reordering impacts learning performance. However, I do not quite see how that classifies as 'masking' of algorithmic properties.

From the perspective of the oracle: If it has no obligations as to preserving a specific order, why should it not choose the most efficient way of processing the queries?

From the perspective of the learner: If the learner wants its queries to be processed in a specific order, why should it delegate them to a callee that does by contract not guarantee preservation of order?

I think part of the issue might be that we use different definitions of the term 'algorithm' in this context. I think that, strictly speaking, when you do batch processing, part of the learning algorithm is outsourced into the oracle, and so you may lose control over some algorithmic details of the learner (as the MAT framework draws the line between learner and teacher at the level of individual queries). However, I do not see any issues with this, as long as the contract of the API clearly communicates that. The implications of allowing parallelization of queries are even more significant for the learner, since that may rob it of determinism.

Personally, I don't understand what's the use of batch processing if it doesn't employ any optimizations in its implementation. I think if the API clearly states contractual conditions, implementers of learning algorithms can freely decide which details of their algorithm they are willing to delegate. One advantage of this would be saving redundant code: If many algorithms perform batch processing, why should all of them reimplement such a generic optimization like sorting?

On the other hand, I may be overlooking some relevant use cases, and having an optional filter for reordering would certainly be more flexible. In the end, it is about trading flexibility vs. complexity of use. I only wanted to provide another perspective, I don't mean to meddle with your design decisions.