Tomasz Steifer, PhD

Department of Experimental Mechanics (ZMD)
Division of Non-Destructive Testing (PBN)
Laboratory of Professional Electronics
position: Assistant Professor
telephone: (+48) 22 826 12 81 ext.: 462
room: 538
e-mail: tsteifer
personal site: http://bluebox.ippt.pan.pl/~tsteifer/

Doctoral thesis
2020-10-15Computable prediction of infinite binary sequences with zero one loss  (Instytut Podstaw Informatyki PAN)
supervisor -- Łukasz Dębowski, PhD, DSc, IPI PAN
supervisor -- Prof. Dr. Dariusz Kalociński, UW
1448 
Recent publications
1.Dębowski Ł., Steifer T., UNIVERSAL CODING AND PREDICTION ON ERGODIC RANDOM POINTS, Bulletin of Symbolic Logic, ISSN: 1079-8986, DOI: 10.1017/bsl.2022.18, Vol.28, No.3, pp.387-412, 2022
Abstract:

Suppose that we have a method which estimates the conditional probabilities of some unknown stochastic source and we use it to guess which of the outcomes will happen. We want to make a correct guess as often as it is possible. What estimators are good for this? In this work, we consider estimators given by a familiar notion of universal coding for stationary ergodic measures, while working in the framework of algorithmic randomness, i.e., we are particularly interested in prediction of Martin-Löf random points. We outline the general theory and exhibit some counterexamples. Completing a result of Ryabko from 2009 we also show that universal probability measure in the sense of universal coding induces a universal predictor in the prequential sense. Surprisingly, this implication holds true provided the universal measure does not ascribe too low conditional probabilities to individual symbols. As an example, we show that the Prediction by Partial Matching (PPM) measure satisfies this requirement with a large reserve.

Keywords:

algorithmic randomness, stationary ergodic processes, universal coding, universal prediction, prediction by partial matching

Affiliations:
Dębowski Ł.-IPPT PAN
Steifer T.-IPPT PAN
2.Steifer T., A note on the learning-theoretic characterizations of randomness and convergence, The Review of Symbolic Logic, ISSN: 1755-0203, DOI: 10.1017/S1755020321000125, pp.1-16, 2021
Abstract:

Recently, a connection has been established between two branches of computability theory, namely between algorithmic randomness and algorithmic learning theory. Learning-theoretical characterizations of several notions of randomness were discovered. We study such characterizations based on the asymptotic density of positive answers. In particular, this note provides a new learning-theoretic definition of weak 2-randomness, solving the problem posed by (Zaffora Blando, Rev. Symb. Log. 2019). The note also highlights the close connection between these characterizations and the problem of convergence on random sequences.

Keywords:

algorithmic randomness, learning theory, effectivization

Affiliations:
Steifer T.-IPPT PAN
3.Steifer T., Lewandowski M., Ultrasound tissue characterization based on the Lempel–Ziv complexity with application to breast lesion classification, Biomedical Signal Processing and Control, ISSN: 1746-8094, DOI: 10.1016/j.bspc.2019.02.020, Vol.51, pp.235-242, 2019
Abstract:

Building upon the recent successes in the application of information-theoretic concepts (e.g. Shannon entropy) in quantitative ultrasound, the authors propose a novel tissue characterization method based on the Lempel–Ziv complexity. In this procedure, standard ultrasound B-Mode images are mapped onto words over finite alphabets before the corresponding Lempel–Ziv complexity of ultrasound images is calculated. Such complexity metric may be used to differentiate between types of tissues. Here, the method is utilized as a binary classifier for the malignancy of breast lesions. The method is tested on OASBUD – an open-access breast lesions image database. Images of 48 malignant and 48 benign lesions were used – two images for each lesion. The new procedure slightly outperforms the state-of-art classifier based on pixel entropy as measured in the size of area under the receiver operating curve (ROC AUC), which suggests that it may serve as a basis for computer-assisted breast cancer ultrasound diagnosis and possibly in other standard applications of the quantitative ultrasound.

Keywords:

