# Revisiting Sparse Retrieval for Few-shot Entity Linking

Yulin Chen111Both authors contributed equally to this work. , Zhenran
Xu111Both authors contributed equally to this work. , Baotian
Hu222Corresponding author. Min Zhang
Harbin Institute of Technology (Shenzhen), Shenzhen, China
{200110528<EMAIL_ADDRESS>
{hubaotian<EMAIL_ADDRESS>
###### Abstract

Entity linking aims to link ambiguous mentions to their corresponding entities
in a knowledge base. One of the key challenges comes from insufficient labeled
data for specific domains. Although dense retrievers have achieved excellent
performance on several benchmarks, their performance decreases significantly
when only a limited amount of in-domain labeled data is available. In such
few-shot setting, we revisit the sparse retrieval method, and propose an
ELECTRA-based keyword extractor to denoise the mention context and construct a
better query expression. For training the extractor, we propose a distant
supervision method to automatically generate training data based on
overlapping tokens between mention contexts and entity descriptions.
Experimental results on the ZESHEL dataset demonstrate that the proposed
method outperforms state-of-the-art models by a significant margin across all
test domains, showing the effectiveness of keyword-enhanced sparse retrieval.
Code is available at https://github.com/HITsz-TMG/Sparse-Retrieval-Fewshot-EL.

##  1 Introduction

Entity linking (EL) aligns entity mentions in documents with the corresponding
entities in a knowledge base (KB), which is a crucial component of information
extraction Ji and Nothman (2016). Typically, EL systems follow a "retrieve and
re-rank" pipeline Logeswaran et al. (2019): Candidate Retrieval, where a small
set of candidates are efficiently retrieved from a large number of entities,
and Candidate Ranking, where candidates are ranked to find the most probable
one. With the rapid development of pre-trained language models (PLM), EL has
witnessed a radical paradigm shift towards dense retrieval Ma et al. (2021);
Sun et al. (2022). Using bi-encoders and Approximate Nearest Neighbors (ANN)
search has become the standard approach for initial entity retrieval,
overcoming the long-standing vocabulary mismatch problem and showing promising
performance gains.

Although the bi-encoder has shown strong in-domain performance, they typically
require training on sufficient labeled data to perform well in a specific
domain Ren et al. (2022). However, such labeled data may be limited or
expensive in new and specialized domains. As reported by Li et al. (2022b), in
the absence of sufficient training data, the recall of bi-encoder
significantly decreases, performing even worse than unsupervised sparse
retrievers (e.g., BM25 Robertson and Zaragoza (2009)). Motivated by the above
finding, in this work, instead of resorting to dense representations in the
“semantic space”, we go back to the “lexical space” and explore PLM-augmented
sparse representations for few-shot EL.

When applying BM25 to the first-stage retrieval, previous work only employs
the mention string as query Wu et al. (2020). However, this can be
insufficient due to under-specified mentions (e.g., “his embodiments” in
Figure 1), requiring additional context to formulate a more comprehensive
query. While an intuitive solution could be incorporating all context into the
query, this approach is suboptimal for two reasons: (i) it does not create
mention-specific queries, i.e., for all mentions in a document, their queries
and retrieved entities are the same; (ii) it may introduce noise into queries
Mao et al. (2022), since not all words in the context are necessary for
understanding the mention.

This paper introduces a keyword extractor to denoise the context for BM25
retrieval. The extraction is modeled as binary token classification,
identifying which tokens in context should be added to the mention string. We
employ a discriminative PLM, specifically ELECTRA Clark et al. (2020), as the
basis of our keyword extractor, and leverage its discriminator head to predict
a score for each token. The top-$k$ tokens with the highest scores are then
added into the final query.

Training the extractor requires binary labels to distinguish whether a token
is a keyword. The keywords are expected to be related to the mention and
necessary for understanding it. We propose a distant supervision method to
automatically generate training data, based on overlapping words between the
mention context and the description of the corresponding entity. These
overlapping words are then ranked based on their BM25 score, which measures
the relevance of the word to the entity description. We select the top-$k$
words with the highest scores as keywords.

Following the few-shot experimental setting in Li et al. (2022b), We evaluate
our approach on the ZESHEL dataset Logeswaran et al. (2019). The results
highlight our approach’s superior performance across all test domains, with an
average of 15.07% recall@64 improvement over the best dense retriever result.
In addition to its superior performance, our method inherits the desirable
properties of sparse representations such as efficiency of inverted indexes
and interpretability.

The contributions of this work are threefold:

  * •

We are the first to explore PLM-augmented sparse retrieval in entity linking,
especially in scenarios of insufficient data.

  * •

We propose a keyword extractor to denoise the mention context, and use the
keywords to formulate the query for sparse retrieval, accompanied by a distant
supervision method to generate training data.

  * •

We achieve the state-of-the-art performance across all test domains of ZESHEL,
outperforming previous dense retrieval methods by a large margin.

##  2 Related work

Entity linking (EL) bridges the gap between knowledge and downstream tasks
Wang et al. (2023); Dong et al. (2022); Li et al. (2022a). Recent entity
linking (EL) methods follow a two-stage “retrieve and re-rank” approach Wu et
al. (2020), and our work focuses on the first-stage retrieval. Traditional
retrieval systems based on lexical matching struggle with vocabulary mismatch
issues Formal et al. (2021). With the advent of pre-trained language models,
the bi-encoder has largely mitigated this problem, but its effectiveness
depends on extensive annotation data Ren et al. (2022). Without sufficient
labeled data in specific domains, the recall of the bi-encoder drastically
decreases Li et al. (2022b), hence the need for further research about few-
shot EL.

Few-shot Entity Linking is recently proposed by Li et al. (2022b). They split
the data in a specific domain of ZESHEL Logeswaran et al. (2019) and provide
few examples to train. They address the data scarcity problem with synthetic
mention-entity pairs, and design a meta-learning mechanism to assign different
weights to synthetic data. With this training strategy, the performance of bi-
encoder is better than simply training with insufficient data. However, it
still cannot surpass the performance of the unsupervised sparse retrieval
method (i.e., BM25 in Table 2). As dense retrievers (e.g., the bi-encoder) and
generative retrievers (e.g., GENRE Cao et al. (2021)) are data-hungry, we go
back to the “lexical space” and resort to sparse retrievers for few-shot EL
solutions.

##  3 Methodology

When applying BM25 to the first-stage retrieval of EL, previous work directly
uses mention string as query. We propose a keyword extractor to denoise the
context, and add the extracted keywords into the query. Then the expanded
query is used for BM25 retrieval. In Section 3.1, we introduce our distant
supervision method to generate keyword labels. In Section 3.2, we present the
architecture, training and inference of our keyword extractor.

Preprocessing. BM25 implementation generally comes with stopword removal Yang
et al. (2017). In this work, we remove the words which occur in more than 20%
of entities’ description documents, resulting in removal of uninformative
words (such as “we”, “the”, etc.).

Figure 1: Overview of our method. The distant supervision method (left)
generates weak keyword labels based on overlapping words. Then the keyword
extractor (right) is trained on these generated keyword labels.

###  3.1 Distant Supervision

Given a mention $m$, its context $M$ and the description document $E$ of its
corresponding entity, the distant supervision method aims to gather keywords
in the context $M$ related to the description $E$. As shown in Figure 1(a),
the overlapping words form a preliminary keyword set (denoted as
$\mathcal{K}^{*}=\\{w_{1},w_{2},\ldots,w_{|\mathcal{K}^{*}|}\\}$), i.e.,

$\mathcal{K}^{*}=words(M)\cap words(E)$ (1)

where $words(x)$ is the set of words in sequence $x$. The words in
$\mathcal{K}^{*}$ are further ranked according to the BM25 score between each
word $w_{i}$ and the document $E$, calculated as follows:

$s(w_{i},E)=\frac{{\rm IDF}(w_{i})\cdot
f(w_{i},E)\cdot(k_{1}+1)}{f(w_{i},E)+k_{1}\cdot(1-b+b\cdot\frac{|E|}{{\rm
avgdl}})}$ (2)

where ${\rm IDF}(w_{i})$ represents the inverse document frequency of word
$w_{i}$, $f(w_{i},E)$ denotes the frequency of word $w_{i}$ appearing in
description $E$, $|E|$ is the length of the description $D$, $\rm avgdl$ is
the average document length in entity descriptions. The hyperparameters
$k_{1}$ and $b$ are adjustable values, where we set $k_{1}=1.5$ and $b=0.75$.
We select the top-$k$ words with the highest scores as the final keyword set
$\mathcal{K}$ for the mention $m$.

###  3.2 Keyword Extractor

Our keyword extractor aims to denoise the context through sequence labeling.
Since discriminative pre-trained models can be easily adapted to tasks
involving multi-token classification Xia et al. (2022), we use ELECTRA as the
backbone of our keyword extractor, as shown in Figure 1(b). For the mention
$m$ in its context $M$, the input $\tau_{m}$ is the word-pieces of the
highlighted mention and its context:

$\texttt{[CLS]}\ {M}_{l}\ \texttt{[START]}\ {m}\ \texttt{[END]}\ M_{r}\
\texttt{[SEP]}$

where $M_{l}$ and $M_{r}$ are context before and after the mention $m$
respectively. [START] and [END] are special tokens to tag the mention. The
token embeddings from the last layer of the extractor $T$ can be denoted as
follows:

$\boldsymbol{H}={T}(\tau_{m})\in{\mathbb{R}}^{L\times d}$ (3)

where $L$ is the number of word-pieces in $\tau_{m}$ and $d$ is the hidden
dimension. Finally, the predicted score of the $i$-th token, denoted as
$\hat{s}_{i}$, is calculated with a discriminator head (i.e., a linear layer
$\boldsymbol{W}$) and the sigmoid activation function:

${\hat{s}_{i}}={\rm Sigmoid}(\boldsymbol{h}_{i}\boldsymbol{W})$ (4)

where $\boldsymbol{h}_{i}\in{\mathbb{R}}^{1\times d}$ is $i$-th row of the
matrix $\boldsymbol{H}$. $\hat{s}_{i}\in[0.0,1.0]$, and a higher score means
the token is more likely to be a keyword.

Optimization. In Section 3.1, for each mention $m$ and its context $M$, we
have obtained the keyword set $\mathcal{K}$. The tokens of every word in
$\mathcal{K}$ should be labeled as keywords. We optimize the extractor with a
binary cross entropy loss, as below:

$\mathcal{L}=-\frac{1}{L}\sum_{i=1}^{L}s_{i}{\rm
log}(\hat{s}_{i})+(1-s_{i}){\rm log}(1-{\hat{s}_{i}})$ (5)

where $s_{i}$ takes the value 1 if the $i$-th token should be labeled as a
keyword, otherwise 0.

Inference. The keyword extractor predicts a score $\hat{s}_{i}$ for every
token. The top-$k$ distinct tokens with the highest scores are selected for
the keyword set $\hat{\mathcal{K}}$. The final query for BM25 combines the
extracted keywords with the mention $m$:

$\mathcal{Q}=words(m)\cup\hat{\mathcal{K}}$ (6)

The top-$n$ retrieved entities by BM25 are the result of our method.

Domains | #Train | #Dev | #Test
---|---|---|---
Forgotten Realms | 50 | 50 | 1100
Lego | 50 | 50 | 1099
Star Trek | 50 | 50 | 4127
YuGiOh | 50 | 50 | 3274
Table 1: Statistics of the few-shot entity linking dataset ZESHEL. Method | Forgotten Realms | Lego | Star Trek | YuGiOh | Macro Average | Micro Average
---|---|---|---|---|---|---
BLINK Wu et al. (2020) | 35.27 | 52.68 | 21.57 | 35.00 | 36.13 | 31.28
MUVER Ma et al. (2021) | 37.27 | 66.15 | 23.89 | 56.38 | 45.92 | 41.34
GENRE Cao et al. (2021) | 67.27 | 50.32 | 55.75 | 29.14 | 50.62 | 47.37
DL4EL Le and Titov (2019) | 66.71 | 75.12 | 59.91 | 59.20 | 65.24 | 62.19
MetaBINK Li et al. (2022b) | 69.56 | 78.17 | 61.41 | 61.28 | 67.61 | 64.22
BM25 (mention words) | 83.87 | 81.62 | 65.99 | 61.03 | 73.13 | 68.14
BM25 (mention context) | 75.22 | 74.19 | 59.20 | 71.45 | 70.02 | 66.93
Ours | 88.53 | 85.48 | 74.81 | 79.75 | 82.14 | 79.29
Ours (w/o mention words) | 80.36 | 77.53 | 62.03 | 74.40 | 73.58 | 70.12
Table 2:  Recall@64 of our method compared with dense and generative retrievers (top) and sparse retrievers (bottom) on all test domains of ZESHEL. Bold denotes the best results.  Mention Context |  Corresponding Entity Description
---|---
Birth of the Ultimate Tag is the forty seventh chapter of the Yu Gi Oh GX manga. It was first printed in Japanese in the V Jump magazine and in English in the Shonen Jump magazine. Both of which were printed in volume 7 of the Yu Gi Oh GX graphic novels afterwards … |  Yu-Gi-Oh! GX-Volume 7 King Atticus True Power!!, known as The King ’ s True Power!! in the Japanese version, is the seventh volume of the Yu -Gi-Oh! GX manga.
Anzu bought magazines with tourist information. The two met at Domino Station at 10:00 where Anzu was nervous at first. They first went to a coffee shop for drinks. … |  Domino Coffee is a restaurant in Domino City in the anime and manga. …Gardner and Yami Yugi went here among other places on their date. …
Table 3: Examples of the extracted keywords and their overlap with the
corresponding entity descriptions. Italic denotes mentions. red in contexts
shows the extracted keywords. Red in entity descriptions represents words
overlapping with the keyword set.

##  4 Experiment

###  4.1 Dataset and Evaluation Metric

For fair comparison with Li et al. (2022b), we follow their few-shot
experimental settings, i.e., choose ZESHEL Logeswaran et al. (2019) as the
dataset, split the data as shown in Table 1 and use top-64 recall (i.e.,
Recall@64) as the evaluation metric.

###  4.2 Baselines

To evaluate our method, we compare it with the state-of-the-art sparse
retriever (i.e., BM25 Robertson and Zaragoza (2009)), dense retrievers (i.e.,
BLINK Wu et al. (2020), MUVER Ma et al. (2021), MetaBLINK Li et al. (2022b),
DL4EL Le and Titov (2019)), and the generative retriever GENRE Cao et al.
(2021). More details of the baselines can be found in Appendix A.
Implementation details are in Appendix B.

###  4.3 Results

Main results. Table 2 shows that our model outperforms all dense and
generative retrieval methods across all domains, and achieves a 15.07% micro-
averaged Recall@64 improvement over the best reported result (i.e.,
MetaBLINK).

Comparison among sparse retrievers in Table 2 highlights the importance of
mention-related context. BM25 (mention words) is apparently not the optimal
solution since it ignores all context; BM25 (mention context) leverages all
context and performs even worse, indicating the importance of context
denoising. The YuGiOh domain has the lowest recall of BM25 (mention words),
showing a large vocabulary mismatch between mention string and entity
documents. However, with mention-related context, our method addresses this
issue effectively, resulting in an impressive 18.72% performance improvement
in the YuGiOh domain.

Ablation study in Table 2, i.e. results of BM25 (mention words) and Ours (w/o
mention words), demonstrates that the mention string and the keywords are both
important to the final query. Deleting either of them in BM25’s query will
result in a significant performance drop. To further explore the contribution
of keywords, we present the case study in Table 3. From these cases, we can
find that the extracted keywords are semantically related to the mention,
excluding the noise in context.

##  5 Conclusion

In this work, we focus on the first-stage retrieval in few-shot entity linking
(EL). Given the significant performance drop in dense retrievers for few-shot
scenarios, we revisit the sparse retrieval method and enhance its performance
with a keyword extractor. We also propose a distant supervision approach for
automated training data generation. Our extensive experiments demonstrate our
method’s superior performance, with case studies showing denoised context and
mention-related keywords. Future work may focus on more PLM-augmented sparse
retrieval solutions for EL, expanding the query to words outside the context.

## Limitations

Despite surpassing the previous state-of-the-art performance by a significant
margin, our method exhibits certain limitations, primarily related to the
constraint on the keywords. The formulated query effectively denoises the
context, but is still limited to the scope of mention context. The vocabulary
mismatch between the mention context and the entity description cannot be
alleviated in our method. Expanding the query to words outside the context
could be an interesting research direction.

## Acknowledgments

We thank Zifei Shan for discussions and the valuable feedback. This work is
jointly supported by grants: Natural Science Foundation of China (No.
62006061, 82171475), Strategic Emerging Industry Development Special Funds of
Shenzhen (No.JCYJ20200109113403826).

## References

  * Cao et al. (2021) Nicola De Cao, Gautier Izacard, Sebastian Riedel, and Fabio Petroni. 2021.  Autoregressive entity retrieval.  In _International Conference on Learning Representations_.
  * Clark et al. (2020) Kevin Clark, Minh-Thang Luong, Quoc V. Le, and Christopher D. Manning. 2020.  Electra: Pre-training text encoders as discriminators rather than generators.  In _International Conference on Learning Representations_.
  * Dong et al. (2022) Yue Dong, John Wieting, and Pat Verga. 2022.  Faithful to the document or to the world? mitigating hallucinations via entity-linked knowledge in abstractive summarization.  In _Findings of the Association for Computational Linguistics: EMNLP 2022_ , pages 1067–1082, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.
  * Formal et al. (2021) Thibault Formal, Benjamin Piwowarski, and Stéphane Clinchant. 2021.  Splade: Sparse lexical and expansion model for first stage ranking.  In _Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval_ , SIGIR ’21, page 2288–2292, New York, NY, USA. Association for Computing Machinery.
  * Ji and Nothman (2016) Heng Ji and Joel Nothman. 2016.  Overview of TAC-KBP2016 tri-lingual EDL and its impact on end-to-end KBP.  In _Proceedings of the 2016 Text Analysis Conference, TAC 2016, Gaithersburg, Maryland, USA, November 14-15, 2016_. NIST.
  * Kingma and Ba (2015) Diederik P. Kingma and Jimmy Ba. 2015.  Adam: A method for stochastic optimization.  In _3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings_.
  * Le and Titov (2019) Phong Le and Ivan Titov. 2019.  Distant learning for entity linking with automatic noise detection.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 4081–4090, Florence, Italy. Association for Computational Linguistics.
  * Li et al. (2022a) Haoran Li, Yangqiu Song, and Lixin Fan. 2022a.  You don’t know my favorite color: Preventing dialogue representations from revealing speakers’ private personas.  _arXiv preprint arXiv:2205.10228_.
  * Li et al. (2022b) Xiuxing Li, Zhenyu Li, Zhengyan Zhang, Ning Liu, Haitao Yuan, Wei Zhang, Zhiyuan Liu, and Jianyong Wang. 2022b.  Effective few-shot named entity linking by meta-learning.  In _2022 IEEE 38th International Conference on Data Engineering (ICDE)_ , pages 178–191, Los Alamitos, CA, USA. IEEE Computer Society.
  * Logeswaran et al. (2019) Lajanugen Logeswaran, Ming-Wei Chang, Kenton Lee, Kristina Toutanova, Jacob Devlin, and Honglak Lee. 2019.  Zero-shot entity linking by reading entity descriptions.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 3449–3460, Florence, Italy. Association for Computational Linguistics.
  * Ma et al. (2021) Xinyin Ma, Yong Jiang, Nguyen Bach, Tao Wang, Zhongqiang Huang, Fei Huang, and Weiming Lu. 2021.  MuVER: Improving first-stage entity retrieval with multi-view entity representations.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 2617–2624, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Mao et al. (2022) Kelong Mao, Zhicheng Dou, and Hongjin Qian. 2022.  Curriculum contrastive context denoising for few-shot conversational dense retrieval.  In _Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval_ , SIGIR ’22, page 176–186, New York, NY, USA. Association for Computing Machinery.
  * Ren et al. (2022) Ruiyang Ren, Yingqi Qu, Jing Liu, Wayne Xin Zhao, Qifei Wu, Yuchen Ding, Hua Wu, Haifeng Wang, and Ji-Rong Wen. 2022.  A thorough examination on zero-shot dense retrieval.  _CoRR_ , abs/2204.12755.
  * Robertson and Zaragoza (2009) Stephen Robertson and Hugo Zaragoza. 2009.  The probabilistic relevance framework: Bm25 and beyond.  _Found. Trends Inf. Retr._ , 3(4):333–389.
  * Sun et al. (2022) Kai Sun, Richong Zhang, Samuel Mensah, Yongyi Mao, and Xudong Liu. 2022.  A transformational biencoder with in-domain negative sampling for zero-shot entity linking.  In _Findings of the Association for Computational Linguistics: ACL 2022_ , pages 1449–1458, Dublin, Ireland. Association for Computational Linguistics.
  * Wang et al. (2023) Weiqi Wang, Tianqing Fang, Baixuan Xu, Chun Yi Louis Bo, Yangqiu Song, and Lei Chen. 2023.  Cat: A contextualized conceptualization and instantiation framework for commonsense reasoning.  _arXiv preprint arXiv:2305.04808_.
  * Wu et al. (2020) Ledell Wu, Fabio Petroni, Martin Josifoski, Sebastian Riedel, and Luke Zettlemoyer. 2020.  Scalable zero-shot entity linking with dense entity retrieval.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 6397–6407, Online. Association for Computational Linguistics.
  * Xia et al. (2022) Mengzhou Xia, Mikel Artetxe, Jingfei Du, Danqi Chen, and Veselin Stoyanov. 2022.  Prompting ELECTRA: Few-shot learning with discriminative pre-trained models.  In _Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing_ , pages 11351–11361, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.
  * Yang et al. (2017) Peilin Yang, Hui Fang, and Jimmy Lin. 2017.  Anserini: Enabling the use of lucene for information retrieval research.  In _Proceedings of the 40th International ACM SIGIR Conference on Research and Development in Information Retrieval_ , SIGIR ’17, page 1253–1256, New York, NY, USA. Association for Computing Machinery.

##  Appendix A Baseline details

To evaluate the performance of our method, we compare with the following
state-of-the-art retrievers that represent a diverse array of approaches.

  * •

BM25 Robertson and Zaragoza (2009), a traditional and strong sparse retrieval
method. We consider two variants: BM25 (mention words), which simply uses the
mention string as query, and BM25 (mention context), which uses all context as
query.

  * •

BLINK Wu et al. (2020) adopts the bi-encoder architecture for dense retrieval.

  * •

MUVER Ma et al. (2021) extends the bi-encoder to multi-view entity
representations and approximates the optimal view for mentions via a heuristic
searching method.

  * •

GENRE Cao et al. (2021) is an autoregressive retrieval method base on
generating the title of candidates with constrained beam search.

  * •

MetaBLINK Li et al. (2022b) proposes a weak supervision method to generate
mention-entity pairs. These pairs are then used for training BLINK with a
meta-learning mechanism.

  * •

DL4EL Le and Titov (2019) is a denoising method based on KL divergence to
force the model to select high-quantity data. It can be combined with
MetaBLINK’s generated data to train BLINK.

##  Appendix B Implementation Details

Our model is implemented with PyTorch 1.10.0. The number of the model
parameters is roughly 109M. All experiments are carried out on a single NVIDIA
A100 GPU. We use Adam optimizer Kingma and Ba (2015) with weight decay set to
0.01, learning rate set to 2e-5. The batch size is 8, and the number of
extracted keywords (denoted as $k$) is 32, For the convenience of comparison,
the number of final retrieved entities (denoted as $n$) is 64. The mention
context length is set to 128, with each left and right context having a length
of 64. For each domain, we train for a total of 10 epochs, and choose the best
checkpoint based on the performance of development set. The whole training
process takes about 1.5 minutes for each domain.

In Table 2, the results of MUVER and GENRE are our reproduction based on their
official Github repositories. These reproduction results, together with
results of sparse retrievers, are from 5 runs of our implementation with
different random seeds.


# Maximum Likelihood Estimators of Quantum Probabilities

Mirko Navara, Jan Ševic
Department of Cybernetics
, Faculty of Electrical Engineering,
Czech Technical University in Prague,
Czech Republic,
<EMAIL_ADDRESS>
###### Abstract

Classical probability theory is based on assumptions which are often violated
in practice. Therefore quantum probability is a proposed alternative not only
in quantum physics, but also in other sciences. However, so far it mostly
criticizes the classical approach, but does not suggest a working alternative.
Maximum likelihood estimators were given very low attention in this context.
We show that they can be correctly defined and their computation in closed
form is feasible at least in some cases.

##  1 Motivation of quantum probability

Classical probability is based on the following principles:

  1. 1.

Results of experiments are evaluated in yes-no terms.

  2. 2.

Experiments can be repeated arbitrarily many times.

  3. 3.

The initial state of a random experiment can be reconstructed.

When the first principle is violated, we need probability of many-valued
statements; this is not the direction studied in this paper. The second
principle is theoretical; we apply the theory also to experiments whose
repeatability is limited by some finite number, e.g., the number of people in
the world. Here we concentrate on the case when the third principle does not
hold. Quantum measurements cause irreversible changes of the system and the
initial state can never be reconstructed. This phenomenon is typical in
quantum physics, therefore we speak of quantum probability, but it occurs in
many other situations. E.g., elections cannot be repeated under the same
conditions, so we have no tool for a direct comparison of two strategies—only
one of them can be tested. Such situations are frequent in sociology,
psychology, and recently even in machine learning; we work with such big
databases that we cannot keep them all in the memory and each experiment will
be performed in different circumstances (e.g., finding different random data
on the internet). For simplicity, we speak here of quantum events.

When we apply the classical Kolmogorovian probability to such systems, we
obviously make an error. It is not the statistical error, well described by
the theory, but an unpredictable error due to the use of assumptions which are
not satisfied. The only correct way is to use more general theory fitting to
the real situations, and this is quantum probability. It shows why the
classical results may be erroneous. However, it is easy to criticize, but
difficult to develop a working alternative. In particular, it is hard to
introduce conditional probability of fuzzy events; performing one measurement,
the Heisenberg’s uncertainty principle makes some other measurements
impossible, although they were allowed at the beginning and therefore must be
included in the probabilistic model. Many statistical tools are based on the
laws of large numbers and the existence of infinite sequences of independent
random experiments, and we do not see a way how to generalize them to quantum
probability.

However, the second principle seems to be valid in quantum probability at
least to the extent that a large repetition of experiments can give us useful
data. Although the initial conditions are not guaranteed, their partial
knowledge can be described by probabilities. The possibility of acquiring
large data enables to use them for estimation of parameters of the model. Here
we show that unknown probabilities can be estimated by a maximum likelihood
estimator (MLE) generalized to quantum probabilities. As far as we know, the
only such attempt was made in [Kläy and Foulis1990]. It solved several
particular cases and demonstrated that the results obtained by quantum
probability substantially differ from those offered by the classical theory.
We continue this research in a similar direction.

##  2 Motivating example

Let us demonstrate the situation on a simple example. A coach of a tennis team
decides which of two players, A or B, will play the first match. (Many random
inputs influence the result, the choice of the oponent, health conditions,
etc. We hope that they can be described by the probabilities of outcomes and
will still allow to compare the players on the base of long-term data.) There
are five possible outcomes:

  1. 1.

$a$ … A played and won,

  2. 2.

$b$ … B played and won,

  3. 3.

$c$ … A played and lost,

  4. 4.

$d$ … B played and lost,

  5. 5.

$e$ … the match was cancelled.

When A is nominated, the possible outcomes are $a$, $c$, and $e$, with the
respective probabilities $p(a)$, $p(c)$, and $p(e)$, summing up to $1$. When B
is nominated, the possible outcomes are $b$, $d$, and $e$, with the respective
probabilities $p(b)$, $p(d)$, and $p(e)$, summing up to $1$. The coach can
decide between two random experiments, each described by a classical
probability. However, only one of the two random experiments can be performed,
disabling the other.

The two possible experiments share one common result, $e$. While the coach
knows which player he nominated, an independent observer knows only which of
the five outcomes occurred. In case $e$, when the match was cancelled, it is
not known which of the two experiments was performed. The observer knows only
a long series of outcomes of preceding matches. Based on it, he wants to
estimate non-negative probabilities $p(a)$, $p(b)$, $p(c)$, $p(d)$, and
$p(e)$, subject to restrictions

$p(a)+p(c)+p(e)=p(b)+p(d)+p(e)=1\,.$ (1)

We shall show that this may be solved by an easy modification of a classical
maximum likelihood estimator, which has also an intuitive interpretation.
However, other models lead to more complicated tasks. We solve them at least
for some classes of quantum probability models.

##  3 Basic notions

We shall deal only with finite models. That is reasonable because the
estimator uses finitely many results and cannot say anything about those which
did not occur in the sample.

As event structures, generalizing classical Boolean algebras, we use
orthomodular lattices, or even orthomodular posets [Beran1984, Kalmbach1983].
To make the text understandable also to readers not well acquainted with these
algebraic structures, we start from their hypergraph representation in simple
cases and leave more general ones to the end of the paper.

A _hypergraph_ is a couple $(A,\mathcal{B})$, where $A$ is a non-empty set and
$\mathcal{B}$ is its covering by non-empty subsets. The elements of $A$ are
_vertices_ and represent all possible _outcomes, results, atoms_ , or
_answers_ of the system. The elements of $\mathcal{B}$ (some subsets of $A$)
are _edges_ and represent all possible _operations, experiments, blocks_ , or
_questions_. Here we follow the terminology of [Kläy and Foulis1990] and call
the elements of $A$ _outcomes_ and the elements of $\mathcal{B}$
_operations_.111Only if there is a risk of confusion, we speak of edges rather
than operations. An operation $B\in\mathcal{B}$ is the set of all its possible
outcomes.

In the example from Section 2, $A=\\{a,b,c,d,e\\}$,
$\mathcal{B}=\\{\\{a,c,e\\},\\{b,d,e\\}\\}$. The respective hypergraph is
drawn in Fig. 1.

$e$$a$$d$$b$$c$$B$$A$ Figure 1: Greechie diagram of the motivating example

We see that a probability is uniquely described by a non-negative evaluation
of the outcomes which sums up to $1$ for each operation. Formally: $p\colon
A\to[0,1]$ such that

$\forall B\in\mathcal{B}:\sum_{x\in B}p(x)=1\,.$ (2)

Such a probability assignment can be uniquely extended to other events which
combine the (elementary) outcomes by logical operations, e.g.,

$p(a\lor c)=p(a)+p(c)=1-p(e)=p(e^{\prime})\,,$ (3)

where $e^{\prime}$ denotes the negation of $e$. Notice that also

$p(b\lor d)=p(b)+p(d)=1-p(e)=p(e^{\prime})\,,$ (4)

thus

$p(a\lor c)=p(b\lor d)\,.$ (5)

This is not only an equality of probabilities; $a\lor c$ and $b\lor d$
represent the same event, “the match was not cancelled”. It has a non-unique
representation as a disjunction of (elementary) outcomes. This is what
motivates the notion of orthomodular lattices for description of _all_ events
of the system. However, it is sufficient to determine the probability of the
elementary events, called outcomes here.

Not all finite hypergraphs represent quantum operations and outcomes. For
that, necessary and sufficient conditions were proved in [Dichtl1981,
Kalmbach1983]. We do not quote these complicated results here because we will
manage with some simple situations. E.g., if every couple of operations shares
at most one common outcome, then the necessary and sufficient conditions for a
hypergraph to represent an orthomodular poset (resp. an orthomodular lattice)
reduce to the conjunction of the following:

  1. (G1)

$\forall B_{1},B_{2}\in\mathcal{B},B_{1}\neq
B_{2}:\operatorname{card}(B_{1}\setminus B_{2})\geq 2\,,$

  2. (G2)

the length of every cycle in $(A,\mathcal{B})$ is at least $4$ (resp.
$5$).222The notion of a cycle in a hypergraph is quite natural, though
mathematically complicated. We refer to [Dichtl1981, Kalmbach1983] for
details.

The finite hypergraphs which represent orthomodular posets are called
_Greechie diagrams_. They were introduced in [Greechie1971].

######  Remark 1.

The two-element Boolean algebra corresponds to the Greechie diagram with a
single vertex and a single edge, $(\\{e\\},\\{\\{e\\}\\})$.

In [Kläy and Foulis1990], a more general approach was studied, based on so-
called _test spaces_ , introduced by Foulis and Randall. They admit also
strict inclusion between Boolean algebras of events generated by outcomes of
two different operations. This allows to represent partial answers to
questions, like “I do not tell you whom I vote for, but it definitely will not
be X.Y.”. Here we restrict attention to the case when all events form an
orthomodular poset and questions are maximal sets of mutually exclusive
outcomes.

##  4 Notation and formulation of the task

We assume that we know the model of events described by a Greechie diagram
$(A,\mathcal{B})$. Further, we have a sequence of realizations of outcomes.
Their order is unimportant, the only useful inputs are absolute frequencies
$n(x)\in\mathbb{N}$ for all $x\in A$. From these, we want to estimate the
probabilities $p(x)\in[0,1]$, $x\in A$. They have to satisfy the restrictions
(2).

We want to choose such $p\colon A\to[0,1]$ which maximizes the likelihood,

$L(p)=\prod_{x\in A}p(x)^{n(x)}\,.$ (6)

The maximum likelihood is positive and then we may equivalently maximize the
log-likelihood

$\ell(p)=\ln L(p)=\sum_{x\in A^{+}}n(x)\,\ln p(x)\,,$

where the sum is taken over the set of all outcomes $x$ with non-zero
probability, $A^{+}=\\{x\in A\mid p(x)\neq 0\\}$. If the absolute frequency
$n(x)=0$ for some outcome $x$, its probability $p(x)$ will not occur in the
formula for likelihood. Maximal likelihood is achieved for $p(x)=0$ (leaving
maximum freedom for the probabilities of other outcomes) and we may omit such
outcomes in our analysis.333We really achieve _maximum_ likelihood for
$p(x)=0$. This does not appear in (6); more exactly, it gives rise to a factor
$p(x)^{n(x)}=0^{0}=1$ which does not affect the product. The sum of other
probabilities is upper bounded by $1-p(x)$, which becomes the maximal bound,
$1$, and thus allows their maximal values. From now on, we shall assume that
all outcomes have non-zero frequencies.444There is one significant difference:
without such outcomes, condition (G1) may be violated. However, this is only a
technical assumption needed for the Greechie diagram to represent an
orthomodular poset. In order to have a hypergraph which properly represents
the probabilities, this is not important and our computations work without
this condition, too.

In a classical system, $\mathcal{B}$ contains only one operation, which is
$A$, the Greechie diagram is $(A,\mathcal{B})=(A,\\{A\\})$. Then (2) attains
the form $\sum_{x\in A}p(x)=1$ and MLE has a well-known solution, which is the
empirical distribution with

$p(x)=\frac{n(x)}{\sum\limits_{y\in A}n(y)}\quad\text{ for all }\quad x\in
A\,.$

We shall use this principle several times, thus we formulate it as a simple
lemma:

######  Lemma 1.

Given numbers $n_{1},\ldots,n_{k}\in[0,\infty]$, we look for probabilities
$p_{1},\ldots,p_{k}\in[0,1]$ such that $\sum_{i}p_{i}=1$ and

$\sum_{i}n_{i}\,\ln p_{i}$

is maximal. This task has a unique solution, which satisfies

$p_{i}=\frac{n_{i}}{\sum\limits_{j}n_{j}}$

for all $i$; equivalently, the ratio

$\frac{n_{i}}{p_{i}}=\sum_{j}n_{j}$

is the same for all $i$.

##  5 Horizontal sums of classical models

Assume now that the event system is described by a Greechie diagram
$(A,\mathcal{B})$ composed of $k$ _mutually disjoint_ operations
$A_{1},\ldots,A_{k}$, i.e., $A=\bigcup_{i}A_{i}$ and
$\mathcal{B}=\\{A_{1},\ldots,A_{k}\\}$. Then $(A,\mathcal{B})$ is called a
_horizontal sum_ of the classical systems described by the Greechie diagrams
$(A_{1},\\{A_{1}\\}),\ldots,(A_{k},\\{A_{k}\\})$. In this case, each outcome
$x\in A$ is contained in a _unique_ operation $A_{i}$, $i\in\\{1,\ldots,k\\}$.

From the absolute frequencies $n\colon A\to\mathbb{N}$, we know that operation
$A_{i}$ produced $n(A_{i}):=\sum_{x\in A_{i}}n(x)$ outcomes. Their
probabilities can be estimated like probabilities conditioned by the fact that
$A_{i}$ was the chosen operation. The log-likelihood becomes

$\displaystyle\ell(p)$ $\displaystyle=\sum_{x\in A}n(x)\,\ln
p(x)=\sum_{i}\sum_{x\in A_{i}}n(x)\,\ln p(x)$
$\displaystyle=\sum_{i}n(A_{i})\,\underbrace{\sum_{x\in
A_{i}}\frac{n(x)}{n(A_{i})}\,\ln p(x)}_{\ell(p|A_{i})}\,.$ (7)

The last sum can be understood as the log-likelihood of a conditional
probability $p|A_{i}\colon A_{i}\to[0,1]$, whose values on $A_{i}$ sum up to
$1$. This log-likelihood is based on the subsample of outcomes belonging to
$A_{i}$. Lemma 1 is applicable and the $i$th summand is maximized if the
restriction $p|A_{i}$ 555Here $p|A_{i}$ denotes the restriction of $p$ to
$A_{i}$ like a conditional probability; it may be understood this way, too.
coincides with the coefficients $\frac{n(x)}{n(A_{i})}$. This maximization is
independent of all other summands of the outer sum, thus giving a global
maximum by

$p(x)=\frac{n(x)}{n(A_{i})}=(p|A_{i})(x)$ (8)

for all $x\in A_{i}$ and all $i\in\\{1,\ldots,k\\}$. Notice that the ratio

$\frac{n(x)}{p(x)}=n(A_{i})$ (9)

depends only on $i$, not on the choice of $x\in A_{i}$.

This result is not surprising and is supported by intuition. We shall
generalize it in Section 9.

##  6 Motivating example continued

The example from Section 2 is not a horizontal sum, outcome $e$ belongs to two
operations and has just one probability, summing the cases when it originates
from the first or the second operation. We shall demonstrate the MLE for this
structure and generalize the procedure in the next section.

MLE requires to maximize the log-likelihood

$\sum_{x\in\\{a,b,c,d,e\\}}n(x)\,\ln p(x)$

under restrictions (1), which can be solved by standard techniques. Another
idea is to estimate first

$p(e)=\frac{n(e)}{\sum_{x\in\\{a,b,c,d,e\\}}n(x)}\,.$ (10)

The remaining outputs form the set $C=\\{a,b,c,d\\}$ and have a total
probability $p(C):=1-p(e)$. Probabilities of outputs from $C$ are restricted
by conditions

$p(a)+p(c)=p(b)+p(d)=1-p(e)=p(C)\,.$

If we define $p(.|C)\colon C\to[0,1]$ by666Here $p(.|C)$ is really an ordinary
conditional probability, not a restriction as in Section 5.
$p(x|C)=\frac{p(x)}{p(C)}$,

$p(a|C)+p(c|C)=p(b|C)+p(d|C)=1\,.$ (11)

Maximization of the expression

$\sum_{x\in C}n(x)\,\ln p(x)$ (12)

under conditions (11) is the same as MLE for the system described by the
Greechie diagram $(C,\\{C_{1},C_{2}\\})$, where $C_{1}=\\{a,c\\}$,
$C_{2}=\\{b,d\\}$, see Fig. 2. This is the horizontal sum of two classical
systems corresponding to operations $C_{1},C_{2}$. The MLE estimator of
probability $p(.|C)$ on $(C,\\{C_{1},C_{2}\\})$ is based on the subsample from
$C$, excluding $e$, which is of sample size $n(C):=\sum_{x\in C}n(x)$.
Similarly, we define $n(C_{1}):=\sum_{x\in C_{1}}n(x)=n(a)+n(c)$ and
$n(C_{2}):=\sum_{x\in C_{2}}n(x)=n(b)+n(d)$. According to Section 5, the
maximum of (12) is achieved for

$\displaystyle p(a|C)$
$\displaystyle=\frac{n(a)}{n(C_{1})}=\frac{n(a)}{n(a)+n(c)}\,,$ $\displaystyle
p(c|C)$ $\displaystyle=\frac{n(c)}{n(C_{1})}=\frac{n(c)}{n(a)+n(c)}\,,$
$\displaystyle p(b|C)$
$\displaystyle=\frac{n(b)}{n(C_{2})}=\frac{n(b)}{n(b)+n(d)}\,,$ $\displaystyle
p(d|C)$ $\displaystyle=\frac{n(d)}{n(C_{2})}=\frac{n(d)}{n(b)+n(d)}\,.$

This optimum is independent of the estimated value of $p(e)$. A routine
verification confirms that the choice (10) is really optimal. The remaining
estimated probabilities are

$\displaystyle p(a)$
$\displaystyle=p(C)\,p(a|C)=(1-p(e))\,\frac{n(a)}{n(a)+n(c)}\,,$
$\displaystyle p(c)$
$\displaystyle=p(C)\,p(c|C)=(1-p(e))\,\frac{n(c)}{n(a)+n(c)}\,,$
$\displaystyle p(b)$
$\displaystyle=p(C)\,p(b|C)=(1-p(e))\,\frac{n(b)}{n(b)+n(d)}\,,$
$\displaystyle p(d)$
$\displaystyle=p(C)\,p(d|C)=(1-p(e))\,\frac{n(d)}{n(b)+n(d)}\,.$

Notice that

$\displaystyle\frac{n(a)}{p(a)}$ $\displaystyle=\frac{n(c)}{p(c)}\,,$
$\displaystyle\frac{n(b)}{p(b)}$ $\displaystyle=\frac{n(d)}{p(d)}\,.$

$a$$b$$c$$d$$C_{1}$$C_{2}$ Figure 2: Greechie diagram of a part of the
motivating example

We shall generalize this procedure in the next section.

##  7 Products

The general construction of products (sometimes called direct sums) of
algebraic structures is applicable to orthomodular posets and lattices. When
expressed in terms of their Greechie diagrams, its description is cumbersome,
but the understanding of probabilities on a product will be easy. It acts as
follows:

Let $(B_{1},\mathcal{B}_{1}),\ldots,(B_{k},\mathcal{B}_{k})$ be Greechie
diagrams with $B_{1},\ldots,B_{k}$ mutually disjoint. Their _product_ is the
Greechie diagram $(B,\mathcal{B})$, where

$\displaystyle B$ $\displaystyle:=\bigcup_{j}B_{j}\,,$
$\displaystyle\mathcal{B}$
$\displaystyle:=\biggl{\\{}\bigcup_{j}C_{j}\mid\forall
j\in\\{1,\ldots,k\\}:C_{j}\in\mathcal{B}_{j}\biggr{\\}}\,.$

Each choice
$(C_{1},\ldots,C_{k})\in\mathcal{B}_{1}\times\ldots\times\mathcal{B}_{k}$
corresponds to one edge (operation) of $\mathcal{B}$, restricting the
probability $p$ on $\mathcal{B}$ by the equation

$\sum_{x\in\bigcup_{j}C_{j}}p(x)=\sum_{j}\sum_{x\in C_{j}}p(x)=1\,.$

If choices
$(C_{1},C_{2},\ldots,C_{k}),(C_{1}^{*},C_{2},\ldots,C_{k})\in\mathcal{B}_{1}\times\ldots\times\mathcal{B}_{k}$
differ only in the first item, we see that

$\displaystyle\sum_{x\in C_{1}}p(x)+\sum_{j=2}^{k}\sum_{x\in C_{j}}p(x)$
$\displaystyle=1=\sum_{x\in C_{1}^{*}}p(x)+\sum_{j=2}^{k}\sum_{x\in
C_{j}}p(x)\,,$ $\displaystyle\sum_{x\in C_{1}}p(x)$ $\displaystyle=\sum_{x\in
C_{1}^{*}}p(x)\,.$ (13)

Thus the value

$p(B_{1}):=\sum_{x\in C_{1}}p(x)\,,$

is independent of the choice of $C_{1}\in\mathcal{B}_{1}$ and $p(B_{1})$ is
correctly defined. Similarly, for any index $i\in\\{1,\ldots,k\\}$ (replacing
index $1$ in (13)), we may correctly define the value

$p(B_{i}):=\sum_{x\in C_{i}}p(x)\,,$

where $C_{i}\in\mathcal{B}_{i}$ can be chosen arbitrarily. It is the
probability that the experiment gives an output from $B_{i}$.777Notice that we
cannot sum over all $B_{i}$ if it has more edges (operations). We also define
conditional probability $p(.|B_{i})\colon B_{i}\to[0,1]$,

$p(x|B_{i}):=\frac{p(x)}{p(B_{i})}$

for all $x\in B_{i}$.

The log-likelihood can be expressed as

$\displaystyle\ell(p)$ $\displaystyle=\sum_{x\in B}n(x)\,\ln
p(x)=\sum_{i}\sum_{x\in B_{i}}n(x)\,\ln p(x)$
$\displaystyle=\sum_{i}\sum_{x\in B_{i}}n(x)\,\ln
p(x|B_{i})+\sum_{i}\sum_{x\in B_{i}}n(x)\,\ln p(B_{i})\,.$

The latter sum can be simplified to

$\sum_{i}\sum_{x\in B_{i}}n(x)\,\ln p(B_{i})=\sum_{i}n(B_{i})\,\ln
p(B_{i})\,,$

where $n(B_{i}):=\sum_{x\in B_{i}}n(x)=\sum_{x\in B_{i}}n(x)$ is the number of
samples belonging to $B_{i}$. Lemma 1 proves that this expression achieves its
maximum for

$p(B_{i})=\frac{n(B_{i})}{\sum_{j}n(B_{j})}\,.$ (14)

It remains to maximize the sum

$\sum_{i}\sum_{x\in B_{i}}n(x)\,\ln p(x|B_{i})\,.$

Parameters describing its maximum are independent of the unconditional
probabilities $p(B_{i})$ and also independent between different indices $i$.
Thus the task of MLE can be decomposed to the following steps:

  1. 1.

Compute $p(B_{1}),\ldots,p(B_{k})$ from (14).

  2. 2.

For each $i$, find MLE of the conditional probability $p(x|B_{i})$. Using
$p(B_{i})$ from Step 1, convert it to an unconditional probability
$p(x)=p(B_{i})\,p(x|B_{i})$, $x\in B_{i}$.

Thus the task of MLE is decomposed to simpler subtasks for each factor
separately.

The Greechie diagram from Section 2 can be considered a product of one one-
element edge (representing the two-element Boolean algebra, see Remark 1) and
a horizontal sum with two two-element edges. Its MLE described in Section 6 is
a special case of the procedure described here.

##  8 Horizontal sums of quantum models

Let $(A_{1},\mathcal{B}_{1}),\ldots,(A_{k},\mathcal{B}_{k})$ be Greechie
diagrams with $A_{1},\ldots,A_{k}$ mutually disjoint. We define
$A=\bigcup_{i}A_{i}$ and $\mathcal{B}=\bigcup_{i}\mathcal{B}_{i}$. Then
$(A,\mathcal{B})$ is a Greechie diagram of an event structure called a
_horizontal sum_ of $(A_{1},\mathcal{B}_{1}),\ldots,(A_{k},\mathcal{B}_{k})$.
As in the special case studied in Section 5, each outcome $x\in A$ is
contained in a _unique_ summand $A_{i}$, $i\in\\{1,\ldots,k\\}$.

A probability $p$ on $(A,\mathcal{B})$ is uniquely determined by its
restrictions $p|A_{i}$, $i\in\\{1,\ldots,k\\}$, and these can be arbitrary
probabilities on the horizontal summands $(A_{i},\mathcal{B}_{i})$.

The situation is analogous to that of Section 5. From the absolute frequencies
$n\colon A\to\mathbb{N}$, we know that the summand $A_{i}$ produced
$n(A_{i}):=\sum_{x\in A_{i}}n(x)$ outcomes. Their probabilities can be
estimated like probabilities conditioned by the fact that $A_{i}$ was the
respective operation. The log-likelihood is again expressed by (7) and
achieves its maximum for (8). Thus the task of MLE is decomposed to simpler
subtasks for each horizontal summand separately.

##  9 Constructible lattices

Janowitz [Janowitz1972] introduced _constructible lattices_ as the class
generated from Boolean algebras by the operations of a product and a
horizontal sum (applied arbitrarily many times). This class does not contain
all orthomodular lattices, but it played a role in numerous papers on quantum
structures. The example from Section 2 is constructible.

MLE works for horizontal sums and also for products, as described in Sections
7 and 8. Thus we directly obtain MLE for all finite constructible lattices,
just by subsequent application of these techniques.

##  10 Non-constructible lattices

The simplest orthomodular lattice which is not constructible is described by
its Greechie diagram in Fig. 3.

Figure 3: Greechie diagram of the smallest non-constructible orthomodular
lattice

For it, the preceding ideas do not work and we do not see any intuitive
solution. We shall show that the MLE is still feasible for it. More generally,
we present it for a Greechie diagram with edges (operations) $A_{1}$, $A_{2}$,
$A_{3}$ satisfying $A_{1}\cap A_{2}=\\{y_{1}\\}$, $A_{2}\cap
A_{3}=\\{y_{2}\\}$, $A_{1}\cap A_{3}=\varnothing$. They form the same shape,
but may have more than three outcomes of each operation, see Fig. 4.

$\vdots$$\cdots$$\vdots$$A_{3}$$A_{1}$$A_{2}$$y_{2}$$y_{1}$ Figure 4: Greechie
diagram of a non-constructible orthomodular lattice for which MLE is feasible

Like Sections 7 and 8, the solution can be done in two steps.

First, we define:

$\displaystyle B_{1}$ $\displaystyle=A_{1}\setminus
A_{2}=A_{1}\setminus\\{y_{1}\\}\,,$ $\displaystyle B_{2}$
$\displaystyle=A_{2}\setminus A_{1}\setminus
A_{3}=A_{2}\setminus\\{y_{1},y_{2}\\}\,,$ $\displaystyle B_{3}$
$\displaystyle=A_{3}\setminus A_{2}=A_{3}\setminus\\{y_{2}\\}\,.$

Consider any $i\in\\{1,2,3\\}$. Using Lemma 1 as in Section 5, necessary
conditions for a maximum likelihood estimator are that the ratio
$\frac{n(x)}{p(x)}$ is the same for all $x\in B_{i}$, namely

$\frac{n(x)}{p(x)}=\frac{\sum\limits_{y\in B_{i}}n(y)}{\sum\limits_{y\in
B_{i}}p(y)}=:\frac{n(B_{i})}{p(B_{i})}=:K_{i}\,,$

where we denoted

$\displaystyle n(B_{i})$ $\displaystyle=\sum_{y\in B_{i}}n(y)\,,$
$\displaystyle p(B_{i})$ $\displaystyle=\sum_{y\in B_{i}}p(y)\,.$

Equivalently,

$p(x|B_{i}):=\frac{p(x)}{p(B_{i})}=\frac{n(x)}{n(B_{i})}\,.$

$B_{1}$$y_{2}$$y_{1}$$B_{3}$$B_{2}$ Figure 5: Simplified diagram of the second
step of MLE of the diagram from Fig. 4

In the second step, the have to optimize the likelihood for a simplified
structure which can be vaguely represented by Fig. 5; here $B_{i}$ play a role
of outcomes rather than sets of outcomes. From the absolute frequencies
$n(B_{1})$, $n(y_{1})$, $n(B_{2})$, $n(y_{2})$, $n(B_{3})$, we have to
estimate the corresponding probabilities, bound by the restrictions

$\displaystyle p(B_{1})+p(y_{1})$ $\displaystyle=1\,,$ $\displaystyle
p(B_{2})+p(y_{1})+p(y_{2})$ $\displaystyle=1\,,$ $\displaystyle
p(B_{3})+p(y_{2})$ $\displaystyle=1\,.$

We define:

$\displaystyle c_{1}$
$\displaystyle:=\frac{K_{2}}{K_{1}+K_{2}}=\frac{n(x_{2})\,p(x_{1})}{n(x_{1})\,p(x_{2})+n(x_{2})\,p(x_{1})}\,,$
$\displaystyle c_{2}$
$\displaystyle:=\frac{K_{2}}{K_{3}+K_{2}}=\frac{n(x_{2})\,p(x_{3})}{n(x_{3})\,p(x_{2})+n(x_{2})\,p(x_{3})}\,.$

The MLE solution of the diagram from Fig. 5 gives conditions:

$\displaystyle\frac{n(B_{1})}{p(B_{1})}$
$\displaystyle=n(B_{1})+(1-c_{1})\,n(y_{1})\,,$
$\displaystyle\frac{n(B_{2})}{p(B_{2})}$
$\displaystyle=n(B_{2})+c_{1}\,n(y_{1})+c_{2}\,n(y_{2})\,,$
$\displaystyle\frac{n(B_{3})}{p(B_{3})}$
$\displaystyle=n(B_{3})+(1-c_{2})\,n(y_{2})\,,$
$\displaystyle\frac{n(y_{i})}{p(y_{i})}$
$\displaystyle=\frac{n(B_{2})+c_{1}\,n(y_{1})+c_{2}\,n(y_{2})}{c_{i}}$
$\displaystyle\forall i\in\\{1,2\\}\,.$

Then the MLE solution of Fig. 5 takes the following form:

$\displaystyle p(x)$ $\displaystyle=\frac{n(x)}{n(B_{1})+(1-c_{1})\,n(y_{1})}$
$\displaystyle\forall x\in B_{1}\,,$ $\displaystyle p(x)$
$\displaystyle=\frac{n(x)}{n(B_{2})+c_{1}\,n(y_{1})+c_{2}\,n(y_{2})}$
$\displaystyle\forall x\in B_{2}\,,$ $\displaystyle p(x)$
$\displaystyle=\frac{n(x)}{n(B_{3})+(1-c_{2})\,n(y_{2})}$
$\displaystyle\forall x\in B_{3}\,,$ $\displaystyle p(y_{i})$
$\displaystyle=\frac{c_{i}\,n(y_{i})}{n(B_{2})+c_{1}\,n(y_{1})+c_{2}\,n(y_{2})}$
$\displaystyle\forall i\in\\{1,2\\}\,.$

Elimination of

$c_{1}=\frac{n(B_{2})+c_{2}\,n(y_{2})}{n(B_{1})+n(B_{2})+c_{2}\,n(y_{2})}$

gives a quadratic equation for $c_{2}$, which has exactly one solution
satisfying the assumptions.

We can notice that this solution is identical to a MLE solution of horizontal
sums where the occurrences of vertices contained within more than one
operation were split between those operations by $c_{1}$ and $c_{2}$
respectively. The same approach with different numbers of splitting parameters
$(c_{1},c_{2},\ldots)$ could also be applied to Greechie diagrams from Figs.
1, 3, 6, and 7.

This gives rise to new intuition about MLE on Greechie diagrams from Figs. 1,
3, 4, 6, and 7. We transform these Greechie diagrams to Greechie diagrams of
horizontal sums by duplicating vertices found within multiple operations and
splitting the recorded occurrences of the original vertices between them and
their duplicates by newly introduced splitting parameters. The MLE solution
for horizontal sums is known, so all we have to do is to find the values of
the aforementioned splitting parameters.

For acyclic Greechie diagrams $(A,\mathcal{B})$, where
$\mathcal{B}=\bigcup_{i}\mathcal{B}_{i}$,
$\mathcal{B}_{i}\cap\mathcal{B}_{i+1}=\\{y_{i}\\}$ for all but the last
$\mathcal{B}_{i}$, $y_{i}\neq y_{j}$ and
$\mathcal{B}_{i}\cap\mathcal{B}_{j}=\emptyset$ for $i\neq j$ like in Figs. 1,
3, 4, 6, and 7, the splitting parameters can be found as solutions to a
polynomial of degree equal to the number of splitting parameters. Only
solutions on interval $[0,1]$ are admissible due to the way the splitting
parameters are defined. As we are maximizing a strictly concave function,
there is exactly one solution in interval $[0,1]$. (It is easy to show that
maximum likelihood cannot be achieved at the boundary.) The MLE can be found
numerically by methods of convex optimization (applied to the negative
likelihood). We derived analytic closed-form solutions for two or three
splitting parameters.

$\vdots$$\cdots$$\vdots$$\cdots$ Figure 6: Greechie diagram of a non-
constructible lattice for which MLE is feasible, with three splitting
parameters $\vdots$$\cdots$$\vdots$$\cdots$$\vdots$ Figure 7: Greechie diagram
of a non-constructible orthomodular lattice for which MLE leads to four
splitting parameters

There are more complex examples which are not of this kind; we leave them for
future research. The simplest two are in Fig. 8 and 9 (which represents the
smallest orthomodular poset which is not a lattice).

Figure 8: Greechie diagram of an orthomodular lattice for which MLE is more
complicated Figure 9: Greechie diagram of an orthomodular poset for which MLE
is more complicated

##  11 Conclusion

We collected arguments why maximum likelihood estimator (MLE) can be correctly
defined for quantum probability (on orthomodular posets). It admits a unique
closed-form solution for a large class called constructible lattices. Also for
some other models MLE is feasible, although it leads to higher-order
polynomial equations whose unique solution is not apparent. For the general
case, MLE exists and can be approximated numerically.

Acknowledgments The first author was supported by the European Regional
Development Fund, project “Center for Advanced Applied Science” (No.
CZ.02.1.01/0.0/0.0/16_019/0000778). The second author received support from
the Czech Science Foundation grant 20-09869L.

## References

  * [Kläy and Foulis1990] Kläy, M.P., Foulis, D.J.: Maximum likelihood estimation on generalized sample spaces: An alternative resolution of Simpson’s paradox. Found. Physics 20, 777–799 (1990)
  * [Beran1984] Beran, L.: Orthomodular Lattices. Algebraic Approach. Academia, Prague (1984)
  * [Kalmbach1983] Kalmbach, G.: Orthomodular Lattices. Academic Press, London (1983)
  * [Dichtl1981] Dichtl, M.: Astroids and pastings. Algebra Universalis 18, 380–385 (1981)
  * [Greechie1971] Greechie, R.J.: Orthomodular lattices admitting no states. J. Combin. Theory Ser. A 10, 119–132 (1971)
  * [Janowitz1972] Janowitz, M.F.: Constructible lattices. J. Austr. Math. Soc. 14, 311–316 (1972)