# Do Pretrained Contextual Language Models Distinguish between
Hebrew Homograph Analyses?

Avi Shmidman1,2,†, Cheyn Shmuel Shmidman2,‡,
Dan Bareket1,‡, Moshe Koppel1,2,‡, Reut Tsarfaty1,†
1Bar Ilan University / Ramat Gan, Israel 2DICTA / Jerusalem, Israel
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
###### Abstract

Semitic morphologically-rich languages (MRLs) are characterized by extreme
word ambiguity. Because most vowels are omitted in standard texts, many of the
words are homographs with multiple possible analyses, each with a different
pronunciation and different morphosyntactic properties. This ambiguity goes
beyond word-sense disambiguation (WSD), and may include token segmentation
into multiple word units. Previous research on MRLs claimed that standardly
trained pre-trained language models (PLMs) based on word-pieces may not
sufficiently capture the internal structure of such tokens in order to
distinguish between these analyses. Taking Hebrew as a case study, we
investigate the extent to which Hebrew homographs can be disambiguated and
analyzed using PLMs. We evaluate all existing models for contextualized Hebrew
embeddings on a novel Hebrew homograph challenge sets that we deliver. Our
empirical results demonstrate that contemporary Hebrew contextualized
embeddings outperform non-contextualized embeddings; and that they are most
effective for disambiguating segmentation and morphosyntactic features, less
so regarding pure word-sense disambiguation. We show that these embeddings are
more effective when the number of word-piece splits is limited, and they are
more effective for 2-way and 3-way ambiguities than for 4-way ambiguity. We
show that the embeddings are equally effective for homographs of both balanced
and skewed distributions, whether calculated as masked or unmasked tokens.
Finally, we show that these embeddings are as effective for homograph
disambiguation with extensive supervised training as with a few-shot setup.

##  1 Introduction

Semitic morphologically-rich languages (MRLs) such as Arabic, Hebrew, and
Aramaic are characterized by extreme ambiguity at the word level Wintner
(2014); Tsarfaty et al. (2020). In a standard text, many (and often most) of
the words will be homographs with multiple possible analyses. The high
ambiguity derives from several factors. First, prepositions, conjunctions,
accusative pronouns, and possessive pronouns are often seamlessly affixed to
words. Next, vowels are generally omitted in written texts. Finally, proper
nouns are not differentiated from common nouns (no capital letters).

The task of distinguishing between Hebrew homograph analyses is related to the
general task of Word Sense Disambiguation (WSD) Agirre and Edmonds (2006);
Navigli (2009), yet it is more challenging. In the standard case of WSD, a
single orthographic form is associated with a single word that can be analyzed
in terms of two or more senses; also, the analyses are generally pronounced
identically, and often have the same morphosyntactic properties (e.g bank of a
river vs. savings bank). In contrast, in Semitic languages, the need for
disambiguation often goes beyond a determination of sense. Hebrew word
ambiguities can be divided into three primary categories (Table 1): 1.
Segmentation ambiguities, in which a given orthographic form may (or may not)
be segmented into multiple word units each bearing its own role (POS tag) in
the sentence. 2\. Morphosyntactic ambiguities, in which the segmentation of
the form is not ambiguous, but multiple analyses of the word reflect different
morphosyntactic properties of each word unit(s). 3. Sense ambiguities (the
aforementioned standard case of WSD), in which the analyses of the unit(s) do
not differ in their morphosyntactic properties, but rather in their sense. One
orthographic form may exhibit multiple types of ambiguity simultaneously.

Pretrained contextualized language models with standard word-piece
tokenization mechanisms have been shown to excel at WSD in English and other
Indo-European languages Yaghoobzadeh et al. (2019). However, for Hebrew and
other semitic languages it has been argued that such models would not
sufficiently capture the structure of MRLs in order to distinguish between
internally-complex homograph analyses Klein and Tsarfaty (2020); Tsarfaty et
al. (2020). In this work, we take Modern Hebrew, a Semitic language with rich
and highly ambiguous morphology, as a case study, and we investigate the
extent to which homographs can be disambiguated by contextualized embeddings,
regarding all three levels of ambiguity. Regarding Arabic — a sister language
to Hebrew — a wide survey of WSD methods is presented by Abderrahim and
Abderrahim (2022). They raise the possibility of utilizing pretrained
contextualized embeddings, yet leave its evaluation to future
work.111Additional studies in Arabic WSD include Haffar and Zrigui (2023),
Merhbene et al. (2013), and Shah et al. (2010).

Type | Form  |  Word (translation) |  Morphology
---|---|---|---
Segmentation |  hqph> |  q*ApEh>+ha> (the+coffee) |  DET + Noun [M,S,abs]
|  haq*ApAh> (credit) |  Noun [F,S,abs]
/s’P> |  ’aP>++sE> (for+even) |  Sconj + Cconj
|  |  +sA’aP> (he aspired) |  Verb [M,S,3,PAST]
Morph |  ’lymwt> |  ’al*iymwot> (violent) |  Adj [F,P,abs]
|  ’al*iymw*t> (violence) |  Noun [F,S,abs/cons]
hryM> |  heriyM> (he lifted) |  Verb [M,S,3,PAST]
|  |  hAriyM> (mountains) |  Noun [M,P,abs]
Semantic |  hzmr> |  z*EmEr>+ha> (the+song) |  DET + Noun [M,S,abs]
|  z*am*Ar>+ha> (the+singer) |  DET + Noun [M,S,abs]
hswpr> |  s*woper>+ha> (the+author) |  DET + Noun [M,S,abs]
|  |  s*w*p*Er>+ha> (the+market) |  DET + Noun [M,S,abs]

Table 1: Examples of Hebrew ambiguity types

Hebrew is a particularly challenging language on which to perform a homograph
disambiguation due to the limited available corpora. First of all, currently
existing Hebrew treebanks are severely limited in size, such that most of the
words in the language are not amply represented. Furthermore, even regarding
common Hebrew words, this corpus is problematic, because the nature of
language is such that many homographs are skewed in their distribution; thus,
even if the primary analysis is sufficiently represented within a tagged
corpus, the secondary analysis will often be hopelessly underrepresented. For
instance, one common Hebrew homograph is mhM> (mhm), which can be analyzed as
a preposition with pronominal suffix, or as an interrogative. The ratio of
these two analyses in naturally-occurring Hebrew text is over 50:1; thus,
occurrences of the secondary analysis within existing tagged corpora are
insufficient.

In theory, these homograph ambiguities could be addressed using POS tagging
systems. For instance, Habash and Rambow (2005) consider the use of a
morphological tagging system to solve WSD in Arabic. A number of Hebrew POS
tagging systems have been published as well Yona and Wintner (2005); Adler and
Elhadad (2006); Shacham and Wintner (2007). The current SOTA for Hebrew POS
tagging is the YAP morpho-syntactic parser Tsarfaty et al. (2019). However, as
we have shown in a previous study (Shmidman et al., 2020, p. 3318, table 2),
although YAP produces high accuracy overall on normal Hebrew text, its scores
drop drastically regarding homographs of skewed distribution.

For analogous cases of skewed distribution in other languages, researchers
have proposed the creation of dedicated challenge sets, containing hard-to-
classify sentences not easily found in naturally-occurring text Gardner et al.
(2020); Elkahky et al. (2018). In the aforementioned previous study, we
produced 22 such challenge sets for Hebrew homographs, and demonstrated that a
Bi-LSTM of non-contextualized embeddings can obtain high accuracy on this
task, establishing the current SOTA for Hebrew homograph disambiguation
Shmidman et al. (2020). In this paper, we extend the investigation by
considering whether contextualized embeddings from pretrained language models
(PLMs) can provide a more optimal solution. We consider all existing
contextualized Hebrew PLMs: multilingual BERT ("mBERT") Devlin et al. (2019);
HeBERT Chriqui and Yahav (2021); and AlephBERT Seker et al. (2021) (Table 2).
Moreover, we evaluate and verify these on a new dataset, substantially larger
than all previous datasets for Hebrew homograph disambiguation.

Our experiments demonstrate that contextualized PLMs pre-trained on
sufficiently large unlabeled data and vocabulary size are excellent at
disambiguating the word-internal structures of homographs, yet face some
challenge with pure sense disambiguation. We show the efficacy of these models
in cases of homographs with skewed distribution, and in a few-shot setup.
Finally, we establish new state-of-the-art results on the challenging task of
homograph disambiguation for a morphologically-rich language printed without
vowels, along with a novel benchmark for assessing the morphological reach of
future PLMs in Hebrew.

##  2 The Data

The challenge sets for Hebrew homograph disambiguation from our previous study
were limited in number (only 22 sets) and insufficiently representative
regarding types of ambiguities; only one of the sets was a prefix-segmentation
ambiguity. Further, they were limited to binary cases, where only two analyses
exist.

Model | Vocab | Corpus Size
---|---|---
| (Heb. tokens) | (Heb. sentences)
mBERT | 2.5K | 6.3M
HeBERT | 30K | 27.2M
AlephBERT | 52K | 98.7M

Table 2: Comparison of available Hebrew BERT models

In contrast, for this study we employed field experts to choose the most
critical homographs in the language. The experts chose 75 homographs from a
list of the 3600 most frequent words in the language, balancing frequency of
word occurrence with practical need for its disambiguation. All of the
homographs occur with a minimum frequency of 27 words per million in naturally
occurring Hebrew text. Our challenge sets include homographs with 2-5 possible
analyses. Our sets contain a wide representation of segmentation ambiguities
(15 in number), as well as 5 cases of purely semantic ambiguities. For each of
the 75 homographs, we collect hundreds of naturally-occurring sentences
attesting to each analysis. In almost all cases, we succeed in collecting 1000
sentences for the primary analysis, at least 500 sentences for the secondary
analysis, and at least 250 for each additional analysis. The sentences were
culled from newspapers, Wikipedia, literature, and social media. We employed a
team of annotators who chose the relevant homograph analysis for each
case.222The annotation process is detailed in Appendix
LABEL:section:appendixCuration. All in all, our 75 challenge sets contain 150K
tagged sentences. The full list of homographs and analyses is provided in
Appendix A.333The dataset is downloadable at: https://github.com/Dicta-Israel-
Center-for-Text-Analysis/EACL_2023