quantitative ultrasound, tissue characterization, speckles, breast cancer, Lempel–Ziv complexity, applied information theory, space-filling curves

Affiliations:
Steifer T.-IPPT PAN
Lewandowski M.-IPPT PAN
4.Kalociński D., Steifer T., On unstable and unoptimal prediction, MATHEMATICAL LOGIC QUARTERLY, ISSN: 1521-3870, DOI: 10.1002/malq.201800085, Vol.65, No.2, pp.218-227, 2019
Abstract:

We consider the notion of prediction functions (or predictors) studied before in the context of randomness and stochasticity by Ko, and later by Ambos‐Spies and others. Predictor is a total computable function which tries to predict bits of some infinite binary sequence. The prediction error is defined as the limit of the number of incorrect answers divided by the number of answers given so far. We discuss indefiniteness of prediction errors for weak 1‐generics and show that this phenomenon affects certain c.e. sequences as well. On the other hand, a notion of optimal predictor is considered. It is shown that there is a sequence for which increasingly better predictors exist but for which no predictor is optimal.

Affiliations:
Kalociński D.-University of Warsaw (PL)
Steifer T.-IPPT PAN
5.Lewandowski M., Walczak M., Steifer T., Zastosowanie metody pełnej akwizycji macierzy do wizualizacji wad w technice UT Phased-Array, PRZEGLĄD SPAWALNICTWA, ISSN: 0033-2364, Vol.88, No.10, pp.43-45, 2016
Abstract:

Ultradźwiękowe systemy Phased-Array pozwalają na różne tryby skanowania i wizualizacji wad oraz zapewniają wyższą jakość inspekcji niż tradycyjne systemy jednokanałowe. Kolejnym krokiem w rozwoju tych systemów będzie metoda akwizycji pełnej macierzy oraz zaawansowane algorytmy rekonstrukcji obrazów. W artykule przedstawiono zasady działania tych technik oraz wymagania jakie stawiają one przed systemami akwizycji i przetwarzania sygnałów. Zaprezentowano także badawczy system Uniwersalnej Platformy Ultradźwiękowej, który został opracowany specjalnie do testowania i praktycznego wdrażania tych metod. Platforma posłużyła do badań i porównania dwóch metod rekonstrukcji przy wykorzystaniu akwizycji pełnej macierzy – metody STA (Synthetic Transmit Aperture) i metody PWI (Plane Wave Imaging).

Keywords:

UT Phased-Array, akwizycja pełnej macierzy, syntetyczna apertura

Affiliations:
Lewandowski M.-IPPT PAN
Walczak M.-IPPT PAN
Steifer T.-IPPT PAN

Conference papers
1.Kozachinskiy A., Steifer T., Simple Online Learning with Consistent Oracle, COLT 2024, 37th Annual Conference on Learning Theory, 2024-06-30/07-03, Edmonton (CA), Vol.247, pp.1-16, 2024
Abstract:

We consider online learning in the model where a learning algorithm can access the class only via the consistent oracle—an oracle, that, at any moment, can give a function from the class that agrees with all examples seen so far. This model was recently considered by Assos et al. (COLT’23). It is motivated by the fact that standard methods of online learning rely on computing the Littlestone dimension of subclasses, a computationally intractable problem. Assos et al. gave an online learning algorithm in this model that makes at most Cd mistakes on classes of Littlestone dimension d, for some absolute unspecified constant C > 0. We give a novel algorithm that makes at most O(256d) mistakes. Our proof is significantly simpler and uses only very basic properties of the Littlestone dimension. We also show that there exists no algorithm in this model that makes less than 3d mistakes. Our algorithm (as well as the algorithm of Assos et al.) solves an open problem by Hasrati and Ben-David (ALT’23). Namely, it demonstrates that every class of finite Littlestone dimension with recursively enumerable representation admits a computable online learner (that may be undefined on unrealizable samples).

Keywords:

Online learning, consistent oracle, Littlestone dimension

