Predictive Uncertainty-based Bias Mitigation in Ranking

Societal biases that are contained in retrieved documents have received increased interest. Such biases, which are often prevalent in the training data and learned by the model, can cause societal harms, by misrepresenting certain groups, and by enforcing stereotypes.
Mitigating such biases demands algorithms that balance the trade-off between maximized utility for the user with fairness objectives, which incentivize unbiased rankings.
Prior work on bias mitigation often assumes that ranking scores, which correspond to the utility that a document holds for a user, can be accurately determined.
In reality, there is always a degree of uncertainty in the estimate of expected document utility.
This uncertainty can be approximated by viewing ranking models through a Bayesian perspective, where the standard deterministic score becomes a distribution.

In this work, we investigate whether uncertainty estimates can be used to decrease the amount of bias in the ranked results, while minimizing loss in measured utility.
We introduce a simple method that uses the uncertainty of the ranking scores for an uncertainty-aware, post hoc approach to bias mitigation. We compare our proposed method with existing baselines for bias mitigation with respect to the utility-fairness trade-off, the controllability of methods, and computational costs. We show that an uncertainty-based approach can provide an intuitive and flexible trade-off that outperforms all baselines without additional training requirements, allowing for the post hoc use of this approach on top of arbitrary retrieval models.

Data and code
To facilitate reproducibility of our work, all code and parameters are shared at <https://github.com/MariaHeuss/2023-CIKM-uncertainty-based-bias-mitigation>.

The research was partially funded by the Hybrid Intelligence Center, a 10-year program funded by the Dutch Ministry of Education, Culture and Science through the Netherlands Organisation for Scientific Research, <https://hybrid-intelligence-centre.nl>, and project LESSEN with project number NWA.1389.20.183 of the research program NWA ORC 2020/21, which is (partly) financed by the Dutch Research Council (NWO).
All content represents the opinion of the authors, which is not necessarily shared or endorsed by their respective employers and/or sponsors.

#1     #1#1#1     #1     #1     #1     #1#1          #1#1

[Angwin, Larson, Mattu, and KirchnerAngwin
et al2016]
authorpersonJulia Angwin, personJeff
Larson, personSurya Mattu, and personLauren
Kirchner. year2016.
Machine Bias.
In booktitleEthics of Data and Analytics.
publisherAuerbach Publications, pages254–264.

[Beutel, Chen, Doshi, Qian, Wei, Wu, Heldt,
Zhao, Hong, Chi, and GoodrowBeutel et al2019]
authorpersonAlex Beutel, personJilin Chen,
personTulsee Doshi, personHai Qian,
personLi Wei, personYi Wu, personLukasz
Heldt, personZhe Zhao, personLichan Hong,
personEd H. Chi, and personCristos Goodrow.
Fairness in Recommendation Ranking through Pairwise
Comparisons. In booktitleProceedings of the 25th ACM SIGKDD
International Conference on Knowledge Discovery & Data Mining.
publisherACM, pages2212–2220.

[Biega, Gummadi, and WeikumBiega
et al2018]
authorpersonAsia J. Biega, personKrishna P.
Gummadi, and personGerhard Weikum.
Equity of Attention: Amortizing Individual Fairness
in Rankings. In booktitleProceedings of the 41st
International ACM SIGIR Conference on Research and Development in Information
Retrieval. pages405–414.

authorpersonCarlos Castillo.
Fairness and Transparency in Ranking. In
booktitleACM SIGIR Forum, Vol. volume52.

[Celis, Mehrotra, and VishnoiCelis
et al2020]
authorpersonL. Elisa Celis, personAnay
Mehrotra, and personNisheeth K. Vishnoi.
Interventions for Ranking in the Presence of
Implicit bias. In booktitleProceedings of the 2020
Conference on Fairness, Accountability, and Transparency.

[Celis, Straszak, and VishnoiCelis
et al2018]
authorpersonL. Elisa Celis, personDamian
Straszak, and personNisheeth K. Vishnoi.
Ranking with Fairness Constraints. In
booktitle45th International Colloquium on Automata,
Languages, and Programming (ICALP 2018). pages28:1–28:15.

[Chen, Ma, Hannák, and WilsonChen
et al2018]
authorpersonLe Chen, personRuijun Ma,
personAnikó Hannák, and personChristo
Wilson. year2018.
Investigating the Impact of Gender on Rank in
Resume Search Engines. publisherACM, pages1–14.

[Cohen, Du, Mitra, Mercurio, Rekabsaz, and
EickhoffCohen et al2022]
authorpersonDaniel Cohen, personKevin Du,
personBhaskar Mitra, personLaura Mercurio,
personNavid Rekabsaz, and personCarsten Eickhoff.
Inconsistent Ranking Assumptions in Medical Search
and Their Downstream Consequences. In booktitleProceedings
of the 45th International ACM SIGIR Conference on Research and Development in
Information Retrieval (Madrid, Spain). publisherACM,

[Cohen, Mitra, Lesota, Rekabsaz, and
EickhoffCohen et al2021]
authorpersonDaniel Cohen, personBhaskar
Mitra, personOleg Lesota, personNavid Rekabsaz,
and personCarsten Eickhoff. year2021.
Not All Relevance Scores Are Equal: Efficient
Uncertainty and Calibration Modeling for Deep Retrieval Models. In
booktitleProceedings of the 44th International ACM SIGIR
Conference on Research and Development in Information Retrieval.

[Deng, Zhou, and ZhuDeng
et al2022]
authorpersonZhijie Deng, personFeng Zhou,
and personJun Zhu. year2022.
Accelerated Linearized Laplace Approximation for
Bayesian Deep Learning. In booktitleAdvances in Neural
Information Processing Systems, editorpersonAlice H.
Oh, personAlekh Agarwal, personDanielle Belgrave,
and personKyunghyun Cho (Eds.), Vol. volume35.

[Diaz, Mitra, Ekstrand, Biega, and
CarteretteDiaz et al2020]
authorpersonFernando Diaz, personBhaskar
Mitra, personMichael D. Ekstrand, personAsia J.
Biega, and personBen Carterette.
Evaluating Stochastic Rankings with Expected
Exposure. In booktitleProceedings of the 29th ACM
International Conference on Information & Knowledge Management.

[Dong, Liu, Cheng, Wang, Cheng, Niu, and
YinDong et al2022]
authorpersonQian Dong, personYiding Liu,
personSuqi Cheng, personShuaiqiang Wang,
personZhicong Cheng, personShuzi Niu, and
personDawei Yin. year2022.
Incorporating Explicit Knowledge in Pre-Trained
Language Models for Passage Re-Ranking. In
booktitleProceedings of the 45th International ACM SIGIR
Conference on Research and Development in Information Retrieval.
publisherACM, pages1490–1501.

[Ekstrand, McDonald, Raj, and JohnsonEkstrand
et al2022]
authorpersonMichael D. Ekstrand,
personGraham McDonald, personAmifa Raj, and
personIsaac Johnson. year2022.
Overview of the TREC 2021 Fair Ranking Track. In
booktitleThe Thirtieth Text REtrieval Conference (TREC 2021)

[Fabris, Purpura, Silvello, and SustoFabris
et al2020]
authorpersonAlessandro Fabris, personAlberto
Purpura, personGianmaria Silvello, and
personGian Antonio Susto. year2020.
Gender Stereotype Reinforcement: Measuring the
Gender Bias Conveyed by Ranking Algorithms.
journalInformation Processing & Management
volume57 (year2020), pages102377.

