# Presentation: 399017

## Some thoughts on vertexing

- L1 Trigger

- Gustavo Cancelo

## Current vertex algorithm

- First cuts:
- pT<1.2 GeV
- Proximity to the beamline<0.025cm

- Name them as Good Candidate Vertex Tracks

- Gustavo Cancelo

## Current vertex algorithm

- Pick 1st track candidate
- Pair with a 2nd track calculating the point of closest approach:

- Where:
* **x**v**, y**v**, z**v* are the estimated vertex coordinates,
*m**xz**, m**yz* are the 2-D slopes,
- Хx, Хy, ХT, are the respectively chi-square values,
- and σzx, σzy are errors associated with the method.

- Tracks are clusterized based on the rule above.
- If a track does not meet the rule is used as a seed for a new cluster.
- The algorithm loops through all good candidate tracks and all existing clusters.

- Gustavo Cancelo

## Current vertex algorithm

- After looping through tracks, vertices must be recalculated.
- The vertex with the most number of tracks is selected as the primary interaction vertex (PIV).
- All tracks not attached to the PIV are tested again to see if they can join the PIV cluster. This last step is based on the track’s  impact parameter calculated as:

- Track added to PIV cluster if *X<5.0*

- Gustavo Cancelo

## Current vertex algorithm

- Deassign all tracks assigned to non-primary clusters.
- Repeat procedure for a new primary cluster
- Once primary vertex search is complete, search for detached tracks based on following rules:

- Apply rule for triggering based on number of detached tracks plus some detector geometry constrains.

- Gustavo Cancelo

## Issues, questions and concerns

- There are 3 “types” of vertices:
- Primary interaction vertices.
- Secondary vertices that we are interested on (b’s).
- Secondary vertices that we are not interested on.
- The number of vertices, hence clusters, is unknown.
- Figuring out the number of vertices and Track-to-vertex assignment must be done “in parallel” with vertex position estimation.
- The current algorithm seems too iterative
- Can the number of vertices be found a priory or at the same time with the clustering process?
- Is the impact parameter the best parameter to do track assignment?
- Can the current algorithm be upgraded easily to use other parameter estimation methods?
- The performance of the algorithm may degrade with data volume or very complicated events specially if the experiment runs at 396ns/BCO instead of 132ns/BCO

- Gustavo Cancelo

## Alternative algorithm

- Basic idea:
- Find an algorithm that can estimate the number of primary vertices, the location of the vertices and cluster the tracks for each vertex “in parallel”.
- Estimate other important parameters such as covariance matrices of the clusters and minimum distances from the tracks to the vertices which will help to figure detached tracks.

- Gustavo Cancelo

## Alternative algorithm

- The model proposed for the clustering problem is the Gaussian mixture, where p(x) is the probability of finding the data x

*Where,**** x**** are the input data (tracks)*
***j=1...k**** is the cluster index*
***α******j**** are the cluster’s prior probabilities and represent the weights of each Gaussian in the model*
***mj**** are the center of clusters (vertices)*
***Cxj**** are the covariance matrices of the data with respect to each vertex*
***All these parameters must be estimated***

*m**1*

*m**2*

*m**3*

- Gustavo Cancelo

## Alternative algorithm

- We also need a metric to measure distances to clusters. If we use a Bayesian model the Euclidean metric is not optimum. I used the Kullback-Leibler divergence:

- Where x is the data and j represent the clusters. The KL divergence measures the distance between two pdf functions. In this case it will be applied to the prior and posterior pdfs.

- The estimation of the unknown parameters based on the Gaussian mixture and using the KL divergence leads us to the well known (EM) expectation-maximization algorithm.

- The KL divergence meets all the requirements to be a distance:
- KL≥0
- KL=0 if p(x|q)=p(x)
- Triangle inequality

- Gustavo Cancelo

## Alternative algorithm

- EM algorithm has 2 steps the E-step estimates the so called “complete data” (i.e. the posterior probability function):

- This represents the conditional probability that the track** *****xi***** **belongs to vertex* ****j***.
- Basically, we assign track ***i*** to the cluster where the probability of pertinence is the highest.

- Note that the ***α******j,*** as shown in the next slide, represent the total probability (i.e. weight) of a cluster in the Gaussian mixture. In other words a cluster with many tracks has a bigger ***α******j*** than a cluster with few tracks.

- Gustavo Cancelo

## Alternative algorithm

- The M-step estimates the unknown parameters using maximization

- Sum of posterior probabilities for each cluster

- Vertex coordinates estimated from the posterior probabilities of track pertinence to a cluster and track data itself. What does Xi mean?

- Covariance matrix of tracks with respect to vertex*** j***.

- This is the standard EM.
- EM is an iterative algorithm which guaranties convergence under very wide assumptions

- Gustavo Cancelo

## Alternative algorithm

- Modified EM algorithm (Gustavo’s EM)
- What does Xi mean? What track feature should we use?
- Xi represents the distance between the track and the vertex.
- The current algorithm uses impact parameter. I’m using the true minimum 3-D Euclidean distance between the track and the estimated vertex.
- I’ve included a clustering step in the EM algorithm that separates the tracks associated to each vertex. So the vertex are calculated using only the tracks in the cluster.

- NOTE: In most clustering problems the Xi input data set, is a fix set of values (experimental measured data). For the current clustering problem we have a new data set xi for each new vertex estimation. In general, this is bad.

- The modified EM algorithm turns this bad feature in something good because the data set quickly converges towards the estimated vertex.

- Gustavo Cancelo

## Alternative algorithm

- Calculate posterior probabilities P(j|xi) for each cluster.
- Calculate cluster weights in the Gaussian mixture αj.
- Separate tracks in clusters based on maximum posterior probabilities P(j|xi).
- Fit the tracks to find vertex parameter estimates.
- Iterate until parameters converge.

- NOTE: The number of iterations is a very small number (3 or 4), and all the clusters are found in parallel.

- Gustavo Cancelo

## Advantages of the alternative algorithm

- The track clusterization happens at the same time with the vertex estimation.
- The tracks are allowed to move from cluster to cluster until convergence.
- The number of clusters may change during this process.
- The algorithm calculates a matrix of closest approach from the tracks to each vertex.
- The entries of these matrices became smaller as the estimated vertex converges towards the true value.
- The entries of these matrices can be used to find detached tracks.
- The fitting process (constrained MSE) is independent of the clustering process.
- The constrained MSE could be upgraded to Kalman or other without having to modify the rest of the algorithm.

- Gustavo Cancelo

## Example: Min_bias event

- Gustavo Cancelo

## Example: Min_bias event

- Gustavo Cancelo

## Example: Min_bias event (Close-up)

- Gustavo Cancelo

## Estimated Track to Vertex Distance

- Gustavo Cancelo

## Example: b event

- Gustavo Cancelo

## Example: Min_bias event 

- Gustavo Cancelo

## Future work

- Analyze EM convergence
- Apply sequential MSE
- MSE can be applied incrementally to incorporate new data or delete data without having to refit everything. This trick can be used between iterations to speed up the algorithm.
- Explore alternatives to EM
- Study alternatives to constrained MSE

- Gustavo Cancelo