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, 2024Abstract: 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. |
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, 2023Abstract: 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 |
| |
3. |
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, 2023Abstract: 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 |
| |
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, 2022Abstract: 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, 2021Abstract: 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:
| |
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, 2019Abstract: 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, 2018Abstract: 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, 2017Abstract: 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, 2016Abstract: 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 |
| |