Combinatorial Hypothesis Algorithms

Last update: 22 Oct 2024 [History] [Edit]

Overview

Instances of the combinatorial hypothesis algorithm sit at the end of each chain step and are the algorithms where the decisions are made based on correlations between multiple Decision objects.

Or, in other words - it is the only place where the different legs of a multi-leg chain are allowed to influence each other. The evaluation of the ComboHypo results in rejection of the chain at a given step. Outside of the ComboHypo, a chain’s individual legs are running entirely independently of each other.

Configuration

This is a framework algorithm, and is not configured directly by trigger signature developer. There are however two cases when it may be necessary to alter its default behaviour. These will both be covered in more detail below.

  1. Request to disable multiplicity checks. In some cases it is not appropriate for the ComboHypo algorithm to apply its regular requirement of satisfying each chain-leg’s specified multiplicity requirement with unique physics objects. There are a number of ways to communicate this as detailed below - this is always done by encoding special properties into the navigation graph which the downstream ComboHypo is able to pick up.
  2. Request to perform special combinatorial logic. When the regular HypoAlg was discussed, we saw that it was required to host one HypoTool per configured HLT chain-leg. The ComboHypo algorithm can also host one ComboHypoTool per chain to customise the multi-leg decision. (note: unlike for HypoAlg the tool here is required per chain rather than per chain leg). The configuration of ComboHypoTool is optional and there is a generic ComboHypoTool which can perform common kinematic selections between objects pertaining to chain legs (ΔR, ΔM, etc.). This common implementation can be configured from set of keywords encoded in the chain’s name. All implementations of ComboHypoTool need to implement IComboHypoTool interface.

Inner workings of a ComboHypo algorithm

The logic of the ComboHypo is one of the most complicated aspects of the HLT, so let’s work through its functionality piece by piece to understand what’s going on.

Instantiation

Unique ComboHypo algorithm instances are added in each step for each category of HLT chain defined by the number of legs of the chain, and the type of reconstruction performed in each chain leg. For example, HLT_e10_L1eEM10 has multiplicity requirement [1]; leg signature {e} and HLT_2e10_L12eEM10 has multiplicity requirement [2]; leg signature {e}. Both of them would share the same ComboHypo algorithm as they are both single-legged electron chains with the same leg signature. The HLT_e10_L1eEM10 chain doesn’t technically need to use a ComboHypo algorithm as it is a single-object selection, but all chains are passed through a ComboHypo algorithm for consistency.

Other examples of chains which would make common use of a shared ComboHypo algorithm instance are HLT_mu20_2e10_L1MU18_2eEM10 ([1,2], {mu,e}) and HLT_3mu20_2e10_L13MU18_2eEM10 ([3,2], {mu,e}). Again, both are two-leg chains with muon reconstruction on the first leg and electron reconstruction on the second leg. Note that the ordering is important, HLT_2e10_mu20_L1MU18_2eEM10 ([2,1], {e,mu}) would need to configure and use a different ComboHypo algorithm instance due to the electron and muon leg-ordering being swapped.

In summary, the chain’s leg signature - such as {mu,e} - determines which instance of ComboHypo algorithm it will use. And the chain’s multiplicity signature - such as [1,2] - determines how the ComboHypo algorithm behaves for that specific chain.

Tip These instantiation logic rules based on the chain’s leg signature are the same ones which govern Filter algorithms. There will be a one-to-one mapping between Filter algorithms in a given chain step and ComboHypo algorithms.

Reading Input Decision Objects

Upon execution in an event, the ComboHypo algorithm will first read the output of a HypoAlg DecisionContainer for each leg, and iterate over all input Decision objects contained within. The ComboHypo algorithm knows what DecisionIDs (chain-legs) to expect on each input, and will only consider these DecisionIDs from that input.

For example the ComboHypo algorithm for chain HLT_mu20_2e10_L1MU18_2eEM10 ([1,2], {mu,e}), will obtain DecisionContainer from a muon HypoAlg containing one Decision object per muon candidate, each discriminated against the mu20 requirement and a second DecisionContainer from an electron HypoAlg containing one Decision object per electron candidate, each discriminated against the e10 requirement. The ComboHypo algorithm can be 100% confident that both of these HypoAlgs are already executed in the step. That is because filter algorithm controlling muon-electron chains will have activated both of these.

The ComboHypo algorithm will begin by building up an internal map of chain-legs keyed by DecisionIDs and associating these to the set of passing Decision objects from the HypoAlg(s). There will normally be other chain-leg outputs present in the output from the HypoAlg too. For example, if HLT_2mu10_L12MU8 ([2], {mu}) were running in addition to HLT_mu20_2e10_L1MU18_2eEM10, then Decision objects flagged as passing this other chain would also be present in the input DecisionContainer from the muon HypoAlg. Our example {mu,e} ComboHypo algorithm instance would ignore these DecisionIDs. However, another instance of ComboHypo setup for processing chains with only {mu} legs will act on DecisionIDs corresponding to HLT_2mu10_L12MU8.