Affiliations:
Kozachinskiy A.-other affiliation
Steifer T.-IPPT PAN
2.Delle Rose V., Kozachinskiy A., Rojas C., Steifer T., Find a witness or shatter: the landscape of computable PAC learning, COLT 2023, The Thirty Sixth Annual Conference on Learning Theory, 2023-07-12/07-15, Bangalore (IN), No.195, pp.1-14, 2023
Abstract:

This paper contributes to the study of CPAC learnability—a computable version of PAC learning—by solving three open questions from recent papers. Firstly, we prove that every improperly CPAC learnable class is contained in a class which is properly CPAC learnable with polynomial sample complexity. This confirms a conjecture by Agarwal et al (COLT 2021). Secondly, we show that there exists a decidable class of hypotheses which is properly CPAC learnable, but only with uncomputably fast-growing sample complexity. This solves a question from Sterkenburg (COLT2022). Finally, we construct a decidable class of finite Littlestone dimension which is not improperly CPAC learnable, strengthening a recent result of Sterkenburg (2022) and answering a question posed by Hasrati and Ben-David (ALT 2023). Together with previous work, our results provide a complete landscape for the learnability problem in the CPAC setting

Keywords:

PAC learnability, CPAC learnability, VC dimension, Littlestone dimension, computability, foundations of machine learning

Affiliations:
Delle Rose V.-University of Siena (IT)
Kozachinskiy A.-other affiliation
Rojas C.-other affiliation
Steifer T.-IPPT PAN
3.Barceló P., Duarte M., Rojas C., Steifer T., No Agreement Without Loss: Learning and Social Choice in Peer Review, ECAI 2023, 26th European Conference on Artificial Intelligence, 2023-09-30/10-04, Kraków (PL), DOI: 10.3233/FAIA230270, pp.190-197, 2023
Abstract:

In peer review systems, reviewers are often asked to evaluate various features of submissions, such as technical quality or novelty. A score is given to each of the predefined features and based on these the reviewer has to provide an overall quantitative recommendation. It may be assumed that each reviewer has her own mapping from the set of features to a recommendation, and that different reviewers have different mappings in mind. This introduces an element of arbitrariness known as commensuration bias. In this paper we discuss a framework, introduced by Noothigattu, Shah and Procaccia, and then applied by the organizers of the AAAI 2022 conference. Noothigattu, Shah and Procaccia proposed to aggregate reviewer’s mapping by minimizing certain loss functions, and studied axiomatic properties of this approach, in the sense of social choice theory. We challenge several of the results and assumptions used in their work and report a number of negative results. On the one hand, we study a trade-off between some of the axioms proposed and the ability of the method to properly capture agreements of the majority of reviewers. On the other hand, we show that dropping a certain unrealistic assumption has dramatic effects, including causing the method to be discontinuous.

Affiliations:
Barceló P.-other affiliation
Duarte M.-other affiliation
Rojas C.-other affiliation
Steifer T.-IPPT PAN
4.Bienvenu L., Delle Rose V., Steifer T., Probabilistic vs deterministic gamblers, STACS 2022, 39th International Symposium on Theoretical Aspects of Computer Science, 2022-03-15/03-18, Marseille (FR), DOI: 10.4230/LIPIcs.STACS.2022.11, pp.11-1-13, 2022
Abstract:

Can a probabilistic gambler get arbitrarily rich when all deterministic gamblers fail? We study this problem in the context of algorithmic randomness, introducing a new notion – almost everywhere computable randomness. A binary sequence X is a.e. computably random if there is no probabilistic computable strategy which is total and succeeds on X for positive measure of oracles. Using the fireworks technique we construct a sequence which is partial computably random but not a.e. computably random. We also prove the separation between a.e. computable randomness and partial computable randomness, which happens exactly in the uniformly almost everywhere dominating Turing degrees.

Keywords:

algorithmic randomness, martingales, probabilistic computation, almost everywhere domination

Affiliations:
Bienvenu L.-Université de Bordeaux (FR)
Delle Rose V.-University of Siena (IT)
Steifer T.-IPPT PAN
5.Steifer T., Simple betting and stochasticity, CiE 2021, Connecting with Computability, 2021-07-05/07-09, Ghent (BE), DOI: 10.1007/978-3-030-80049-9_42, No.12813, pp.424-433, 2021
Abstract:

