---
OA_place: publisher
OA_type: hybrid
_id: '22006'
abstract:
- lang: eng
text: Runtime monitoring checks, during execution, whether a partial signal produced
by a hybrid system satisfies its specification. Signal First-Order Logic (SFO)
offers expressive real-time specifications over such signals, but currently comes
only with Boolean semantics and has no tool support. We provide the first robustness-based
quantitative semantics for SFO, enabling the expression and evaluation of rich
real-time properties beyond the scope of existing formalisms such as Signal Temporal
Logic. To enable online monitoring, we identify a past-time fragment of SFO and
give a pastification procedure that transforms bounded-response SFO formulas into
equisatisfiable formulas in this fragment. We then develop an efficient runtime
monitoring algorithm for this past-time fragment and evaluate its performance
on a set of benchmarks, demonstrating the practicality and effectiveness of our
approach. To the best of our knowledge, this is the first publicly available prototype
for online quantitative monitoring of full SFO.
acknowledgement: We thank the anonymous reviewers for their helpful comments. This
work was supported by the European Research Council (ERC) Grants VAMOS (No. 101020093)
and HYPER (No. 101055412), and by the Advanced Research and Invention Agency under
the Safeguarded AI programme (MSAI-PR01-P047).
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Marek
full_name: Chalupa, Marek
id: 87e34708-d6c6-11ec-9f5b-9391e7be2463
last_name: Chalupa
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000-0002-2985-7724
- first_name: Naci E
full_name: Sarac, Naci E
id: 8C6B42F8-C8E6-11E9-A03A-F2DCE5697425
last_name: Sarac
- first_name: Zhengqi
full_name: Yu, Zhengqi
id: 20aa2ae8-f2f1-11ed-bbfa-8205053f1342
last_name: Yu
orcid: 0000-0002-4993-773X
citation:
ama: 'Chalupa M, Henzinger TA, Sarac NE, Yu E. Quantitative monitoring of Signal
First-Order logic. In: 27th International Symposium on Formal Methods.
Vol 16557. Springer Nature; 2026:214-233. doi:10.1007/978-3-032-26220-2_11'
apa: 'Chalupa, M., Henzinger, T. A., Sarac, N. E., & Yu, E. (2026). Quantitative
monitoring of Signal First-Order logic. In 27th International Symposium on
Formal Methods (Vol. 16557, pp. 214–233). Tokyo, Japan: Springer Nature. https://doi.org/10.1007/978-3-032-26220-2_11'
chicago: Chalupa, Marek, Thomas A Henzinger, Naci E Sarac, and Emily Yu. “Quantitative
Monitoring of Signal First-Order Logic.” In 27th International Symposium on
Formal Methods, 16557:214–33. Springer Nature, 2026. https://doi.org/10.1007/978-3-032-26220-2_11.
ieee: M. Chalupa, T. A. Henzinger, N. E. Sarac, and E. Yu, “Quantitative monitoring
of Signal First-Order logic,” in 27th International Symposium on Formal Methods,
Tokyo, Japan, 2026, vol. 16557, pp. 214–233.
ista: 'Chalupa M, Henzinger TA, Sarac NE, Yu E. 2026. Quantitative monitoring of Signal
First-Order logic. 27th International Symposium on Formal Methods. FM: Formal
Methods, LNCS, vol. 16557, 214–233.'
mla: Chalupa, Marek, et al. “Quantitative Monitoring of Signal First-Order Logic.”
27th International Symposium on Formal Methods, vol. 16557, Springer Nature,
2026, pp. 214–33, doi:10.1007/978-3-032-26220-2_11.
short: M. Chalupa, T.A. Henzinger, N.E. Sarac, E. Yu, in:, 27th International Symposium
on Formal Methods, Springer Nature, 2026, pp. 214–233.
conference:
end_date: 2026-05-22
location: Tokyo, Japan
name: 'FM: Formal Methods'
start_date: 2026-05-18
das_tickbox: '0'
date_created: 2026-06-14T22:01:44Z
date_published: 2026-05-18T00:00:00Z
date_updated: 2026-06-22T08:21:09Z
day: '18'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.1007/978-3-032-26220-2_11
ec_funded: 1
external_id:
arxiv:
- '2603.00728'
file:
- access_level: open_access
checksum: 7055199ecb985e9e2e272f4988827067
content_type: application/pdf
creator: dernst
date_created: 2026-06-22T08:18:41Z
date_updated: 2026-06-22T08:18:41Z
file_id: '22113'
file_name: 2026_LNCS_Chalupa.pdf
file_size: 849237
relation: main_file
success: 1
file_date_updated: 2026-06-22T08:18:41Z
has_accepted_license: '1'
intvolume: ' 16557'
keyword:
- Signal first-order logic
- Robustness-based quantitative semantics
- Online runtime monitoring
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '05'
oa: 1
oa_version: Published Version
page: 214-233
project:
- _id: 62781420-2b32-11ec-9570-8d9b63373d4d
call_identifier: H2020
grant_number: '101020093'
name: Vigilant Algorithmic Monitoring of Software
publication: 27th International Symposium on Formal Methods
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783032262196'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Quantitative monitoring of Signal First-Order logic
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 16557
year: '2026'
...
---
OA_place: publisher
_id: '10799'
abstract:
- lang: eng
text: "Because of the increasing popularity of machine learning methods, it is becoming
important to understand the impact of learned components on automated decision-making
systems and to guarantee that their consequences are beneficial to society. In
other words, it is necessary to ensure that machine learning is sufficiently trustworthy
to be used in real-world applications. This thesis studies two properties of machine
learning models that are highly desirable for the\r\nsake of reliability: robustness
and fairness. In the first part of the thesis we study the robustness of learning
algorithms to training data corruption. Previous work has shown that machine learning
models are vulnerable to a range\r\nof training set issues, varying from label
noise through systematic biases to worst-case data manipulations. This is an especially
relevant problem from a present perspective, since modern machine learning methods
are particularly data hungry and therefore practitioners often have to rely on
data collected from various external sources, e.g. from the Internet, from app
users or via crowdsourcing. Naturally, such sources vary greatly in the quality
and reliability of the\r\ndata they provide. With these considerations in mind,
we study the problem of designing machine learning algorithms that are robust
to corruptions in data coming from multiple sources. We show that, in contrast
to the case of a single dataset with outliers, successful learning within this
model is possible both theoretically and practically, even under worst-case data
corruptions. The second part of this thesis deals with fairness-aware machine
learning. There are multiple areas where machine learning models have shown promising
results, but where careful considerations are required, in order to avoid discrimanative
decisions taken by such learned components. Ensuring fairness can be particularly
challenging, because real-world training datasets are expected to contain various
forms of historical bias that may affect the learning process. In this thesis
we show that data corruption can indeed render the problem of achieving fairness
impossible, by tightly characterizing the theoretical limits of fair learning
under worst-case data manipulations. However, assuming access to clean data, we
also show how fairness-aware learning can be made practical in contexts beyond
binary classification, in particular in the challenging learning to rank setting."
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Nikola H
full_name: Konstantinov, Nikola H
id: 4B9D76E4-F248-11E8-B48F-1D18A9856A87
last_name: Konstantinov
orcid: 0009-0009-5204-7621
citation:
ama: Konstantinov NH. Robustness and fairness in machine learning. 2022. doi:10.15479/at:ista:10799
apa: Konstantinov, N. H. (2022). Robustness and fairness in machine learning.
Institute of Science and Technology Austria. https://doi.org/10.15479/at:ista:10799
chicago: Konstantinov, Nikola H. “Robustness and Fairness in Machine Learning.”
Institute of Science and Technology Austria, 2022. https://doi.org/10.15479/at:ista:10799.
ieee: N. H. Konstantinov, “Robustness and fairness in machine learning,” Institute
of Science and Technology Austria, 2022.
ista: Konstantinov NH. 2022. Robustness and fairness in machine learning. Institute
of Science and Technology Austria.
mla: Konstantinov, Nikola H. Robustness and Fairness in Machine Learning.
Institute of Science and Technology Austria, 2022, doi:10.15479/at:ista:10799.
short: N.H. Konstantinov, Robustness and Fairness in Machine Learning, Institute
of Science and Technology Austria, 2022.
corr_author: '1'
date_created: 2022-02-28T13:03:49Z
date_published: 2022-03-08T00:00:00Z
date_updated: 2026-04-07T14:19:48Z
day: '08'
ddc:
- '000'
degree_awarded: PhD
department:
- _id: GradSch
- _id: ChLa
doi: 10.15479/at:ista:10799
ec_funded: 1
file:
- access_level: open_access
checksum: 626bc523ae8822d20e635d0e2d95182e
content_type: application/pdf
creator: nkonstan
date_created: 2022-03-06T11:42:54Z
date_updated: 2022-03-06T11:42:54Z
file_id: '10823'
file_name: thesis.pdf
file_size: 4204905
relation: main_file
success: 1
- access_level: closed
checksum: e2ca2b88350ac8ea1515b948885cbcb1
content_type: application/x-zip-compressed
creator: nkonstan
date_created: 2022-03-06T11:42:57Z
date_updated: 2022-03-10T12:11:48Z
file_id: '10824'
file_name: thesis.zip
file_size: 22841103
relation: source_file
file_date_updated: 2022-03-10T12:11:48Z
has_accepted_license: '1'
keyword:
- robustness
- fairness
- machine learning
- PAC learning
- adversarial learning
language:
- iso: eng
month: '03'
oa: 1
oa_version: Published Version
page: '176'
project:
- _id: 2564DBCA-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '665385'
name: International IST Doctoral Program
publication_identifier:
isbn:
- 978-3-99078-015-2
issn:
- 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
related_material:
record:
- id: '10802'
relation: part_of_dissertation
status: public
- id: '10803'
relation: part_of_dissertation
status: public
- id: '6590'
relation: part_of_dissertation
status: public
- id: '8724'
relation: part_of_dissertation
status: public
status: public
supervisor:
- first_name: Christoph
full_name: Lampert, Christoph
id: 40C20FD2-F248-11E8-B48F-1D18A9856A87
last_name: Lampert
orcid: 0000-0001-8622-7887
title: Robustness and fairness in machine learning
type: dissertation
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
year: '2022'
...
---
_id: '10802'
abstract:
- lang: eng
text: "Addressing fairness concerns about machine learning models is a crucial step
towards their long-term adoption in real-world automated systems. While many approaches
have been developed for training fair models from data, little is known about
the robustness of these methods to data corruption. In this work we consider fairness-aware
learning under worst-case data manipulations. We show that an adversary can in
some situations force any learner to return an overly biased classifier, regardless
of the sample size and with or without degrading\r\naccuracy, and that the strength
of the excess bias increases for learning problems with underrepresented protected
groups in the data. We also prove that our hardness results are tight up to constant
factors. To this end, we study two natural learning algorithms that optimize for
both accuracy and fairness and show that these algorithms enjoy guarantees that
are order-optimal in terms of the corruption ratio and the protected groups frequencies
in the large data\r\nlimit."
acknowledgement: The authors thank Eugenia Iofinova and Bernd Prach for providing
feedback on early versions of this paper. This publication was made possible by
an ETH AI Center postdoctoral fellowship to Nikola Konstantinov.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Nikola H
full_name: Konstantinov, Nikola H
id: 4B9D76E4-F248-11E8-B48F-1D18A9856A87
last_name: Konstantinov
orcid: 0009-0009-5204-7621
- first_name: Christoph
full_name: Lampert, Christoph
id: 40C20FD2-F248-11E8-B48F-1D18A9856A87
last_name: Lampert
orcid: 0000-0002-4561-241X
citation:
ama: Konstantinov NH, Lampert C. Fairness-aware PAC learning from corrupted data.
Journal of Machine Learning Research. 2022;23:1-60.
apa: Konstantinov, N. H., & Lampert, C. (2022). Fairness-aware PAC learning
from corrupted data. Journal of Machine Learning Research. ML Research
Press.
chicago: Konstantinov, Nikola H, and Christoph Lampert. “Fairness-Aware PAC Learning
from Corrupted Data.” Journal of Machine Learning Research. ML Research
Press, 2022.
ieee: N. H. Konstantinov and C. Lampert, “Fairness-aware PAC learning from corrupted
data,” Journal of Machine Learning Research, vol. 23. ML Research Press,
pp. 1–60, 2022.
ista: Konstantinov NH, Lampert C. 2022. Fairness-aware PAC learning from corrupted
data. Journal of Machine Learning Research. 23, 1–60.
mla: Konstantinov, Nikola H., and Christoph Lampert. “Fairness-Aware PAC Learning
from Corrupted Data.” Journal of Machine Learning Research, vol. 23, ML
Research Press, 2022, pp. 1–60.
short: N.H. Konstantinov, C. Lampert, Journal of Machine Learning Research 23 (2022)
1–60.
corr_author: '1'
date_created: 2022-02-28T14:05:42Z
date_published: 2022-05-01T00:00:00Z
date_updated: 2026-04-07T14:19:48Z
day: '01'
ddc:
- '004'
department:
- _id: ChLa
external_id:
arxiv:
- '2102.06004'
file:
- access_level: open_access
checksum: 9cac897b54a0ddf3a553a2c33e88cfda
content_type: application/pdf
creator: kschuh
date_created: 2022-07-12T15:08:28Z
date_updated: 2022-07-12T15:08:28Z
file_id: '11570'
file_name: 2022_JournalMachineLearningResearch_Konstantinov.pdf
file_size: 551862
relation: main_file
success: 1
file_date_updated: 2022-07-12T15:08:28Z
has_accepted_license: '1'
intvolume: ' 23'
keyword:
- Fairness
- robustness
- data poisoning
- trustworthy machine learning
- PAC learning
language:
- iso: eng
month: '05'
oa: 1
oa_version: Published Version
page: 1-60
publication: Journal of Machine Learning Research
publication_identifier:
eissn:
- 1533-7928
issn:
- 1532-4435
publication_status: published
publisher: ML Research Press
quality_controlled: '1'
related_material:
record:
- id: '13241'
relation: shorter_version
status: public
- id: '10799'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Fairness-aware PAC learning from corrupted data
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 23
year: '2022'
...