##  3 Experimental Setup

To evaluate the ability of pre-trained language models (PLMs) to disambiguate
the in-context analyses of morphologically rich and highly ambiguous
homographs in Hebrew, we adopt a "word expert" approach, producing dedicated
classifiers for each individual homograph Zhao et al. (2020).

We use two types of PLMs, contextualized and non-contextualized. For the non-
contextualized case, we replicate our previous method detailed in Shmidman et
al. (2020). For each training example, we use a BiLSTM on top of the word2vec
embeddings of all of the words in the sentence (other than the homograph
itself) to produce an encoding for disambiguation.444We also tested fastText,
but results were inferior. An MLP is trained to predict the correct homograph
analysis based on this encoding.555For implementation details, see Appendix
LABEL:section:appendixImplementation. For the contextualized case, we run the
sentence through a pretrained contextualized language model and retrieve the
768-dimension embedding representing the homograph in question. An MLP is
trained to predict the correct analysis based on the homographs embeddings
alone. In the standard "unmasked" scenario, the sentence is fed into the model
as is, including the homograph in question. In the "masked" scenario, the
homograph is replaced with a [MASK] token.

We evaluate the performance of each given method on each given challenge set
using 10-fold cross-validation. We calculate an F1 score for each homograph
analysis, based upon the precision and recall scores micro-averaged across all
folds. We then calculate the macro-average of the F1 scores for all possible
analyses for a given homograph, and this is the score reported in the charts
herein.

##  4 Results and Analysis

#### Standard (Unmasked) Scenario

Figure 1:  Comparison of previous SOTA (w2v-based Bi-LSTM method) versus BERT-
based approaches. Figure 2:  Disambiguation accuracy across various categories
of homograph ambiguity. Figure 3: AlephBERT’s disambiguation accuracy across
homographs with differing counts of possible analyses. Figure 4:
Disambiguation accuracy across varying degrees of word piece splits within the
target homograph, using mBERT.

Figure 1 presents the cumulative F1 score obtained by the models for all
challenge sets. Our results show that HeBERT and AlephBERT far outperform
mBERT, with AlephBERT achieving the higher score. The poor performance of
mBERT is likely due to its smaller pre-training data size and exceedingly lean
Hebrew vocabulary (cf. Table 2). Furthermore, the HeBERT and AlephBERT models
both substantially outperform the previous word2vec-based SOTA. It is thus
apparent that contextualized language models do effectively capture Hebrew
homograph distinctions, even those based on word-pieces, even for an MRL, and
they do so more effectively than non-contextualized models.

Figure 2 demonstrates AlephBERT’s performance on different ambiguity types.
AlephBERT performs equally well on cases of segmentation ambiguity and
morphosyntactic ambiguity. In contrast, when it comes to ambiguities that are
purely semantic, the scores are noticeably lower. This is in line with the
findings of Ettinger (2020), who shows that BERT is stronger with syntax than
semantics; Goldberg (2019) also notes BERT’s strong syntactic abilities.
Interestingly, the same gap exists with the W2V-based method. Thus, both
contextualized and non-contextualized embeddings struggle to differentiate
between senses which are morphologically equivalent. Although such cases are
only of minimal import when it comes to sentence parsing, they are critical
for downstream tasks such as coreference resolution and relation extraction.
It thus remains a desideratum to improve disambiguation of purely semantic
Hebrew homographs.

The results in Figure 3 demonstrate that AlephBERT performs equally well on
cases of binary homographs as on cases of three-way homograph classification.
However, when faced with cases of 4-way or 5-way classification, accuracy
declines.

#### The Effect of Word-Pieces

Previous studies have hypothesized that word-pieces are not adequate for
capturing complex morphosyntactic structures due to arbitrary (non-linguistic)
word-splits. To probe into this we investigate the question, do such splits
affect performance. Our 75 homographs are all treated as single tokens in
HeBERT and AlephBERT. However, many of the homographs are broken up into word
pieces in mBERT, due to its meager Hebrew vocabulary. We thus compare mBERT’s
results on words treated as single tokens versus those that are broken up into
two or three pieces, which are aggregated using first, sum, or average of the
vectors. With regard to cases of split words, we train models using three
separate methods: providing the MLP with only the embedding of the first word
piece; with an average of the word piece embeddings; or with the sum of the
embeddings. As shown in Figure 4, the splitting of a homograph into three
word-pieces appears to have a negative impact on the ability of the resulting
embedding to differentiate between homograph analyses, for all aggregation
methods.

#### Masked Scenario

Figure 5:  Comparison of unmasked vs. masked scenarios, across varying degrees
of skewed homographs. The ratio axis indicates the relative distribution
between the least and most frequent analyses of each plotted homograph within
naturally-occurring Hebrew text.

We consider whether AlephBERT embeddings are more effective if we replace the
homograph word with [MASK] when running the challenge set sentences through
AlephBERT. The motivation behind this experiment is that, as explained above,
many of the homographs are skewed in their natural proportion. In such cases,
we worry whether AlephBERT might be disproportionately influenced by the
skewed distribution; replacing the word with [MASK] would prevent the model
from being influenced as such. As shown in figure 5, AlephBERT achieves high
scores both with balanced homographs as well as with homographs of highly
skewed distribution. Using a [MASK] token instead of the actual word does not
generally improve performance, whether or not the homographs are of skewed
proportion.

#### Few-Shot Scenarios

In our experiments thus far, the 10-fold cross-validation allows the MLP to
leverage 90% of the data in each fold (hundreds of sentences for each
analysis) in order to learn the difference between the analyses. We now
consider whether the AlephBERT embeddings can suffice on a few-shot basis,
where the training stage has access to only 100, 50, 25, 10 or even 5 examples
of each analysis. In these cases, we train an MLP based only on these few
samples, and we use the rest of the sentences for evaluation. Astoundingly, as
demonstrated in Figure 6, the AlephBERT embeddings provide a highly accurate
solution even on this few-shot basis. Even when training with only 5 examples
of each homograph analysis, AlephBERT reaches an accuracy that is not far
below the accuracy achieved when performing full 10-fold CV across hundreds of
sentences of each analysis.

#### Probing Scenarios

Finally, we probe the pretrained AlephBERT embeddings Yaghoobzadeh et al.
(2019); Tenney et al. (2019); Klafka and Ettinger (2020); Belinkov (2021) to
see whether in and of themselves they reflect clusters which correspond to
different homograph analyses. We skip the MLP, and instead use the raw
embeddings directly, classifying sentences based on their proximity to the
centroid of the training samples for each homograph analysis. As shown in the
orange bars in Figure 6, this method generally does not perform as well as the
MLP-based method; however, the degradation is limited to only a few percentage
points, indicating that the raw embeddings are generally clustered in groups
which indeed reflect the distinctions between the analyses.

Figure 6:  Use of AlephBERT embeddings to differentiate between homographs on
a few-shot basis, contrasted with scores from the full 10-fold CV ("All").

##  5 Conclusion

In this study we have utilized a wide-ranging collection of Hebrew homograph
challenge sets in order to evaluate the extent to which raw contextualized
embeddings can be leveraged to disambiguate Hebrew homographs. We found that
contextualized embeddings can effectively disambiguate analyses of homographs,
much more so than non-contextualized ones, regarding multiple types of
ambiguity: segmentation, morphosyntactic and sense. Yet, efficacy on pure
sense ambiguity is lower than on the other two types. Additionally, an
increasing number of splits, or an increasing number of different possible
analyses of a token, each lower efficacy. Finally, we found that
contextualized embeddings can function effectively for this purpose on a few-
shot basis, with as little as 5 examples of each analysis. This indicates that
with relatively modest effort, highly ambiguous homographs may be effectively
treated.

## Limitations

One of the major strengths of this paper is its new and comprehensive dataset
for the training and benchmarking Hebrew homograph disambiguation. The dataset
is uncomparable in size, quality and balance to all previous Hebrew homograph
datasets; we have made every effort to be as inclusive as possible in the
creation of the dataset, making sure to include data from a widely diverse set
of genres. Nevertheless, a perennial challenge in corpus-based studies is that
the lion’s share of the available data tends to be authored by male writers.
In order to offset this bias, we bolstered our corpus with a large corpus of
texts specifically taken from blog sites devoted entirely to female bloggers.
Even so, we cannot escape the fact that female writing and feminine
conjugations are underrepresented in our dataset.

A further limitation derives from our filter for sentences with offensive
language. We perceived early on that our human annotators were not comfortable
tagging sentences with offensive language, and we therefore took steps to
remove such sentences from our corpus. Nevertheless, this means that our
resulting dataset is limited in that it does not properly reflect the use of
offensive language in naturally-occurring Hebrew sentences. Furthermore, our
resulting tests and reported scores may not accurately reflect the performance
of our models when applied to sentences with offensive language.

## Ethics Statement

#### Creation of the Dataset

As noted, our dataset contains over 150K sentences in all. Every sentence was
reviewed and tagged by our team of human annotators, who chose the relevant
homograph analysis for each instance of each of our 75 homographs. Our
annotator team included members of diverse genders and sexual orientations.
They were paid hourly wages with legal pay stubs. Their hourly wage was well
above the minimum wage required by law. The entirety of the dataset will be
made available for research purposes with the acceptance of this article,
together with the tagging information.

#### Risks of the Research

Ultimately, this data will enable end-users to automatically diacritize and
parse large corpora of Hebrew text. For the most part, this will provide a
beneficial contribution to the world: for the visually impaired, this
technology will enable the development of more precise text-to-speech
products; teachers will be able to provide children and second-language
learners with accessible diacritized texts; and humanities and linguistics
researchers can bolster their research with big-data analysis. However, there
also is a risk of nefarious use, for instance, if an end user were to leverage
these capabilities in order to produce anonymous texts or recordings
containing threats to life, liberty, or happiness.

