Äîêóìåíò âçÿò èç êýøà ïîèñêîâîé ìàøèíû. Àäðåñ îðèãèíàëüíîãî äîêóìåíòà : http://acat02.sinp.msu.ru/presentations/waltenberger/Robust.pdf Äàòà èçìåíåíèÿ: Tue Jun 25 03:11:12 2002 Äàòà èíäåêñèðîâàíèÿ: Mon Oct 1 20:26:35 2012 Êîäèðîâêà:

New Developments in VertexReco
Rudi FrÝhwir th, Kirill Prokofiev, Thomas Speer, Pascal Vanlaer, Wolfgang Waltenberger . ACAT'02 , Moscow, June 24
th

28th , 2002

Recap: Linear fitting Robustifications Results Outlook



New developments in vertex reconstruction ­ p.1/24


Recap: Linear Fitters
Kalman Fit
¡

(ORCA Implementation)

Linear Fit
Linearizes tracks at the impactPoints. Iterative.
¡

(ORCA Implementation)

Simplified Kalman Fit
Kalman Fit, with 3 "frozen" track parameters. "Full" (non-linear) track model. Problems in forward region. Iterative. Fast.
¢

(ORCA Implementation)

Differencies in CPU time / precision are currently under study.

New Developments in Vertex Reconstruction ­ p.2/24


Recap: Linear Fitters (contd)
Kirill Prokofiev, Thomas Speer

Linear

Kalman

New Developments in Vertex Reconstruction ­ p.3/24


Why robust estimators?
Robust estimators are insensitive to outlying obser vations Outlier recognition improved Lower bias in the overall fit Better separation between primar y ver tices and secondar y ver tices Good star ting point for more complex algorithms (Multiver tex fit)

New Developments in Vertex Reconstruction ­ p.4/24


Examples of robust estimators
Median (very old)

L1 =Least Sum of Absolute Values (Edgewor th)
M-estimators (Huber) ORCA implementation planned Adaptive estimators (Peterson et al., FrÝhwir th and Strandlie) Implemented with lin. annealing schedule LTS=Least Trimmed Sum of Squares (Rousseeuw) Implemented

New Developments in Vertex Reconstruction ­ p.5/24


Examples of robust estimators
LMS=Least Median of Sqares (Rousseeuw) Coordinate-wise implementation MVE=Minimum Volume Ellipsoid (Rousseeuw) MCD=Minimum Covariance Determinant (Rousseeuw) Implemented

New Developments in Vertex Reconstruction ­ p.6/24


Adaptive estimators
These are very similar to M-estimators and differ only in the computation of the weights. If µ is the current estimate (e.g. of location) and mi a (multivariate) obser vation with cov. matrix , the weight wi is given by

wi

mi ; µ ci mi ; µ
¤ ¤ ¥ ¦ ¥

¸

The constant ci defines the cut beyond which the weight quickly drops to 0.

¦

New Developments in Vertex Reconstruction ­ p.7/24


Adaptive estimators (contd)

1 assignment probability 0.8 0.6 0.4 0.2 0

0

1

2

3 distance/s.d.

4

5

6

Weight of a univariate observation with a cut at 4

New Developments in Vertex Reconstruction ­ p.8/24


Adaptive estimator (contd)
ORCA implementation:

wi

1
¸

1
Deterministic annealing:

e

2 2 cutoff 2T


T = Temperature, default: 1 T
¨

Tr
§

for every iteration step. cutoff "cut off " parameter, defaults to 3

¸

1 % cut

New Developments in Vertex Reconstruction ­ p.9/24

©


LTS estimator
Instead of minimizing the total sum of the squared residuals, the sum of the h smallest squared residulas is minimized ( n 2 1 h n). The breakdown point is roughly equal to the trimming propor tion.


The LTS estimate can be computed exactly only by an exhaustive search. However, there is a very good approximate iterative algorithm (FAST-LTS).

New Developments in Vertex Reconstruction ­ p.10/24




LTS estimator (contd)
The FAST-LTS algorithm: Compute squared residuals with current estimate Recompute estimate using obser vations corresponding to the h smallest squared residuals Iterate until convergence

New Developments in Vertex Reconstruction ­ p.11/24


LMS estimator
The LMS estimator minimizes the median of the squared residuals. Its breakdown point is n 2 p 2 n.
¤ ¦

In the univariate case, the LMS estimate of the location is the midpoint of the shor test inter val covering one half of the sample. In the case of a fitting a line to data points in the plane, the LMS line is the narrowest band (measured in the y-direction) which covers half of the sample. This line passes through two of the data points (exact fit proper ty).





New Developments in Vertex Reconstruction ­ p.12/24


LMS estimator (contd)
ORCA implementation: (non-robust) Principal Component Analysis + coordinate-wise LMS