[Ganin and LempitskyGanin and
authorpersonYaroslav Ganin and
personVictor S. Lempitsky. year2015.
Unsupervised Domain Adaptation by Backpropagation.
In booktitleProceedings of the 32nd International Conference
on Machine Learning, ICML 2015, Lille, France, 6-11 July 2015
(seriesJMLR Workshop and Conference Proceedings),
Vol. volume37. pages1180–1189.

[Geyik, Ambler, and KenthapadiGeyik
et al2019]
authorpersonSahin Cem Geyik, personStuart
Ambler, and personKrishnaram Kenthapadi.
Fairness-aware Ranking in Search & Recommendation
Systems with Application to Linkedin Talent Search. In
booktitleProceedings of the 25th ACM SIGKDD International
Conference on Knowledge Discovery & Data Mining.

[Ghosh, Dutt, and WilsonGhosh
et al2021]
authorpersonAvijit Ghosh, personRitam Dutt,
and personChristo Wilson. year2021.
When Fair Ranking Meets Uncertain Inference. In
booktitleProceedings of the 44th International ACM SIGIR
Conference on Research and Development in Information Retrieval.

[Gorantla, Deshpande, and LouisGorantla
et al2021]
authorpersonSruthi Gorantla, personAmit
Deshpande, and personAnand Louis.
On the Problem of Underranking in Group-Fair
Ranking. In booktitleInternational Conference on Machine
Learning. PMLR, pages3777–3787.

[Heuss, Sarvi, and de RijkeHeuss
et al2022]
authorpersonMaria Heuss, personFatemeh
Sarvi, and personMaarten de Rijke.
Fairness of Exposure in Light of Incomplete
Exposure Estimation. In booktitleSIGIR 2022: 45th
international ACM SIGIR Conference on Research and Development in Information
Retrieval. publisherACM, pages759–769.

[Hofstätter, Lin, Yang, Lin, and
HanburyHofstätter et al2021]
authorpersonSebastian Hofstätter,
personSheng-Chieh Lin, personJheng-Hong Yang,
personJimmy Lin, and personAllan Hanbury.
Efficiently Teaching an Effective Dense Retriever
with Balanced Topic Aware Sampling. In booktitleProceedings
of the 44th International ACM SIGIR Conference on Research and Development in
Information Retrieval. publisherACM,

[Kleinberg and RaghavanKleinberg and
authorpersonJon Kleinberg and personManish
Raghavan. year2018.
Selection Problems in the Presence of Implicit
Bias. In booktitle9th Innovations in Theoretical Computer
Science Conference (ITCS 2018). publisherSchloss
Dagstuhl–Leibniz-Zentrum fuer Informatik, pages33:1–33:17.

[Kletti, Renders, and LoiseauKletti
et al2022]
authorpersonTill Kletti, personJean-Michel
Renders, and personPatrick Loiseau.
Pareto-Optimal Fairness-Utility Amortizations in
Rankings with a DBN Exposure Model. In booktitleProceedings
of the 45th International ACM SIGIR Conference on Research and Development in
Information Retrieval. pages748–758.

[Kristiadi, Hein, and HennigKristiadi
et al2020]
authorpersonAgustinus Kristiadi,
personMatthias Hein, and personPhilipp Hennig.
Being Bayesian, Even Just a Bit, Fixes
Overconfidence in ReLU Networks. In booktitleProceedings of
the 37th International Conference on Machine Learning.

[Lahoti, Gummadi, and WeikumLahoti
et al2019a]
authorpersonPreethi Lahoti, personKrishna P.
Gummadi, and personGerhard Weikum.
iFair: Learning Individually Fair Data
Representations for Algorithmic Decision Making. In
booktitle2019 IEEE 35th International Conference on Data
Engineering (ICDE). IEEE, pages1334–1345.

[Lahoti, Gummadi, and WeikumLahoti
et al2019b]
authorpersonPreethi Lahoti, personKrishna P.
Gummadi, and personGerhard Weikum.
Operationalizing Individual Fairness with Pairwise
Fair Representations.
journalProceedings of the VLDB Endowment
(year2019), pages506–518.

[Lin, Nogueira, and YatesLin
et al2021]
authorpersonJimmy Lin, personRodrigo
Nogueira, and personAndrew Yates.
Pretrained Transformers for Text Ranking: BERT
and Beyond.
journalSynthesis Lectures on Human Language
Technologies volume14, number4
(year2021), pages1–325.

authorpersonDavid J. C. Mackay.
A Practical Bayesian Framework for Backpropagation
journalNeural Computation  volume4
(year1992), pages448–472.

[Mehrotra and VishnoiMehrotra and
authorpersonAnay Mehrotra and
personNisheeth Vishnoi. year2022.
Fair Ranking with Noisy Protected Attributes. In
booktitleAdvances in Neural Information Processing
Systems, Vol. volume35. pages31711–31725.

[Nguyen, Rosenberg, Song, Gao, Tiwary,
Majumder, and DengNguyen et al2016]
authorpersonTri Nguyen, personMir
Rosenberg, personXia Song, personJianfeng Gao,
personSaurabh Tiwary, personRangan Majumder, and
personLi Deng. year2016.
MS MARCO: A Human Generated Machine Reading
Comprehension Dataset. In booktitleProceedings of the
Workshop on Cognitive Computation: Integrating Neural and Symbolic Approaches

[Nogueira and ChoNogueira and Cho2019]
authorpersonRodrigo Frassetto Nogueira and
personKyunghyun Cho. year2019.
Passage Re-ranking with BERT.
journalarXiv preprint arXiv:1901.04085

[Patro, Porcaro, Mitchell, Zhang, Zehlike, and
GargPatro et al2022]
authorpersonGourab K. Patro, personLorenzo
Porcaro, personLaura Mitchell, personQiuyue Zhang,
personMeike Zehlike, and personNikhil Garg.
Fair Ranking: A Critical Review, Challenges, and
Future Directions. In booktitle2022 ACM Conference on
Fairness, Accountability, and Transparency. publisherACM,

[Penha and HauffPenha and Hauff2021]
authorpersonGustavo Penha and
personClaudia Hauff. year2021.
On the Calibration and Uncertainty of Neural
Learning to Rank Models for Conversational Search. In
booktitleProceedings of the 16th Conference of the European
Chapter of the Association for Computational Linguistics: Main Volume, EACL
2021, Online, April 19 - 23, 2021. publisherAssociation for
Computational Linguistics, pages160–170.

[Rekabsaz, Kopeinik, and SchedlRekabsaz
et al2021]
authorpersonNavid Rekabsaz, personSimone
Kopeinik, and personMarkus Schedl.
Societal Biases in Retrieved Contents: Measurement
Framework and Adversarial Mitigation of Bert Rankers. In
booktitleProceedings of the 44th International ACM SIGIR
Conference on Research and Development in Information Retrieval.

[Rekabsaz and SchedlRekabsaz and
authorpersonNavid Rekabsaz and
personMarkus Schedl. year2020.
Do Neural Ranking Models Intensify Gender Bias?.
In booktitleProceedings of the 43rd International ACM SIGIR
Conference on Research and Development in Information Retrieval.

[Ritter, Botev, and BarberRitter
et al2018]
authorpersonHippolyt Ritter,
personAleksandar Botev, and personDavid Barber.
A Scalable Laplace Approximation for Neural
Networks. In booktitle6th International Conference on
Learning Representations, ICLR 2018-Conference Track Proceedings.
International Conference on Representation Learning.

authorpersonStephen E Robertson.
The Probability Ranking Principle in IR.
journalJournal of Documentation
volume33 (year1977), pages294–304.

[Santhanam, Khattab, Saad-Falcon, Potts, and
ZahariaSanthanam et al2022]
authorpersonKeshav Santhanam, personOmar
Khattab, personJon Saad-Falcon, personChristopher
Potts, and personMatei Zaharia.
ColBERTv2: Effective and Efficient Retrieval
via Lightweight Late Interaction. In booktitleProceedings
of the 2022 Conference of the North American Chapter of the Association for
Computational Linguistics: Human Language Technologies.
publisherACM, pages3715–3734.

[Sarvi, Heuss, Aliannejadi, Schelter, and
de RijkeSarvi et al2022]
authorpersonFatemeh Sarvi, personMaria
Heuss, personMohammad Aliannejadi, personSebastian
Schelter, and personMaarten de Rijke.
Understanding and Mitigating the Effect of Outliers
in Fair Ranking. In booktitleProceedings of the Fifteenth
ACM International Conference on Web Search and Data Mining.

[Singh and JoachimsSingh and
authorpersonAshudeep Singh and
personThorsten Joachims. year2018.
Fairness of Exposure in Rankings. In
booktitleProceedings of the 24th ACM SIGKDD International
Conference on Knowledge Discovery & Data Mining.

[Singh and JoachimsSingh and
authorpersonAshudeep Singh and
personThorsten Joachims. year2019.
Policy Learning for Fairness in Ranking. In
booktitleProceedings of the 33rd International Conference on
Neural Information Processing Systems. pages5426–5436.

[Singh, Kempe, and JoachimsSingh
et al2021]
authorpersonAshudeep Singh, personDavid
Kempe, and personThorsten Joachims.
Fairness in Ranking under Uncertainty. In
booktitleAdvances in Neural Information Processing
Systems, Vol. volume34. pages11896–11908.

[Stoyanovich, Yang, and JagadishStoyanovich
et al2018]
authorpersonJulia Stoyanovich, personKe
Yang, and personHV Jagadish. year2018.
Online Set Selection with Fairness and Diversity
Constraints. In booktitle21st International Conference on
Extending Database Technology, EDBT 2018. pages241–252.

[Turc, Chang, Lee, and ToutanovaTurc
et al2019]
authorpersonIulia Turc, personMing-Wei
Chang, personKenton Lee, and personKristina
Toutanova. year2019.
Well-Read Students Learn Better: The Impact of
Student Initialization on Knowledge Distillation.
journalarXiv preprint arXiv:1908.08962

[Wang and JoachimsWang and Joachims2021]
authorpersonLequn Wang and personThorsten
Joachims. year2021.
User Fairness, Item Fairness, and Diversity for
Rankings in Two-Sided Markets. In booktitleProceedings of
the 2021 ACM SIGIR International Conference on Theory of Information
Retrieval. pages23–41.

[Yang, Gkatzelis, and StoyanovichYang
et al2019]
authorpersonKe Yang, personVasilis
Gkatzelis, and personJulia Stoyanovich.
Balanced Ranking with Diversity Constraints. In
booktitleProceedings of the Twenty-Eighth International
Joint Conference on Artificial Intelligence, IJCAI.

[Yang, Luo, Lu, Gupta, Yin, and AiYang
et al2022]
authorpersonTao Yang, personChen Luo,
personHanqing Lu, personParth Gupta,
personBing Yin, and personQingyao Ai.
Can Clicks Be Both Labels and Features? Unbiased
Behavior Feature Collection and Uncertainty-Aware Learning to Rank. In
booktitleProceedings of the 45th International ACM SIGIR
Conference on Research and Development in Information Retrieval.
publisherACM, pages6–17.

[Yang, Xu, Wang, Tran, and AiYang
et al2023]
authorpersonTao Yang, personZhichao Xu,
personZhenduo Wang, personAnh Tran, and
personQingyao Ai. year2023.
Marginal-Certainty-aware Fair Ranking Algorithm.
In booktitleProceedings of the Sixteenth ACM International
Conference on Web Search and Data Mining. pages24–32.

[Zehlike, Bonchi, Castillo, Hajian, Megahed,
and Baeza-YatesZehlike et al2017]
authorpersonMeike Zehlike, personFrancesco
Bonchi, personCarlos Castillo, personSara Hajian,
personMohamed Megahed, and personRicardo
Baeza-Yates. year2017.
FA*IR: A Fair Top-k Ranking Algorithm. In
booktitleProceedings of the 2017 ACM on Conference on
Information and Knowledge Management. pages1569–1578.

[Zehlike and CastilloZehlike and
authorpersonMeike Zehlike and personCarlos
Castillo. year2020.
Reducing Disparate Exposure in Ranking: A Learning
To Rank Approach. In booktitleProceedings of The Web
Conference 2020. pages2849–2855.

[Zehlike, Sühr, Baeza-Yates, Bonchi,
Castillo, and HajianZehlike et al2022a]
authorpersonMeike Zehlike, personTom
Sühr, personRicardo Baeza-Yates, personFrancesco
Bonchi, personCarlos Castillo, and personSara
Hajian. year2022a.
Fair Top-k Ranking with Multiple Protected Groups.
journalInformation Processing & Management
volume59, number1 (year2022),

[Zehlike, Yang, and StoyanovichZehlike
et al2022b]
authorpersonMeike Zehlike, personKe Yang,
and personJulia Stoyanovich. year2022b.
Fairness in Ranking, Part I: Score-based Ranking.
journalComput. Surveys volume55,
number6 (year2022), pages1–36.

[Zehlike, Yang, and StoyanovichZehlike
et al2022c]
authorpersonMeike Zehlike, personKe Yang,
and personJulia Stoyanovich. year2022c.
Fairness in Ranking, Part II: Learning-to-rank and
Recommender Systems.
journalComput. Surveys volume55,
number6 (year2022), pages1–41.

[Zerveas, Rekabsaz, Cohen, and
EickhoffZerveas et al2022]
authorpersonGeorge Zerveas, personNavid
Rekabsaz, personDaniel Cohen, and personCarsten
Eickhoff. year2022.
Mitigating Bias in Search Results Through
Contextual Document Reranking and Neutrality Regularization. In
booktitleProceedings of the 45th International ACM SIGIR
Conference on Research and Development in Information Retrieval.

[Zhu, Wang, Taylor, and CoxZhu
et al2009]
authorpersonJianhan Zhu, personJun Wang,
personMichael Taylor, and personIngemar J. Cox.
Risk-Aware Information Retrieval. In
booktitleAdvances in Information Retrieval: 31th European
Conference on IR Research, ECIR 2009, Toulouse, France, April 6-9, 2009.
Proceedings 31. publisherSpringer-Verlag,


# Optimizing Passenger Comfort in Cost Functions for Trajectory Planning

Jean Elsner  Technische Universität München
Email<EMAIL_ADDRESS>
###### Abstract

Current advances in the development of autonomous cars suggest that driverless
cars may see wide-scale deployment in the near future. Research by both
industry and academia is driven by potential benefits of this new technology,
including reductions in fatalities and improvements in traffic and fuel
efficiency as well as greater mobility for people who will or cannot drive
cars themselves. A deciding factor for the adoption of self-driving cars
besides safety will be the comfort of the passengers. This report looks at
cost functions currently used in motion planning methods for autonomous on-
road driving. Specifically, how the human perception of how comfortable a
trajectory is, can be formulated within cost functions.

##  I Introduction

General interest and research into autonomous cars has been growing rapidly in
recent years, fueled by promises such as enhanced safety, more efficient
traffic flow, greater mobility as well as decreased fuel consumption. While
verification of the safety and reliability of a self-driving car is paramount,
real world systems will eventually be judged by the amount of comfort they
provide their passengers. Fully autonomous transportation systems will no
longer allow the human passengers to control the vehicle. Therefore, it is up
to the system to plan the motion of the vehicle in a way, that does not put
too much stress on the passengers and does not decrease their level of
comfort. Ignoring human factors and ergonomics in the design of self-driving
systems may induce negative side-effects in passengers and ultimately lead to
their rejection of the technology.

This report discusses different criteria that may be used to quantify how
comfortable a trajectory is as perceived by humans and reviews how these
criteria are currently implemented inside the cost functions of trajectory
planning algorithms.

###  I-A Motion planning for on-road driving

Planning for autonomous on-road driving can generally be divided into three
stages [1]:

  1. 1.

Finding a global path to the goal destination

  2. 2.

Planning and selecting the best maneuver to perform

  3. 3.

Finding the best trajectory to follow

While maneuver planning is concerned with selecting the most suitable high-
level action (e.g. overtaking or lane changes), the path planer provides a
geometric path to the destination. Trajectory planning on the other hand (also
referred to as motion planning) is the most low-level planner and is evaluated
each iteration of the planning cycle (consisting of sensing, planing and
execution).

###  I-B Cost Functions in Motion Planning

During motion planning, a number of trajectories are generated each cycle. The
cost function is used to evaluate each of these trajectories and select the
optimal trajectory according to the cost function’s objectives.
Mathematically, the cost function can be formulated as

$\displaystyle J_{C}(x(t),u(t),t_{0},t_{f})=\;$
$\displaystyle\underbrace{\Phi_{C}(x(t_{0}),t_{0},x(t_{f}),t_{f})}_{\text{terminal
cost}}+$ (1)
$\displaystyle\underbrace{\int_{t_{0}}^{t_{f}}L_{C}(x(t),u(t),t)\differential
t.}_{\text{running cost}}$

With $x(t)$ the vehicle’s state vector, $u(t)$ the input vector and $t_{0}$
and $t_{f}$ the initial and final time of the trajectory. The cost function
can further be generalized to consist of two summands, the first of which
depends only on the initial and final state and time. The second summand
depends on state and input over the entire trajectory. To find the best
trajectory the cost function will be minimized

$\displaystyle
u^{*}(\cdot)=\underset{u(\cdot)}{\operatorname{arg\,min}}\;J_{C}(x(t),u(t),t_{0},t_{f})$
(2)

subject to the constraints

$\displaystyle\dot{x}(t)=f_{M}(x(t),u(t)),\qquad
O(x(t))\in\mathcal{W}_{\text{S,free}},$ (3) $\displaystyle
g_{\text{S}}(x(t),u(t),t)\leq 0,\qquad x(t_{0}),\qquad
x(t_{f})\in\mathcal{G}_{\mathrm{S}}.$

Where the first constraint defines the vehicle’s dynamics and therefore
enforces feasible solutions. The second one concerns the vehicle’s occupancy
$O(x(t))$, effectively avoiding collisions. Additional hard constraints, like
speed limits or other traffic rules, can be encoded in
$g_{\text{S}}(x(t),u(t),t)$. Finally, the trajectory must begin at the
vehicle’s current position given by $x(t_{0})$ and end in an accepted goal
region $\mathcal{G}_{\text{S}}$.

###  I-C CommonRoad

The notation for cost functions in this report follows the convention
introduced in the composable benchmarks for motion planning on roads
(CommonRoad) framework [2]. CommonRoad provides ready made vehicle dynamics,
traffic scenarios and cost functions. A combination of these fully defines a
motion planning benchmark that can be identified by a unique ID and therefore
becomes easy to reproduce.

In order to construct arbitrary cost functions, the framework provides a set
of both running and terminal basis cost functions, which have been listed in
Table I. A cost function of the form seen in equation (1) can then be written
as a weighted superposition of these partial cost functions:

$\displaystyle
J_{C}(x(t),u(t),t_{0},t_{f})=\sum_{i\in\mathcal{I}}w_{i}J_{i}(x(t),u(t),t_{0},t_{f}).$
(4)

A shorthand is introduced to describe cost functions by the indices and
weights of the partial cost functions used to construct them:

$\displaystyle[(X_{1}\mid w_{1}),...,(X_{N}\mid
w_{N})]=w_{1}J_{X_{1}}+...+w_{N}J_{X_{N}}.$ (5)

TABLE I: Partial cost functions in CommonRoad Running costs
---
Acceleration | $J_{A}=\int_{t_{0}}^{t_{f}}a^{2}\differential t$
Jerk | $J_{J}=\int_{t_{0}}^{t_{f}}\dot{a}^{2}\differential$
Steering angle | $J_{SA}=\int_{t_{0}}^{t_{f}}\delta^{2}\differential t$
Steering rate | $J_{SR}=\int_{t_{0}}^{t_{f}}a_{\delta}^{2}\differential t$
Energy | $J_{E}=\int_{t_{0}}^{t_{f}}P(x,u)^{2}\differential t$
Yaw rate | $J_{Y}=\int_{t_{0}}^{t_{f}}\dot{\Psi}^{2}\differential t$
Lane center offset | $J_{LC}=\int_{t_{0}}^{t_{f}}d^{2}(t)\differential t$
Velocity offset | $J_{V}=\int_{t_{0}}^{t_{f}}(v_{\text{des}}(x(t))-v(t))^{2}\differential t$
Orientation offset | $J_{O}=\int_{t_{0}}^{t_{f}}(\theta_{\text{des}}(x(t))-\theta(t))^{2}\differential t$
Distance to obstacles | $J_{D}=\int_{t_{0}}^{t_{f}}\operatorname{max}(\xi_{1},...,\xi_{0})\differential t$
Path length | $J_{L}=\int_{t_{0}}^{t_{f}}v\differential t$
Terminal costs
Time | $J_{T}=t_{f}$
Terminal offset | $J_{TO}=d^{2}(t_{f})$
Terminal distance to goal | $J_{TG}=d^{2}_{\text{goal}}(t_{f})$

##  II Human Comfort Criteria

Most commonly, passenger comfort is taken into account by minimizing the
vehicle’s motion in regard to acceleration, jerk or both [3, 4]. While
vertical forces act due to road disturbances as illustrated in figure 1,
horizontal forces are the direct result of acceleration and steering and can
therefore be considered by the system’s motion planning algorithm. Within the
CommonRoad framework, this approach may be quantified in the context of a cost
function as

$\displaystyle J_{\text{comf}}(x(t),u(t),t_{0},t_{f})=\;$ $\displaystyle
w_{1}J_{A}+w_{2}J_{J}=$ (6) $\displaystyle
w_{1}\int_{t_{0}}^{t_{f}}a^{2}\differential
t+w_{2}\int_{t_{0}}^{t_{f}}\dot{a}^{2}\differential t.$

Or, using the shorthand, as

$\displaystyle[(A\mid w_{1}),(J\mid w_{2})].$ (7)

Figure 1: Illustration of the resulting forces acting on a passenger within a
vehicle and their root cause [3]. Note that only the horizontal forces are
subject to be influenced by driver behavior.

Another method occasionally used is the selection of smoother paths. It is
assumed that smoother paths are more natural and more closely resemble the
behavior of human drivers [3]. Often, this is combined with a path planer that
generates continuous curvilinear trajectory candidates, as illustrated in
figure 2.

Figure 2: Smooth candidate trajectory next to base path [5]. Path planners
will often generate a bunch of candidate trajectories that are parallel to the
base path in a space where the base path is a straight line and rank them in
euclidean space using cost functions.

One way to penalize non-smooth trajectories in the cost function, is to
minimize curvature. While there is no partial cost function for curvature in
the CommonRoad framework, a respective cost function can be derived using the
geometric definition:

$\displaystyle
J_{\kappa}=\operatorname{max}\quantity{\frac{x^{\prime}_{i}\cdot
y^{\prime\prime}_{i}-x^{\prime\prime}_{i}\cdot
y^{\prime}_{i}}{(x^{\prime}_{i}+y^{\prime}_{i})^{3/2}}}$ (8)

Here, the maximum curvature of a trajectory is considered by calculating the
curvature at each point $(x_{i}\mid y_{i})$ on the trajectory. Note however,
that a more convenient method may be used to compute the curvature, if the
candidate is a curvilinear function such as, for example, a clothoid.

The criteria for passenger comfort discussed so far are of a physical nature.
Due to the loss of control however, human passengers in a driverless car may
experience discomfort due to psychological effects, such as a perceived lack
of safety [6]. For a motion planning system with a given response ratio

$\displaystyle\frac{vT}{d},$ (9)

where $v$ is the current velocity and T is the response time (given by the
period of the planning cycle), a minimum distance $d$ to obstacles must be
kept, such that the system can respond quickly enough to changes in the
environment so as to drive safely. Because a computer’s responsiveness is
orders of magnitude higher than a human’s, a motion planning system might
choose trajectories, that are perfectly safe for the system to execute, but
would be impossible to navigate safely by a human driver. Because of this
perceived lack of safety and the anxiety it may induce in human passengers,
the proximity to obstacles may be artificially decreased by the motion
planner. This can be quantified using the partial cost function

$\displaystyle
J_{D}(x(t),u(t),t_{0},t_{f})=w_{1}\int_{t_{0}}^{t_{f}}\operatorname{max}(\xi_{1},...,\xi_{o})\differential
t=[(D\mid w_{1})].$ (10)

##  III State of the art

This section discusses the state of the art of passenger comfort criteria in
cost functions for motion planning systems by example of several publications.
An attempt is made to formulate cost functions according to the conventions of
the CommonRoad framework, were applicable.

Mohseni 2017 presents fuel and comfort efficient control for autonomous
vehicles [7]. The optimization of passenger comfort and fuel consumption is
explicitly taken into account by the cost function. Non-comfort is defined as
high jerk and acceleration. The average fuel power consumed by the engine is
given as

$\displaystyle P=\frac{Fv}{\eta}$ (11)

where $\eta$ is the engine efficiency, $F$ and $v$ are force and velocity
respectively. This power is used to approximate the fuel flow

$\displaystyle V=\frac{P}{H\rho}\approx Fv.$ (12)

With $\rho$ and $H$ the fuel density and fuel lower heating value
respectively. With this, it is reasoned, that optimal fuel efficiency can be
achieved by minimizing the engine power. The overall cost function can be
written as

$\displaystyle J_{FM1}=[(A\mid w_{1}),(J\mid w_{2}),(E\mid w_{2})].$ (13)

Here, the CommonRoad convention to use the initials of the first author and a
running number has been used to index the cost function. Note however, that no
weights are given in Mohseni 2017. It is hinted, that they may even use
different weights for the $x$ and $y$ components in global coordinates within
the cost function. While no further evaluation of passenger comfort is made,
it is worth mentioning, that Mohseni 2017 apply their cost function to several
vehicles so as to plan cooperative maneuvers, such as synchronized lane
changes or the zipper-like opening of a passage for an emergency vehicle
(illustrated in figure 3).

Figure 3: Two examples of cooperative maneuvers presented in Mohseni 2017. The
left illustration shows the for phases involved in creating a moving emergency
passage. On the right a synchronized lane change is shown.

In Du 2016 a nonlinear model predictive control (NMPC) scheme is used to
control the velocity and steering of a vehicle [8]. Genetic algorithms are
utilized to optimize a cost function, that is designed specifically to take
the safety and comfort of human passengers into account. The cost function
includes costs for tracking errors, control smoothness as well as high
acceleration. While the cost function in Du 2016 is given in L1-norm and sums
over discrete points on the trajectory up to the control or prediction
horizon, here the cost function is written using the established CommonRoad
conventions.

$\displaystyle J_{XD1}=\;$ $\displaystyle[(LC\mid w_{1}),(O\mid w_{2}),(SR\mid
w_{3}),(A\mid w_{5}(t))]\;+$ (14)
$\displaystyle\int_{t_{0}}^{t_{f}}w_{4}a_{tan}^{2}+w_{6}(t)\operatorname{sgn}({a_{tan}})a_{tan}^{2}\differential
t\;+$ $\displaystyle\int_{t_{0}}^{t_{f}}w_{7}(t)(v_{max}-v)^{2}\differential
t$

With the last 3 weights defined as

$\displaystyle w_{5}(t)=\;$ $\displaystyle\begin{cases}0,\qquad\text{if }a\leq
a_{max}\\\ w_{5,0}\mbox{\quad otherwise\quad}\end{cases}$ (15) $\displaystyle
w_{6}(t)=\;$ $\displaystyle\begin{cases}w_{6,0},\mbox{\quad if
condition1\quad}\\\ 0,\mbox{\quad otherwise\quad}\end{cases}$ (16)
$\displaystyle w_{7}(t)=\;$ $\displaystyle\begin{cases}0,\mbox{\quad if
condition1\quad}\\\ w_{7,0},\mbox{\quad otherwise\quad}\end{cases}$ (17)
$\displaystyle\text{condition1}=\;$
$\displaystyle(a_{tan}>0)\land((a>a_{max})\;\lor$ (18)
$\displaystyle(d(t)>$0.3\text{\,}\frac{\mathrm{m}}{}$)\lor((\theta_{des}(x(t))-\theta(t))>$0.09$))$

In dangerous situations as identified in equation (18), forward acceleration
is penalized, while under normal conditions, the vehicle is supposed to drive
at a prescribed cruise speed of $v_{max}$. Furthermore, minimizing the
steering rate is thought to prevent sudden and large changes that may induce
shaking, while horizontal acceleration is penalized so as to follow the ISO
2631-1 standard. Du 2016 argues that passengers will not feel any shaking or
jerking effects, as steering acceleration and vehicle acceleration during
their tests were confined to comfort regions as illustrated in figure 4.

Figure 4: Vehicle and steering acceleration of a vehicle controlled by the
method proposed in Du 20016 [8]. The red dashed lines represent safety and
comfort boundaries that may not be crossed. Figure 5: Cost function library
used in Wei 2016 [8]. Each cost function consists of a sequence of connected
vertices with the cost outside defined as infinite. From left to right and top
down the cost functions are the distance keeper progress cost, comfort cost,
braking distance cost and clear distance cost respectively.

Wei 2010 uses a prediction and cost function based algorithm to implement
autonomous freeway driving [9]. A library of cost functions, consisting of
progress, comfort and safety costs, is used to evaluate the strategies
generated by the three modules _distance keeper_ , _lane selector_ and _merge
planner_. While the latter two modules are concerned with maneuver planning,
the former is a sort of lower level cruise control, that follows the leading
vehicle. If no leading vehicle is detected, a virtual vehicle driving at the
speed limit is inserted $150\text{\,}\mathrm{m}\text{/}$ ahead. The cost
functions used in Wei 2010 are designed to be human-understandable and
informative. They consist of piecewise linear functions, while unacceptable
inputs are mapped to infinite costs, as pictured in figure 5. For the
_distance keeper_ , the cost function consists of a progress, safety and
comfort cost. The progress cost is defined as the difference between the
current distance to the leading vehicle and the desired distance to it (a
function of velocity), called the gap error in figure 5. The safety cost
penalizes proximity to other vehicles as well as the braking distance to the
leading vehicles. These two costs are evaluated according to the $\Delta\text{
brake distance }$ and distance costs of figure 5. Finally, the comfort part of
the cost functions in Wei 2010 corresponds to the acceleration cost in figure
5. Introducing a partial cost function for the distance to the leading vehicle
as

$\displaystyle J_{LV}=\int_{t_{0}}^{t_{f}}(d_{l,des}-d_{l})^{2}\differential
t.$ (19)

With the desired distance to the leading vehicle
$d_{l,des}=d_{l,min}+k_{gain}v$ and the current distance to the leading
vehicle $d_{l}$. As well as a partial cost function for the brake distance to
the leading vehicle

$\displaystyle
J_{BD}=\int_{t_{0}}^{t_{f}}(d_{l}+\frac{1}{2}v_{l}^{2}a_{maxdec}^{-1}-vT-\frac{1}{2}v^{2}a_{maxdev}^{-1})^{2}\differential
t.$ (20)

Where $v_{l}$ is the velocity of the leading vehicle, $a_{maxdec}$ the maximum
deceleration and $T$ is the motion planner’s response time. Allows us to
introduce the cost function

$\displaystyle J_{JW1}=[(LV\mid 50),(A\mid 10),(BD\mid 30),(D\mid 20)].$ (21)

With $k_{gain}$ given in [9] as $1.14\text{\,}\mathrm{s}\text{/}$,
$d_{l,min}=$5\text{\,}\mathrm{m}\text{/}$$ and
$T=$0.6\text{\,}\mathrm{s}\text{/}$$. Note, that this formulation uses an L2
norm to calculate the running costs and ignores the piecewise functional forms
given in Wei 2010. The regions with infinite cost however, can be trivially
checked within the hard constraints $g_{s}(x(t),u(t),t)\leq 0$. Arnay 2016
introduces a local planner, that produces a set of candidate trajectories,
which are scored using a linear combination of weighted cost functions [5]. An
attempt is made, to discern the influence of the different weights on the
prototype’s behavior and find the optimal set of weights. Candidate local
paths are generated by transforming the euclidean coordinate system into
Frenét space, with the global path as the base frame. Trajectories are
computed in curvilinear space and then transformed to the original euclidean
space, where the cost is computed.

Figure 6: The Verdino platform on which the method presented in Arnay 2016 is
tested [5]. The vehicle is a golf car that has been modified to be controlled
by an on-board computer. It can reach a speed of around
$20\text{\,}\mathrm{km}\text{/}\mathrm{h}$ and is equipped with several
sensors for mapping and localization.

Before the cost function can be formulated in CommonRoad notation, an
additional partial running cost has to be introduced

$\displaystyle
J_{C}=\omega_{c}\frac{1}{s_{2}-s_{1}}\int_{s_{1}}^{s_{2}}l_{i}\differential
s.$ (22)

$J_{C}$, referred to as the consistency cost, penalizes changing the
trajectory candidate between planning cycles. Where $l_{i}(s)$ is the lateral
distance between the current and the previous chosen trajectory at the same
longitudinal position parameterized by $s$. $s_{1}$ and $s_{2}$ are the first
and last positions over $s$ where the trajectories share points. Given this
and the previously introduced curvature cost, the cost function can be written
as

$\displaystyle J_{RAi}=$
$\displaystyle[(D\mid\omega_{o}),(L\mid\omega_{l}),(LC\mid\omega_{d}),(\kappa\mid\omega_{k}),(C\mid\omega_{c})].$
(23)

The curvature cost is chosen to select smooth paths and consider passenger
comfort. While horizontal forces and jerk are not considered explicitly, it’s
worth mentioning, that the motion planning system is run on a modified golf
car with only a 36 $V_{CC}$ electrical motor that achieves a maximum speed
between 19 and 25 $\mathrm{km}\text{/}\mathrm{h}$ (cf. figure 6).

Figure 7: Influence of single weights on choosing trajectories in the path
planner presented in Arnay 2016 [5]. The measurements are taken by clamping
all the other weights while varying one weight in on the interval $[0-1]$. The
x-axis defines the value assigned to the varied weight while the y-axis shows
the influence on the 4 measured metrics path distance, occlusion, speed and
curvature respectively. Figure 8: Ranking of different tuples of weight values
scored according to distance to obstacles and proximity to lane center in
Arnay 2016 [5]. Figure 9: Ranking of different tuples of weight values
according to distance to obstacles, proximity to lane center, speed and the
inverse of curvature in Arnay 2016 [5].

In order to evaluate the relative importance of each weight, a simulation was
set up, where the start and goal position as well as the positions of the
obstacles were kept the same. Starting from a base configuration of
$\omega_{d}=0.17$, $\omega_{o}=0.2$, $\omega_{c}=0.02$, $\omega_{l}=0.7$,
$\omega_{k}=0.01$, which was found empirically, each of the weights was varied
between 0 and 1, while the other weights kept their default value. The
resulting trajectories of the simulation are then evaluated in regard to their
lane center offset (a), distance to obstacles (b), speed(c) and curvature(d).
The results can be seen in Fig. 7. As would be expected, the measured
variables of the trajectories correlate more strongly with their corresponding
cost weight. For example, variation of the lane center offset weight $w_{d}$
is inversely proportional to the lance center cost of the resulting trajectory
in figure 7 (a), whereas the same weight is proportional to the distance to
obstacles cost in 7 (b). The latter might be explained by the fact, that
forcing the system to keep close to the global path as much as possible, might
result in proximity to obstacles not considered during geometric path
generation. The opposite can be observed for the distance to obstacles weight
$\omega_{o}$. The more influence the weight gets, the costlier the
trajectories become in regard to lane center offset. This seems also sensible:
if the vehicle’s priority is to give obstacles a wide berth at all costs, it
may strongly deviate from its path. The weights’ influence on the speed cost
are more specific to the motion planner used in Arnay 2016, as speed commands
are e.g. computed based on the inverse of the length of the path and proximity
to obstacles. No discernible pattern can be determined for the curvature cost,
all included weights seem to influence it concurrently, with no one weight
strictly dominant.

Finally, different sets of weights are ranked as seen in figure 8 and figure
9. The ranking in figure 8 considers proximity to obstacles and lane center
offset, while the one seen in Fig. 9 also takes speed and path curvature into
account. For reference, the weights used in Chu 2012 are added to the ranking
[10]. The comparison however does not seem fair, as Chu 2012 does not include
weights for lane center offset as well as path length, both of which are
considered in the ranking, albeit path length only indirectly via speed. This
is especially true, as the weights are otherwise nearly the same. The highest
ranking weights for the two respective rankings in figure 8 and figure 9 for
Arnay 2016 can be summarized using CommonRoad notation as

$\displaystyle J_{RA1}=\;$ $\displaystyle[(D\mid 0.2),(L\mid 0.2),(LC\mid
0.17)]+$ (24) $\displaystyle[(\kappa\mid 0.01),(C\mid 0.02)]$ $\displaystyle
J_{RA2}=\;$ $\displaystyle[(D\mid 0.1),(L\mid 0.7),(LC\mid 0.17)]$ (25)
$\displaystyle[(\kappa\mid 0.01),(C\mid 0.02)].$

The cost function in [10] accordingly can be written as

$\displaystyle J_{KC1}=\;$ $\displaystyle[(D\mid 0.1),(\kappa\mid 0.01),(C\mid
0.02)].$ (26)

Note that even though curvature and therefore smoothness of the trajectories
was specifically mentioned as a means to consider passenger comfort in Arnay
2016, most of the final results assign only a small weight or none at all to
curvature.

##  IV Conclusion

This report presented a review of cost functions employed in current motion
planning systems in regard to passenger comfort. It was established, that most
approaches are concerned with directly limiting resulting forces and jerk on
the passenger. While there are sometimes references to norms concerning
exposure of the human body to vibration and shock, such as ISO-2631-1 [1],
[8], [3], [12], there are few reports validating their assumptions in studies
including live test subjects. Side effects such as motion sickness or anxiety
may have very subjective root causes, that are difficult to quantify [3], [6].
Because of this, approaches outside of the cost function may proof fruitful.
In Whitsitt 2012 an upper bound for the forward velocity in relation to the
steering angle was derived from data captured from human drivers [11]. As an
extension, even more complex control relations could be learned using methods
from machine learning. Another research direction, seen in Gonzáles 2016
directly generates smooth speed profiles using quintic Bézier curves. In the
end, more field tests with live subjects under real conditions are required to
identify the needs of passengers more precisely. Eventually it may turn out,
that a robust and safe motion planner, that obeys all traffic rules, is
inherently comfortable for the majority of people.

## References

  * [1] C. Katrazakas and M. Quddus and W. Chen and L. Deka, _Real-time motion planning methods for autonomous on-road driving: State-of-the-art and future research directions_. Transportation Research Part C: Emerging Technologies, 60:416–442, 2015.
  * [2] M. Althoff and M. Koschi and S. Manzinger. _CommonRoad: Composable Benchmarks for Motion Planning on Roads_. Intelligent Vehicles Symposium (IV), 2017 IEEE, 2017.
  * [3] M. Elbanhawi and M. Simic and R. Jazar. _In the Passenger Seat: Investigating Ride Comfort Measures in Autonomous Cars_. IEEE Intelligent Transportation Systems Magazine, 7(3):4–17, 2015.
  * [4] R. Zanasi and R. Morselli and A. Visconi and M. Cavanna. _Head-neck model for the evaluation of passenger’s comfort_. Intelligent Robots and Systems, 2002. IEEE/RSJ International Conference on, 2002.
  * [5] R. Arnay and N. Morales and A. Morell and J. Hernández-Aceituno and D. P. Ström and J. Toledo and A. Hamilton and J. Sánchez-Medina and Leopoldo Acosta, _Safe and Reliable Path Planning for the Autonomous Vehicle Verdino_. IEEE Intelligent Transportation Systems Magazine, 8(2):22–32, 2016.
  * [6] M. Beggiato and F. Hartwich and J. Krems. _Der Einfluss von Fahrermerkmalen auf den erlebten Fahrkomfort imhochautomatisierten Fahren_. at - Automatisierungstechnik, 65(7):512–521, 2016.
  * [7] F. Mohseni and J. Åslund and E. Frisk and L. Nielsen. _Fuel and Comfort Efficient Cooperative Control for Autonomous_. Intelligent Vehicles Symposium (IV), 2017 IEEE, 2017.
  * [8] X. Du and K. K. Tan. _Autonomous vehicle velocity and steering control through nonlinear model predictive control scheme_. Transportation Electrification Asia-Pacific (ITEC Asia-Pacific), 2016 IEEE Conference and Expo, 2016.
  * [9] J. Wei and J. M. Dolan and B. Litkouhi. _A Prediction- and Cost Function-Based Algorithm for Robust Autonomous Freeway Driving_. Intelligent Vehicles Symposium (IV), 2010 IEEE, 2010.
  * [10] K. Chu and M. Lee and M. Sunwoo, _A Passenger Comfort Controller for an Autonomous Ground Vehicle_. IEEE Transactions on Intelligent Transportation Systems, 13(4):1599–1616, 2012.
  * [11] S. Whitsitt and J. Sprinkle, _A Passenger Comfort Controller for an Autonomous Ground Vehicle_. Decision and Control (CDC), 2012 IEEE 51st Annual Conference on, 2012.
  * [12] D. Gonzáles and V. Milanés and J. Pérez and F. Nashashibi. _Speed Profile Generation based on Quintic Bezier Curves for Enhanced Passenger Comfort_. Intelligent Transportation Systems (ITSC), 2016 IEEE 19th International Conference on, 2016.


# Spoken Term Detection Methods for Sparse Transcription
in Very Low-resource Settings

###### Abstract

We investigate the efficiency of two very different spoken term detection
approaches for transcription when the available data is insufficient to train
a robust ASR system. This work is grounded in very low-resource language
documentation scenario where only few minutes of recording have been
transcribed for a given language so far. Experiments on two oral languages
show that a pretrained universal phone recognizer, fine-tuned with only a few
minutes of target language speech, can be used for spoken term detection with
a better overall performance than a dynamic time warping approach. In
addition, we show that representing phoneme recognition ambiguity in a graph
structure can further boost the recall while maintaining high precision in the
low resource spoken term detection task.

Index Terms: speech transcription, language documentation, low resource
languages, spoken term detection

##  1 Introduction

Efforts are made across Australia to preserve, document and revitalize
Aboriginal languages. These languages exist primarily in spoken form, and even
if there is an official orthography it is not widely used by local people.
Making recordings of speakers has been a widespread practice for documenting
traditional knowledge. However, such recordings are often not transcribed,
making them hard to access.

Manual transcription is time consuming and is often described as a bottleneck
[1]. While automatic speech recognition (ASR) has seen great improvement in
recent years [2, 3], it relies on a large amount of annotated data. Attempts
to build ASR systems for low-resource languages end up with high word error
rate or single-speaker models making them of limited use in indigenous
contexts [4, 5, 6, 7].

Such methods assume that everything should be transcribed. [8] describes a
sparse transcription model where we only transcribe the words we can
confidently recognise, using word-spotting, while leaving the transcription of
more difficult sections for later, perhaps when a speaker is available [8].
Based on this model, we proposed a workflow which combines spoken term
detection and human-in-the-loop to support transcription in under-resourced
settings [9]. Here, we focus on the spoken term detection stage of the
workflow, trying to seek a higher-precision method that better supports
interactive transcription.

Automatic phone recognition has seen progress with minimal data [5, 10]. While
[8] argues that phonetic transcriptions do not stand in for the speech data
and cannot be segmented to generate the required higher-level word units, we
can nevertheless use phone transcriptions as a speech encoding, retaining our
commitment to the sparse transcription model. In this paper we show how this
can be done, and compare it with another spoken term detection method, namely
dynamic time warping (DTW) [11]. We consider both methods as applied to two
very low-resource languages, Kunwinjku (gup) and Mboshi (mdw).

##  2 Background

Several sources of annotated data can be used to support transcription.
Combining automatic processes and human intervention can be a way to
iteratively fine-tune a speech recognition model with newly produced data, and
enhance the manual transcription with automatically annotated data. [8]
proposes an approach to transcription which combines word spotting with human-
in-the-loop in a iterative process. [9] explore this further, using DTW with
basic speech representations to transcribe up to 42% of a lexicon in their
speech collection. However, this method is not robust in the face of speaker
variability. Research around speech features for spoken term detection has
explored the use of bottleneck features, or the hidden representation of an
AutoEncoder [12, 13], although they make negligible difference in the context
of the workflow in [9]. Others have exploited neural approaches to train word
classifiers from words pair using Siamese loss [14, 15], however pairs of
words are required, limiting the selection of words that can be searched.

While standard automatic speech recognition methods tend to give poor
performance in low-resource setting [4, 5], recent work has shown that it is
possible to obtain an automatic phone transcription with minimal training [5,
10, 16]. In the context of word-level transcription, [8] describes phone
transcription as a `retrograde step' given that optimising the recognition of
low-level units such as phones does not necessarily help with identifying
higher-level units. He also observes that only linguists can provide the
required phone transcriptions or graph-to-phone rules. In many spoken
languages, we can find standard orthographies and a small amount of spoken
material transcribed. These orthographies are built in a written system close
to the language phonology. Such system is documented enough so an approximate
phone transcription can be easily obtained through a basic mapping from
graphemes to phonemes on existing written data. [17] explain that the linguist
should aim for a faithful phones transcription to aim to a better Phone Error
Rate (PER). However a noisy phones transcription or even an orthographic
transcription mapped into phonemes can also be used to train a phone
recognizer. Phone transcription has this advantage over speech representation
that its level of abstraction gives a speaker-independent representation.

Doing word spotting, while some terms are unlikely to be found in a noisy
phone transcription, doing exact matching between the written forms of a
lexicon (transliterated into phones) and a stream of the k-best phones output
by the recogniser offers inter-speaker robustness.

In the context of textual data annotation, [18] argues that an automatic
annotation is likely to improve the speed of the annotator if the precision is
at least 80% and the accuracy if it is at least 60%. Even though a wide set of
factors can have an influence on the speed and accuracy, like the quality of
the data or the confidence of the transcriber, we argue that a higher
precision is to be prioritized over a higher recall.

##  3 Methods

We begin with a lexicon of size s consisting of audio clips of spoken words,
along with their orthographic transcription, and a speech collection in which
more instances of those words may be found. Two spoken term detection
approaches are investigated here: (a) a baseline method based on DTW applied
on MFCC features (normalised for cepstral mean and variance); and (b) a method
based on automatic phone recognition in which phones units are mapped to word
units (P2W).

###  3.1 Baseline: Sparse Transcription using DTW

The baseline is a simplified version of the workflow of [9] which introduced
an iterative process to transcribe speech with a growing spoken lexicon. We
use DTW to retrieve lexical items from the speech collection, sliding query
terms across the utterances.

For each entry in the lexicon, based on the DTW score, we select the $n$ best
matches in the collection to be evaluated. The value of $n$ has been optimized
using a development set ($n=5$ for Kunwinjku and $n=20$ for Mboshi).

###  3.2 Sparse Transcription using Phone Recognition (P2W)

[10] introduced Allosaurus, a universal phone recognition system which
combines a language independent encoder and phone predictor, and a language
dependent allophone layer and a loss function associated with each language
(Fig. 1). Allosaurus models are trained using standard phonetic transcriptions
and the allovera database [19], a multilingual allophone database that can be
used to map allophones to phonemes. The model first encodes speech with a
standard ASR encoder which computes the universal phone distribution. Then an
allophone layer is initialized with the allophone matrix and maps the
universal phone distribution into the phoneme distribution for the given
target language. The resulting model can be fine-tuned and applied to unseen
languages.

Figure 1: Allosaurus model [10] Figure 2: Illustration of P2W workflow

In the current context, since we only have an orthographic transcription for
Kunwinjku, we transliterate it into IPA (Fig. 2a) with the mapping shown in
Table 1. The transcription contains some English words which will be mapped as
if they were Kunwinjku words (eg., school is written /sPkool/ instead of
/skl/). For Mboshi, the orthographic transcription already mostly matches the
corresponding phonetic transcription.111The tones are marked in the
orthographic transcription but this feature is not taken into account in the
Allosaurus model. We thus decided to treat the orthographic transcription as a
phonetic transcription so the accentuated vowels are considered as new phones.

graphs | a | b | d | h | e | i | ch | y | o | k | dj | s | r | rr
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
phones |  | b | d |  |  | i |  | j |  | k |  | s |  | r
graphs | ng | rd | rl | nj | rn | u | f | l | m | n | w | p | t |
phones | ŋ |  |  |  |  | u | f | l | m | n | w | p | t |
Table 1: Grapheme to phoneme mapping for Kunwinjku

We fine-tuned the original pretrained model with the training subsets
described in Section 4 following the mapping described above resulting on one
new phone recognition model per language (Fig. 2b). We used the resulting
models to automatically transcribe the validation set of the two languages
(Mboshi and Kunwinjku) (Fig. 2c). For Kunwinjku, we reverse the mapping
function to get a grapheme transcription (Fig. 2d). Finally, we use the
written lexicon for each language and perform spoken term detection using the
queries' transcripts using a longest string matching algorithm (Fig. 2e).

##  4 Data

The same datasets of [9] will be used: a corpus in Kunwinjku which consists of
301 utterances aligned with an orthographic transcription and a forced
alignment created using the MAUS forced aligner [20], and a corpus in Mboshi
which consists of 5130 utterances elicited from text, with orthographic
transcription and a forced alignment at the word level [21].

In order to train the phone recognition system, an additional collection of 20
min of Kunwinjku (newly recorded guided tours) is used as training set. For
Mboshi, a subset of 30 min is randomly extracted from the original corpus.

The lexicon queries (for spoken term detection) are made of 100 words for
Mboshi and 60 words for Kunwinjku. We randomly selected words which occur at
least 3 times. For each word, we manually selected examples clearly
pronounced, verified and respecting the speaker distribution of the corpora
(Table 2 and 3) and clipped them out of the corpora used for spoken term
detection.

Speaker | RB | TG | GN | SG | MM
---|---|---|---|---|---
Distribution | 10% | 25% | 15% | 38% | 12%
Table 2: Speaker distribution across Kunwinjku lexicon Speaker | Abiayi | Kouarata | Martial
---|---|---|---
Distribution | 63% | 33% | 4%
Table 3: Speaker distribution across Mboshi lexicon

##  5 Results

We first evaluate the phone error rate (PER) for both languages. For Kunwinjku
the PER started at 53.15%, and we obtained 40.55% after the system early
stopped at the 17th epoch. For Mboshi the PER started at 59% and reached
35.49% at the 29th epoch. Although the PER is low considering the small amount
of data used for fine-tuning Allosaurus, we would expect a bigger difference
between Kunwinjku and Mboshi considering that Mboshi is read speech without
foreign words and Kunwinjku is spontaneous speech containing English words.

We evaluate the two spoken term detection approaches presented in previous
section, using recall and precision. Since the recall of the baseline includes
the words from the lexicon used as queries, we also provide the recall without
the instances of the lexicon (recall-no-lex). The F-score is computed using
regular recall. In the case of Kunwinjku, the size of the validation set is
small, which means that the words from the lexicon represent a large portion
of the final results.

| recall-no-lex | recall | precision | F-score
---|---|---|---|---
DTW | 17.43% | 33.24% | 21.67% | 26.24%
P2W | - | 15.15% | 85.07% | 25.72%
Table 4: Performance of spoken term detection in Kunwunjku | recall-no-lex | recall | precision | F-score
---|---|---|---|---
DTW | 15.47% | 21.18% | 13.55% | 16.53%
P2W | - | 13.07% | 62.91% | 21.64%
Table 5: Performance of spoken term detection in Mboshi

Results are detailed in Table 4 for Kunwinjku and in Table 5 for Mboshi. DTW
has an advantage over P2W that it allows us to look deeply into the speech
collection and so to retrieve more items and increase the recall, while
decreasing precision.

P2W allows us to navigate into a limited number of symbols and matched words
from an initial lexicon. This method allows us to navigate only in the stream
of symbols automatically generated which makes the word matching results
highly dependant of the phones recognition performance. However, navigating
into written forms allows very accurate matches and a high precision since we
are matching only exact same forms between the lexicon and the unsegmented
stream of characters. The lower precision for Mboshi can be explained by the
fact that this language has tones which increases the number of confusable
vowels.

[9] pointed out the limitation of their method in terms of cross speaker
spoken term detection. To compare the two approaches on this aspect, we
analyze each true positive output: we check if the word matched is pronounced
by a same or different speaker that the query term. Even if we only use the
written forms of the queries for P2W, we also make the same analysis.

Figure 3:  Proportion of same-speaker/different-speaker retrieval in Kunwinjku
Figure 4:  Proportion of same-speaker/different-speaker retrieval in Mboshi

Figures 3 and 4 present the proportion of retrieved spoken term from same-
speaker or different-speaker. For a fair comparison, we also compute the
distribution of same/different speaker between the lexicons and the words to
be retrieved in the corpora (reference). We can see from Figures 3 and 4 that
P2W method follows the general distribution in the corpora while the baseline
DTW retrieves mostly terms pronounced by the same speaker.

Figure 5: Relative coverage of the combined methods, the recall of the
baselines includes the spoken lexicon

We mentioned in Section 2 that DTW and phone recognition have their own
strength. DTW will cope easily with spontaneous speech and sounds elision due
to co-articulation effects. Phone recognition allows us to avoid gathering
spoken query and retrieve terms with exact matching between written forms. To
highlight the complementary of the two methods, we analyse the intersection of
their true positives in figure 5. We show that for both corpora the
intersection of the true positives are small and combining the two methods can
help us increase the coverage of the transcription.

##  6 Taking advantage of phoneme transcription ambiguity

$token\leftarrow None$

$valid\leftarrow None$

$i\leftarrow 0$

while $i\leq confnet[0].length$ do

for each $phone\in confnet[i]$ do

if $confnet[i][phone]\in lexState.current.validPath$ then

$token\leftarrow token+confnet[i][phone]$

$lexState.current\leftarrow confnet[i][phone]$

if $lexState.current.isword$ then $valid\leftarrow token$

end if

if $savePoint=None$ then $savePoint\leftarrow i$

end if

break

else

if $valid\neq token$ then

$index\leftarrow savePoint$

$savePoint\leftarrow None$

end if

$lexState.current\leftarrow lexState.root$

$token\leftarrow None$

if $valid\neq None$ then return $valid$

end if

end if

end for

$i\leftarrow i+1$

end while

Algorithm 1 search of the phoneme confusion network

Allosaurus allows us to output a confusion network [22] of phonemes instead of
a simple phoneme transcription sequence. This graph contains the top $k$
hypotheses for each phone in the sequence, associated with a probability (Fig.
6b). In order to push the search further, we incorporate the words of the
lexicon in a trie and implement a simple search (see Algorithm 1). The idea is
to check in the confusion network ($confnet$) for each top $k$ phone from the
most likely to the least likely if it corresponds to a valid path in the
lexicon ($lexState$). If a given phone is recognized as a final state in the
lexicon, the corresponding word is kept as a candidate. If a followed path
cannot find a final state, the search starts back from the index corresponding
to the first state recognized. This is a basic search which allows us to
easily explore the network but could be optimized following a Viterbi
algorithm adapted for this task. An illustration of the search is shown in
Figure 6 where we start searching for manu. The search starts back from a
since no final state has been found. No phone is recognized as a valid state
until b. The search ends recognizing bun.

(a) lexicon

(b) confusion network

Figure 6: search of the phoneme confusion network 6b with lexicon stored in a
trie 6a

We applied this search on the top 5 phonemes applying a pruning of the network
based on two arbitrary thresholds (0.2 and 0.1). We then compute the same
evaluation described in Section 5 and report the results in Tables 6 and 7.

| recall-no-lex | recall | precision | F-score
---|---|---|---|---
baseline | 17.43% | 33.24% | 21.67% | 26.24%
P2W | - | 15.16% | 85.07% | 25.72%
P2W 0.2 | - | 19.15% | 74.23% | 30.45%
P2W 0.1 | - | 26.60% | 65.35% | 37.81%
Table 6: Results of the search for Kunwinjku | recall-no-lex | recall | precision | F-score
---|---|---|---|---
baseline | 15.47% | 21.18% | 13.55% | 16.53%
P2W | - | 13.07% | 62.91% | 21.64%
P2W 0.2 | - | 18.77% | 58.23% | 28.39%
P2W 0.1 | - | 23.74% | 47.54% | 31.67%
Table 7: Results of the search for Mboshi

We can see that a simple search allows us to boost the recall maintaining the
precision at an acceptable rate. We can also see that P2W with a pruning set
at 0.2 outperforms the DTW baseline in terms of recall when the spoken lexicon
is not included in the results.

##  7 Conclusion

Although traditional methods of spoken term detection are more robust in
spontaneous speech and cope more easily with speech elision due to
coarticulation effects, the phone recognition based approach appears to be
much more accurate mostly because of its speaker independence. Even if cleaner
data is to be privileged for fine-tuning the model for better recall, a noisy
transcription can still be usable. In the context of interactive
transcription, precision is to be privileged over recall in order to properly
assist the transcriber limiting the correction of wrong output.

The spoken lexicon required by DTW can be hard to collect: we saw that
differences of speaker between the corpus and the lexicon have a impact on the
final precision which force us to carefully select the example to be used and
extract them manually. A phone recognition based approach would only need a
written lexicon.

Phones recognition based methods give us the possibility of quickly and
precisely exploring the content of a given speech collection through simple
textual queries. The confusion network output by Allosaurus lets us enable a
deeper search, replacing a given phone by another. Such exploration
outperforms the DTW baseline in terms of recall, while maintaining high
precision.

##  8 Acknowledgements

We are grateful to the Bininj people of Northern Australia for the opportunity
to work in their community, and particularly to artists at Injalak Arts and
Craft (Gunbalanya) and to the Warddeken Rangers (Kabulwarnamyo, Manmoyi). This
research was covered by a research permit from the Northern Land Council,
ethics approved from CDU and was supported by the Australian government
through a PhD scholarship, and grants from the Australian Research Council and
the Indigenous Language and Arts Program.

## References

  * [1] C. Brinckmann, ``Transcription bottleneck of speech corpus exploitation,'' _Proceedings of the 2nd Colloquium on Lesser Used Languages and Computer Linguistics_ , pp. 165 – 179, 2009.
  * [2] D. Povey, A. Ghoshal, G. Boulianne, L. Burget, O. Glembek, N. Goel, M. Hannemann, P. Motlicek, Y. Qian, P. Schwarz, J. Silovsky, G. Stemmer, and K. Vesely, ``The kaldi speech recognition toolkit,'' in _IEEE 2011 Workshop on Automatic Speech Recognition and Understanding_. IEEE Signal Processing Society, Dec. 2011, iEEE Catalog No.: CFP11SRW-USB.
  * [3] S. Watanabe, T. Hori, S. Karita, T. Hayashi, J. Nishitoba, Y. Unno, N.-E. Y. Soplin, J. Heymann, M. Wiesner, N. Chen _et al._ , ``Espnet: End-to-end speech processing toolkit,'' _Proc. Interspeech 2018_ , pp. 2207–2211, 2018\.
  * [4] V. Gupta and G. Boulianne, ``Automatic transcription challenges for Inuktitut, a low-resource polysynthetic language,'' in _Proceedings of the 12th Language Resources and Evaluation Conference_ , 2020, pp. 2521–27.
  * [5] ——, ``Speech transcription challenges for resource constrained indigenous language Cree,'' in _Proceedings of the 1st Joint Workshop on Spoken Language Technologies for Under-Resourced Languages and Collaboration and Computing for Under-Resourced Languages (CCURL)_ , 2020, pp. 362–367.
  * [6] B. Foley, J. T. Arnold, R. Coto-Solano, G. Durantin, T. M. Ellison, D. van Esch, S. Heath, F. Kratochvil, Z. Maxwell-Smith, D. Nash _et al._ , ``Building speech recognition systems for language documentation: The coedl endangered language pipeline and inference system (elpis).'' in _SLTU_ , 2018, pp. 205–209.
  * [7] O. Adams, B. Galliot, G. Wisniewski, N. Lambourne, B. Foley, R. Sanders-Dwyer, J. Wiles, A. Michaud, S. Guillaume, L. Besacier _et al._ , ``User-friendly automatic transcription of low-resource languages: Plugging espnet into elpis,'' in _ComputEL-4: Fourth Workshop on the Use of Computational Methods in the Study of Endangered Languages_ , 2020.
  * [8] S. Bird, ``Sparse transcription,'' _Computational Linguistics_ , vol. 46, pp. 713–744, 2020.
  * [9] E. Le Ferrand, S. Bird, and L. Besacier, ``Enabling interactive transcription in an indigenous communitỳ,'' in _COLING 2020_ , 2020.
  * [10] X. Li, S. Dalmia, J. Li, M. Lee, P. Littell, J. Yao, A. Anastasopoulos, D. R. Mortensen, G. Neubig, A. W. Black _et al._ , ``Universal phone recognition with a multilingual allophone system,'' in _ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2020, pp. 8249–8253.
  * [11] H. Sakoe and S. Chiba, ``Dynamic programming algorithm optimization for spoken word recognition,'' _IEEE Transactions on Acoustics, Speech, and Signal Processing_ , vol. 26, pp. 43–49, 1978.
  * [12] R. Menon, H. Kamper, E. van der Westhuizen, J. Quinn, and T. Niesler, ``Feature exploration for almost zero-resource ASR-free keyword spotting using a multilingual bottleneck extractor and correspondence autoencoders,'' _Proceedings of Interspeech 2019_ , pp. 3475–3479, 2019.
  * [13] H. Kamper, M. Elsner, A. Jansen, and S. Goldwater, ``Unsupervised neural network based feature extraction using weak top-down constraints,'' in _2015 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2015, pp. 5818–22.
  * [14] S. Settle and K. Livescu, ``Discriminative acoustic word embeddings: Tecurrent neural network-based approaches,'' in _2016 IEEE Spoken Language Technology Workshop (SLT)_. IEEE, 2016, pp. 503–510.
  * [15] S. Settle, K. Levin, H. Kamper, and K. Livescu, ``Query-by-example search with discriminative neural acoustic word embeddings,'' _Proc. Interspeech 2017_ , pp. 2874–2878, 2017.
  * [16] O. Adams, T. Cohn, G. Neubig, H. Cruz, S. Bird, and A. Michaud, ``Evaluating phonemic transcription of low-resource tonal languages for language documentation,'' in _LREC 2018 (Language Resources and Evaluation Conference)_ , 2018, pp. 3356–3365.
  * [17] A. Michaud, O. Adams, T. A. Cohn, G. Neubig, and S. Guillaume, ``Integrating automatic transcription into the language documentation workflow: Experiments with na data and the persephone toolkit,'' 2018.
  * [18] P. L. Felt, ``Improving the effectiveness of machine-assisted annotation,'' Ph.D. dissertation, Brigham Young University-Provo, 2012.
  * [19] D. Mortensen, X. Li, P. Littell, A. Michaud, S. Rijhwani, A. Anastasopoulos, A. Black, F. Metze, and G. Neubig, ``Allovera: a multilingual allophone database,'' in _LREC 2020: 12th Language Resources and Evaluation Conference_ , 2020.
  * [20] T. Kisler, U. Reichel, and F. Schiel, ``Multilingual processing of speech via web services,'' _Computer Speech and Language_ , vol. 45, pp. 326–347, 2017\.
  * [21] P. Godard, G. Adda, M. Adda-Decker, J. Benjumea, L. Besacier, J. Cooper-Leavitt, G.-N. Kouarata, L. Lamel, H. Maynard, M. Müller _et al._ , ``A very low resource language speech corpus for computational language documentation experiments,'' _arXiv preprint arXiv:1710.03501_ , 2017\.
  * [22] L. Mangu, E. Brill, and A. Stolcke, ``Finding consensus in speech recognition: word error minimization and other applications of confusion networks,'' _Computer Speech & Language_, vol. 14, no. 4, pp. 373–400, 2000. [Online]. Available: https://doi.org/10.1006/csla.2000.0152