## Acknowledgments

The work of the third and last authors has been funded by a grant from the
Israeli Ministry of Science and Technology (MOST) grant no. 3-17992.

## References

  * Abderrahim and Abderrahim (2022) Mohammed Alaeddine Abderrahim and Mohammed El-Amine Abderrahim. 2022.  Arabic word sense disambiguation for information retrieval.  _ACM Trans. Asian Low-Resour. Lang. Inf. Process._ , 21(4).
  * Adler and Elhadad (2006) Meni Adler and Michael Elhadad. 2006.  An unsupervised morpheme-based hmm for hebrew morphological disambiguation.  In _COLING/ACL 2006 - 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics, Proceedings of the Conference_ , COLING/ACL 2006 - 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics, Proceedings of the Conference, pages 665–672, United States. Association for Computational Linguistics (ACL).  21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics, COLING/ACL 2006 ; Conference date: 17-07-2006 Through 21-07-2006.
  * Agirre and Edmonds (2006) Eneko Agirre and Philip Edmonds, editors. 2006.  _Word Sense Disambiguation: Algorithms and Applications_, volume 33 of _Text, Speech and Language Technology_.  Springer.
  * Belinkov (2021) Yonatan Belinkov. 2021.  Probing Classifiers: Promises, Shortcomings, and Advances.  _Computational Linguistics_ , pages 1–13.
  * Chriqui and Yahav (2021) Avihay Chriqui and Inbal Yahav. 2021.  Hebert & hebemo: a hebrew bert model and a tool for polarity analysis and emotion recognition.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  Bert: Pre-training of deep bidirectional transformers for language understanding.
  * Elkahky et al. (2018) Ali Elkahky, Kellie Webster, Daniel Andor, and Emily Pitler. 2018.  A challenge set and methods for noun-verb ambiguity.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 2562–2572, Brussels, Belgium. Association for Computational Linguistics.
  * Ettinger (2020) Allyson Ettinger. 2020.  What BERT is not: Lessons from a new suite of psycholinguistic diagnostics for language models.  _Transactions of the Association for Computational Linguistics_ , 8:34–48.
  * Gardner et al. (2020) Matt Gardner, Yoav Artzi, Victoria Basmova, Jonathan Berant, Ben Bogin, Sihao Chen, Pradeep Dasigi, Dheeru Dua, Yanai Elazar, Ananth Gottumukkala, Nitish Gupta, Hanna Hajishirzi, Gabriel Ilharco, Daniel Khashabi, Kevin Lin, Jiangming Liu, Nelson F. Liu, Phoebe Mulcaire, Qiang Ning, Sameer Singh, Noah A. Smith, Sanjay Subramanian, Reut Tsarfaty, Eric Wallace, Ally Zhang, and Ben Zhou. 2020.  Evaluating models’ local decision boundaries via contrast sets.
  * Goldberg (2019) Yoav Goldberg. 2019.  Assessing bert’s syntactic abilities.  _CoRR_ , abs/1901.05287.
  * Habash and Rambow (2005) Nizar Habash and Owen Rambow. 2005.  Arabic tokenization, part-of-speech tagging and morphological disambiguation in one fell swoop.  In _Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics (ACL’05)_ , pages 573–580, Ann Arbor, Michigan. Association for Computational Linguistics.
  * Haffar and Zrigui (2023) Nafaa Haffar and Mounir Zrigui. 2023.  A synergistic bidirectional lstm and n-gram multi-channel cnn approach based on bert and fasttext for arabic event identification. _ACM Transactions on Asian and Low-Resource Language Information Processing_ , 22.
  * Klafka and Ettinger (2020) Josef Klafka and Allyson Ettinger. 2020.  Spying on your neighbors: Fine-grained probing of contextual embeddings for information about surrounding words.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 4801–4811, Online. Association for Computational Linguistics.
  * Klein and Tsarfaty (2020) Stav Klein and Reut Tsarfaty. 2020.  Getting the ##life out of living: How adequate are word-pieces for modelling complex morphology? In _Proceedings of the 17th SIGMORPHON Workshop on Computational Research in Phonetics, Phonology, and Morphology_ , pages 204–209, Online. Association for Computational Linguistics.
  * Merhbene et al. (2013) Laroussi Merhbene, Anis Zouaghi, and Mounir Zrigui. 2013.  A semi-supervised method for Arabic word sense disambiguation using a weighted directed graph.  In _Proceedings of the Sixth International Joint Conference on Natural Language Processing_ , pages 1027–1031, Nagoya, Japan. Asian Federation of Natural Language Processing.
  * Navigli (2009) Roberto Navigli. 2009.  Word sense disambiguation: A survey.  _ACM Comput. Surv._ , 41.
  * Seker et al. (2021) Amit Seker, Elron Bandel, Dan Bareket, Idan Brusilovsky, Refael Shaked Greenfeld, and Reut Tsarfaty. 2021.  Alephbert:a hebrew large pre-trained language model to start-off your hebrew nlp application with.
  * Shacham and Wintner (2007) Danny Shacham and Shuly Wintner. 2007.  Morphological disambiguation of Hebrew: A case study in classifier combination.  In _Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP-CoNLL)_ , pages 439–447, Prague, Czech Republic. Association for Computational Linguistics.
  * Shah et al. (2010) Rushin Shah, Paramveer S. Dhillon, Mark Liberman, Dean Foster, Mohamed Maamouri, and Lyle Ungar. 2010.  A new approach to lexical disambiguation of Arabic text.  In _Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing_ , pages 725–735, Cambridge, MA. Association for Computational Linguistics.
  * Shmidman et al. (2020) Avi Shmidman, Joshua Guedalia, Shaltiel Shmidman, Moshe Koppel, and Reut Tsarfaty. 2020.  A novel challenge set for Hebrew morphological disambiguation and diacritics restoration.  In _Findings of the Association for Computational Linguistics: EMNLP 2020_ , pages 3316–3326, Online. Association for Computational Linguistics.
  * Tenney et al. (2019) Ian Tenney, Patrick Xia, Berlin Chen, Alex Wang, Adam Poliak, R Thomas McCoy, Najoung Kim, Benjamin Van Durme, Samuel R. Bowman, Dipanjan Das, and Ellie Pavlick. 2019.  What do you learn from context? probing for sentence structure in contextualized word representations.
  * Tsarfaty et al. (2020) Reut Tsarfaty, Dan Bareket, Stav Klein, and Amit Seker. 2020.  From SPMRL to NMRL: What did we learn (and unlearn) in a decade of parsing morphologically-rich languages (MRLs)? In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 7396–7408, Online. Association for Computational Linguistics.
  * Tsarfaty et al. (2019) Reut Tsarfaty, Amit Seker, Shoval Sadde, and Stav Klein. 2019.  What’s wrong with hebrew nlp? and how to make it right.
  * Wintner (2014) Shuly Wintner. 2014.  Morphological processing of semitic languages.  In _NLP of Semitic Languages_.
  * Yaghoobzadeh et al. (2019) Yadollah Yaghoobzadeh, Katharina Kann, T. J. Hazen, Eneko Agirre, and Hinrich Schütze. 2019.  Probing for semantic classes: Diagnosing the meaning content of word embeddings.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 5740–5753, Florence, Italy. Association for Computational Linguistics.
  * Yona and Wintner (2005) Shlomo Yona and Shuly Wintner. 2005.  A finite-state morphological grammar of Hebrew.  In _Proceedings of the ACL Workshop on Computational Approaches to Semitic Languages_ , pages 9–16, Ann Arbor, Michigan. Association for Computational Linguistics.
  * Zhao et al. (2020) Mengjie Zhao, Philipp Dufter, Yadollah Yaghoobzadeh, and Hinrich Schütze. 2020\.  Quantifying the contextualization of word representations with semantic class probing.  In _Findings of the Association for Computational Linguistics: EMNLP 2020_ , pages 1219–1234, Online. Association for Computational Linguistics.

##  Appendix A Appendix A: Table of Homographs

We present three tables of homographs, corresponding to the three categories
of homographs discussed within the paper (segmentation ambiguity,
morphosyntactic ambiguity, and semantic ambiguity).666It should be noted that
the higher level of ambiguity are supersets of the lower levels: segmentation
ambiguities generally entail differences on the morphosyntactic and semantic
levels as well, and morphosyntactic ambiguities generally also entail semantic
ambiguities. Furthermore, because many of the homographs admit to more than
two analyses, it is often the case that a subset of the analyses may form a
lower level of ambiguity (e.g., just a semantic ambiguity), while other
analyses form a higher level of ambiguity (e.g. segmentation ambiguity). For
the purposes of this paper, we categorize each homograph according to the
highest level of ambiguity involved: First, if a segmentation ambiguity is
indicated anywhere across the possible analyses, then we include the homograph
in the ”segmentation ambiguity” category. Next, if there is no segmentation
ambiguity, but a morphosyntactic ambiguity is indicated anywhere across the
possible analyses, then we include the homograph in the ”morphosyntactic
ambiguity” category. Finally, if the analyses all differ only on the semantic
level, then we include the homograph in the ”semantic ambiguity” category. In
each table, the first column ("form") indicates the homograph as it is found
in naturally-occurring non-diacritized Hebrew text.777The ranking of analyses
is based on a frequency analysis of our in-house annotated corpus. It is worth
emphasizing that the paper as a whole relates to each of the 75 homographs
specifically as they are spelled in this list, and does not relate to cases
where further prefixes are attached to the homographs. As a result, the
frequency analysis may sometimes seem counterintuitive. For instance,
regarding the form r’/sy¿, a native Hebrew speaker might intuit that the
adjectival form is primary (rA’+siy¿). However, in practice, that sense is
common only when prefixed with a definitive marker (hr’/sy¿). In contrast, the
homograph considered here involves the form r’/sy¿ as is, without any
prefixes; in this case, the other analyses are far more common. The second
column ("word") indicates the possible diacritizations of each form. In cases
where the diacritized word includes an attached prefix, a plus sign indicates
the segmentation point between the prefix letters and the primary word.
Regarding all homographs considered in this paper, different segmentation
options are diacritized differently. Thus, for each sentence in the dataset,
our human annotators were asked simply to choose the correct diacritization
for the target homograph (that is, they were asked to choose among the options
listed in the "word" column). There was no need for the annotators to
separately tag the segmentation, because in all cases the choice of
diacritization itself indicates the segmentation.888It should be noted that in
certain sentences, an exceedingly rare diacritization was warranted, which was
not among the options listed in the ”word” column. The annotators were
instructed to tag such cases as ”none of the above”, and all such sentences
were removed from the corpus. Similarly, some sentences do not provide enough
context to determine the correct diacritization; the annotators were asked to
tag such sentences as ”unclear”, and these sentences too were removed from the
corpus.  The third column indicates the morphology of each of the possible
diacritizations.999In most cases, a diacritized form has one specific
morphological analysis. However, in other cases, the diacritized form can
admit to multiple morphologies. In such cases, we list all of the practically
relevant morphological analyses in the third column, separated by a slash
(thus for instance in the case of zr¿). Rare analyses which hardly ever occur
in practice are not listed. The fourth column lists the
translation.101010Naturally, a given Hebrew term often captures a substantial
range of potential English translations, and it would not be practical to list
them all in this column; therefore, we generally present only a single
representative translation. Within each table the homographs are listed
alphabetically.111111Ideally, we might have grouped the homographs based on
part-of-speech instead. However, as can be seen from the following tables, the
75 homographs vary so widely in terms of the parts of speech that they can
represent, such that alphabetical listing was deemed most useful.