+

New Developments in Vertex Reconstruction ­ p.13/24


MCD estimator
Multivariate location estimator, mean of the h n 2 1 points for which the determinant of the covariance matrix is minimal. Its breakdown point is n 2 p 1 n.
¸ ¤ ¦

Gives a covariance estimate at the same time. Computationally similar to the LTS. Can be generalized to other values of h.





New Developments in Vertex Reconstruction ­ p.14/24


LTS/MCD in ORCA
LTS and MCD have been generalized in ORCA to work with any kind of distance measure, the most general weight being

1 wtot
LTS: ctrack MCD: ctrack
¸ ¥

ctrack wtrack
tex tex

cvertex wvertex 0 1
¸

1 cver
¸ ¥

¸

0 cver

¸

New Developments in Vertex Reconstruction ­ p.15/24


Results
Four simulation experiments: Ver texGun events with "well-behaved" outliers: .
25 tracks, 5 outliers, P=20 5 mm,
dxdir

2 GeV.


x

2 mm,





x(Outlier)

5 mrad,

dxdir(Outlier)

8 mrad. 1 mm,

Ver texGun events with "evil" outliers: .
25 tracks, 5 outliers, P=20 10 mm,
dxdir



2 GeV.





x


x(Outlier)

5 mrad,

dxdir(Outlier)


25 mrad.

¯ Pythia events: cc - 100 GeV, . ¯ Pythia events: qq - 100 GeV, 1 4 . NoPU




1 4 - NoPU




24



New Developments in Vertex Reconstruction ­ p.16/24








PCLMSFit
- resolution in x
Entries

pclmse
485 0.0004564 0.01911 39.44 / 49 Mean RMS 2 / ndf

- pulls in x 400 350 300 250 200 150
Entries Mean RMS

pclmse
499 -0.03713 0.63

60 50 40 30 20

Constant_BG 47.83 ± 3.958 Mean_BG -0.0001747 ± 0.0004007 Sigma_BG Constant Mean Sigma 0.005735 ± 0.000504 4.326 ± 1.23 -0.001754 ± 0.003405 0.03304 ± 0.007046

2 6.416 / 5 / ndf Constant_BG 8.481e+04 ± 1.04e+06 Mean_BG 555.2 ± 226.2

Sigma_BG Constant Mean Sigma

-119.6 ± 46.39 385.8 ± 19.94 -0.04067 ± 0.02037 0.3915 ± 0.0112


100 10 0 -0.1 50 -0.05 0 0.05 0.1 0 -30 -20 -10 0 10 20 30

- resolution in z
Entries

pclmse
478 -0.0006548 0.02413 55.71 / 58 Mean RMS 2 / ndf

- pulls in z
Entries Mean

pclmse 499 -0.06822 0.7372 RMS 2 2.246 / 3 / ndf 1.374± 5.2 Constant_BG 348.1± 4158 Mean_BG -521.5± 6538 Sigma_BG Constant 376.2± 21.84 Mean -0.08319± 0.02466 0.5375 ± 0.01979 Sigma

50

300 250 200 150 100

40

Constant_BG 34.81 ± 3.624 Mean_BG -9.122e-05 ± 0.0005641 Sigma_BG Constant 0.007054 ± 0.0008631 3.499 ± 0.8865 -0.0005575 ± 0.004944 0.04623 ± 0.01022

30

Mean Sigma

20

10 50 0 -0.1 0 -30

-0.05

0

0.05

0.1

-20

-10

0

10

20

30

New Developments in Vertex Reconstruction ­ p.17/24


LinearFit
- resolution in x
Entries

linfit
468 0.0007521 0.02481 61.26 / 66 Mean RMS 2 / ndf

- pulls in x

70 60 50 40 30 20 10 0 -0.1

35 30 25 20 15 10 5

Constant_BG 51.68 ± 5.66 Mean_BG 0.0001543 ± 0.0003087 Sigma_BG Constant Mean Sigma 0.004101 ± 0.0004381 3.783 ± 0.6384 0.002689 ± 0.003914 0.04253 ± 0.006332

linfit Entries 426 Mean 0.9086 RMS 8.807 2 / ndf 44.89 / 67 Constant_BG 3.852 ± 0.6262 1.102 ± 1.308 Mean_BG Sigma_BG 14.19 ± 1.969 Constant 30.16 ± 3.091 Mean 0.1388 ± 0.1584 Sigma 1.773 ± 0.1648


-0.05

0

0.05

0.1

0 -30

-20

-10

0

10

20

30

- resolution in z
Entries Mean RMS

linfit
466 -0.001119 0.02481 42.79 / 60

- pulls in z

60 50 40 30 20

40 35 30 25 20 15 10

2 / ndf

