# Annotating Hate and Offenses on Social Media

Francielle Vargas¹, Fabiana Góes¹, Isabelle Carvalho¹, Fabrício Benevenuto²,
Thiago Pardo¹
¹Institute of Mathematical and Computer Sciences, University of São Paulo,
Brazil
²Computer Science Department, Federal University of Minas Gerais, Brazil
<EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>

###### Abstract

This paper describes a corpus annotation process to support the identification
of hate speech and offensive language in social media. The corpus was
collected from Instagram pages of political personalities and manually
annotated, being composed by 7,000 documents annotated according to three
different layers: a binary classification (offensive versus non-offensive
comments), the level of the offense (highly offensive, moderately offensive
and slightly offensive messages), and the identification regarding the target
of the discriminatory content (xenophobia, racism, homophobia, sexism,
religion intolerance, partyism, apology to the dictatorship, antisemitism and
fat phobia). Each comment was annotated by three different annotators, which
achieved high inter-annotator agreement.

##  1 Introduction

In recent years, the use of social media has increased and brought a lot of
advantages for the society, as virtual human interactions that enables people
from anywhere to connect with anyone Leite et al. (2020). Nevertheless,
society has also been affected in negative ways, such as the spread of
offenses and hate speech. Thus, the identification of offensive, aggressive,
and other kinds of abusive language has attracted the interest from
institutions and become an important research topic Çöltekin (2020a); Leite et
al. (2020).

Offensive language is used to insult, attack or disrespect a reader. Its
content may be characterized in different ways, such as abusive Steimel et al.
(2019); Mubarak et al. (2017), cyberbullying Rosa et al. (2019) and hate
speech content Schmidt and Wiegand (2017); Fortuna et al. (2019).

Nockleby (2000) defines hate speech as “any communication that disparages a
person or a group on the basis of some characteristic such as race, color,
ethnicity, gender, sexual orientation, nationality, religion or other
characteristic”. More recently, Fortuna and Nunes (2018) adopted the following
hate speech definition: “language that attacks or diminishes, that incites
violence or hate against groups, based on specific characteristics such as
physical appearance, religion, descent, national or ethnic origin, sexual
orientation, gender identity or other, and it can occur with different
linguistic styles, even in subtle forms or when humour is used”. For Brugger
(2007), the international law consistently allows or prohibits hate speech,
depending on the country: such speech is sometimes protected (with varied
tolerance levels), sometimes not.

Recent cases show the impact of offensive language in social media around the
world. As observed in Figure 1, the “hate speech” term has become very common
over the last years.

Figure 1: Occurrence of the term “Hate Speech” in English-language
publications indexed in Google Books Ngram
Viewer222https://books.google.com/ngrams/

.

On the report of Mesquita (2018), the Safernet Non-Governmental Organization,
which operates in cooperation with Public Organizations in Brazil, as well as
companies such as Google, Facebook and Twitter, proposed a collection of data
on actions that violate human rights. They state very clearly that
“denunciations with xenophobia content grew by 2,369.5%, apology and
incitement to crimes against life, 630.52%, Neo-Nazism, 548.4%, homophobia,
350.2%, racism, 218.2%, and religious intolerance, 145.13%.

In United States and South America, hate against minorities or based on party
options (also called partyism) has caused serious events of violence. Westwood
et al. (2018) showed that, in USA, affective polarization 333According to
Westwood et al. (2018), affective polarization consists of the tendency to
negatively identify opposing supporters, while co-supporters are positively
identified. This affective separation is the result of a classification of
opposing supporters as an external group and co-supporters as internal group
members. based on the political party is as strong as the polarization caused
by skin color and, consequently, party-based discrimination is so profound
that outweighs discrimination based on skin color. Sunstein (2016) argues that
partyism is real and growing, currently revealing itself to be even worse than
racism by provoking consequences to the governmental spectrum. In Brazil, some
notorious cases have also recently occurred.

Given the relevance of the topic, the existence of annotated corpora is
essential to carry out experiments on automatic offensive language and hate
speech detection. Nevertheless, annotation process is an intrinsically
challenging and time-consuming task. The identification of offensive comments
requires well-deﬁned context and its absence may lead to a difficult label
choice. Another challenge is the presence of sarcasm, which hides the real
intention of the comment and makes the decision of the annotators more
confusing. The understanding of an offense is also subjective and people may
have different opinions about the offensiveness of a comment.

Consistency and quality of the data is directly related to the performance of
the Machine Learning classifiers. In Natural Language Processing (NLP),
subjective tasks, such as offensive language and hate speech detection,
present high complexity and several challenges. Therefore, a definition of an
annotation schema is relevant, mainly because a reliable annotation approach
offers adequate characterization of particularities for subjective tasks,
which, consequently, improves the quality of the annotated data.

###  1.1 Contributions of this paper

To the best of our knowledge, no previous annotated corpus exists in order to
detect offensive language and hate speech for the Brazilian Portuguese
language. To fill this important gap, in this paper, we present a new corpus
and its annotation process for offensive language and hate speech detection on
social media. The corpus was collected from different accounts of political
personalities on Instagram. The political context was chosen due to the
identification of several types of offenses and hate attacks in different
groups. The entire annotation process was guided by a linguist, which is NLP
specialist, as well as Guideline and training steps have been proposed in
order to ensure the same understanding of the tasks and bias minimization,
resulting in greater reliability of the annotation and quality of the proposed
data to be used in automatic classification tasks.

More specifically, the main contributions of this paper are: (i) a new corpus
with 7,000 documents in Brazilian Portuguese, which possess three different
layers of annotation (a. offensive versus non-offensive comments; b. offensive
comments sorted into highly offensive, moderately offensive and slightly
offensive levels; c. nine hate groups: xenophobia, racism, homophobia, sexism,
religion intolerance, partyism, apology to dictatorship, antisemitism and fat
phobia); (ii) the definition of an annotation process for hate speech and
offensive language detection on social media, which is language and domain
independent (although it has been used for Brazilian Portuguese).

The remainder of the paper is structured as follows. In Section 2, we
introduce the most relevant related works. Section 3 describes the corpus
development process, as well as our annotation approach. Sections 4 and 5 show
the corpus statistics and its evaluation. In Section 6, final remarks and
future works are presented.

##  2 Related Corpus

Most of hate speech and offensive language corpora are for English Davidson et
al. (2017), de Gibert et al. (2018), Waseem and Hovy (2016), Gao and Huang
(2017), Jha and Mamidi (2017), Fersini et al. (2018), Basile et al. (2019),
Golbeck et al. (2017). However, Chung et al. (2019) and Ousidhoum et al.
(2019) constructed corpora of Facebook and Twitter data for Islamophobia,
sexism, homophobia, religion intolerance and disability detection in French
language. German Bretschneider and Peters (2017) provides an anti-foreigner
prejudice corpus with 5,836 Facebook posts hierarchically annotated for
slightly and explicitly/substantially offensive language with six targets:
foreigners, government, press, community, other, and unknown. For Arabic,
Albadi et al. (2018) proposed a dataset with 6,136 twitter posts, which is
annotated in religion subcategories. Ljubešić et al. (2018) provides a large-
scale dataset composed of 17,000,000 posts, with 2% of abusive language on the
24sata website 44424sata (lit. “24hours”) is the leading media company in
Croatia. for Slovene and Croatian Moderated News Comments. For Greek,
Pavlopoulos et al. (2017) and Pitenis et al. (2020) contributed with datasets
of Twitter and Gazeta posts for flagged content detection. For Indonesian
language, Alfina et al. (2017) and Ibrohim and Budi (2018) provided a dataset
from Twitter. For Italian, Spanish, Polish, Slovene and Turkish, see details
at Sanguinetti et al. (2018), Aragón et al. (2019), Ptaszynski et al. (2019),
Ljubešić et al. (2018), and Çöltekin (2020b), respectively.

For European Portuguese, Fortuna et al. (2019) adopted the definition of hate
speech proposed by Fortuna and Nunes (2018), and proposed a new dataset using
a hierarchy of hate to identify social groups of discrimination. For Brazilian
Portuguese, de Pelle and Moreira (2017) provided a dataset of offensive
comments, as well as classification results achieved by standard
classification algorithms, which represent the current baseline for offensive
language detection in Brazilian Portuguese.

##  3 Corpus Development

In this section, we describe our approach to build an annotated corpus for
offensive language and hate speech detection on social media. Moreover, we
provide a new robust dataset for the Brazilian Portuguese language. The entire
process of annotation was supported by annotation guidelines, as well as a
offensive lexicon, which we constructed from Brazilian Portuguese social media
texts. The Multilingual Offensive Lexicon (MOL)
555https://github.com/francielleavargas/MOL is composed by 1,000 offensive and
swearing terms and expressions, and annotated with the following binary
classes: context dependent offensive expression, and context-independent
offensive expression.

###  3.1 Data Acquisition

The dataset was collected by scraping data from the social network Instagram.
Instagram is a representative platform for showcasing digital influencers,
making it a powerful option for mass media. According to the Statistical
portal [December/
2020]666https://www.statista.com/statistics/578364/countries-with-most-
instagram-users/, Brazil occupies the third position in the worldwide ranking
of Instagram’s audience with 95 million active Brazilian users. Each person
has an account with shared photos and it is possible for others to like,
comment, save and share this information. Our data collection focused on the
comments of the posts.

We collected 15,000 comments from six public Instagram’s accounts of the
Brazilian political domain (see Table 1). We selected three liberal-party
accounts and three conservative-party accounts, being four women and two men
(see Table 2).

Table 1: Data Collection Information Data/Account |  Total
---|---
Extracted Comments |  15,000
Posts |  30
Accounts |  6
Table 2: Account Profiles Profile |  Description
---|---
Gender |  4 women and 2 man
Political |  3 liberals and 3 conservative

Posts were selected at random, regarding any subject, not just political,
arranged throughout the second half of 2019 (see the subjects of these posts
in Table 3). The choice of influencers aimed at balancing variables such as
sex and political nature; therefore, men and women were chosen, representing
the two main Brazilian political strands with more than 500 thousand
followers. We removed comments that contained only emotes, laughs (kkk or
hahah or hshshs) and accounts (e.g., @namesomeone). In Figure 2, we have an
overview of the corpus construction with detailed steps of the data collection
process. The resulting corpus was named “HateBr”.

Table 3: Topics Topics |  Total |  %
---|---|---
Politics |  16 |  61.54
Fake News |  2 |  7.69
Crimes |  2 |  7.69
Sexism |  2 |  7.69
Racism |  1 |  3.85
Economy |  1 |  3.85
Harassment |  1 |  3.85
Environment |  1 |  3.85
Figure 2: Overview of the process of corpus development

###  3.2 Concepts

Recent papers addressed the detection of hate speech on social media focusing
on different aspects. The main aspects are (i) detecting hate groups, such as
racism Hasanuzzaman et al. (2017), antisemitism Jikeli et al. (2019), and
cyberbullying Van Hee et al. (2015); (ii) filtering pages with hate and
violence Liu and Forss (2015); (iii) offensive or abusive language detection
Gao et al. (2020); and (iv) toxic comment detection Guimarães et al. (2020).
For a comprehensive survey of NLP techniques in order to detect hate speech,
see Schmidt and Wiegand (2017). For multilingual approaches, see Steimel et
al. (2019).

This paper contributes for tasks of offensive language detection and detecting
hate groups. In our approach, in addition to offensive and non-offensive
comments, we identified flaming-levels for offensive language, as well as
groups of hate. In order to achieve that, we distinguish offensive terms or
expressions from swearing and hate speech. Therefore, for annotation theory or
concept, we evaluate three main dictionary definitions on offense and
swearing, as well as the most commonly shared literature definition for hate
speech, and we adopted the following concepts for offenses, swearing and hate
speech annotation.

####  3.2.1 Offenses

Term or expression that intends to undermine or disparage any of the following
social aspects: moral, appearance, physical and psychological health, sexual
behavior and orientation, intellectual, economic, religious and political
aspects.

####  3.2.2 Swearing

Swearing words or expressions are used to convey hateful opinion, with high
aggressive value and great potential to generate negative reactions to the
interlocutor.

Table 4 show examples of annotation for each offense and swearing labels.