###  A.1 Homographs with Segmentation Ambiguity

Form  |  Word |  Morphology121212Key to morphology abbreviations: F=Feminine; M=Masculine; S=Singular; P=Plural; abs=absolute; cons=construct; 1,2,3=First Person, Second Person, Third Person; suf=suffix; Det = determiner; SConj=Subordinating Conjunction; Adj=Adjective; Conj=Conjunction; Prep=Preposition; Propn=Proper Noun; Adv=Adverb; Ptcp=Participle; ACC=Accusative marker. | Translation | #Sentences
---|---|---|---|---
h’M> |  ha’iM> |  Interrogative | does | 1,000
|  ’eM>+hA> |  Det + Noun [F,S,abs] | the + mother | 1,000
hmr’h> |  m*ar:’Eh>+ha> |  SConj + Ptcp [M,S] / Det + Noun [M,S,abs] | that + indicates / the + sight | 1,000
|  m*ar:’Ah>+ha> |  SConj + Ptcp [F,S] / Det + Noun [F,S,abs] | that + indicates / the + mirror | 882
|  ham:rA’Ah> |  Noun [F,S,abs] | takeoff | 735
hqph> |  q*ApEh>+ha> |  Det + Noun [M,S,abs] | the + coffee | 1,000
|  haq*ApAh> |  Noun [F,S,abs] | credit | 500
hq/sr> |  q*E+sEr>+ha> |  Det + Noun [M,S,abs] | the + connection | 1,000
|  q*a+s*Ar>+ha> |  Det + Noun [M,S,abs] | the + signaler | 1,000
|  hEq:+ser> |  Noun [M,S,abs/cons] | context | 588
h/slmh> |  ha+s:lAmAh> |  Noun [F,S,abs] | completion | 1,000
|  +s*:lemAh>+ha> |  Det + Adj [F,S] | the + complete | 906
w‘d> |  ‘ad>+w:> |  Conj + Prep | and + until | 1,000
|  wa‘ad> |  Noun [M,S,abs/cons] | committee | 519
l/sM> |  l:+seM> |  Prep | for the purpose of | 1,000
|  +sAM>+l:> |  Prep + Adverb | to + there | 1,000
mb.hynh> |  b*:.hiynAh>+mi> |  Prep + Noun [F,S,abs] | from + point of view | 1,000
|  mab:.hiynAh> |  Participle [F,S,abs] | she notices | 607
msybwt> |  m:siyb*wot> |  Noun [F,P,abs] | parties | 1,000
|  s*iyb*wot>+mi> |  Prep + Noun [F,P,abs/cons] | due to + reasons | 1,000
mpt.h> |  map:t*e.ha> |  Noun [M,S,abs] | key | 1,000
|  m:pat*e.ha> |  Participle [M,S,abs] | develops / developer | 329
|  p*Eta.h>+mi> |  Prep + Noun [M,S,abs/cons] | from + opening | 206
/s’lh> |  +s:’elAh> |  Noun [F,S,abs] | question | 1,000
|  +sA’a:lAh> |  Verb [F,S,3,Past] | she asked | 1,000
|  ’el*Eh>++sE> |  SConj + Pronoun [MF,P,3] | that + these | 228
/s’P> |  ’aP>++sE> |  SConj + CConj | for + even | 1,000
|  +sA’aP> |  Verb [M,S,3,Past] | he aspired | 665
/sbh> |  b*Ah*>++sE> |  Sconj + Prep [suf=F,S,3] | that + in it | 1,000
|  +sAbAh> |  Verb [F,S,Present/Past] | she returns / she returned | 1,000
/smN> |  +sEmEN> |  Noun [M,S,abs/cons] | oil | 1,000
|  +sAmeN> |  Adj [M,S,abs] | wide | 335
|  m*iN>++sE> |  SConj + Prep | that + from | 207
|  +s:mAN> |  Noun [M,S,abs,suf=F,P,3] | their name | 149
/smr> |  +sAmar> |  Verb [M,S,3,Past] | he guarded | 1,000
|  +sEmEr> |  Propn | Shemer | 872
|  m*ar>++sE> |  SConj + Titular [M,S] | that + Mr. | 224

This text will be invisible

###  A.2 Homographs with Morphosyntactic Ambiguity