Constant_BG 61.74 ± 5.46 Mean_BG -2.822e-05 ± 0.0002676 Sigma_BG Constant Mean Sigma 0.003408 ± 0.0002372 5.255 ± 0.7748 -0.005186 ± 0.002882 0.03475 ± 0.004121

linfit Entries 441 Mean 0.1149 RMS 9.136 2 / ndf 58.02 / 68 Constant_BG 2.489 ± 0.408 Mean_BG -2.648 ± 3.396 Sigma_BG 22.05 ± 6.109 Constant 39.42 ± 3.332 Mean 0.01702 ± 0.1276 Sigma 1.625 ± 0.1025

10 0 -0.1

5 -0.05 0 0.05 0.1 0 -30 -20 -10 0 10 20 30

New Developments in Vertex Reconstruction ­ p.18/24


AdaptiveFit
- resolution in x
Entries Mean

adafit
494 5.733e-05 0.006918 13.51 / 13

- pulls in x 160 140 120 100 80 60
Entries Mean

adafit 498 -0.005823 1.555 RMS 3.74 / 7 2 / ndf 9.804± 8.408 Constant_BG -0.5653 ± 1.415 Mean_BG 3.535± 1.839 Sigma_BG 154.2± 10.58 Constant Mean -0.01628± 0.06063 1.072± 0.09345 Sigma


180 160 140 120 100 80 60 40 20 0 -0.1 -0.05 0

RMS 2 / ndf

Constant_BG 202.1 ± 12.52 Mean_BG -5.811e-05 ± 0.0001244 Sigma_BG Constant Mean Sigma 0.002579 ± 0.0001194 1.691 ± 0.567 -0.005061 ± 0.0187 -0.0499 ± 0.02898

40 20 0.05 0.1 0 -30 -20 -10 0 10 20 30

- resolution in z
Entries

adafit
493 -0.0002835 0.007122 13.55 / 13 Mean RMS 2 / ndf

- pulls in z
Entries Mean

adafit 498 -0.09754 1.468 RMS 2 1.949 / 4 / ndf 2.355± 2.037 Constant_BG -3.175± 2.849 Mean_BG 4.812± 3.101 Sigma_BG Constant 240.7± 14.04 Mean -0.02604± 0.06133 1.226± 0.05119 Sigma

200 180 160 140 120 100 80 60 40 20 0 -0.1 -0.05 0

220 200 180 160 140 120 100 80 60 40 20

Constant_BG 208 ± 13.15 Mean_BG 4.702e-05 ± 0.0001456 Sigma_BG Constant Mean Sigma 0.003033 ± 0.0001338 1.426 ± 0.4597 -0.001098 ± 0.03873 -0.07163 ± 0.07588

0.05

0.1

0 -30

-20

-10

0

10

20

30

New Developments in Vertex Reconstruction ­ p.19/24


AdaptiveFit + annealing
- resolution in x
Entries Mean

adaanneal
494 6.316e-05 0.006922 13.71 / 12

- pulls in x 160 140 120 100 80 60

180 160 140 120 100 80 60 40 20 0 -0.1 -0.05 0

RMS 2 / ndf

Constant_BG 202.4 ± 13.1 Mean_BG -3.368e-05 ± 0.0001261 Sigma_BG Constant Mean Sigma 0.002567 ± 0.0001252 1.974 ± 0.7266 -0.001659 ± 0.01409 0.04225 ± 0.02148

adaanneal Entries 499 Mean 0.009018 RMS 1.56 2 / ndf 4.891 / 8 Constant_BG 1.51 ± 539.7 -2.271 ± 528.1 Mean_BG Sigma_BG -17.23 ± 4.888 Constant 157.7 ± 541.9 Mean -0.01196 ± 533.7 Sigma 1.198 ± 82.37

40 20 0.05 0.1 0 -30 -20 -10 0 10 20 30

- resolution in z
Entries

adaanneal
493 -0.0002765 0.007149 13.52 / 12 Mean RMS 2 / ndf

- pulls in z
Entries Mean

adaanneal 499 -0.1215 1.453 RMS 2 1.116 / 4 / ndf 2.391± 1.896 Constant_BG -3.135± 2.587 Mean_BG -4.479± 2.39 Sigma_BG Constant 242.3± 12.92 Mean -0.05669± 0.05964 1.235± 0.04815 Sigma

200 180 160 140 120 100 80 60 40 20 0 -0.1 -0.05 0

220 200 180 160 140 120 100 80 60 40 20

Constant_BG 208.5 ± 13.2 Mean_BG 6.873e-05 ± 0.0001487 Sigma_BG Constant Mean Sigma 0.00302 ± 0.0001323 1.617 ± 0.6568 -0.01027 ± 0.03043 0.06101 ± 0.08259

0.05