A sequence of zeros and ones is called Church stochastic if all subsequences chosen in an effective manner satisfy the law of large numbers with respect to the uniform measure. This notion may be independently defined by means of simple martingales, i.e., martingales with restricted (constant) wagers (hence, simply random sequences). This paper is concerned with generalization of Church stochasticity for arbitrary (possibly non-stationary) measures. We compare two ways of doing this: (i) via a natural extension of the law of large numbers (for non-i.i.d. processes) and (ii) via restricted martingales, i.e., by redefining simple randomness for arbitrary measures. It is shown that in the general case of non-uniform measures the respective notions of stochasticity do not coincide but the first one is contained in the second.

Affiliations:
Steifer T.-IPPT PAN
6.Kalociński D., Steifer T., An Almost Perfectly Predictable Process with No Optimal Predictor, IEEE-ISIT, IEEE International Symposium on Information Theory, 2019-07-07/07-12, Paryż (FR), DOI: 10.1109/ISIT.2019.8849587, pp.2504-2508, 2019
Abstract:

A novel kind of a negative result is presented for the problem of computable prediction. A non-stationary binary stochastic process is constructed for which almost surely no effective method of prediction achieves the infimum of prediction errors defined as the normalized Hamming distance between the sequence of predictions and the realization of the process. Yet it is shown that this process may be effectively predicted almost surely up to an arbitrarily small error since the infimum of prediction errors is zero.

Affiliations:
Kalociński D.-University of Warsaw (PL)
Steifer T.-IPPT PAN
7.Lewandowski M., Walczak M., Witek B., Rozbicki J., Steifer T., A GPU-Based Portable Phased-Array System with Full-Matrix Capture, IUS 2018, IEEE International Ultrasonics Symposium, 2018-10-22/10-25, KOBE (JP), DOI: 10.1109/ULTSYM.2018.8579964, pp.1-3, 2018
Abstract:

The widely adopted ultrasound Phased-Array (PA) systems for nondestructive testing (NDT) use standard beamforming for line-by-line image creation. The introduction of the new full-matrix capture (FMC) technique enables the implementation of advanced processing algorithms (e.g. the total focusing method, multi-pass adaptive techniques). However, the limited availability of portable PA systems with FMC capabilities prevents widespread introduction. Our goal was to demonstrate the feasibility of a portable PA solution with FMC and advanced processing with the help of a mobile GPU. Using an OEM ultrasound front-end module (us4us Ltd., Poland), we integrated a complete PA system with an embedded Nvidia Tegra X2 module. An external probe adapter enables a direct connection to commercial Olympus-NDT PA probes with up to 128-elements (32-element active RX aperture). The system is fully programmable, both in the front-end (TX/RX schemes, acquisition parameters), as well as in the digital signal processing chain. Raw RF data is acquired and transferred to mobile GPU memory for processing. The algorithm can be conveniently implemented using a standard Nvidia CUDA toolkit. We implemented real-time B-mode imaging with the total focusing method for demonstration purposes. The presented all-in-one system is a fully flexible tool for the research and evaluation of novel Phased-Array FMC methods and complex signal processing algorithms. An extended programmability and real-time access to raw channel data allows to create custom solutions specifically dedicated to any one NDT application. Mobile GPU parallel processing provides a strong enough performance for real-time imaging. Its small size and low-power consumption make the system an ideal candidate for a portable industrial flaw detector with advanced processing.

Affiliations:
Lewandowski M.-IPPT PAN
Walczak M.-IPPT PAN
Witek B.-IPPT PAN
Rozbicki J.-IPPT PAN
Steifer T.-IPPT PAN
8.Rozbicki J., Witek B., Steifer T., Lewandowski M., Doppler-based blood pressure measurement system for patients supported by a continuous-flow rotary left ventricular assist device, IUS 2017, IEEE International Ultrasonics Symposium, 2017-09-06/09-09, Washington (US), DOI: 10.1109/ULTSYM.2017.8091990, pp.1-4, 2017
Abstract:

The medical management of patients with continuous-flow left ventricular assist devices (LVADs) requires frequent measurement and analysis of various physiological parameters. Among the most important is blood pressure (BP), which cannot be reliably measured by the standard oscillometric method because of an impaired pulsation due to continuous flow. The objective of this work is to show the feasibility of ultrasound-based BP measurement in a portable, easy to use device for patients with LVAD in home-based rehabilitation environments, enabling long-term remote monitoring. We have implemented a BP measurement system which uses continuous wave (CW) Doppler ultrasound for blood flow detection. The system is based on a standard cuff design with custom analog CW circuitry connected to a high-performance, low-power 32-bit microcontroller (ARM Cortex-M7). The uC is responsible for system control, as well as Doppler signal acquisition and processing. A dedicated ultrasound probe equipped with an elastic strap is placed over the radial artery. In the target solution, the cuff pressure and CW signal will be analyzed in real-time to provide systolic and/or mean blood pressure. At present, we have acquired raw signals for off-line analysis. The system was tested in clinical experiments both on healthy patients and patients with three types of commercially available LVADs (HeartWare, HeartMate II and HeartMate III). The observed morphology of Doppler signals in patients with LVADs was much more variable between patients and pumps. In most cases, we were able to estimate the systolic pressure, but the measurement of diastolic pressure was not conclusive. We observed variable blood flow patterns generated by the Lavare cycle (a periodic speed modulation feature of some LVADs), which further complicates the estimation. A prototype of an automatic BP measuring device for patients with rotary LVADs has been demonstrated. In the next step, we are planning an animal validation study with invasive blood pressure monitoring

Keywords:

Biomedical monitoring, Doppler effect, Blood pressure, Blood, Pressure measurement, Ultrasonic variables measurement, Standards

Affiliations:
Rozbicki J.-IPPT PAN
Witek B.-IPPT PAN
Steifer T.-IPPT PAN
Lewandowski M.-IPPT PAN
9.Lewandowski M., Walczak M., Witek B., Steifer T., A GPU-based Ultrasound Phased-Array Research System for Non-destructive Testing, IUS 2016, IEEE International Ultrasonics Symposium, 2016-09-18/09-21, Tours (FR), DOI: 10.1109/ULTSYM.2016.7728843, pp.1-4, 2016
Abstract:

Ultrasound Phased-Array (PA) systems for nondestructive testing (NDT) use standard beamforming for line-byline image creation. New methods utilizing full-matrix capture (FMC) enable the application of advance processing algorithms, such as the total focusing method and multi-pass adaptive techniques for enhanced flaw visualization. The effective FMC data acquisition and its real-time processing require a very high data throughput and powerful computational resources. Most commercial PA systems support some form of FMC acquisition, but the limited external data bandwidth prevents this mode of operation from being useful. We have developed a fully programmable ultrasound research system capable of performing FMC data acquisition and image reconstruction with a high framerate. The ultrasound platform is supporting up to 192 parallel TX/RX electronics channels integrated with an embedded control PC and a GPU cluster for parallel processing. The implemented software libraries give the end-user control over TX/RX schemes, the acquisition process and signal processing algorithms. This all-in-one system is a fully flexible tool for the research and evaluation of novel Phased-Array FMC imaging methods and complex signal processing algorithms.

Keywords:

GPU, ultrasound, Phased-Array

Affiliations:
Lewandowski M.-IPPT PAN
Walczak M.-IPPT PAN
Witek B.-IPPT PAN
Steifer T.-IPPT PAN

Patents
Filing No./Date
Filing Publication
Autor(s)
Title
Protection Area, Applicant Name
Patent Number
Date of Grant
pdf
443063
2022-12-06
-
-
Lewandowski M. J., Rozbicki J., Witek B., Steifer T.
Sposób automatycznego pomiaru ciśnienia krwi
PL, Instytut Podstawowych Problemów Techniki PAN
-
-
-