For a HLT_mu10_mu15_L12MU8 ([1,1], {mu,mu}) chain with a muon-leg-muon-leg input, the corresponding ComboHypo algorithm will read the same input DecisionContainer twice! One read for each leg. It can hence end up with different keys (corresponding to the mu10 and mu15 legs) in its map containing links which are pointing to the same muon - this will become important later when we consider how we’re going to stop a two-muon chain from triggering an event which only contains one muon!

Applying the Multiplicity Test

With the input data sorted into a useable map the multiplicity requirement is imposed. Let’s use HLT_mu20_2e10_e15_L1MU18_3eEM10 ([1,2,1], {mu,e,e}) as an example.

We have a mapping of Decision objects which have passed the respective mu20, e10 and e15 legs. But in the multiplicity computation we need to go beyond Decision objects and resolve the physics objects which these decisions concern.

In fact, not even this is enough. In tag-and-probe chains (see menu section) reconstruction can be delayed for some objects. Because of this we can even end up comparing the same physics object at different stages of its reconstruction!

For that reason the multiplicity requirement is a multi-stage process.

1. Collection of physics objects on each leg

This stage goes from a set of Decision objects associated to each leg to a set of hashes associated to each leg.

  • Does the Decision object have a feature link i.e. points to a physical object? If it does - then take the hash of this physics object (note: we’re referring here to the most-recent feature, i.e. applied by the HypoAlg which ran immediately prior to it).
  • If there is no feature link, then obtain the initialRoI link instead and take the hash of it. All Decision objects must have an initialRoI attached back up their lineage at their initial L1 node - so this will always succeed.

We’re going to use these hash values to enforce the multiplicity check. Thus by modifying them we can also program that the multiplicity check is skipped. This is done under the following situations:

  • If there was no feature and we fell back on the initialRoI, and the initialRoI is the special FSNOSEED full-scan ROI.
  • If the feature is itself and RoI, and that RoI is flagged as full-scan.
  • If the HypoAlg signalled to the ComboHypo algorithm that it should not act on this decision object. This is achieved by decorating Decision objects with <int32_t>("noCombo") == 1.

If any of these three conditions are satisfied, then instead of adding our single hash value we instead add N new guaranteed-unique hashes. Here N is the required multiplicity of the leg. By adding these N unique hashes, we ensure that the following code will count the requisite number of unique physics objects on the leg.

This special ability to effectively disable the multiplicity requirement on a leg is added such that full-scan chain with delayed reconstruction (e.g. a full-scan muon leg requiring more than one muon, but which will only start to perform the full-scan reconstruction after an RoI-based muon has been identified) can progress up to the point where the reconstruction starts, even though there is only one unique feature (the initialRoI known as FSNOSEED).

It additionally enables preselections such as in the hadronic sector. Pre-selection jets are not tracked in the navigation individually like the subsequently reconstructed jets are. Hence the HypoAlg needs to be able to disable the multiplicity checks when it only supplies a single dummy Decision object which represents just the final decision of the preselection.

2. Up-cast physics objects

We now have a set of hash values on each leg. Some might correspond to physics objects, others to ROI. Yet others might be special unique hashes added to force the following multiplicity check to pass.

We have one more thing to do however before we can actually do the multiplicity test, and that is to check and correct for misaligned reconstruction.

There is an extra piece of information which was collected above when we searched for features: for every feature just added by a HypoAlg, we also looked back through the full history of the Decision object - all the way back to L1 - and collected the hashes of all of the prior features from earlier steps.

This gives us a mapping between each hash and a set of hash values which correspond to prior features from earlier steps.

We look through all of the hash values on each leg and see if any of these corresponds to a prior feature (of the other leg). If it does, we perform an up-cast by deleting the hash of the the prior feature and inserting the hash of the physics object from the current step.

This up-casting step lets a ComboHypo instance operate efficiently on tag-and-probe chains, as it allows for an equivalence to be drawn between the same physics object at different stages of processing. This will normally be a final-physics-object on the tag leg being compared against a non-final physics object on the probe leg.

3. Enforce uniqueness requirements

Our example HLT_mu20_2e10_e15_L1MU18_3eEM10 ([1,2,1], {mu,e,e}) chain requires a minimum of one unique hash on the first leg, two on the second leg and one on the third leg. To check this we now need to enforce the uniqueness requirement. We expect, for this example, that any electrons above 15 GeV will have their hash entered on both the e10 leg and the e15 leg - but each electron hash can only be allowed to contribute towards exactly one leg.