Form  |  Word |  Morphology | Translation | #Sentences
---|---|---|---|---
’hbh> |  ’aha:bAh> |  Noun [F,S,abs] | love | 1,000
|  ’Aha:bAh> |  Verb [F,S,3,Past] | she loved | 1,000
’wkl> |  ’owkEl> |  Noun [M,S,abs/cons] | food | 748
|  ’w*kal> |  Modal [MF,S,1,Future] | I can | 729
|  ’wokel> |  Participle [M,S,abs/cons] | eats | 640
’.hdwt> |  ’a:.hAdwot> |  Det [F,P,abs] | several | 1,000
|  ’a.h:dw*t> |  Noun [F,S,abs] | unity | 1,000
’.hyw> |  ’E.hAyw> |  Noun [MF,P,abs,suf=M,S,3] | his brothers | 1,000
|  ’A.hiyw> |  Noun [MF,S,abs,suf=M,S,3] | his brother | 774
’lymwt> |  ’al*iymwot> |  Adj [F,P] | violent | 1,000
|  ’al*iymw*t> |  Noun [F,S,abs/cons] | violence | 1,000
’M> |  ’iM> |  Conj | if | 1,000
|  ’eM> |  Noun [F,S,abs/cons] | mother | 1,000
’m.s‘y> |  ’Em:.sA‘ey> |  Noun [M,P,cons] | centers of / methods of | 1,000
|  ’Em:.sA‘iy> |  Noun [M,S,abs] / Adj [M,S] | method / central | 969
’mrh> |  ’Am:rAh> |  Verb [F,S,3,Past] | she said | 1,000
|  ’im:rAh> |  Noun [F,S,abs] | a saying | 343
’p/sr> |  ’Ep:+sAr> |  Modal / Adv | possible | 1,000
|  ’ip:+ser> |  Verb [M,S,3,Past] | he allowed | 511
’t> |  ’Et> |  ACC | accusative | 1,000
|  ’at*:> |  Pronoun [F,S,2] | you | 1,000
bhm/sK> |  hEm:+seK:>+b*:> |  Prep + Noun [M,S,cons] | in + continuation of | 1,000
|  hEm:+seK:>+b*a> |  Prep [with Det] + Noun [M,S,abs] | in the + future | 930
b.hyy> |  .hay*ey>+b*:> |  Prep + Noun [M,P,cons] | in + lives of | 1,000
|  .hay*ay>+b*:> |  Prep + Noun [M,P,abs,suf=MF,S,1] | in + my life | 1,000
b‘wlM> |  ‘wolAM>+b*A> |  Prep [with Det] + Noun [M,S,abs] | in the + world | 1,000
|  ‘wolaM>+b*:> |  Prep + Noun [M,S,cons] | in + a world of | 913
|  ‘wolAM>+b*:> |  Prep + Noun [M,S,abs] | in + a world | 485
bqrb> |  qErEb>+b*:> |  Prep + Noun [M,S,cons] | in + midst of | 1,000
|  q*:rAb>+b*a> |  Prep [with Det] + Noun [M,S,abs] | in the + battle | 1,000
|  q:rab>+b*i> |  Prep + Verb [Bare Infinitive] | in + approaching of | 734
|  q:rAb>+b*i> |  Prep + Noun [M,S,abs] | in + a battle | 256
gylw> |  g*iyl*w*> |  Verb [MF,P,3,Past] | they discovered | 1,000
|  g*iylwo> |  Noun [M,S,abs,suf=M,S,3] | his age | 859
dy> |  d*ay> |  Adverb | sufficiently | 1,000
|  d*ey> |  Det [cons] | enough of | 828
|  d*iy> |  Prefix | di- | 808
hzqN> |  z*AqAN>+ha> |  Det + Noun [M,S,abs] | the + beard | 739
|  z*AqeN>+ha> |  Det + Adj [M,S] / Det + Noun [M,S,abs] | the + old / the + elderly man | 533
h.hl> |  he.hel> |  Verb [M,S,3,Past] | he began | 1,000
|  hA.hel> |  Verb [Bare Infinitive] | starting (from) | 1,000
hm/snh> |  m*i+s:nEh>+ha> |  Det + Noun [M,S,abs] | the + deputy | 1,000
|  m*i+s:nAh>+ha> |  Det + Propn [F,S,abs] | the + Mishna | 1,000
hn.hh> |  han*A.hAh> |  Noun [F,S,abs] | placing | 1,000
|  hin:.hAh> |  Verb [M,S,3,Past] | he directed | 731
|  ha:nA.hAh> |  Noun [F,S,abs] | discount | 517
hryM> |  heriyM> |  Verb [M,S,3,Past] | he lifted | 1,000
|  hAriyM> |  Noun [M,P,abs] | mountains | 1,000
w’t> |  ’Et>+w:> |  Conj + ACC | and + accusative | 1,000
|  ’at*:>+w:> |  Conj + Pronoun [F,S,2] | and + you | 1,000
zr> |  zer> |  Noun [M,S,abs/cons] | bouquet | 1,000
|  zAr> |  Adj [M,S] / Noun [M,S,abs] | foreign / stranger | 1,000
.hbrwt> |  .ha:bArwot> |  Noun [F,P,abs] | companies | 1,000
|  .hEb:rwot> |  Noun [F,P,cons] | companies of | 1,000
|  .ha:berwot> |  Noun [F,P,abs/cons] | friends | 501
|  .ha:berw*t> |  Noun [F,S,abs/cons] | friendship | 398
|  .hab:rwot> |  Noun [F,P,cons] | friends of | 261
.hdr> |  .ha:dar> |  Noun [M,S,cons] | room of | 1,000
|  .hEdEr> |  Noun [M,S,abs] | room | 1,000
|  .hAdar> |  Verb [M,S,3,Past] | penetrated | 783
.twb> |  .twob> |  Adj [M,S] | good | 1,000
|  .tw*b> |  Noun [M,S,abs/cons] | goodness | 357
yhwdy> |  y:hw*diy> |  Noun [M,S,abs] / Adj [M,S] | a Jew / Jewish | 1,000
|  y:hw*dey> |  Noun [M,P,cons] | Jews | 1,000
kywwN> |  k*eywAwN> |  Conj | because | 487
|  k*iyw*w*N> |  Noun [M,S,abs] / Noun [M,S,cons] | direction | 468
|  k*iyw*ewN> |  Verb [M,S,3,Past] | directed | 455
lw> |  lwo> |  Prep [suf=M,S,3] | to him | 1,000
|  lw*> |  Conj | if only | 1,000
l.hM> |  lE.hEM> |  Noun [M,S,abs] | bread | 1,000
|  lA.haM> |  Verb [M,S,3,Past] | he fought | 1,000
lpnwt> |  lip:nwot> |  Prep / Verb [Infinitive] | facing / to turn | 1,000
|  l:pan*wot> |  Verb [Infinitive] | to clear out | 570
mdy> |  mid*ey> |  Det [cons] | every | 1,000
|  mid*ay> |  Adv | too much | 802
|  mad*ey> |  Noun [M,P,cons] | uniforms of | 541
mhM> |  mehEM> |  Preposition [suf=M,P,3] | from them | 1,000
|  mAheM> |  Interrogative | what are | 587
my> |  miy> |  Interrogative / Pronoun [S,3] | who | 1,000
|  mey> |  Noun [M,P,cons] | waters of | 1,000
mlK> |  mElEK:> |  Noun [M,S,abs/cons] | king | 1,000
|  mAlaK:> |  Verb [M,S,3,Past] | he ruled | 522
m‘br> |  me‘ebEr> |  Prep | beyond | 1,000
|  ma‘a:bAr> |  Noun [M,S,abs] | passage | 1,000
|  ma‘a:bar> |  Noun [M,S,cons] | passage of | 883
mr’h> |  mar:’Eh> |  Participle [M,S] | he shows | 1,000
|  mar:’Ah> |  Participle [F,S] | she shows | 1,000
mrkz> |  mEr:k*az> |  Noun [M,S,cons] | center of | 1,000
|  mEr:k*Az> |  Noun [M,S,abs] | center | 1,000
|  m:rak*ez> |  Participle [M,S,abs/cons] | organizes / organizer | 393
m/s.hq> |  mi,s:.hAq> |  Noun [M,S,abs] | game | 1,000
|  m:,sa.heq> |  Participle [M,S,abs] | plays / player | 479
n‘/sh> |  na‘a:,sEh> |  Verb [MF,P,1,Future] | we will do | 1,000
|  na‘a:,sAh> |  Verb [M,S,3,Past] | was done | 1,000
n/syM> |  nA+siyM> |  Noun [F,P,abs] | women | 1,000
|  nA,siyM> |  Verb [MF,P,1,Future] | we will put | 613
ntN> |  nAtaN> |  Verb [M,S,3,Past] | gave | 1,000
|  nAtAN> |  Propn | Nathan | 681
‘br> |  ‘Abar> |  Verb [M,S,3,Past] | he passed | 1,000
|  ‘AbAr> |  Noun [M,S,abs] | past | 1,000
|  ‘ebEr> |  Noun [M,S,abs/cons] | side | 456
‘d> |  ‘ad> |  Prep | until | 1,000
|  ‘ed> |  Noun [M,S,abs/cons] | witness | 1,000
‘wbdwt> |  ‘uwb:d*wot> |  Noun [F,P,abs/cons] | facts | 1,000
|  ‘wob:dwot> |  Participle [F,P] | they work / workers | 1,000
‘M> |  ‘iM> |  Prep | with | 1,000
|  ‘aM> |  Noun [M,S,abs/cons] | nation | 1,000
pny> |  p*:ney> |  Noun [M,P,cons] | faces of | 1,000
|  p*Anay> |  Noun [MF,P,abs,suf=MF,S,1] | my face | 338
prs> |  p*:rAs> |  Noun [M,S,abs] | award | 1,000
|  p*ErEs> |  Propn | Peres | 956
|  p*Aras> |  Verb [M,S,3,Past] | he spread | 630
|  p*:ras> |  Noun [M,S,cons] | award of | 290
.sywN> |  .siy*woN> |  Propn | Zion | 1,000
|  .siy*w*N> |  Noun [M,S,abs/cons] | mark | 1,000
qwdM> |  qowdEM> |  Adv | before | 1,000
|  qwodeM> |  Adj [M,S] | previous | 1,000
|  quwd*aM> |  Verb [M,S,3,Past] | was promoted | 284
r’/sy> |  rA’+sey> |  Noun [M,P,cons] | heads | 1,000
|  ro’+siy> |  Noun [M,S,abs,suf=MF,S,1] | my head | 881
|  rA’+siy> |  Adj [M,S,abs] | head | 399
/syrt> |  +seyret> |  Verb [M,S,3,Past] | he served | 1,000
|  +siyrat> |  Noun [F,S,cons] | poetry of | 896
/skr> |  ,sAkAr> |  Noun [M,S,abs] | salary | 1,000
|  ,s:kar> |  Noun [M,S,cons] | salary of | 751
|  ,sAkar> |  Verb [M,S,3,Past] | rented | 681
/sM> |  +seM> |  Noun [M,S,abs/cons] | name | 1,000
|  +sAM> |  Adv | there | 1,000
|  ,sAM> |  Verb [M,S,Present/Past] | he placed | 1,000
tn’y> |  t*:nA’ey> |  Noun [M,P,cons] | conditions of | 1,000
|  t*:na’y> |  Noun [M,S,abs/cons] | condition | 834

This text will be invisible

###  A.3 Homographs with Semantic Ambiguity

Form  |  Word |  Morphology | Translation | #Sentences
---|---|---|---|---
hzmr> |  z*EmEr>+ha> |  Det + Noun [M,S,abs] | the + music | 1,000
|  z*am*Ar>+ha> |  Det + Noun [M,S,abs] | the + musician | 1,000
hswpr> |  s*w*p*Er>+ha> |  Det + Noun [M,S,abs] | the + market | 763
|  s*woper>+ha> |  Det + Noun [M,S,abs] | the + author | 570
zmr> |  zam*Ar> |  Noun [M,S,abs] | musician | 1,000
|  zEmEr> |  Noun [M,S,abs] | song | 602
.hbrh> |  .ha:berAh> |  Noun [F,S,abs] | friend | 1,000
|  .hEb:rAh> |  Noun [F,S,abs] | company | 1,000
r/swt> |  r:+sw*t> |  Noun [F,S,abs/cons] | permission | 1,000
|  rA+sw*t> |  Noun [F,S,abs/cons] | authority | 1,000

This text will be invisible

##  Appendix B Appendix B: Creation of our Annotated Dataset

We present here further details regarding the creation of our annotated
homograph dataset. As noted above, our dataset contains challenge sets for 75
Hebrew homographs. In almost all cases, we collect 1000 sentences for the
primary analysis, at least 500 sentences for the secondary analysis, and at
least 250 for each additional analysis. Every sentence was tagged by our team
of human annotators.

The main challenge that we faced is that it is often extraordinarily difficult
to identify a sufficient number of naturally-occurring Hebrew sentences
attesting to the non-primary homograph analyses. In many cases, the naturally-
occurring ratio of these analyses is 100:1 or worse, meaning that the non-
primary analyses only occur once in 100 or more sentences. In such cases,
prima facie, we would need to tag some 50,000 randomly-selected cases of the
homograph in order to gather 500 cases of the alternate analysis. It would not
be practical to tag this number of sentences for each of the 75 homographs.
Therefore, we devised the following three-step process to allow us to
efficiently gather a sufficient number of sentences attesting each possible
analysis of each homograph:

1\. For each homograph, we first gather 4000 randomly-selected sentences from
an untagged Hebrew corpus. For each sentence, our annotation team determines
the correct analysis of the homograph. This initial step virtually always
provides us with a sufficient number of sentences attesting to the primary
analysis, and sometimes for the secondary analysis as well. However, it often
leaves us with an insufficient number of sentences regarding the non-primary
analyses.