Table 4: Offenses, Swearing Terms and Expressions Type |  Term/Expression |  Translation
---|---|---
Swearing |  Vai Tomar no Cú |  Go Fuck Yourself
Swearing |  Vergonha na Cara |  Get Your Shit Together
Swearing |  Vai para o Inferno |  Go to Hell
Swearing |  Filho da Puta |  Motherfucker
Swearing |  Foda-se |  Fuck it
Offenses |  Mentiroso |  Lier
Offenses |  Vagabunda |  Bitch
Offenses |  Canalha |  Jerk
Offenses |  Desgraçado |  Bastard
Offenses |  Facista |  Fascist

####  3.2.3 Hate Speech

Hate speech is a language that attacks or diminishes, that incites violence or
hate against groups, based on specific characteristics such as physical
appearance, religion, descent, national or ethnic origin, sexual orientation,
gender identity or other, and it may occur with different linguistic styles,
even in subtle forms or when humour is used Fortuna and Nunes (2018).

  * •

Partyism: Westwood et al. (2018) demonstrated that partyism and partisan
affect influence behaviors and non-political judgment. According to the
professor at Harvard University, “partyism” is a form of hostility and
prejudice that operates across political lines Sunstein (2016). In our corpus,
the most relevant occurrence of hate speech consist of partyism, as the
following example shows: Os petralhas colocaram sua corja em todos os lugares,
não salva ninguém, que tristeza .. Esquerda parasita lixo. “The petralhas put
their crowds everywhere, no one can be saved, how sad. They are parasite and
trash”.

  * •

Sexism: Sexism behavior is mostly related to patriarchy, which, according to
Walby (1990), consist of a system of social structures that relate among one
another and that allow men to exploit women. Nonetheless, Delphy (2000)
complements that women are seen as objects of sexual satisfaction of men,
reproducers of heirs, labor force and new breeders. An example found in our
corpus shown: Cala esse bueiro de falar merda sua vagabunda safada. “Shut that
manhole to talk shit you dirty slutmachi”.

  * •

Religious Intolerance: As maintained by Altemeyer (1996), theoretical
constructs loom large in the literature on religiosity and intolerance:
namely, religious fundamentalism, which is consistently associated with high
levels of intolerance and prejudice toward out-groups. An example follows:
Aqui na Bahia se chama ”crente do cu quente”. “Here in Bahia it is called
“Christian of the hot ass” ”.

  * •

Apology to Dictatorship: According to Brazilian Penal Code 777The Brazilian
Penal Code, Decree-Law No. 2,848 / 1940, is formed by a set of systematic
rules with a punitive character. Its purpose is the application of sanctions
in conjunction with discouraging the practice of crimes that threaten the
social fabric., apology to dictatorship consists of comments that incite the
subversion of the political or social order, the animosity between the Armed
Forces or between them and the social classes or civil institutions. An
example follows: Intervenção militar já !!! Acaba STF não serve pra nada
mesmo… “Military intervention now !!! It’s over STF is of no use at all …”.

  * •

Fat Phobia: Robinson et al. (1993) defines fat phobia as negative attitudes
towards and stereotypes about fat people. An example follows: Velha barriguda
d bem folgada, heim? Porca rosa, peppa! “Old bellied and very loose, huh? Pink
Nut, peppa!”.

  * •