0.1

0 -30

-20

-10

0

10

20

30

New Developments in Vertex Reconstruction ­ p.20/24


LTSFit (80%)
- resolution in x
Entries

ltsfit_0.8
500 -1.824e-05 0.003955 3.741 / 5 Mean RMS 2 / ndf

- pulls in x
Entries Mean

ltsfit_0.8
500 -0.00504 1.91 4.346 / 6 7.161 ± 4.958 -0.2101 ± 1.123 4.627 ± 1.633 204.7 ± 12.68 -0.004573 ± 0.07239 1.352 ± 0.07531


220 200 180 160 140 120 100 80 60 40 20 0 -0.1 -0.05 0

200 180 160 140 120 100 80 60 40 20

RMS / ndf Constant_BG Mean_BG Sigma_BG Constant Mean Sigma
2

Constant_BG 267.5 ± 16.49 Mean_BG 3.644e-05 ± 0.0001382 Sigma_BG Constant Mean Sigma 0.002532 ± 0.000128 9.822 ± 3.665 -0.001458 ± 0.001644 0.009862 ± 0.001731

0.05

0.1

0 -30

-20

-10

0

10

20

30

- resolution in z 200 180 160 140 120 100 80 60 40 20 0 -0.1 -0.05 0 0.05
Entries Mean RMS

ltsfit_0.8
499 -9.739e-05 0.005926 12.02 / 11 172.4 ± 14.88 7.63e-05 ± 0.0001918 0.002573 ± 0.0003115 14.83 ± 16.13 -0.000615 ± 0.001038 0.007206 ± 0.003502

- pulls in z
Entries Mean

ltsfit_0.8 499 -0.06223 RMS 2.183 2 / ndf 10.6 / 12 Constant_BG 137.6 ± 8.705 Mean_BG 0.03855± 0.06242 Sigma_BG 1.21 ± 0.07188 Constant 3.233 ± 2.355 Mean 0.05546± 1.74 Sigma 5.96 ± 3.549


140 120 100 80 60 40 20

/ ndf Constant_BG Mean_BG Sigma_BG Constant Mean Sigma

2

0.1

0 -30

-20

-10

0

10

20

30

New Developments in Vertex Reconstruction ­ p.21/24


Final comparison - VertexGun
"nice" Ver texGun
Name LinearFitter LTSFitter (20% trim) MCDFitter (20% trim) PCLMSFitter (err.mat) AdaptiveFitter Adaptive + anneal t(msecs) 15 57 57 12 29 28 Res(x) 67µ 64µ 65µ 260µ 59µ 59µ Pulls(x) 1.4 1.2 1.2 0.3 1 1 Res(z) 67µ 53µ 52µ 129µ 50µ 49µ Pulls(z) 1.4 1.2 1.2 0.26 0.97 0.97

Name

t(msecs) 15 58 58 22 31 30

Res(x) 101µ 29µ 29µ 134µ 28µ 28µ

Pulls(x) 4.2 1 1.1 0.26 0.91 0.92

Res(z) 84µ 24µ 24µ 76µ 24µ 24µ

Pulls(z) 4.2 1 1 0.076 0.94 0.95

"evil" Ver texGun

LinearFitter LTSFitter (20% trim) MCDFitter (20% trim) PCLMSFitter (err.mat) AdaptiveFitter Adaptive + anneal

New Developments in Vertex Reconstruction ­ p.22/24


Final comparison - Pythia events
Name t(msecs) 12 45 45 8 30 18 Res(x) 58µ 27µ 36µ 78µ 26µ 26µ Pulls(x) 3.5 1.5 1.8 0.4 1.2 1.2 Res(z) 42µ 30µ 32µ 113µ 26µ 31µ Pulls(z) 1.9 1.3 1.6 0.54 1.3 1.3

¯ cc - 100 GeV

LinearFitter LTSFitter (20% trim) MCDFitter (20% trim) PCLMSFitter (err.mat) AdaptiveFitter Adaptive + anneal

Name

t(msecs) 18 67 67 12 44 24

Res(x) 39µ 25µ 21µ 74µ 21µ 22µ

Pulls(x) 2.1 1.1 1.2 0.66 1.1 1

Res(z) 39µ 29µ 27µ 90µ 28µ 28µ

Pulls(z) 1.9 1.1 1.2 0.64 1.1 1.1

¯ qq - 100 GeV

LinearFitter LTSFitter (20% trim) MCDFitter (20% trim) PCLMSFitter (err.mat) AdaptiveFitter Adaptive + anneal

New Developments in Vertex Reconstruction ­ p.23/24


Outlook
Test robust fitters on multi-ver tex fits. Test robust fitters on Finding-thru-Fitting algorithms.

New Developments in Vertex Reconstruction ­ p.24/24