2\. In order to find additional sentences for the non-primary homograph
analyses, we train classifiers to identify a wide net of potential candidate
sentences. For these classifiers, we use the known cases of the primary
homograph analysis (identified in the previous step) as the first class, and
we use various proxies to represent the opposing class. The proxies used for
the opposing class include the following: (A) Hebrew words which unambiguously
function morphosyntactically in a manner that is different from the
morphosyntactic function of the primary class; (B) Hebrew words whose word2vec
embedding is maximally distant from that of the homograph in question
(because, in practice, for homographs of skewed proportions, the word2vec
embedding of the word tends to represent the primary usage); (C) Randomly-
selected Hebrew words. These classifiers are trained with a BiLSTM encoding of
the word2vec embeddings of the four neighbors on either side of the target
word (not including the target word itself). Essentially, the point of these
classifiers is to identify a generous selection of cases in which the
homographs may possibly be functioning in a way that is different than their
primary usage.

3\. We run these classifiers on all instances of the target homograph in our
untagged Hebrew corpus. Cases that are classified as the opposing class are
sent to our annotators for human verification. In practice, these proxy-based
classifiers reach a precision of 15-30% on the task of identifying sentences
in which the target homographs function according to a non-primary analysis.
Thus, on average, for any given homograph, tagging an additional 2222
sentences allows us to collect 500 relevant cases of the secondary analysis.

Our procedure ensures diversity while keeping the process cost-effective. All
in all it took approximately 1500 hours of annotation time to amass the
sentences in the present dataset.

##  Appendix C Appendix C: Computational Equipment

We performed all computations on a desktop workstation with an i9-10980XE
processor and 256GB of memory. This system enabled us to run 36 experiments in
parallel (the processor contains 18 hyperthreaded cores), and thus we were
able to complete all of the relevant experiments and computations over the
course of several weeks of calendar time.

##  Appendix D Appendix D: Neural Network Implementation Details