Homophobia: According to for Fundamental Rights FRA (2009), homophobia is an
irrational fear of, and aversion to, homosexuality and to lesbian, gay and
bisexual people based on prejudice. An example follows: Quem falou isso deve
ser um global que não sai do armário :) :( e tem esse desejo :( :( nessa hora
que tinha que intervir aqui e botar um merda desse no pau. …Dá muito o cú.
“Whoever said that must be a global who does not come out of the closet :( :(
and has that desire :( :( at that time they had to intervene here and apply
the law against them. … It gives the ass a lot”.

  * •

Racism / Racial Segregation: According to Wilson (1999), racism consists of
the “an ideology of racial domination”. In addition, Clair and Denis (2001)
argues that racism presumes biological or cultural superiority of one or more
racial groups, used to justify or prescribe the inferior treatment or social
position(s) of other racial groups. Through the process of racialization,
perceived patterns of physical difference, such as skin color or eye shape –
are used to differentiate groups of people, thereby constituting them as
“races”; racialization becomes racism when it involves the hierarchical and
socially consequential valuation of racial groups. In our corpus, we found
many offenses such as “monkey” and “cheetah”, as well as another offenses
related to racial segregation. An example follows: E uma chita ela né! Opssss,
uma chata. “And she is a cheetah right! Oopssss, a boring.”.

  * •

Antisemitism: The definition of antisemitism adopted by the IHRA 888The
International Holocaust Remembrance Alliance (IHRA) unites governments and
experts to strengthen, advance, and promote Holocaust education, research, and
remembrance, as well as to uphold the commitments of the 2000 Stockholm
Declaration. in 2016 states that “Antisemitism is a certain perception of
Jews, which may be expressed as hatred toward Jews. Rhetorical and physical
manifestations of antisemitism are directed toward Jewish or non-Jewish
individuals and/or their property, toward Jewish community institutions and
religious facilities. Manifestations might include the targeting of the state
of Israel, conceived as a Jewish collectivity.”. An example follows: Que
escroto caquético! É a velha hipocrisia judaica no mundo dos pilantras
monetários. Judeu dos infernos!. “What a cachectic scrotum! It’s the old
Jewish hypocrisy in the world of monetary hustlers. Jew from hell!”.

  * •

Xenophobia: Oliveira (2019) describes xenophobia as a form of prejudice, which
is manifested through discriminating actions and hate against the foreigners.
An example follows: Ele está certo. Vai ter um monte de argentino faminto
invadindo. “He is right. There will be a lot of hungry Argentines invading the
Brazil”.

###  3.3 Method

In order to achieve a reliable annotation process, we proposed a method that
we divided in three main steps. In the first step, we annotated the corpus in
two classes: offensive or non-offensive comments. In the second step, we
selected only offensive comments, and classified them in flaming-levels. The
flaming-levels consist of three classes: highly offensive, moderately
offensive and slightly offensive comments. Finally, in the third step, we
classified the offensive comments according to the hate groups. Figure 3 shows
our approach.

Figure 3: Annotation Method for Hate Speech and Offensive Language
Classification.

In order to identify offensive terms and expressions, as well as swearing
words, annotators were supported by MOL - Multilingual Offensive Lexicon
999MOL consists of a multilingual lexicon composed by 1,000 explicit and
implicit pejorative expressions of opinion in context, which was extracted
from a 7,000-document corpus of offensive and non-offensive comments on social
media. More information may be obtained in
https://github.com/francielleavargas/MOL..

We initially assume that, if in a comment there is any explicit or implicit
offensive expression and swear word, then this comment has offensive content.
If there are no such linguistic markings in the text, this comment is non-
offensive. That was our first classification.

In a second step, the set of offensive comments received a new label according
to its level of offense. The process consists in the following checkings: [i]
if the comment contains at least one explicit swear word or a sequence of
explicit and implicit offensive words, this comment is highly offensive; [ii]
if the comment contains at least one explicit and strong offensive term or
expression, this comment is moderately offensive, and [iii] if the comment
does not present the previous issues, this comment is slightly offensive. As
product of this step, we obtained the flaming-levels of offensive comments.

In parallel with the flaming-levels annotation, we also annotated the hate
speech groups. Nine groups were identified, which were previously described.
This activity was built on the set of offensive comments and consists of
flagging offenses or/and discrimination against these minority groups.

###  3.4 Annotators Background

Due to the degree of complexity of the task for offensive language and hate
speech detection, mainly because it involves a highly politicized domain, we
decided to enroll annotators at higher levels of education. Moreover, in order
to minimize bias, we selected annotators from different political
orientations, as well different colors, as shown in Table 5.

Table 5: Annotator Profiles Profile |  Description
---|---
Education |  PhD
Gender |  feminine
Political |  liberal and conservative
Color |  white and black

We selected annotators with higher levels of education. Two annotators have
PhD degrees and one is a PhD candidate. Furthermore, we diversified the color
and political profile as a bias-minimization strategy.

##  4 Dataset Statistics

One of the struggles of the annotation process is the difference between the
amount of comment classes, since there are much less offensive comments than
non-offensive comments present in randomly sampled data Schmidt and Wiegand
(2017); Çöltekin (2020a). Thus, a large number of comments had to be collected
and annotated in order to find a balanced number of offensive and non-
offensive instances. Therefore, from all comments collected in the data
acquisition step, a balanced dataset was selected, which contains 7,000
comments sorted into offensive and non-offensive classes, as displayed in
Table 6.

Table 6: Binary class: offensive x non-offensive Binary Class |  | Total
---
Non-Offensive | 3,500
Offensive | 3,500
Total | 7,000

Comments labeled as offensive were selected for a second annotation layer
according to the level of offense, which identified 1,678 comments as slightly
offensive, 1,044 as moderately offensive, and 778 as highly offensive. Results
are shown in Table 7

Table 7: Offensive Flaming-levels Flaming-level Classes |  | Total
---
Slightly Offensive | 1,678
Moderately Offensive | 1,044
Highly Offensive | 778
Total | 3,500

Furthermore, offensive comments were categorized according to the nine
discrimination groups in order to identify the comments that contain hate
speech, as presented in Table 8.

Table 8: Groups for Hate Speech Detection N. |  Hate Groups |  Total
---|---|---
1 |  Partyism |  496
2 |  Sexism |  97
3 |  Religion Intolerance |  47
4 |  Apology to Dictatorship |  32
5 |  Fat Phobia |  27
6 |  Homophobia |  17
7 |  Racism |  8
8 |  Antisemitism |  2
9 |  Xenophobia |  1

##  5 Evaluation

The entire process of annotation was carried out by three annotators. Each
comment was annotated by each one in order to guarantee the reliability of the
annotation process. Therefore, we computed inter-annotator agreement, using
three different metrics: simple inter-annotator, Cohen’s kappa, and Fleiss’
kappa, which are described below.

  * •

Simple inter-annotator agreement

Calculation of labels marked equally by the annotators. Peer agreement inter-
annotator over 0.80 is a good result for subjective tasks Vargas et al.
(2020).

We obtained, on average, 0.89 of agreement in binary-class annotation, and
0.80 of agreement in annotation of flaming-levels (Table 9, where each
annotator is represented by a capital letter), showing satisfactory results.

Table 9: Simple inter-annotator agreement Peer Agreement |  AB |  BC |  CA |  AVG
---|---|---|---|---
Binary class |  0.89 |  0.89 |  0.90 |  0.89
Flaming-levels |  0.79 |  0.77 |  0.84 |  0.80

When full agreement is expected, there is an expected decrease in agreement
rates, because it is considered a match in three evaluations and not by pairs.
In this evaluation, we obtained 0.84 of agreement in binary-class annotation,
and 0.70 of agreement in annotation of flaming-levels (Table 10), still
presenting satisfactory results Vargas et al. (2020).

Table 10: Full inter-annotator agreement (i.e., when the three annotators used the same label for the same comment) Full Agreement |  ABC
---|---
Binary class |  0.84
Flaming-levels |  0.70
  * •

Cohen’s kappa

Described by Equation 1; where po is the relative agreement observed between
raters and pe is the hypothetical probability of random agreement, it shows
the degree of agreement between two or more judges beyond what would be
expected by chance Cook (2005); Sim and Wright (2005).

$k=\frac{\rho o-\rho e}{1-\rho e}$ (1)

Kappa values range from 0 to 1, and in Table 11 there are possible
interpretations of these values Landis and Koch (1977) (although it is known
that there may be differences according to the subjectiveness of the evaluated
task).

Table 11: Kappa values and strength of agreement according to Landis and Koch (1977) Kappa values | Strength of agreement
---|---
0.00-0.20 | Slight
0.021-0.40 | Fair
0.41-0.60 | Moderate
0.61-0.80 | Substantial
>0.80 | Almost Perfect

In this metric, we obtained, on average, 0.75 of agreement in the binary-class
annotation and 0.47 of agreement in the annotation of offensive levels (Table
12). According to 11, binary-class kappa value is considered a Substantial
Agreement and flaming-levels kappa value is considered a Moderate Agreement.
These results are satisfactory, and the stratum difference empirically
reinforces a greater difficulty in activity of annotating levels of offense.

Table 12: Cohen’s kappa Peer Agreement |  AB |  BC |  CA |  AVG
---|---|---|---|---
Binary class |  0.76 |  0.72 |  0.76 |  0.75
Flaming-levels |  0.46 |  0.44 |  0.50 |  0.47
  * •

Fleiss’ kappa

It is an extension of Cohen’s kappa for the case where there are more than two
evaluators (or methods). This means that Fleiss’ kappa works for any number of
evaluators giving categorical ratings (with binary or nominal scale), for a
fixed number of items Fleiss (1971). The interpretation for the values of
Fleiss’ kappa also follows Table 11.

In Fleiss’ kappa evaluation, we obtained 0.74 of agreement in binary-class
annotation, and 0.46 of agreement in annotation of flaming-levels (Table 13),
maintaining the same levels of agreement presented by Cohen’s kappa. Our
Fleiss’ kappa value to binary class is in agreement with the literature,
mainly with OFFCOMBR-2, so far the only annotation for offensive comments on
the Brazilian web. OFFCOMBR-2 labeled 1,250 comments as offensive or not
offensive, annotated by three judges and presenting Fleiss’ Kappa equal to
0.71 de Pelle and Moreira (2017).

Table 13: Fleiss’ kappa Fleiss’ kappa |  ABC
---|---
Binary class |  0.74
Flaming-levels |  0.46

In addition to these evaluation metrics, two steps were taken to account for
hate speech groups: [i] the comments flagged by at least two annotators were
immediately inserted in the groups, and [ii] the comments flagged by only one
annotator passed a new checking, where the three annotators flagged the
comment as validated or not. When at least two annotators validated the
comment, it was added to the group.

##  6 Final Remark and Future Work

In this paper, we presented an annotation process and manually annotated
corpus of offensive language on social media. The proposed dataset was
collected from different accounts of political personalities on Instagram and
consists of randomly sampled 7,000 comments with 3,500 non-offensive and 3,500
offensive samples. Additionally, comments labeled as offensive were classified
according to three flaming-levels, named as highly offensive, moderately
offensive, and slightly offensive. High annotation agreement was obtained.
Finally, the proposed annotation process is also language and domain
independent (although it was evaluated for Brazilian Portuguese).

As future work, we intend to perform a corpus-based analysis and to create and
evaluate classifiers for offensive language and hate speech detection on
social media. We also aim at testing our annotation methodology for other
languages, in order to build a multilingual dataset for offensive language
detection and to develop multilingual detection methods.

## References

  * Albadi et al. (2018) N. Albadi, M. Kurdi, and S. Mishra. 2018.  Are they our brothers? analysis and detection of religious hate speech in the arabic twittersphere.  In _2018 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM)_ , pages 69–76.
  * Alfina et al. (2017) Ika Alfina, Rio Mulia, Mohamad Ivan Fanany, and Yudo Ekanata. 2017.  Hate speech detection in the indonesian language: A dataset and preliminary study.  In _2017 International Conference on Advanced Computer Science and Information Systems (ICACSIS)_ , pages 233–238. IEEE.
  * Altemeyer (1996) R.A. Altemeyer. 1996.  _The authoritarian specter_.  The authoritarian specter. Cambridge, MA: Harvard University.
  * Aragón et al. (2019) Mario Ezra Aragón, Miguel Ángel Álvarez Carmona, Manuel Montes-y-Gómez, Hugo Jair Escalante, Luis Villaseñor Pineda, and Daniela Moctezuma. 2019.  Overview of MEX-A3T at iberlef 2019: Authorship and aggressiveness analysis in mexican spanish tweets.  In _Proceedings of the Iberian Languages Evaluation Forum co-located with 35th Conference of the Spanish Society for Natural Language Processing, IberLEF@SEPLN 2019, Bilbao, Spain, September 24th, 2019_ , volume 2421 of _CEUR Workshop Proceedings_ , pages 478–494. CEUR-WS.org.
  * Basile et al. (2019) Valerio Basile, Cristina Bosco, Elisabetta Fersini, Debora Nozza, Viviana Patti, Francisco Manuel Rangel Pardo, Paolo Rosso, and Manuela Sanguinetti. 2019\.  SemEval-2019 task 5: Multilingual detection of hate speech against immigrants and women in Twitter.  In _Proceedings of the 13th International Workshop on Semantic Evaluation_ , pages 54–63, Minneapolis, Minnesota, USA. Association for Computational Linguistics.
  * Bretschneider and Peters (2017) Uwe Bretschneider and Ralf Peters. 2017.  Detecting offensive statements towards foreigners in social media.  In _Proceedings of the 50th Hawaii International Conference on System Sciences_ , pages 2213–2222, Waikoloa Village, Hawaii, USA.
  * Brugger (2007) Winfried Brugger. 2007.  Proibição ou proteção do discurso do ódio?: algumas observações sobre o direito alemão e o americano.  _Direito Público_ , 4(15):117–136.
  * Chung et al. (2019) Yi-Ling Chung, Elizaveta Kuzmenko, Serra Sinem Tekiroglu, and Marco Guerini. 2019\.  CONAN - COunter NArratives through nichesourcing: a multilingual dataset of responses to fight online hate speech.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 2819–2829, Florence, Italy. Association for Computational Linguistics.
  * Clair and Denis (2001) Matthew Clair and Jeffrey S Denis. 2001.  Sociology of racism.  _International Encyclopedia of the Social & Behavioral Sciences,_, 19(2nd edition).
  * Çöltekin (2020a) Çağrı Çöltekin. 2020a.  A corpus of turkish offensive language on social media.  In _Proceedings of the 12th Language Resources and Evaluation Conference_ , pages 6174–6184.
  * Çöltekin (2020b) Çağrı Çöltekin. 2020b.  A corpus of Turkish offensive language on social media.  In _Proceedings of the 12th Language Resources and Evaluation Conference_ , pages 6174–6184, Marseille, France. European Language Resources Association.
  * Cook (2005) Richard J Cook. 2005.  Kappa.  _Encyclopedia of biostatistics_ , 4.
  * Davidson et al. (2017) Thomas Davidson, Dana Warmsley, Michael W. Macy, and Ingmar Weber. 2017.  Automated hate speech detection and the problem of offensive language.  In _Proceedings of the Eleventh International Conference on Web and Social Media, ICWSM 2017, Montréal, Québec, Canada, May 15-18, 2017_ , pages 512–515. AAAI Press.
  * Delphy (2000) Christine Delphy. 2000.  Théories du patriarcat.  In _Dictionaire critique du féminisme_ , pages 141–146. PUF.
  * Fersini et al. (2018) Elisabetta Fersini, Paolo Rosso, and Maria Anzovino. 2018.  Overview of the task on automatic misogyny identification at ibereval 2018.  In _Proceedings of the Third Workshop on Evaluation of Human Language Technologies for Iberian Languages (IberEval 2018) co-located with 34th Conference of the Spanish Society for Natural Language Processing (SEPLN 2018), Sevilla, Spain, September 18th, 2018_ , volume 2150 of _CEUR Workshop Proceedings_ , pages 214–228. CEUR-WS.org.
  * Fleiss (1971) Joseph L Fleiss. 1971.  Measuring nominal scale agreement among many raters.  _Psychological bulletin_ , 76(5):378.
  * Fortuna and Nunes (2018) Paula Fortuna and Sérgio Nunes. 2018.  A survey on automatic detection of hate speech in text.  _ACM Comput. Surv._ , 51(4).
  * Fortuna et al. (2019) Paula Fortuna, João Rocha da Silva, Juan Soler-Company, Leo Wanner, and Sérgio Nunes. 2019.  A hierarchically-labeled Portuguese hate speech dataset.  In _Proceedings of the Third Workshop on Abusive Language Online_ , pages 94–104, Florence, Italy. Association for Computational Linguistics.
  * for Fundamental Rights FRA (2009) European Union Agency for Fundamental Rights FRA. 2009.  _Homophobia and Discrimination on Grounds of Sexual Orientation and Gender Identity in the EU Member States: Part II - The Social Situation_.  European Institute for Gender Equality.
  * Gao and Huang (2017) Lei Gao and Ruihong Huang. 2017.  Detecting online hate speech using context aware models.  In _Proceedings of the International Conference Recent Advances in Natural Language Processing, RANLP 2017_ , pages 260–266, Varna, Bulgaria. INCOMA Ltd.
  * Gao et al. (2020) Zhiwei Gao, Shuntaro Yada, Shoko Wakamiya, and Eiji Aramaki. 2020.  Offensive language detection on video live streaming chat.  In _Proceedings of the 28th International Conference on Computational Linguistics_ , pages 1936–1940, Barcelona, Spain (Online). International Committee on Computational Linguistics.
  * de Gibert et al. (2018) Ona de Gibert, Naiara Perez, Aitor García-Pablos, and Montse Cuadros. 2018\.  Hate speech dataset from a white supremacy forum.  In _Proceedings of the 2nd Workshop on Abusive Language Online (ALW2)_ , pages 11–20, Brussels, Belgium. Association for Computational Linguistics.
  * Golbeck et al. (2017) Jennifer Golbeck, Zahra Ashktorab, Rashad O. Banjo, Alexandra Berlinger, Siddharth Bhagwan, Cody Buntain, Paul Cheakalos, Alicia A. Geller, Quint Gergory, Rajesh Kumar Gnanasekaran, Raja Rajan Gunasekaran, Kelly M. Hoffman, Jenny Hottle, Vichita Jienjitlert, Shivika Khare, Ryan Lau, Marianna J. Martindale, Shalmali Naik, Heather L. Nixon, Piyush Ramachandran, Kristine M. Rogers, Lisa Rogers, Meghna Sardana Sarin, Gaurav Shahane, Jayanee Thanki, Priyanka Vengataraman, Zijian Wan, and Derek Michael Wu. 2017.  A large labeled corpus for online harassment research.  In _Proceedings of the 2017 ACM on Web Science Conference_ , WebSci ’17, page 229–233, New York, NY, USA. Association for Computing Machinery.
  * Guimarães et al. (2020) Samuel S. Guimarães, Julio C. S. Reis, Filipe N. Ribeiro, and Fabrício Benevenuto. 2020.  _Characterizing Toxicity on Facebook Comments in Brazil_, page 253–260. Association for Computing Machinery, New York, NY, USA.
  * Hasanuzzaman et al. (2017) Mohammed Hasanuzzaman, Gaël Dias, and Andy Way. 2017.  Demographic word embeddings for racism detection on Twitter.  In _Proceedings of the Eighth International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 926–936, Taipei, Taiwan. Asian Federation of Natural Language Processing.
  * Ibrohim and Budi (2018) Muhammad Okky Ibrohim and Indra Budi. 2018.  A dataset and preliminaries study for abusive language detection in indonesian social media.  _Procedia Computer Science_ , 135:222–229.  3rd International Conference on Computer Science and Computational Intelligence, ICCSCI 2018 ; Conference date: 07-09-2018 Through 08-09-2018.
  * Jha and Mamidi (2017) Akshita Jha and Radhika Mamidi. 2017.  When does a compliment become sexist? analysis and classification of ambivalent sexism using twitter data.  In _Proceedings of the Second Workshop on NLP and Computational Social Science_ , pages 7–16, Vancouver, Canada. Association for Computational Linguistics.
  * Jikeli et al. (2019) Gunther Jikeli, Damir Cavar, and Daniel Miehling. 2019.  Annotating antisemitic online content. towards an applicable definition of antisemitism.  _CoRR_ , abs/1910.01214.
  * Landis and Koch (1977) J Richard Landis and Gary G Koch. 1977.  The measurement of observer agreement for categorical data.  _Biometrics_ , pages 159–174.
  * Leite et al. (2020) Joao Augusto Leite, Diego F. Silva, Kalina Bontcheva, and Carolina Scarton. 2020\.  Toxic language detection in social media for brazilian portuguese: New dataset and multilingual analysis.  In _Proceedings of the 1st Conference of the Asia-Pacific Chapter of the Association for Computational Linguistics and the 10th International Joint Conference on Natural Language Processing, AACL/IJCNLP 2020, Suzhou, China, December 4-7, 2020_ , pages 914–924. Association for Computational Linguistics.
  * Liu and Forss (2015) Shuhua Liu and Thomas Forss. 2015.  Text classification models for web content filtering and online safety.  In _IEEE International Conference on Data Mining Workshop, ICDMW 2015, Atlantic City, NJ, USA, November 14-17, 2015_ , pages 961–968. IEEE Computer Society.
  * Ljubešić et al. (2018) Nikola Ljubešić, Tomaž Erjavec, and Darja Fišer. 2018.  Datasets of Slovene and Croatian moderated news comments.  In _Proceedings of the 2nd Workshop on Abusive Language Online (ALW2)_ , pages 124–131, Brussels, Belgium. Association for Computational Linguistics.
  * Mesquita (2018) Lígia Mesquita. 2018.  Denúncias de discurso de ódio online dispararam no 2º turno das eleições.  _BBC_ , 1.
  * Mubarak et al. (2017) Hamdy Mubarak, Kareem Darwish, and Walid Magdy. 2017.  Abusive language detection on arabic social media.  In _Proceedings of the first workshop on abusive language online_ , pages 52–56.
  * Nockleby (2000) John T. Nockleby. 2000.  Hate speech.  In _Encyclopedia of the American Constitution_ , page 1277–1279, New York, USA. Macmillan.
  * Oliveira (2019) Leila Maria Oliveira. 2019.  _Imigrantes, xenofobia e racismo: uma análise de conflitos em escolas municipais de São Paulo_.  Ph.D. thesis, Programa de Pós-Graduação em Educação, Pontifícia Universidade Católica de São Paulo.
  * Ousidhoum et al. (2019) Nedjma Ousidhoum, Zizheng Lin, Hongming Zhang, Yangqiu Song, and Dit-Yan Yeung. 2019\.  Multilingual and multi-aspect hate speech analysis.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 4675–4684, Hong Kong, China. Association for Computational Linguistics.
  * Pavlopoulos et al. (2017) John Pavlopoulos, Prodromos Malakasiotis, and Ion Androutsopoulos. 2017.  Deep learning for user comment moderation.  In _Proceedings of the First Workshop on Abusive Language Online_ , pages 25–35, Vancouver, BC, Canada. Association for Computational Linguistics.
  * de Pelle and Moreira (2017) Rogers de Pelle and Viviane Moreira. 2017.  Offensive comments in the brazilian web: a dataset and baseline results.  In _Anais do VI Brazilian Workshop on Social Network Analysis and Mining_ , Porto Alegre, RS, Brasil. SBC.
  * Pitenis et al. (2020) Zesis Pitenis, Marcos Zampieri, and Tharindu Ranasinghe. 2020.  Offensive language identification in Greek.  In _Proceedings of the 12th Language Resources and Evaluation Conference_ , pages 5113–5119, Marseille, France. European Language Resources Association.
  * Ptaszynski et al. (2019) Michal Ptaszynski, Agata Pieciukiewicz, and Paweł Dybała. 2019.  Results of the poleval 2019 shared task 6 : first dataset and open shared task for automatic cyberbullying detection in polish twitter.  In _Proceedings of the PolEval 2019 Workshop_ , pages 89–110. Institute of Computer Sciences. Polish Academy of Sciences, Warszawa.
  * Robinson et al. (1993) Beatrice “Bean” E Robinson, Lane C Bacon, and Julia O’reilly. 1993.  Fat phobia: Measuring, understanding, and changing anti-fat attitudes.  _International Journal of Eating Disorders_ , 14(4):467–480.
  * Rosa et al. (2019) Hugo Rosa, Nádia Pereira, Ricardo Ribeiro, Paula Costa Ferreira, João Paulo Carvalho, Sofia Oliveira, Luísa Coheur, Paula Paulino, AM Veiga Simão, and Isabel Trancoso. 2019.  Automatic cyberbullying detection: A systematic review.  _Computers in Human Behavior_ , 93:333–345.
  * Sanguinetti et al. (2018) Manuela Sanguinetti, Fabio Poletto, Cristina Bosco, Viviana Patti, and Marco Stranisci. 2018.  An Italian Twitter corpus of hate speech against immigrants.  In _Proceedings of the Eleventh International Conference on Language Resources and Evaluation (LREC 2018)_ , Miyazaki, Japan. European Language Resources Association (ELRA).
  * Schmidt and Wiegand (2017) Anna Schmidt and Michael Wiegand. 2017.  A survey on hate speech detection using natural language processing.  In _Proceedings of the Fifth International Workshop on Natural Language Processing for Social Media_ , pages 1–10, Valencia, Spain. Association for Computational Linguistics.
  * Sim and Wright (2005) Julius Sim and Chris C Wright. 2005.  The kappa statistic in reliability studies: use, interpretation, and sample size requirements.  _Physical therapy_ , 85(3):257–268.
  * Steimel et al. (2019) Kenneth Steimel, Daniel Dakota, Yue Chen, and Sandra Kübler. 2019.  Investigating multilingual abusive language detection: A cautionary tale.  In _Proceedings of the International Conference on Recent Advances in Natural Language Processing (RANLP 2019)_ , pages 1151–1160, Varna, Bulgaria. INCOMA Ltd.
  * Sunstein (2016) Cass R. Sunstein. 2016.  Partyism.  _University of Chicago Legal Forum_ , 2016(2).
  * Van Hee et al. (2015) Cynthia Van Hee, Els Lefever, Ben Verhoeven, Julie Mennes, Bart Desmet, Guy De Pauw, Walter Daelemans, and Veronique Hoste. 2015.  Detection and fine-grained classification of cyberbullying events.  In _Proceedings of the International Conference Recent Advances in Natural Language Processing_ , pages 672–680, Hissar, Bulgaria. INCOMA Ltd. Shoumen, BULGARIA.
  * Vargas et al. (2020) Francielle Alves Vargas, Rodolfo Sanches Saraiva Dos Santos, and Pedro Regattieri Rocha. 2020.  Identifying fine-grained opinion and classifying polarity on coronavirus pandemic.  In _Proceedings of the 9th Brazilian Conference on Intelligent Systems_ , pages 511–520, Rio Grande, RS, Brazil.
  * Walby (1990) Sylvia Walby. 1990.  _Theorzsing Patriarchy_.  Brasil BlackWell: Oxford, London.
  * Waseem and Hovy (2016) Zeerak Waseem and Dirk Hovy. 2016.  Hateful symbols or hateful people? predictive features for hate speech detection on Twitter.  In _Proceedings of the NAACL Student Research Workshop_ , pages 88–93, San Diego, California. Association for Computational Linguistics.
  * Westwood et al. (2018) Sean J. Westwood, Shanto Iyengar, Stefaan Walgrave, Rafael Leonisio, Luis Miller, and Oliver Strijbis. 2018.  The tie that divides: Cross-national evidence of the primacy of partyism.  _European Journal of Political Research_ , 57:333–354.
  * Wilson (1999) W.J. Wilson. 1999.  _The Bridge over the Racial Divide: Rising Inequality and Coalition Politics_.  University of California Press, Berkeley, CA.


# On several properties of uniformly optimal search plans

Liang Hong111Liang Hong is an Associate Professor in the Department of
Mathematical Sciences, The University of Texas at Dallas, 800 West Campbell
Road, Richardson, TX 75080, USA. Tel.: 972-883-2161. Email address:
<EMAIL_ADDRESS>
###### Abstract

The uniformly optimal search plan is a cornerstone of the optimal search
theory. It is well-known that when the target distribution is circular normal
and the detection function is exponential, the uniformly search plan has
several desirable properties. This article establishes that these properties
hold for any continuous target distribution. Since there is no true target
distribution, our results provide useful information to the search team when
they need to choose a non-circular normal target distribution in a real-world
search mission.

_Keywords and phrases:_ Bayesian analysis; explainable analytics; naval
operations research; maritime search and rescue; stationary target.

##  1 Introduction

The theory of optimal search for a stationary target was first developed by
Koopman (1946, 1956a, b, c) and later refined by several authors such as Stone
and Stanshine (1971) and Stone (1973, 1975, 1976). It has been successfully
applied in both civil and military search missions; see, for instance,
Richardson and Stone (1971), Richardson et al. (1980), Stone (1992), Kratzke
et al. (2010), and Stone et al. (2014). While recent research mainly focuses
on moving targets (e.g. Washburn 2014, Stone et al. 2016), the optimal search
theory for a stationary target is still developing, as evidenced by Kadane
(2015) and Clarkson et al. (2020). More importantly, its immediate or
potential value never fades over time in view of several high-profile civil
and military accidents in the last decade, such as the vanishing of AF 447 on
June 1, 2009, the disappearance of Malaysia Airlines Flight 370 in 2014, the
loss of Indonesia’s KRI Nanggala submarine in April 2021, and the collision of
the USS Connecticut with a seamount in South China Sea in 2021. In addition,
the optimal search theory for moving targets is based upon its counterpart for
stationary targets. Thus, the optimal search theory for stationary targets is
still relevant and important for both theory and practice.

Each search has a budget. Koopman (1956c) first investigated maximizing the
probability of finding the target once the budget has been exhausted. In the
extant literature, the uniformly optimal search plan plays a major role in the
optimal search theory. A uniformly optimal search plan is desirable because
(a) it maximizes the amount of budget that could be saved (by making the
search more likely to end early) and (b) it will still maximize the
probability of detection if the budget is unexpectedly cut halfway through the
search. Arkin (1964) first derived sufficient conditions for existence of a
uniformly optimal search policy in the Euclidean search space
$\mathbb{R}^{n}$. This work was extended and generalized by other authors,
such as Stone (1973, 1975, 1976).

In addition, it is known that when the target distribution, which encodes
belief about the target’s location, is circular normal (i.e., a bivariate
normal distribution with circular symmetry), the detection function is
exponential, and the cost is proportional to effort, the uniformly optimal
search plan has some appealing properties; see Section 2 for more details.
Under the assumption that the cost is proportional to allocation, this article
shows that these properties hold for an arbitrary continuous target
distribution when the detection function is exponential (some of these
properties also hold when the detection function is regular). It is important
to note that a major challenge in a search problem is the uncertainty of the
target location. A target distribution is chosen to account for this
uncertainty in terms of probabilities. Therefore, the target distribution is
always subjective and there is no true target distribution.

As pointed out in Soza and USCG (1996), the circular normal distribution has
been widely employed as the target distribution in the theory of optimal
search. This seems to result from the mathematical convenience it provides;
that is, many key quantities in the prior literature will admit a closed-form
formula if the target distribution is taken to be circular normal. However,
the target distribution is subjective, and there is no reason, theoretically
or practically, to restrict our choices to the circular normal distribution.
The search team should honestly encode its knowledge and expertise into a
target distribution and proceed from there. Choosing a circular normal target
distribution for mathematical convenience will reduce the efficiency of the
search as well as the likelihood of success. For example, if the location a
ship sank is known, then a circular normal distribution centered at that point
could be an appropriate starting choice. But if the current is known to drift
in a certain complex pattern, then one must incorporate this prior information
into the target distribution by skewing the circular normal. Hence, it is
crucial to investigate whether the aforementioned properties will still hold
when the target distribution is an arbitrary continuous one. Therefore, our
results offer important insights for any search team when they need to employ
a non-circular normal target distribution in practice.

The remainder of the article is organized as follows. In Section 2, we set the
scene by reviewing the optimal search model and the uniformly optimal search
plan. Next, in Section 3, we establish four general properties of the
uniformly optimal search plan. In Section 4 we provide a numerical example to
illustrate our key results. Finally, we conclude the article with some remarks
in Section 5.

##  2 Model setup and notation

We consider the problem of searching for a stationary target where the exact
target location $x$ is unknown. The Bayesian approach naturally fits here.
Specifically, based on available information and professional judgment, we
construct a _target distribution_ for $x$. Let $\Pi$ be the (cumulative)
distribution function of the target distribution. The support of $\Pi$ is
often called the _possibility area_ and is denoted as $X$; it is the area, in
our assessment, which contains the target. Mathematically, $X$ is a subset of
the $n$-dimensional Euclidean space $\mathbb{R}^{n}$. In most real-world
applications, we take $n=2$. Intuitively, $\Pi$ reflects our knowledge prior
to the search and, at the same time, accounts for our uncertainty about the
target location. Throughout, we assume the target is stationary and we only
consider the case where the target distribution is continuous with a
probability density function $\pi$.

To plan a search, we must decide how to distribute the effort in $X$. To this
end, we let $\mathbb{R}_{+}\equiv[0,\infty)$ and call a function
$f:X\rightarrow\mathbb{R}_{+}$ an _allocation_ on $X$ if $\int_{A}f(x)dx$
equals the amount of effort put in $A$ where $A$ is any subset of $X$. Since
detection is rarely perfect in any search, we define the _detection function_
$d:X\times\mathbb{R}_{+}\rightarrow[0,1]$ to be a function such that $d(x,y)$
denotes the _conditional_ probability that the target is detected if the
allocation density equals $y$ at $x$ given that the target is located at $x$.
Given an allocation $f$ on $X$, the _probability of detection_ , denoted as
$P[f]$, is given by

$P[f]=\int_{X}d(x,f(x))\pi(x)dx.$

The _cost function_ $c(x,y):X\times\mathbb{R}_{+}\rightarrow\mathbb{R}_{+}$
stands for the cost density of applying allocation density $y$ at $x$. For a
given allocation $f$ on $X$, the cost resulting from $f$, denoted as $C[f]$,
is given by

$C[f]=\int_{X}c(x,f(x))dx.$

We assume $c(x,y)=y$ throughout this paper. We define a _search plan_ on $X$
to be a function $\varphi:X\times\mathbb{R}_{+}\rightarrow\mathbb{R}_{+}$ such
that

  1. (i)

$\varphi(\cdot,t)$ is an allocation on $X$ for all $t\geq 0$;

  2. (ii)

$\varphi(x,\cdot)$ is an increasing function for all $x\in X$.

Property (i) says that $\varphi(\cdot,t)$ is an allocation in the first $t$
time units; Property (ii) ensures that the allocations must “build on each
other” as time progresses (i.e., efforts cannot be “undone”).

In practice, the budget for conducting a search is always limited. For a given
time $T>0$, let $E(T)>0$ be the search budget available by time $T$. That is,
$E(T)$ is the effort available by $T$. Throughout, we assume the search is
conducted at speed $v$ using a sensor with a sweep width $W$ and the time
available for the search is $T>0$. Hence, $E(T)=WvT$. Intuitively, the “best”
search plan $\varphi^{\star}$, if it exists, should be the one that maximizes
the probability of detection at each time $t\geq 0$, subject to the constraint
$C[\varphi^{\star}]\leq E(T)$. In the current literature, such a search plan
is called a _uniformly optimal search plan_. Precisely, we define the
_cumulative effort function_ $E$ to be a non-negative function with domain
$\mathbb{R}_{+}$ where $E(t)$ symbolizes the effort available by time $t$. We
always assume that $E$ is increasing. Let $\Phi(E)$ denote the class of search
plans $\varphi$ such that

$\int_{X}\varphi(x,t)dx=E(t),\quad\text{for all $t\geq 0$}.$

A search plan $\varphi^{\star}\in\Phi(E)$ is said to be _uniformly optimal
with $\Phi(E)$_ if

$P[\varphi^{\star}(\cdot,t)]=\max\\{P[\varphi(\cdot,t)]\mid\varphi\in\Phi(E)\\}\quad\text{for
all $t\geq 0$}.$

Example 2.2.9 in Stone (1975) shows that a uniformly optimal search plan does
not always exist. However, Stone (1976) establishes that there is a uniformly
optimal plan if the detection function $d(x,\cdot)$ is increasing and right-
continuous for each $x\in X$. Based on the key results in Everett (1963), a
semi-closed form of the uniformly optimal plan can be derived under mild
conditions using the Lagrange multiplier; see Chapter 2 of Stone (1975) or
Chapter 5 of Washburn (2014) for details. In particular, we have the following
theorem. The detection function is said to be regular if $d(x,0)=0$ and
$\partial d(x,y)/\partial y$ is continuous, positive, and strictly decreasing
for all $x\in X$.

######  Theorem 2.1 (Stone 1975).

If the cost function takes the form $c(x,y)=y$ for all $y\geq 0$ and $x\in X$
and the detection function is regular, a uniformly optimal search plan
$\varphi^{\star}$ for budget $E(T)$ can be found for any target distribution
as follows. Put

$q_{x}(y)=\pi(x)\frac{\partial}{\partial y}d(x,y),\quad x\in X\text{ and
$y\geq 0$},$

$q^{-1}_{x}(\lambda)=\left\\{\begin{array}[]{ll}\text{the inverse function of
$q_{x}(y)$ evaluated at $\lambda$},&\hbox{if $0<\lambda\leq q_{x}(0)$,}\\\
0,&\hbox{if $\lambda>q_{x}(0)$,}\end{array}\right.$

and

$Q(\lambda)=\int_{X}q_{x}^{-1}(\lambda)dx,\quad x\in X.$

Then a uniformly optimal search plan for budget $B$ is given by
$\varphi^{\star}(x,T)=q_{x}^{-1}(Q^{-1}(E(T)))$ where $Q^{-1}$ is the inverse
function of $Q$.

Here $q_{x}(y)$ takes into account the future change in detection and the
prior probability. Intuitively, it represents the “attractiveness” of
allocating more effort to the location $x$ given that $y$ amount of effort has
already been allocated there, and $q^{-1}_{x}(\lambda)$ is the amount of
allocation already required at $x$ so the attractiveness of more allocation is
$\lambda$, or $0$ if the attractiveness is less than $\lambda$ before any
allocation at $x$. The idea behind Theorem 2.1 is as follows: distribute
search effort by gradually decreasing the minimum attractiveness of $\lambda$
that is allowed into the allocation, hence distributing effort is proportional
to the most attractive areas at the current moment. Stop when $\lambda$ falls
enough so that the total allocation has reached the budget $E$. This stopping
is monitored by the function $Q$ where $Q(\lambda)$ is the total allocation if
every location $x$ in the search space is allocated effort until the
attractiveness of $q_{x}(y)$ of allocating more effort there falls to
$\lambda$.

##  3 Several general properties of uniformly optimal search plans

We first recall a few known facts (e.g. Stone 1975, Chapter 2). If the target
distribution is circular normal, i.e.,

$\pi(x_{1},x_{2})=\frac{1}{2\pi\sigma^{2}}e^{-\frac{x_{1}^{2}+x_{2}^{2}}{2\sigma^{2}}},\quad(x_{1},x_{2})\in
X=\mathbb{R}^{2},$

and the detection function is exponential, i.e., $d(x,y)=1-e^{-y}$ for all
$x\in X$ and $y\geq 0$, then the uniformly optimal plan exists and takes the
form (in polar coordinates)

$\varphi^{\star}((r,\theta),T)=\left\\{\begin{array}[]{ll}H\sqrt{T}-\frac{r^{2}}{2\sigma^{2}},&\hbox{if
$0\leq r\leq R(T)$,}\\\ 0,&\hbox{if $r>R(T)$,}\end{array}\right.$

where $R^{2}(t)=2\sigma^{2}H\sqrt{t}$ and $H=\sqrt{Wv/\pi\sigma^{2}}$. Note
that here the allocation at a point depends only on $r$ (not on $\theta$) and
that the area assigned non-zero allocation is a circle whose radius grows with
$T$. These two properties result from the fact the target distribution is
circular normal, but they do not hold for an arbitrary target distribution.

Moreover, the probability of detection is given by

$P[\varphi^{\star}(\cdot,T)]=1-(1+H\sqrt{T})e^{-H\sqrt{T}},\quad T\geq 0.$

Let $\pi_{T}$ be the density of the posterior probability distribution for the
target location given that the target has not been found by time $T$. Then

$\pi_{T}((r,\theta))=\left\\{\begin{array}[]{ll}\frac{1}{2\pi\sigma^{2}(1+H\sqrt{T})},&\hbox{if
$0\leq r\leq R(T)$,}\\\
\frac{\exp\\{-\frac{r^{2}}{2\sigma^{2}}+H\sqrt{T}\\}}{2\pi\sigma^{2}(1+H\sqrt{T})},&\hbox{if
$r>R(T)$.}\end{array}\right.$

It is easy to verify that this piecewise-defined function is continuous. Also,
the definition of $R(T)$ shows that
$e^{-\frac{r^{2}}{2\sigma^{2}}+H\sqrt{T}}<1$ for $r>R(T)$. Thus, the second
piece of $\pi_{T}$ is no greater than the first piece.

For $t\geq 0$, define the _additional effort density_ that accumulates at
point $(r,\theta)$ in the time interval $[T,T+t]$ as

$\varphi^{\star}_{T}((r,\theta),t)=\varphi^{\star}((r,\theta),T+t)-\varphi^{\star}((r,\theta),T),\quad
x\in X\text{ and $t\geq 0$}.$

Then

$\varphi_{T}^{\star}((r,\theta),t)=\left\\{\begin{array}[]{ll}H(\sqrt{T+t}-\sqrt{T}),&\hbox{if
$0\leq r\leq R(T)$,}\\\ H\sqrt{T+t}-\frac{r^{2}}{2\sigma^{2}},&\hbox{if
$R(T)<r\leq R(T+t)$,}\\\ 0,&\hbox{if $r>R(T+t)$.}\end{array}\right.$

It is clear that this uniformly optimal search plan has the following nice
properties:

  1. (i)

The detection probability $P[\varphi^{\star}(x,T)]$ goes to $1$ as time
$T\rightarrow\infty$;

  2. (ii)

the posterior density $\pi_{T}$ for the target location given that the target
has not been found by time $T$ is constant inside a circle of radius $R(T)$
around the origin but not constant outside this circle;

  3. (iii)

the posterior density $\pi_{T}$ is flattening and spreading as $T$ increases
and $\pi_{T}$ vanishes as $T\rightarrow\infty$;

  4. (iv)

the additional effort that accumulates in the interval $[T,T+t]$ will be
placed uniformly over the area that has been searched by time $T$.

Do these properties still hold when the target distribution is not circular
normal? We give an affirmative answer to each of them. Intuitively, Property
(i) says that if we keep searching, we will eventually find the target using
the uniformly optimal search plan. The next theorem shows that this property
holds for an arbitrary continuous target distribution when the detection
function is regular.

######  Theorem 3.1.

If the target distribution is continuous with a probability density function
$\pi$, the detection function $d$ is regular, and
$\lim_{T\rightarrow\infty}E(T)=\infty$, then
$\lim_{T\rightarrow\infty}P[\varphi^{\star}(\cdot,T)]=1$.

###### Proof.

By Theorem 2.1, a uniformly optimal search plan $\varphi^{\star}$ exists and
is given by $\varphi^{\star}(x,T)=q_{x}^{-1}(Q^{-1}(E(T)))$. Therefore, the
probability of detection is given by

$P[\varphi^{\star}(\cdot,T)]=\int_{X}d(x,\varphi^{\star}(x,T))\pi(x)dx=\int_{X}d(x,q_{x}^{-1}(Q^{-1}(E(T))))\pi(x)dx.$

Since $Q$ is continuous on $(0,\infty)$ and strictly decreasing on the
interval $(0,\sup\\{\lambda\mid Q(\lambda)>0\\})$, $Q^{-1}$ is continuous and
strictly decreasing on $(0,\infty)$. In addition, note that $q_{x}^{-1}$ is
continuous and strictly decreasing on $(0,q_{x}(0)]$. Therefore,
$q_{x}^{-1}(Q^{-1})$ is continuous and strictly increasing on $(0,\infty)$.
Also, it is known that $\lim_{\lambda\rightarrow\infty}Q^{-1}(\lambda)=0$;
see, for example, Section 2.2 of Stone (1975). This, in view of the assumption
that $d$ is regular, implies that
$\lim_{\lambda\rightarrow\infty}q_{x}^{-1}(Q^{-1}(\lambda))=\infty$. Since
$|d(x,y)|\leq 1$ for all $x\in X$ and $y\geq 0$, the Dominated Convergence
Theorem implies

$\displaystyle 1\geq\lim_{T\rightarrow\infty}P[\varphi^{\star}(\cdot,T)]$
$\displaystyle=$
$\displaystyle\lim_{T\rightarrow\infty}\int_{X}d(x,q_{x}^{-1}(Q^{-1}(E(T))))\pi(x)dx$
$\displaystyle=$
$\displaystyle\int_{X}\lim_{T\rightarrow\infty}d(x,q_{x}^{-1}(Q^{-1}(E(T))))\pi(x)dx$
$\displaystyle=$
$\displaystyle\int_{X}d(x,q_{x}^{-1}(Q^{-1}(\lim_{T\rightarrow\infty}E(T))))\pi(x)dx$
$\displaystyle=$ $\displaystyle 1.$

It follows that $\lim_{T\rightarrow\infty}P[\varphi^{\star}(\cdot,T)]=1$. ∎

To investigate Property (ii) for an arbitrary continuous target distribution,
we note that the posterior density $\pi_{T}$ of the target location given that
the target has not been found by time $T$ can be written as

$\pi_{T}(x)=\frac{[1-d(x,\varphi^{\star}(x,T))]\pi(x)}{\int_{X}[1-d(x,\varphi^{\star}(x,T))]\pi(x)dx}=\frac{[1-d(x,q_{x}^{-1}(Q^{-1}(E(T))))]\pi(x)}{\int_{X}[1-d(x,q_{x}^{-1}(Q^{-1}(E(T))))]\pi(x)dx}.$

The denominator of $\pi_{T}$ is constant because $x$ is integrated out. For
the circular normal case, the condition $r\leq R(T)$ is equivalent to the
condition $Q^{-1}(E(T))\leq q_{x}(0)$. Therefore, we need to examine two
cases: (I) $Q^{-1}(E(T))>q_{x}(0)$ and (II) $Q^{-1}(E(T))\leq q_{x}(0)$. Here
$q_{x}(0)$ is the attractiveness of allocating a first bit of effort to
location $x$, while $Q^{-1}(E(T))$ is the “baseline” of attractiveness to get
into the allocation at time $T$. If $Q^{-1}(E(T))>q_{x}(0)$, allocation at $x$
never reaches this threshold, so $x$ is never allocated any search effort
before time $T$. In Case (I), the numerator of $\pi_{T}$ equals
$[1-d(x,0)]\pi(x)=\pi(x)$ if the detection function is regular. Therefore, the
numerator of $\pi_{T}$ is not constant unless the target distribution is
uniform. For Case (II), the next theorem demonstrates that the numerator of
$\pi_{T}$ (hence $\pi_{T}$ itself) is constant in the area $D_{T}=\\{x\mid
Q^{-1}(E(T))\leq q_{x}(0)\\}$ if the detection function is exponential.

######  Theorem 3.2.

Suppose the target distribution is continuous with a probability density
function $\pi$.

  1. (i)

If the detection function is of the form $d(x,y)=1-e^{-\alpha y}$ for all
$x\in X$ and $y\geq 0$ where $\alpha>0$, then the posterior density $\pi_{T}$
is constant and equals $Q^{-1}(E(T))$ in the area $D_{T}=\\{x\mid
Q^{-1}(E(T))\leq q_{x}(0)\\}$.

  2. (ii)

If the detection function is regular and the target distribution is non-
uniform, then $\pi_{T}$ is not constant outside $D_{T}$.

###### Proof.

The second statement follows from the above discussion. Thus, it remains to
establish the first statement. In this case, we have
$q_{x}(y)=\alpha\pi(x)e^{-\alpha y}$ and

$q_{x}^{-1}(\lambda)=\left\\{\begin{array}[]{ll}[-\ln\lambda+\ln(\alpha\pi(x))]/\alpha,&\hbox{if
$0<\lambda\leq q_{x}(0)$,}\\\ 0,&\hbox{$\lambda>q_{x}(0)$.}\end{array}\right.$

Therefore, the uniformly optimal plan is given by

$\varphi^{\star}(x,T)=\left\\{\begin{array}[]{ll}[-\ln(Q^{-1}(E(T)))+\ln(\alpha\pi(x))]/\alpha,&\hbox{if
$0<Q^{-1}(E(T))\leq q_{x}(0)$,}\\\
0,&\hbox{$Q^{-1}(E(T))>q_{x}(0)$.}\end{array}\right.$

If $0<Q^{-1}(E(T))\leq q_{x}(0)$, the numerator of $\pi_{T}$ equals

$\displaystyle[1-d(x,\varphi^{\star}(x,T))]\pi(x)$ $\displaystyle=$
$\displaystyle\exp\\{\ln(Q^{-1}(E(T)))-\ln(\alpha\pi(x))\\}\pi(x)$
$\displaystyle=$ $\displaystyle Q^{-1}(E(T))/\alpha.$

∎

Remark. Statement (i) cannot be extended to the case where the detection
function is regular. To see this, let $d(x,y)=1-e^{-x^{2}y}$. Then $d(x,y)$ is
regular, $q_{x}(y)=\pi(x)x^{2}e^{-x^{2}y}$, and

$q_{x}^{-1}(\lambda)=\left\\{\begin{array}[]{ll}-\frac{1}{x^{2}}\ln\left[\frac{\lambda}{x^{2}\pi(x)}\right],&\hbox{if
$0<\lambda\leq q_{x}(0)$,}\\\ 0,&\hbox{otherwise.}\end{array}\right.$

Thus, when $x\in D_{T}$, the numerator of $\pi_{T}$ equals

$\displaystyle
1-\left[1-\exp\left\\{-x^{2}\left(-\frac{1}{x^{2}}\ln\left[\frac{U^{-1}(E(T))}{x^{2}\pi(x)}\right]\right)\right\\}\pi(x)\right]=U^{-1}(E(T))/x^{2},$

which depends on $x$.

When the target distribution is circular normal, Property (iii) shows that
$\pi_{T}$ is flattening and spreading as $T$ increases and
$\lim_{T\rightarrow\infty}\pi_{T}(x)=0$ for all $x\in X$. In fact, this
phenomenon also holds for any continuous target distribution. Let $\phi$
denote the empty set and $\mu$ stand for the Lebesgue measure on
$\mathbb{R}^{n}$.

######  Theorem 3.3.

If the possibility area $X$ satisfies $\mu(X)=\infty$, the target distribution
is continuous with a probability density function $\pi$, and the detection
function takes the form $d(x,y)=1-e^{-\alpha y}$ for all $x\in X$ and $y\geq
0$ where $\alpha>0$, then $\pi_{T}$ is flattening and spreading as $T$
increases and $\lim_{T\rightarrow}\pi_{T}(x)=0$ for all $x\in X$.

###### Proof.

Put $D_{T}=\\{x\in X\mid Q^{-1}(E(T))\leq q_{x}(0)\\}$. Then the proof of
Theorem 3.2 implies $q_{x}(0)=\alpha\pi(x)$ and

$\displaystyle\pi_{T}(x)$ $\displaystyle=$
$\displaystyle\frac{[1-d(x,\varphi^{\star}(x,T))]\pi(x)}{\int_{X}[1-d(x,\varphi^{\star}(x,T))]\pi(x)dx}=\left\\{\begin{array}[]{ll}\frac{Q^{-1}(E(T))/\alpha}{\int_{X}[1-d(x,\varphi^{\star}(x,T))]\pi(x)dx},&\hbox{if
$x\in D_{T}$,}\\\
\frac{\pi(x)}{\int_{X}[1-d(x,\varphi^{\star}(x,T))]\pi(x)dx},&\hbox{$x\in
D_{T}^{c}$.}\end{array}\right.$ (3)

Thus, when $x\in D_{T}^{c}$, we have $Q^{-1}(E(T))/\alpha<\pi(x)$, showing
that the part of $\pi_{T}$ on $D_{T}$ is no greater than the part of $\pi_{T}$
on $D_{T}^{c}$. Since $D^{c}_{T}=\\{x\in X\mid
Q^{-1}(E(T))>q_{x}(0)\\}\rightarrow\phi$ as $T\rightarrow\infty$, it suffices
to show that $\lim_{T\rightarrow\infty}\pi_{T}(x)=0$ for $x\in D_{T}$. It
follows from the proof of Theorem 3.2 that

$[1-d(x,\varphi^{\star}(x,T))]\pi(x)=\left\\{\begin{array}[]{ll}Q^{-1}(E(T))/\alpha,&\hbox{if
$x\in D_{T}$,}\\\ 1,&\hbox{$x\in D_{T}^{c}$.}\end{array}\right.$

Therefore, for $x\in D_{T}$, we have

$\displaystyle 0\leq\pi_{T}(x)$ $\displaystyle=$
$\displaystyle\frac{Q^{-1}(E(T))/\alpha}{\int_{D_{T}}Q^{-1}(E(T))/\alpha
dx+\int_{D_{T}^{c}}\pi(x)dx}$ $\displaystyle\leq$
$\displaystyle\frac{Q^{-1}(E(T))}{\int_{D_{T}}Q^{-1}(E(T))dx}=\frac{Q^{-1}(E(T))}{Q^{-1}(E(T))\int_{D_{T}}1\
dx}=\frac{1}{\mu(D_{T})}.$

To finish the proof, it remains to show that
$\lim_{T\rightarrow\infty}\mu(D_{T})=\infty$. To this end, note that $Q^{-1}$
is continuous and strictly decreasing. As
$\lim_{\lambda\rightarrow\infty}Q(\lambda)=0$ (e.g. Stone 1975, p.48), we know
$\lim_{T\rightarrow\infty}Q^{-1}(E(T))=0$. (This is consistent with the
interpretation of $Q^{-1}(E(T))$ as the baseline of attractiveness we
mentioned before Theorem 3.2.) Since $\int_{X}\pi(x)dx=1<\infty$, we have
$\lim_{||x||\rightarrow\infty}\pi(x)=0$ where $||\cdot||$ is the Euclidean
norm on $\mathbb{R}^{n}$. Therefore, the continuity of the Lebegsue measure
implies

$\displaystyle\lim_{T\rightarrow\infty}\mu(D_{T})$ $\displaystyle\leq$
$\displaystyle\lim_{T\rightarrow\infty}\mu(\\{x\mid||x||\leq\inf\\{||a||\mid\pi(a)=Q^{-1}(E(T))\\}\\})$
$\displaystyle=$
$\displaystyle\mu\left(\lim_{T\rightarrow\infty}\\{x\mid||x||\leq\inf\\{||a||\mid\pi(a)=Q^{-1}(E(T))\\}\\}\right)$
$\displaystyle=$ $\displaystyle\infty.$

∎

Remark. Theorem 3.3 does not extend to a regular detection function. To see
this, consider the example in Remark of Theorem 3.2. In this case, if $x\in
D_{T}$, then

$\displaystyle 0\leq\pi_{T}(x)$ $\displaystyle=$
$\displaystyle\frac{Q^{-1}(M(T))/x^{2}}{\int_{X}Q^{-1}(M(T))/x^{2}dx}=\frac{1/x^{2}}{\int_{X}1/x^{2}dx},\quad\text{for
all $T>0$. }$

Therefore, for any $T>0$ we have

$\pi_{T}(x)=\left\\{\begin{array}[]{ll}0,&\hbox{if the the possibility area
$X$ contains the origin,}\\\ \text{a positive
constant},&\hbox{otherwise.}\end{array}\right.$

Property (iv) says that a uniformly optimal search plan will place the
additional effort that accumulates in the interval $[T,T+t]$ uniformly over
the area that has been searched by time $T$. It turns out this property holds
for an arbitrary continuous target distribution too.

######  Theorem 3.4.

If the target distribution is continuous with a density function $\pi$ and the
detection function has the form $d(x,y)=1-e^{-\alpha y}$ for all $x\in X$ and
$y\geq 0$ where $\alpha>0$, then the uniformly optimal search plan will place
the additional effort uniformly over the area that has been searched by time
$T$.

###### Proof.

From the proof of Theorem 3.2, we know that the uniformly optimal search plan
$\varphi^{\star}$ is given by

$\varphi^{\star}(x,T)=\left\\{\begin{array}[]{ll}[-\ln(Q^{-1}(E(T)))+\ln(\alpha\pi(x))]/\alpha,&\hbox{if
$0<Q^{-1}(E(T))\leq q_{x}(0)$,}\\\ 0,&\hbox{if
$Q^{-1}(E(T))>q_{x}(0)$.}\end{array}\right.$

Let $\varphi^{\star}_{T}(x,t)=\varphi^{\star}(x,T+t)-\varphi^{\star}(x,T)$ for
$x\in X$ and $t\geq 0$ be the additional effort density. It follows that
$\varphi^{\star}_{T}(x,t)$ equals

$\left\\{\begin{array}[]{ll}-\frac{1}{\alpha}[\ln(Q^{-1}(E(T+t))/Q^{-1}(E(T)))],&\hbox{if
$0<Q^{-1}(E(T+t))<Q^{-1}(E(T))\leq q_{x}(0)$,}\\\
\frac{1}{\alpha}[-\ln(Q^{-1}(E(T+t)))+\ln(\alpha\pi(x))],&\hbox{if
$0<Q^{-1}(E(T+t))\leq q_{x}(0)<Q^{-1}(E(T))$,}\\\ 0,&\hbox{if
$Q^{-1}(E(T+t))>q_{x}(0)$,}\end{array}\right.$

for all $t>0$. Therefore, the theorem follows. ∎

Remark. When $d$ is regular, the uniformly optimal search plan
$\varphi^{\star}$ is given by

$\varphi^{\star}(x,T)=\left\\{\begin{array}[]{ll}q_{x}^{-1}(Q^{-1}(E(T))),&\hbox{if
$0<Q^{-1}(E(T))\leq q_{x}(0)$,}\\\ 0,&\hbox{if
$Q^{-1}(E(T))>q_{x}(0)$,}\end{array}\right.$

and $\varphi^{\star}_{T}(x,t)$ equals

$\left\\{\begin{array}[]{ll}q_{x}^{-1}(Q^{-1}(E(T+t)))-q_{x}^{-1}(Q^{-1}(E(T))),&\hbox{if
$0<Q^{-1}(E(T+t))<Q^{-1}(E(T))\leq q_{x}(0)$,}\\\
q_{x}^{-1}(Q^{-1}(E(T+t))),&\hbox{if $0<Q^{-1}(E(T+t))\leq
q_{x}(0)<Q^{-1}(E(T))$,}\\\ 0,&\hbox{if
$Q^{-1}(E(T+t))>q_{x}(0)$,}\end{array}\right.$

In generally, $q_{x}^{-1}(Q^{-1}(E(T+t)))-q_{x}^{-1}(Q^{-1}(E(T)))$ might
depend on $x$. For example, if we consider the example in Remark of Theorem
3.2, then $\varphi^{\star}_{T}(x,t)$ equals

$\left\\{\begin{array}[]{ll}-\frac{1}{x^{2}}[\ln(Q^{-1}(E(T+t))/Q^{-1}(E(T)))],&\hbox{if
$0<Q^{-1}(E(T+t))<Q^{-1}(E(T))\leq q_{x}(0)$,}\\\
\frac{1}{x^{2}}[-\ln(Q^{-1}(E(T+t)))+\ln(x^{2}\pi(x))],&\hbox{if
$0<Q^{-1}(E(T+t))\leq q_{x}(0)<Q^{-1}(E(T))$,}\\\ 0,&\hbox{if
$Q^{-1}(E(T+t))>q_{x}(0)$,}\end{array}\right.$

for all $t>0$. Therefore, Theorem 3.4 does not extend to the case of a regular
detection function.

##  4 Example

######  Example 1.

Suppose a search team is tasked with searching for a sunk ship. It is known
that the current has been drifting towards north or/and east since the ship
sank. The teams decides to choose the density of the target distribution to be

$\pi(x)=\pi(x_{1},x_{2})=\left\\{\begin{array}[]{ll}e^{-(x_{1}+x_{2})},&\hbox{$x_{1}>0$
and $x_{2}>0$,}\\\ 0,&\hbox{otherwise,}\end{array}\right.$

where $x=(x_{1},x_{2})\in X=\mathbb{R}^{2}$. In addition, the team takes the
detection function to be $d(x,y)=1-e^{-y}$ for $x\in X$ and $y\geq 0$. In this
case, $q_{x}(y)=\pi(x)e^{-y}$ and

$q_{x}^{-1}(\lambda)=\left\\{\begin{array}[]{ll}-\ln\lambda-(x_{1}+x_{2}),&\hbox{if
$0<\lambda\leq e^{-(x_{1}+x_{2})}$,}\\\
0,&\hbox{otherwise,}\end{array}\right.$

Therefore,
$Q(\lambda)=\int_{0}^{-\ln\lambda}\int_{0}^{(-\ln\lambda)-x_{1}}[(-\ln\lambda)-x_{1}-x_{2}]dx_{1}dx_{2}=-\frac{1}{6}(\ln\lambda)^{3}$
and the uniformly optimal search plan given by

$\varphi^{\star}((x_{1},x_{2}),T)=\left\\{\begin{array}[]{ll}(6WvT)^{1/3}-(x_{1}+x_{2}),&\hbox{if
$0<x_{1}+x_{2}\leq(6WvT)^{1/3}$,}\\\ 0,&\hbox{otherwise,}\end{array}\right.$
(4)

where $T$ is the time available for search. For $W=1$, $v=5$, and two values
of $T$, Figure 1 provides a 3-D plot of the uniformly optimal search plan
$\varphi^{\star}$ given by (4).

(a) $T=10$

(b) $T=50$

Figure 1: Figure 1: 3-D plots of the uniformly optimal search plan
$\varphi^{\star}$ in Example 1 when $W=1$ and $v=5$ for $T=10$ and $T=50$.

Put $D_{T}=\\{(x_{1},x_{2})\mid x_{1}+x_{2}\leq(6WvT)^{1/3}\\}$. Then the
probability of detection equals

$\displaystyle P[\varphi^{\star}(\cdot,T)]$ $\displaystyle=$
$\displaystyle\int_{X}d(x,\varphi^{\star}(x,T))\pi(x)dx$ $\displaystyle=$
$\displaystyle\int_{D_{t}}[1-e^{(-(6WvT)^{1/3}+(x_{1}+x_{2}))}]e^{-(x_{1}+x_{2})}dx_{1}dx_{2}$
$\displaystyle=$ $\displaystyle
1-e^{-(6WvT)^{1/3}}-(6WvT)^{1/3}e^{-(6WvT)^{1/3}}-(1/2)(6WvT)^{2/3}e^{-(6WvT)^{2/3}}.$

Thus, $\lim_{T\rightarrow\infty}P[\varphi^{\star}(x,T)]=1$.

By (4), we know $\pi(x)[1-d(x,\varphi^{\star}(x,T))]=e^{-(6Wvt)^{1/3}}$ for
$x\in D_{T}$. Also, $m(D_{T})=(1/2)(6Wvt)^{2/3}$ and

$\displaystyle\int_{D^{c}_{T}}\pi(x)dx$ $\displaystyle=$ $\displaystyle
1-\int_{0}^{(6Wvt)^{1/3}}\int_{0}^{(6Wvt)^{1/3}-x_{1}}e^{-(x_{1}+x_{2})}dx_{2}dx_{1}=[1+(6Wvt)^{1/3}]e^{-(6Wvt)^{1/3}}.$

It follows from (3) that

$\displaystyle\pi_{T}(x_{1},x_{2})$ $\displaystyle=$
$\displaystyle\left\\{\begin{array}[]{ll}\frac{1}{1+(6WvT)^{1/3}+1/2(6WvT)^{2/3}},&\hbox{if
$0<x_{1}+x_{2}\leq(6WvT)^{1/3}$,}\\\
\frac{e^{-(x_{1}+x_{2})}}{1+(6WvT)^{1/3}+1/2(6WvT)^{2/3}},&\hbox{if
$x_{1}+x_{2}>(6WvT)^{1/3}$.}\end{array}\right.$

It is evident that $D^{c}_{T}=\\{(x_{1},x_{2})\mid
x_{1}+x_{2}>(6WvT)^{1/3}\\}\rightarrow\phi$ as $T\rightarrow\infty$ and that
the part of $\pi_{T}$ on $D_{T}^{c}$ is less than the part of $\pi_{T}$ on
$D_{T}$. On the area $D_{T}$, the posterior density $\pi_{T}$ is constant and
tends to zero as $T\rightarrow\infty$. Therefore, $\pi_{T}(x)\rightarrow 0$ as
$T\rightarrow\infty$ for all $x\in X$. Figure 2 provides 3-D plots of the
posterior density $\pi_{T}$ for $W=1$, $v=5$, and two values of $T$. As we can
see, the posterior density $\pi_{T}$ is flattering and spreading as $T$
increases.

(a) $T=10$

(b) $T=50$

Figure 2: Figure 2: 3-D plots of the posterior density $\pi_{T}$ outside
$D_{T}$ in Example 1 when $W=1$ and $v=5$ for $T=10$ and $T=50$.

In this case, the additional effort density equals

$\varphi^{\star}_{T}((x_{1},x_{2}),t)=\left\\{\begin{array}[]{ll}\
[6Wv(T+t)]^{1/3}-(6WvT)^{1/3},&\hbox{if $0<x_{1}+x_{2}\leq(6WvT)^{1/3}$, }\\\
\ [6Wv(T+t)]^{1/3}-(x_{1}+x_{2}),&\hbox{if
$(6WvT)^{1/3}<x_{1}+x_{2}\leq[6Wv(T+t)]^{1/3}$,}\\\ \ 0,&\hbox{if
$x_{1}+x_{2}>[6Wv(T+t)]^{1/3}$.}\end{array}\right.$

Therefore, $\varphi_{T}^{\star}$ is uniform over the area that has been
searched by time $T$.

##  5 Concluding remarks

The uniformly optimal search plan plays a vital role in the theory of optimal
search. In the existing literature as well as many applications, a circular
normal target distribution is often employed for mathematical convenience. In
such a case, a uniformly optimal search plan has been proved to possess
several desirable properties. To improve search efficiency and increase the
probability of success, a search team should choose whatever target
distribution that most closely reflects the prior information. Therefore, it
is important to investigate whether these properties still hold for an
arbitrary continuous target distribution. This article confirms that it is the
case.

## Acknowledgments

I thank the Editor-in-Chief, the Associate Editor, and two anonymous reviewers
for many useful comments and suggestions.

## References

Arkin, V.I. (1964). Uniformly optimal strategies in search problems. _Theory
of Probability and its Applications_ 9(4): 647–677.

Clarkson, J., Glazebrook, K.D. and Lin, K.Y. (2020). Fast or slow: search in
discrete locations with two search models. _Operations Research_ 68(2),
552–571.

Everett, H. (1963). Generalized Lagrange multiplier method for solving
probglems of optimum allocation of resources. _Operations Research_ 11,
399–417.

Kadane, J.B. (2015). Optimal discrete search with technological choice.
_Mathematical Methods of Operations Research_ 81, 317–336.

Koopman, B.O. (1946). Search an screening. _Operations Evaluation Group Report
No. 56 (unclassified)._ Center for Naval Analysis, Rosslyn, Virginia.

Koopman, B.O. (1956a). The theory of search, I. Kinematic bases. _Operations
Research_ 4, 324–346.

Koopman, B.O. (1956b). The theory of search, II. Target detection. _Operations
Research_ 4, 503–531.

Koopman, B.O. (1956a). The theory of search, III The optimum distribution of
seraching efforts. _Operations Research_ 4, 613–626.

Kratzke, T.M., Stone, L.D., and Frost J.R. (2010). Search and rescue optimal
planning system. _Proceedings of the 13th International Conference on
Information Fusion, Edinburgh, UK, July 2010_ , 26–29.

Richardson, H.R. and Stone, L.D. (1971). Operations analysis during the
underwater search for Scorpion. _Naval Research Logistic Quarterly_ 18,
141–157.

Ricardson, H.R., Wagner D.H. and Discenza, J.H. (1980). The United States
Coast Guard Computer-assisted Search Planning System (CASP). _Naval Research
Logistic Quarterly_ 27, 659–680.

Soza Co. Ltd and U.S. Coast Guard (1996). _The Theory of Search: A Simplified
Explanation_. U.S. Coast Guard: Washington, D.C..

Stone, L.D. (1973). Totally optimality of incrementally optimal allocations.
_Naval Research Logistics Quarterly_ 20, 419–430.

Stone, L.D. (1975). _Theory of Optimal Search_. Academic Press: New York.

Stone, L.D. (1976). Incremental and total optimization of separable
functionals with constraints. _SIAm Journal on Control and Optimization_ 14,
791–802.

Stone, L.D., Royset, J.O., and Washburn, A.R. (2016). _Optimal Search for
Moving Targets_. Springer: New York.

Stone, L.D. and Stanshine J.A. (1971). Optimal searching using uninterrupted
contact investigation. _SIAM Journal of Applied Mathematics_ 20, 241–263.

Stone, L.D. (1992). Search for the SS Central America: mathematical treasure
hunting. _Interfaces_ 22: 32–54.

Stone, L.D., Keller, C.M. , Kratzke, T.M. and Strumpfer, J.P. (2014). Search
for the wreckage of Air France AF 447. _Statistical Science_ 29:69–80.

Washburn, A. (2014). _Search and Detection_ , 5th Edition. Create Space: North
Carolina.


Simplifying the axiomatization for ordered affine geometry via a theorem
prover

Dafa Li

Dept of mathematical sciences

Tsinghua University, Beijing 100084, China

Abstract

Jan von Plato proposed in 1998 an intuitionist axiomatization of ordered
affine geometry consisting of 22 axioms. It is shown that axiom I.7, which is
equivalent to a conjunction of four statements, two of which are redundant,
can be replaced with a simpler axiom, which is von Plato’s Theorem 3.10.

Keywords: ordered affine geometry, axiomatization, automated theorem proving,
intuitionistic logic.

##  1 Introduction

Heyting proposed a constructive axiomatization for affine geometry [1], by
adopting the primitive notions of distinct points and distinct lines. von
Plato proposed 22 axioms for constructive ordered affine geometry [2], based
on the five basic relations DiPt, DiLn, Undir, L-Apt, and L-Con and four
constructions ln($a,b$), pt($a,b$), par$(l,m)$, and rev($l$).

With the aid of the automatic theorem prover ANDP, we simplify in this paper
von Plato’s axiomatization. Von Plato’s axiom I.7 is shown to include some
redundancy and we show that it can be replaced with a simpler and more
intuitive new axiom, which is von Plato’s Theorem 3.10 [2].

##  2 Von Plato’s axiomatization for ordered affine geometry

In this paper, we want to replace axiom I.7 with a simpler and more intuitive
axiom. Only four axioms I.5-I.8 are of concern to the presented work [2]. Only
a basic relation Undir$(l,m)$ and only a construction rev$(l)$ appear in the
axioms I.5-I.8. Undir$(l,m)$ means $l$ and $m$ are unequally directed lines.
rev($l$) stands for the reverse of line $l$. For readability, we list the four
axioms as follows.

The axiom I.5:

$(\forall l)\thicksim Undir(l,l).$ (1)

The axiom I.6:

$(\forall l)(\forall m)(\forall n)[Undir(l,m)\rightarrow Undir(l,n)\vee
Undir(m,n)]$ (2)

The axiom I.7:

$\displaystyle(\forall l)(\forall m)(\forall n)[Undir(l,m)\&Undir(l,rev(m))$
(3) $\displaystyle\rightarrow$ $\displaystyle Undir(l,n)\&Undir(l,rev(n))\vee
Undir(m,n)\&Undir(m,rev(n))].$

The axiom I.8:

$(\forall l)(\forall m)[Undir(l,m)\vee Undir(l,rev(m))]$ (4)

The convergence $Con(l,m)$ is defined by means of the basic relation Undir as
$Undir(l,m)\&Undir(l,rev(m))$ [2]. Thus, $Con(l,m)$ means that $l$ and $m$ are
convergent lines. And then, axiom I.7 becomes

$(\forall l)(\forall m)(\forall n)[Con(l,m)\rightarrow Con(l,n)\vee
Con(m,n)].$ (5)

(5) describes the convergence of three lines (the direction is ignored).

Axiom I.7 can be rewritten constructively equivalently as w1&w2&w3&w4, where
wi, i=1,2,3,4, are listed in order as follows.

$\displaystyle Undir(l,m)\&Undir(l,rev(m))$ $\displaystyle\rightarrow$
$\displaystyle Undir(l,n)\vee Undir(m,n),$ (6) $\displaystyle
Undir(l,m)\&Undir(l,rev(m))$ $\displaystyle\rightarrow$ $\displaystyle
Undir(l,n)\vee Undir(m,rev(n)),$ (7) $\displaystyle
Undir(l,m)\&Undir(l,rev(m))$ $\displaystyle\rightarrow$ $\displaystyle
Undir(l,rev(n))\vee Undir(m,n),$ (8) $\displaystyle
Undir(l,m)\&Undir(l,rev(m))$ $\displaystyle\rightarrow$ $\displaystyle
Undir(l,rev(n))\vee Undir(m,rev(n)),$ (9)

where the prefix $(\forall l)(\forall m)(\forall n)$ for w1-w4 is omitted.

##  3 Replacing axiom I.7 with a shorter formula

By means of ANDP, after lots of trials, we chose SYM to replace axiom I.7,
where SYM stands for:

$(\forall l)(\forall m)[Undir(l,rev(m))\rightarrow Undir(m,rev(l))].$ (10)

SYM reads that for any lines $l$ and $m$, if $l$ and the reverse of $m$ are
unequally directed lines, then $m$ and the reverse of $l$ are unequally
directed lines. Here, SYM is referred as to the symmetry of the reverse line.
Clearly, SYM is shorter and more intuitive than axiom I.7. One notices that
there are two and respectively six occurrences of the predicate Undir in SYM
and in axiom I.7.

The proofs obtained via ANDP are classical. By means of the ANDP proofs, we
find the corresponding resolution proofs omitted here and corresponding
constructive proofs below.

###  3.1  Axioms I.5, I.6, and SYM constructively imply axiom I.7

To reduce the difficulty of deriving axiom I.7, we derive w1, w2, w3, and w4
from the axioms I.5, I.6, and SYM.

It is easily seen that w1 and w4 weakenings of I.6 and thus follow from I.6
alone.

####  3.1.1 Proof of w2

Lemma 1. w2 can be constructively derived from the axioms I.5, I.6 and SYM.

Proof of (7). Assume (∗) $Undir(l,m)$ and (∗∗) $Undir(l,rev(m))$. Then, let us
derive $Undir(l,n)\vee Undir(m,rev(n))$.

$Undir(l,rev(m))\rightarrow Undir(l,n)\vee Undir(rev(m),n)\text{ \ \ \ \ \ \ \
\ (by I.6)}$ (11)

$Undir(l,n)\vee Undir(rev(m),n)\text{ \ \ \ \ (by (}^{\ast\ast}\text{) and
(\ref{b1}))}$ (12)

There are the following two cases for (12).

Case 1. $Undir(l,n)$. Therefore, $Undir(l,n)\vee Undir(m,rev(n))$.

Case 2. (∗∗∗) $Undir(rev(m),n)$.

$Undir(rev(m),n)\rightarrow Undir(rev(m),rev(m))\vee Undir(n,rev(m))\text{ \ \
\ \ (by I.6)}$ (13)

$Undir(rev(m),rev(m))\vee Undir(n,rev(m))\text{ \ \ \ \ \ \ \ (by
(}^{\ast\ast\ast}\text{) and (\ref{b4}))}$ (14)

$\sim Undir(rev(m),rev(m))\text{ \ \ \ \ \ \ \ \ (by I.5)}$ (15)

$Undir(n,rev(m))\text{ \ \ \ \ \ \ \ (by (\ref{b5}) and (\ref{ad-1})) }$ (16)

$Undir(n,rev(m))\rightarrow Undir(m,rev(n))\text{ \ \ \ \ \ \ (by SYM)}$ (17)

$Undir(m,rev(n))\text{ \ \ \ \ \ \ \ (by (\ref{ad-2}) and (\ref{b6}))}$ (18)

$Undir(l,n)\vee Undir(m,rev(n))\text{ \ \ \ \ \ \ (by (\ref{ad-3}))}$ (19)

Therefore, in all cases, we have $Undir(l,n)\vee Undir(m,rev(n))$. Q.E.D.

####  3.1.2 Proof of w3

Lemma 2. w3 can be constructively derived from the axioms I.5, I.6 and SYM.

Proof of (8). Assume (∗) $Undir(l,m)$ and (∗∗) $Undir(l,rev(m))$. Then, let us
derive $Undir(l,rev(n))\vee Undir(m,n)$.

$Undir(l,rev(m))\rightarrow Undir(m,rev(l))\text{ \ \ \ \ \ \ (by SYM)}$ (20)

$Undir(m,rev(l))\text{ \ \ \ \ \ \ \ \ \ \ \ (by (}^{\ast\ast}\text{) and
(\ref{sy-1}))}$ (21)

$Undir(m,rev(l))\rightarrow Undir(m,n)\vee Undir(rev(l),n)\text{ \ \ \ \ \ \ \
\ \ \ (by I.6)}$ (22)

$Undir(m,n)\vee Undir(rev(l),n)\text{ \ \ \ \ \ \ \ \ \ \ \ \ (by (\ref{sy-2})
and (\ref{c2}))}$ (23)

There are the following two cases for (23).

Case 1. $Undir(m,n)$. Therefore, $Undir(l,rev(n))\vee Undir(m,n)$.

Case 2. (∗∗∗) $Undir(rev(l),n)$.

$Undir(rev(l),n)\rightarrow Undir(rev(l),rev(l))\vee Undir(n,rev(l))\text{ \ \
\ \ \ (by I.6)}$ (24)

$Undir(rev(l),rev(l))\vee Undir(n,rev(l))\text{ \ \ \ \ \ (by
(}^{\ast\ast\ast}\text{) and (\ref{c4})}$ (25)

$\sim Undir(rev(l),rev(l))\text{ \ \ \ \ \ \ \ \ \ \ \ (by I.5)}$ (26)

$Undir(n,rev(l))\text{ \ \ \ \ \ \ \ \ \ \ \ (by (\ref{sy-3}) and
(\ref{c5}))}$ (27)

$Undir(n,rev(l))\rightarrow Undir(l,rev(n)\text{ \ \ \ \ \ \ \ (by SYM) }$
(28)

$Undir(l,rev(n)\text{ \ \ \ \ \ (by (\ref{sy-4}) and (\ref{c6}))}$ (29)

$Undir(l,rev(n))\vee Undir(m,n)\text{ \ \ \ \ \ \ \ (by (\ref{sy-5}))}$ (30)

Therefore, in all cases, we have $Undir(l,rev(n))\vee Undir(m,n)$. Q.E.D.

In light of Lemmas 1 and 2, we can conclude the following.

Theorem 1. Axioms I.5, I.6, and SYM constructively imply axiom I.7.

###  3.2 Conversely, the axioms I.5-I.8 constructively imply SYM

Lemma 3. SYM can be constructively derived from the axioms I.5, I.6, I.8, and
w2.

Proof. First, we want to indicate that SYM is von Plato’s Theorem 3.10 [2]. To
derive SYM from the axioms I.5, I.6, I.8, and w2, we only need to derive
$Undir(m,rev(l))$ by assuming (∗) $Undir(l,rev(m))$.

$Undir(m,l)\vee Undir(m,rev(l))\text{ \ \ \ \ \ \ \ (by I.8)}$ (31)

There are the following two cases for (31).

Case 1. (∗∗) $Undir(m,l)$.

$Undir(m,l)\rightarrow Undir(m,m)\vee Undir(l,m)\text{ \ \ \ \ \ \ (by I.6)}$
(32)

$Undir(m,m)\vee Undir(l,m)\text{ \ \ \ \ \ \ \ \ \ \ (by (}^{\ast\ast}\text{)
and (\ref{sym-2}))}$ (33)

$\sim Undir(m,m)\text{ \ \ \ \ \ \ \ (by I.5)}$ (34)

$Undir(l,m)\text{ \ \ \ \ \ \ \ \ \ \ \ (by (\ref{sym-3}) and (\ref{sm-1}))}$
(35)

$Undir(l,m)\wedge Undir(l,rev(m))\rightarrow Undir(l,l)\vee
Undir(m,rev(l))\text{ \ \ \ \ (by (\ref{W-2}))}$ (36)

$Undir(l,l)\vee Undir(m,rev(l))\text{ \ \ \ \ \ \ \ \ (by (}^{\ast}\text{),
(\ref{sm-2}), and (\ref{sym-6}))}$ (37)

$\sim Undir(l,l)\text{ \ \ \ \ \ \ \ \ \ \ \ \ \ (by I.5)}$ (38)

$Undir(m,rev(l))\text{ \ \ \ \ \ \ \ \ \ \ \ \ (by (\ref{sym-7}) and
(\ref{sm-3}))}$ (39)

Case 2. $Undir(m,rev(l))$. This is the desired result.

Therefore, in all cases, we have $Undir(m,rev(l))$. Q.E.D.

In light of Lemma 3, we can conclude the following.

Theorem 2. The axioms I.5-I.8 constructively imply SYM.

In light of Theorems 1 and 2, we obtain the following.

Theorem 3. The set of the axioms I.5, I.6, I.8 and SYM is constructively
equivalent to the set of the axioms I.5-I.8. In other words, axiom I.7 is
constructively equivalent to SYM, by using the axioms I.5, I.6, and I.8. Thus,
axiom I.7 can be replaced with SYM.

Acknowledgements

Thank the reviewer for the deep and helpful comments.

No funding; D. Li wrote the main manuscript text.; no conflict interest;

Data availability statement: All data generated or analysed during this study
are included in this published article.

## References

  * [1] Heyting, A.: Axioms for intuitionistic plane affine geometry In L. Henkin et al., eds.. The Axiomatic Method, North-Holland, Amsterdam, 160-173 (1959).
  * [2] von Plato, J.: A constructive theory of ordered affine geometry. Indag. Mathem., N.S. 9 (4), 549-562 (1998).