The unique-hash enforcement identifies all hash values which are duplicated in more than one leg, and it also computes how close each leg is to failing its multiplicity requirement. For example, if there were currently three hashes on the e15 leg - then this leg is able to loose up to two hashes and still satisfy its multiplicity requirement of 1. If there were at the same time five hashes on the e10 leg - then this leg is able to loose up to three hashes and still satisfy its multiplicity requirement of 2. In this case, a hash which was common to the e15 and e10 legs would be excluded from the e10 leg - as this was the leg with the largest margin. In case of a tie, the hash gets removed from the earlier leg.

4. Apply multiplicity requirements

The final step of the multiplicity test is the simplest of all above. We have a set of hash values associated to each leg. And we have guaranteed that each hash value appears on exactly one leg.

We now simply count that the number of hash values on each leg meets the multiplicity requirement for this leg.

An output DecisionCollection is made to mirror each input DecisionCollection, and an output Decision object is added for each input Decision object. If a chain passes the multiplicity test, then the DecisionIDs of all of its legs propagate into all appropriate output Decision object.

Applying custom ComboHypoTool tests

After having confirmed that a chain satisfies the requisite multiplicity on each leg, additional discrimination may be applied between physics objects on the different legs - this is normally specific topological and kinematic requirements.

These requirements are applied by ComboHypoTool instances, where each chain may have one or zero tool instances in each step. There are two options here and these are as follows.

1. The TrigComboHypoTool

The TrigComboHypoTool is a generic tool instance which can be configured from a chain’s name via the TrigComboHypoToolFromDict function.

It performs generic two-body kinematic cuts over parings of physics objects from two specified legs (which can be the same leg).

Supported cuts are angular dR, deta or dphi; and mass invm or mT.

Lower and upper cut bounds are given sandwiched with the cut type and a pair of letters correspond to the legs from which to take the physics objects. Here, A is the first leg, B the second etc..

Using this syntax, 11invmAA60 denotes requirement of an invariant mass between 11 and 60 GeV for any pairing of two physics objects from the first leg (A).

90invmAB_02dRAB is then a requirement of an invariant mass above 90 GeV and a ΔR greater than 0.2 between any pairing of one physics object from the first leg (A) and one physics object from the second leg (B).

2. A bespoke ComboHypoTool

A custom ComboHypoTool may be used to implement any arbitrary selection. The base requirement is that the tool implements IComboHypoTool, however it is recommended that the custom tool inherits from ComboHypoToolBase and lets the base class deal with the underlying combinatorics.

The ComboHypoToolBase has two configurable parameters.

  • ModeOR (default: true): The default behaviour is for the chain to be satisfied providing that any one considered combination of physics objects is flagged as passing. If this flag is set to false then the tool will behave as ModeAND and require every considered combination to pass.
  • EnableOverride (default: false): Stops the tool considering combinations of physics objects as soon as a final decision may be inferred. For ModeOR this is as soon as any combination passes. For ModeAND it is as soon as any combination fails. Caution: override can save CPU, but it can also affect which physics objects get propagated to later steps of the trigger!

You are required to implement the

virtual bool executeAlg(const std::vector<Combo::LegDecision>& combination) const;

method, here Combo::LegDecision is a std::pair where the first element of the pair is the DecisionID of a chain-leg and the second element of the pair is an ElementLink to the Decision object in the navigation graph which in turn contains the ElementLink to the feature which should be used in the selection.

The size of the vector will always match the chain’s multiplicity signature, so for the example of HLT_mu20_2e10_e15_L1MU18_3eEM10 ([1,2,1], {mu,e,e}) the vector will always be size 4. The first element in the vector will be a muon on the mu20 leg. The second and third elements of the vector will be electrons on the em10 leg and the final element of the vector will be an electron on the e15 leg.

The executeAlg function will be called once for each possible combination of physics objects, based on the number of physics objects on each leg. The set of combinations which are to be processed are generated via an instance of HLT::NestedUniqueCombinationGenerator. There is no deduplication applied at this stage, so the same electron may be supplied simultaneously on the e10 leg and the e15 leg.

Every time executeAlg returns true, the set of physics objects which were supplied in that iteration are flagged as being part of a good combination. Once all combinations are processed (or EnableOverride kicks in), an overall pass/fail decision is made.

Should the ComboHypoTool’s overall decision be a pass, then all of the Decision objects which were flagged as contributing to at least one valid combination are allowed to keep there DecisionIDs for the chain’s various legs. For any Decision objects which were not part of any valid combination (or for all Decision objects, if the overall decision is a fail) - then all of the chain’s DecisionIDs are removed.

It should be noted that the output of this process is a set of physics objects which satisfy the combinatorial requirement in one or more ways. But the exact detail of how the combinatorial requirement was satisfied is lost.

Additional special cases

The B-Physics group reconstruct various states from muon or electron pairs. Given the fine level of control required by the BLS group over this process, BLS chains have their own top-level ComboHypoAlg instance, tailored to their specific needs. These ComboHypo algorithms inherit from the primary class type and override the execute function but still make use of helper functions from the base class.