All BiLSTMs and MLPs were trained using dynet (http://dynet.io/). All MLPs are
constructed with a hidden layer of size 100, and with two layers. We train
with the Adam optimizer at a learning rate of .001, for 3 epochs.

Our word2vec embeddings for Hebrew are of size 100. We trained them on a
500M-word Hebrew corpus using word2vecf (https://github.com/BIU-NLP/word2vecf,
adding position info to context words, and excluding words with a frequency of
less than seven. All in all, our word2vec vocabulary covers 94.6% of the
tokens in our dataset. For the out-of-vocabulary words, we use a trainable UNK
parameter in place of the word2vec embedding, which is trained from scratch
for each “word expert” classifier.

As per the "word expert" paradigm, a completely separate MLP is trained for
each homograph. In each case, the possible homograph analyses are each treated
as a possible class for prediction, and the MLP is trained to choose from
among those classes. Thus, for instance, if the homograph has two analyses, we
train an MLP to predict one of the two classes; if the homograph has three
analyses, then we train an MLP to predict one of the three classes; and so on.

For the Probing Scenarios based on centroid classification, we proceed as
follows. For each of the homographs, given the training sample size (100, 50,
25, etc.), we randomly select that amount of training sentences for each of
the possible analyses of the homograph. We calculate the centroid for each of
the analyses by averaging the embeddings of the target homographs within the
corresponding training sentences. The remainder of the available sentences for
the homograph forms the test set. We classify them by calculating the dot
product of the embedding of the target homograph in each given test sentence
with the centroid of each of the homograph analyses. We run this process 200
times, each time selecting a different random set of training sentences. The
values plotted in Figure 6 reflect the average of the F1 scores across these
200 rounds. For the corresponding MLP-based experiments presented for
comparison in the aforementioned table, we follow an analogous procedure,
across 10 rounds.


Iterative Detection and Decoding of Finite-Length Polar Codes in Gaussian Multiple Access Channels

Moustafa Ebada, Sebastian Cammerer, Ahmed Elkelesh, Marvin Geiselhart and Stephan ten Brink This work has been supported by DFG, Germany, under grant BR 3205/5-1.

Institute of Telecommunications, Pfaffenwaldring 47, University of  Stuttgart, 70569 Stuttgart, Germany

ECCerror-correcting code

HDDhard decision decoding
SDDsoft decision decoding
MLmaximum likelihood
GPUgraphical processing unit
BPbelief propagation
BPLbelief propagation list
LDPClow-density parity-check
HDPChigh density parity check
BERbit error-rate
BPSKbinary phase shift keying
AWGNadditive white Gaussian noise
MSEmean squared error
LLRlog-likelihood ratio
MAPmaximum a posteriori
NEnormalized error
BLERblock error rate
PEprocessing element
SCLsuccessive cancellation list
SCsuccessive cancellation
BI-DMCbinary input discrete memoryless channel
CRCcyclic redundancy check
CA-SCLCRC-aided successive cancellation list
BECbinary erasure channel
BSCbinary symmetric channel
PSCLpartitioned successive cancellation list
3GPP$3^{\text{rd}}$ generation partnership project
eMBBenhanced mobile broadband
PCCparity-check concatenated
CA-polar codesCRC-aided polar codes
CNcheck nodes
GenAlgGenetic Algorithm
AIartificial intelligence
MCMonte Carlo
CSIchannel state information
PSCLpartitioned successive cancellation list
5G-NR5G new radio
5G$5^{th}$ generation mobile communication
mMTCmassive machine-type communications
URLLCultra-reliable low-latency communications
SGDstochastic gradient descent
NNneural network
MImutual information
SPAsum product algorithm
DLDeep learning
RLreinforcement learning
MIMOmultiple-input multiple-output
RCBrandom coding bound
GMACGaussian multiple access channel
MACmultiple access channel
NOMAnon-orthogonal multiple access
FECforward error-correction
IDMAinterleave-division multiple-access
MUDmulti-user detector
SoICsoft interference cancellation
JSCjoint successive cancellation
IDDiterative detection and demapping
FCCfrozen channel chart
PICparallel interference cancellation

We consider the usage of finite-length polar codes for the GMAC with a finite number of users. Based on the IDMA concept, we implement an iterative detection and decoding NOMA receiver that benefits from a low complexity, while scaling (almost) linearly with the amount of active users.
We further show the conceptual simplicity of the BP-based decoder in a step-by-step illustration of its construction. Beyond its conceptual simplicity, this approach benefits from an improved performance when compared to some recent work tackling the same problem, namely the setup of finite-length FEC codes for finite-number of users. We consider the 5G polar code with a block length $N=512$ applied to both a two-user and a four-user GMAC scenario with a sum-rate of $R_{\mathrm{sum}}=0.5$ and $R_{\mathrm{sum}}=1$, respectively. Simulation results show that a BP-based SoIC receiver outperforms a JSC scheme. Finally, we investigate the effect of a concatenated repetition code which suggests that alternative polar code design rules are required in multi-user scenarios.

§ INTRODUCTION

Polar codes [1] are not only proven to be capacity achieving when the block length tends to infinity, they also have shown to outperform LDPC codes in the short-length regime [2]. A key feature of polar codes is their per-bit-level rate flexibility which can be seen as one of the reasons for their selection for the control channels of the 5G mobile communications standard [3].
Since their introduction, several decoding algorithms for polar codes have been developed. While SCL decoding [4] is widely used, its inherent hard-decision output is limiting its application in iterative receiver architectures, such as IDD. Moreover, the serial nature of the algorithm puts limits to achievable latency and throughput. In contrast, iterative decoding schemes for polar codes such as BP [5] and its derivative [6] are based on the exchange of soft messages and, thus, appear more promising for iterative multi-user detection.

Driven by the continuous increase of active network devices, NOMA schemes have become a fast-growing field of research, opening up many exciting new research possibilities that require a careful reconsideration and re-evaluation of existing coding schemes [7]. For this, we focus on the application of short length communications motivated by IoT sensor networks or similar industrial applications with strict latency requirements that prevent designers from using longer codewords.
Note that, besides its conceptual simplicity in terms of orthogonalization of the channel resources, such a multi-user system may also significantly reduce the medium access latency.
However, contrarily to the single-user case, the multi-user setup is characterized by many more code design parameters such as SNR, flexible number of users and, potentially, non-equal transmit powers that need to be considered for the optimal code design [8]. This amount of configurable system parameters – leading to the need of an individual code rate per user – renders a practical deployment difficult. In particular for the short length regime, it urges the need for a multi-user coding scheme with the highest possible rate flexibility while maintaining a powerful error-rate performance at low decoding complexity.

Block diagram of a 2-user BP-based IDMA receiver.

Polar codes were analytically shown to achieve the channel capacity region of the two-user binary input MAC [9, 10].
In [11], this was proven for the K-user scenario.
However, none of these work provide an efficient decoding scheme for the case of finite code blocklength.
The authors of [12] have proposed to use finite-length polar codes in an JSC-based IDD setup for two and four users for the special case of the unsourced MAC[Unsourced MAC is a novel	paradigm where the number of users, sharing the same codebook, can be unlimited; whereas only a finite number of users can be active on a time slot. ].

We adapt the well-known IDMA principle [13] to short length polar codes with iterative decoding. IDMA is an attractive NOMA superposition coding scheme known to have an exceptionally good performance while maintaining a low decoding complexity using a simple MUD based on PIC. All users can transmit using the same channel code and modulation scheme, only a user-specific interleaver is required.
We show that polar codes under iterative decoding can be seamlessly integrated into the conventional IDMA scheme by replacing the LDPC coding scheme. This promises an unseen rate flexibility on a per-bit-level and the full compatibility to the existing 5G polar coding framework.
In this work, we focus on (relatively) short-length NOMA schemes that are difficult to realize with LDPC codes [8] due to their inherent random graph structure. Because of its inherent SISO property, BP decoding of polar codes appears to be a promising candidate for iterative decoding and detection for multiple users allowing fully parallel decoding.

§ PRELIMINARIES

We provide a brief introduction to the IDMA system model and refer the interested reader to [8] for further details about the system setup.

§.§ IDMA System Model

Consider the IDMA system model with $K_\mathrm{a}$ active users, where each user encodes and decodes its data separately using a fixed polar code of code rate $R_\mathrm{c}$ followed by a repetition code of rate $R_\mathrm{r}~=~\tfrac{1}{d_\mathrm{r}}$. The total information rate is then given by $R_\mathrm{sum}~=~K_\mathrm{a}\cdot R_\mathrm{u}$, where $R_\mathrm{u}=R_\mathrm{c} \cdot R_\mathrm{r}$. After interleaving, the coded bits of the $i^{\text{th}}$ user $\mathbf{c}_i$ undergo a BPSK mapping to $\mathbf{x}_i$. Outputs from $K_\mathrm{a}$ active users are superimposed and transmitted over an AWGN channel which can be expressed as

\begin{equation}
\mathbf{y} = \sum_{i=1}^{K_\mathrm{a}} \sqrt{P_i} \cdot \tilde{\mathbf{x}}_i + \mathbf{n}
\end{equation}

where $P_i$ is the received signal power of the $i^{\text{th}}$ user, $\tilde{\mathbf{x}}_i~=~\mathbf{x}_i\cdot e^{\mathrm{j}\varphi_i}$, with $\varphi_i$ being random phase shifts which are independently and uniformly distributed in $\left[ 0, \pi \right)$ and user-specific. This phase scrambling was shown to improve the performance of superimposed multi-user scenarios [14], especially for AWGN channels.

§.§ Polar Codes

FG; Red nodes: frozen bits

Processing element

Factor graph (FG) of a polar code with $N=8$ and $R_\mathrm{c}=0.5$.

Polar codes are the first provably capacity-achieving channel codes over any arbitrary binary-input discrete memoryless channel [1].
Channel polarization is the core idea of polar codes, where synthesized bit-channels show a polarization behavior.
The synthesized bit-channels polarize such that bit-channels become either noiseless or completely noisy and, thus, can be used for information/data transmission or frozen/known bit transmission.
A polar code of length $N$ and code dimension $k$ (i.e., $\mathcal{P}\left( k,N \right)$) can be fully described with the frozen-bits set.
Since every bit-channel can be either frozen or non-frozen, we can represent the frozen and non-frozen bits by a logical vector $\mathbb{A}$ of length $N$.
Element $i$ in the $\mathbb{A}$-vector (i.e., $a_i$) indicates whether the $i^{th}$ bit-channel is frozen or not.
Throughout this work, $a_i=0$ means that the $i$-th bit-channel is a frozen bit, while $ a_i=1$ indicates an information bit-channel.
Thus, the polar code rate can be formulated as $R_\mathrm{c} = \frac{k}{N} = \frac{\sum_{i=1}^{N} a_i}{N}$.

Originally, the choice of frozen/non-frozen bit-channels was based on the assumption of using a SC decoder to decode the polar code [1].
However, for finite length polar codes, the SC decoder performs poorly in terms of error-rate.
Thus, other decoding algorithms were proposed in the literature (e.g., BP decoder [5] and SCL decoder [4]) outperforming the SC decoder.
The BP decoder of polar codes is a soft-in/soft-out decoder, thus, it is very suitable for decoding concatenated coding schemes (e.g., see [15, 16, 17]) and suitable for iterative detection and decoding. In this work, we mainly focus on BP decoding of polar codes when applied to iterative detection and decoding.

§.§ BP Decoding and Factor Graphs

Polar codes can be visualized as a code on a graph [18] and, thus, iterative BP decoding (i.e., SPA) can be used to decode polar codes [5].
The Forney-style factor graph of polar codes (shown in Fig. <ref>) consists of $\log_2 \left(N\right)$ stages. Each stage contains $\frac{N}{2}$ PE (shown in Fig. <ref>).
The channel output in terms of LLR $ \mathbf{L_{\text{ch}} }$ is fed into the right-most stage of the factor graph.
The code structure is defined by the left-most stage of the factor graph or, in other words, the frozen and non-frozen bit-channel positions.
Then, LLR-based messages propagate over the edges of the factor graph from right-to-left ($\bf{L}$-messages) and then from left-to-right ($\bf{R}$-messages), until a maximum number of iterations $N_{\text{it,max}}$ is reached or until an early stopping condition is satisfied [19]. Throughout this work, we use a $\mathbf{G}$-matrix-based early stopping condition which terminates the iterations when $\mathbf{\hat{x}}$ is equal to $\mathbf{\hat{u}} \cdot \mathbf{G}$ where $\mathbf{G}$ is the $k \times N$ polar code generator matrix.
A codeword estimate $\mathbf{\hat{x}}$ and the information bits estimate $\mathbf{\hat{u}}$ are the outputs from the BP decoder after performing a hard-decision operation on the LLR messages in the right-most and the left-most stages, respectively.

The $\bf{L}$- and $\bf{R}$-messages are updated in each PE as follows:

\begin{align*}
R_{\mathrm{out},1} &=f(R_{\mathrm{in},1},L_{\mathrm{in},2}+R_{\mathrm{in},2}) \\  R_{\mathrm{out},2} &=f(R_{\mathrm{in},1},L_{\mathrm{in},1})+R_{\mathrm{in},2}  \\    L_{\mathrm{out},1} &=f(L_{\mathrm{in},1},L_{\mathrm{in},2}+R_{\mathrm{in},2}) \\  L_{\mathrm{out},2}&=f(R_{\mathrm{in},1},L_{\mathrm{in},1})+L_{\mathrm{in},2}
\end{align*}

where $f(L_1,L_2)=L_1 \boxplus L_2$ is commonly referred to as boxplus operator
, which can be expressed as

$$ f(x,y)=x \boxplus y= \operatorname{log}\frac{1+e^{x+y}}{e^x+e^y}.$$

§ BP-BASED MULTI-USER DECODING AND DETECTION OF POLAR CODES

Similar to [8], the proposed decoder setup is composed of several blocks, namely:

* a sub-optimal soft interference cancellation (SoIC)-based MUD block as mentioned before,

* a repetition (REP) decoder,

* a polar iterative decoder (i.e., BP decoder).

§.§ General scheme

Assume that $\mathbf{y}$ is the received noisy channel observation of superimposed symbols $\mathbf{x}_i$.
As depicted in Fig. <ref>, the proposed decoder setup processes $\mathbf{y}$ as follows:

* SoIC-MUD

* Optimally: MUD would compute a posteriori probability (APP) per bit with complexity $\mathcal{O}\left(M^{K_\mathrm{a}}\right)$, where $M$ is the number of constellation symbols per user

* Here: a sub-optimal soft interference cancellation based low complexity MUD is implemented
with complexity $\mathcal{O}\left(M \cdot K_\mathrm{a} \right)$

* $\mathbf{\hat{x}}_{i}$: feedback from single user decoder

* $\mathbf{y}_{j}$: forward message after SoIC
$$\mathbf{y}_{j}=\mathbf{y}-\sum_{i\neq j}\mathbf{\hat{x}}_{i}$$

For more details, we refer the interested reader to [8].

* Demapping and De-scrambling: where log-likelihood-ratio
(LLR) of each bit is computed by the (soft) demapper while treating the residual interference	as noise; followed by user-specific phase scrambling.

* Deinterleaving: according to each user's specific interleaving pattern. Accordingly, the a priori knowledge of the REP decoder comes from the extrinsic message from MUD.

* REP decoding: of code rate $R_\mathrm{r}=\tfrac{1}{d_\mathrm{r}}$ in case of repetition (discussed later), which enhances the signal-to-interference-plus-noise ratio (SINR) for further outer decoding. The extrinsic information of the $j^{\text{th}}$ information symbol of the
repetition code is the summation of the LLRs of all corresponding repeated symbols.

* BP decoding: run a few $N_{\text{it,BP}}$ decoder-internal BP iterations (e.g., 1 or 2 iterations) to get an enhanced soft estimate of a codeword. As discussed later, more (sufficient) BP iterations are required in case of resetting the BP graph's internal memory after each BP decoding step.

* Repetition

* Interleaving

$6)$ Scrambling and remapping

* Repeating previous steps for $N_{\text{it,MUD}}$ times, and, thus, denoted as: $\left( N_{\text{it,BP}} \times N_{\text{it,MUD}} \right)$.

Each individual BP decoder for a single user generates an improved soft-information output, which is then used by other user detectors to further de-noise the soft input to their BP decoders. The decoder setup is illustrated in Fig. <ref>.

§.§ Internal memory effects of polar BP factor graph

Influence of initialization of the BP factor graph for a $\mathcal{P}\left(N=512,k=256\right)$ 5G polar code; 20 BP iterations; single user scenario.

Internal LLR values of a BP factor graph instance, namely $L_{i,j}$ and $R_{i,j}$, are equivalently noted as factor graph internal states. These states form the so-called “internal memory” of a graph which affects the decoding convergence to a specific codeword. To further illustrate that, two BP decoding setups are compared in Fig. <ref>:

* A BP decoding graph that clears the graph internal states before starting to decode a new codeword (i.e., resets the factor graph).

* BP decoding graph where the internal memory of it persists (i.e., internal LLR values from previous codeword are not removed while decoding a new codeword).

As can be seen in Fig. <ref>, the graph internal memory initialization plays a significant role in the convergence behavior of a specific decoding instance. This has a strong impact on the multi user turbo decoder setup.  After each MUD iteration, the BP factor graph is already at some state and, thus, the soft information is strongly affected by the previously acquired graph state. Thus, one solution might be as follows:

* run BP for a sufficient number of iterations, instead of only a few iterations

* pass information to MUD

* reset BP factor graph (resetFG), i.e., “start over” whenever MUD output is updated.

The resultant new decoding setup enjoys an improved error-rate performance when compared to the previously mentioned setups, as depicted in Fig. <ref> and Fig. <ref>.

§ RESULTS

BLER performance for codelength $N=512$ and $R_\mathrm{sum}=0.5$ bits per channel use with $ K_\mathrm{a}=2 $ users over an AWGN channel.

Throughout this work,  all polar BP curves correspond to a polar code of length $N=512$ designed with the 5G bit-channel ordering [3],  whereas the curves from [12] are optimized for their respective scheme (i.e., different polar code or $\mathbb{A}$-vector). We show results for two specific scenarios while benchmarking against the iterative SCL and JSC results of [12].

§.§ 2-User GMAC

Here, codewords from two active users are superimposed, each with a rate of $R_\mathrm{c}=\tfrac{1}{4}$ and $d_\mathrm{r}=1$ (no repetition), thus, overall information rate $R_\mathrm{sum}=\tfrac{1}{2}$. The error-rate simulation results for this setup are shown in Fig. <ref>.

§.§ 4-User GMAC

Here, codewords from four active users are superimposed with $R_\mathrm{sum}=1$ fixed.
For the case of $R_\mathrm{c}=\tfrac{1}{4}$ with $d_\mathrm{r}=1$ (no repetition) and $R_\mathrm{c}=\tfrac{1}{2}$ with $d_\mathrm{r}=2$ (two-fold repetition).
The error-rate simulation results for this setup are shown in Fig. <ref>.

Combined with repetition coding, the resultant scheme can be of significantly superior performance under joint polar BP-REP-SoIC decoding compared to that under JSC decoding introduced in [12].
It is worth-mentioning that scaling up the setup for (much) more users is straightforward.

BLER performance for codelength $N=512$ and $R_\mathrm{sum}=1$ bits per channel use with $ K_\mathrm{a}=4 $ users over an AWGN channel.

§ THE REPETITION CODING DILEMMA

It is a well-known fact that repetition coding has no coding gain for the single-user case. However, it seems as if repetition codes are very efficient for interference cancellation as pointed out in [8]. As depicted in Fig. <ref>, a joint BP-based IDD receiver can benefit from an inner repetition code of repetition factor $d_\mathrm{r}=2$ when compared to a setup that does not involve a repetition code. The resultant code/receiver setup outperforms all of the previously mentioned coding/joint-IDD setups, as can be observed in Fig. <ref>. Here, we further explore this for the case of $K_\mathrm{a}=4$ active users.

A polar code of length $N$ concatenated with an inner repetition code of repetition factor $d_\mathrm{r}$ can be viewed as another equivalent polar code of length $N \cdot d_\mathrm{r}$, as depicted in Fig. <ref>. As can be seen, the equivalent polar code in Fig. <ref> is constructed by appending $N \cdot \left(d_\mathrm{r}-1\right)$ frozen bits to the original polar code in Fig. <ref>. The equivalent polar code results in the same error-rate performance when compared to the original code setup, as depicted in Fig. <ref> (i.e., compare <ref> and <ref>).

Based on that, one might deduce that the effect of concatenating an inner repetition code, with the polar code is equivalent to a  design enhancement for polar codes for the multi user setup (i.e., a better $\mathbb{A}$-vector tailored to the multi-user scenario). The performance gain with repetition is not merely a result of increasing the codelength by repetition, as can be observed from Fig. <ref> (i.e., compare <ref> and <ref>). Fig. <ref> shows a frozen channel chart (FCC) [21] for each of the equivalent and plain polar codes of the same length. One can easily see that the new equivalent polar code differs in many bit-positions from a polar code that follows the single user construction rules (e.g., 5G and Bhattacharyya-based polar codes). The equivalent polar code is, thus, not suitable for a traditional single user setup where it leads to a severe performance loss, as can be seen in Fig. <ref> (i.e., compare <ref> and <ref>).

Factor graph of polar code $\left(N=4\right)$ + REP-2 ($d_\mathrm{r}=2$   repetition code)

Factor graph of the “equivalent” polar code

An equivalent perspective of the polar code concatenated with an inner repetition code.

Difference between the equivalent $\mathbb{A}$-vector and a good single-user code design (i.e., 5G-based $\mathbb{A}$-vector) visualized using a frozen channel chart (FCC) [21]. The $1024$ bit positions are plotted over a $16\times64$ matrix. Note that the bit-channels are sorted with decreasing Bhattacharyya parameter value. White: non-frozen; colored: frozen.

§ CONCLUSION

In this paper, we proposed the usage of BP decoders for iterative detection and decoding of polar codes in a multi-user scenario. Combined with repetition coding, the resulting scheme can compete with, and even outperform, JSC based IDD [12] for two and four users, while the inherent parallel nature of polar BP decoding may lead to more desirable hardware implementations. Further analysis is required to investigate the case for a massive number of users.

Error-rate of a conventional polar code concatenated with an inner repetition code compared to that of the equivalent longer polar code, similar to Fig. <ref>. Single-user performance is also plotted to show difference to multi-user setup (i.e., in a multi-user setup: equivalent code is superior in performance to that of a typically constructed polar code without repetition; whereas for a single-user setup it is exactly the opposite). Sum-rates of both setups are obviously not comparable. All curves shown for codelength $N=1024$.

We also shed some light on the gains by the usage of a concatenated repetition code and verified its effectiveness in Monte-Carlo simulations, a theoretical explanation remains, however, an open problem. We concluded that this repetition code corresponds to a different selection of frozen bit-positions (different $\mathbb{A}$-vector) in the polar code design, suggesting that the multi-user detection can benefit from a different polar code design than the single-user case. Finding such an optimized polar code construction is an interesting open future work and an important step towards efficient deployment of multi-user polar coding with iterative detection and decoding.

[1]
E. Arıkan, “Channel Polarization: A Method for Constructing
Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels,”
IEEE Trans. Inf. Theory, vol. 55, no. 7, pp. 3051–3073, Jul. 2009.

[2]
M. C. Coşkun, G. Durisi, T. Jerkovits, G. Liva, W. E. Ryan, B. Stein, and
F. Steiner, “Efficient Error-Correcting Codes in the Short Blocklength
Regime,” Physical Communication, vol. 34, pp. 66–79, Jun. 2019.

[3]
“Technical Specification Group Radio Access Network,” 3GPP, 2018, TS
38.212 V.15.1.1. [Online]. Available:

[4]
I. Tal and A. Vardy, “List Decoding of Polar Codes,” IEEE Trans. Inf.
Theory, vol. 61, no. 5, pp. 2213–2226, May 2015.

[5]
E. Arıkan, “Polar Codes: A Pipelined Implementation,” Proc. 4th
ISBC, pp. 11–14, 2010.

[6]
A. Elkelesh, M. Ebada, S. Cammerer, and S. ten Brink, “Belief Propagation
List Decoding of Polar Codes,” IEEE Commun. Lett., vol. 22, no. 8,
pp. 1536–1539, Aug. 2018.

[7]
L. Dai, B. Wang, Z. Ding, Z. Wang, S. Chen, and L. Hanzo, “A Survey of
Non-Orthogonal Multiple Access for 5G,” IEEE Commun. Surveys &
Tutorials, vol. 20, no. 3, pp. 2294–2323, 2018.

[8]
X. Wang, S. Cammerer, and S. ten Brink, “Near-Capacity Detection and
Decoding: Code Design for Dynamic User Loads in Gaussian Multiple Access
Channels,” IEEE Trans. Commun., vol. 67, no. 11, pp. 7417–7430,

[9]
E. Şaşoğlu, E. Telatar, and E. M. Yeh, “Polar Codes for the Two-User
Multiple-Access Channel,” IEEE Trans. Inf. Theory, vol. 59, no. 10,
pp. 6583–6592, 2013.

[10]
S. Önay, “Successive Cancellation Decoding of Polar Codes for the Two-User
Binary-Input MAC,” in IEEE Inter. Symp. Inf. Theory (ISIT), 2013,
pp. 1122–1126.

[11]
E. Abbe and E. Telatar, “Polar Codes for the $m$-User Multiple Access
Channel,” IEEE Trans. Inf. Theory, vol. 58, no. 8, pp. 5437–5448,

[12]
E. Marshakov, G. Balitskiy, K. Andreev, and A. Frolov, “A Polar Code
Based Unsourced Random Access for the Gaussian MAC,” in IEEE 90th
Vehicular Technology Conference (VTC2019-Fall), 2019, pp. 1–5.

[13]
Li Ping, Lihai Liu, Keying Wu, and W. K. Leung, “Interleave Division
Multiple-Access,” IEEE Trans. on Wireless Commun., vol. 5, no. 4,
pp. 938–947, 2006.

[14]
G. Song and J. Cheng, “Distance Enumerator Analysis for
Interleave-Division Multi-User Codes,” IEEE Trans. Inf. Theory,
vol. 62, no. 7, pp. 4039–4053, 2016.

[15]
J. Guo, M. Qin, A. G. i Fàbregas, and P. H. Siegel, “Enhanced Belief
Propagation Decoding of Polar Codes through Concatenation,” in IEEE
Inter. Symp. Inf. Theory (ISIT), Jun. 2014, pp. 2987–2991.

[16]
A. Elkelesh, M. Ebada, S. Cammerer, and S. ten Brink, “Improving Belief
Propagation Decoding of Polar Codes Using Scattered EXIT Charts,” in
IEEE Inf. Theory Workshop (ITW), Sep. 2016, pp. 91–95.

[17]
——, “Flexible Length Polar Codes through Graph Based Augmentation,” in
IEEE Inter. ITG Conf. on Syst., Commun. and Coding (SCC), Feb. 2017.

[18]
G. D. Forney, “Codes on Graphs: Normal Realizations,” IEEE Trans.
Inf. Theory, vol. 47, no. 2, pp. 520–548, Feb. 2001.

[19]
B. Yuan and K. K. Parhi, “Early Stopping Criteria for Energy-Efficient
Low-Latency Belief-Propagation Polar Code Decoders,” IEEE Trans. Sig.
Process., vol. 62, no. 24, pp. 6496–6506, Dec. 2014.

[20]
Y. Polyanskiy, “A Perspective on Massive Random-Access,” in IEEE
Inter. Symp. Inf. Theory (ISIT), 2017, pp. 2523–2527.

[21]
A. Elkelesh, M. Ebada, S. Cammerer, and S. ten Brink,
“Decoder-Tailored Polar Code Design Using the Genetic Algorithm,”
IEEE Trans. Commun., vol. 67, no. 7, pp. 4521–4534, Jul. 2019.