Search

Medical diagnosis is a crucial task in the medical field, in terms of providing accurate classification and respective treatments. Having near-precise decisions based on correct diagnosis can affect a patient's life itself, and may extremely result in a catastrophe if not classified correctly. Several traditional machine learning (ML), such as support vector machines (SVMs) and logistic regression, and state-of-the-art tabular deep learning (DL) methods, including TabNet and TabTransformer, have been proposed and used over tabular medical datasets. Additionally, due to the superior performances, lower computational costs, and easier optimization over different tasks, ensemble methods have been used in the field more recently. They offer a powerful alternative in terms of providing successful medical decision-making processes in several diagnosis tasks. In this study, we investigated the benefits of ensemble methods, especially the Gradient Boosting Decision Tree (GBDT) algorithms in medical classification tasks over tabular data, focusing on XGBoost, CatBoost, and LightGBM. The experiments demonstrate that GBDT methods outperform traditional ML and deep neural network architectures and have the highest average rank over several benchmark tabular medical diagnosis datasets. Furthermore, they require much less computational power compared to DL models, creating the optimal methodology in terms of high performance and lower complexity., Comment: 8 pages, 2 figures

We introduce a new concept, the APN-defect, which can be thought of as measuring the distance of a given function $G:\mathbb{F}_{2^n} \rightarrow \mathbb{F}_{2^n}$ to the set of almost perfect nonlinear (APN) functions. This concept is motivated by the detailed analysis of the differential behaviour of non-APN functions (of low differential uniformity) $G$ using the so-called difference squares. We describe the relations between the APN-defect and other recent concepts of similar nature. Upper and lower bounds for the values of APN-defect for several classes of functions of interest, including Dembowski-Ostrom polynomials are given. Its exact values in some cases are also calculated. The difference square corresponding to a modification of the inverse function is determined, its APN-defect depending on $n$ is evaluated and the implications are discussed. In the forthcoming second part of this work we further examine modifications of the inverse function. We also study modifications of classes of functions of low uniformity over infinitely many extensions of $\mathbb{F}_{2^n}$. We present quantitative results on their differential behaviour, especially in connection with their APN-defects., Comment: 33 pages, 1 table (the table is not separate, it is included in the tex file))

Much of learning theory is concerned with the design and analysis of probably approximately correct (PAC) learners. The closely related transductive model of learning has recently seen more scrutiny, with its learners often used as precursors to PAC learners. Our goal in this work is to understand and quantify the exact relationship between these two models. First, we observe that modest extensions of existing results show the models to be essentially equivalent for realizable learning for most natural loss functions, up to low order terms in the error and sample complexity. The situation for agnostic learning appears less straightforward, with sample complexities potentially separated by a $\frac{1}{\epsilon}$ factor. This is therefore where our main contributions lie. Our results are two-fold: 1. For agnostic learning with bounded losses (including, for example, multiclass classification), we show that PAC learning reduces to transductive learning at the cost of low-order terms in the error and sample complexity via an adaptation of the reduction of arXiv:2304.09167 to the agnostic setting. 2. For agnostic binary classification, we show the converse: transductive learning is essentially no more difficult than PAC learning. Together with our first result this implies that the PAC and transductive models are essentially equivalent for agnostic binary classification. This is our most technical result, and involves two steps: A symmetrization argument on the agnostic one-inclusion graph (OIG) of arXiv:2309.13692 to derive the worst-case agnostic transductive instance, and expressing the error of the agnostic OIG algorithm for this instance in terms of the empirical Rademacher complexity of the class. We leave as an intriguing open question whether our second result can be extended beyond binary classification to show the transductive and PAC models equivalent more broadly.

Protein phosphorylation involves the reversible modification of a protein (substrate) residue by another protein (kinase). Liquid chromatography-mass spectrometry studies are rapidly generating massive protein phosphorylation datasets across multiple conditions. Researchers then must infer kinases responsible for changes in phosphosites of each substrate. However, tools that infer kinase-substrate interactions (KSIs) are not optimized to interactively explore the resulting large and complex networks, significant phosphosites, and states. There is thus an unmet need for a tool that facilitates user-friendly analysis, interactive exploration, visualization, and communication of phosphoproteomics datasets. We present PhosNetVis, a web-based tool for researchers of all computational skill levels to easily infer, generate and interactively explore KSI networks in 2D or 3D by streamlining phosphoproteomics data analysis steps within a single tool. PhostNetVis lowers barriers for researchers in rapidly generating high-quality visualizations to gain biological insights from their phosphoproteomics datasets. It is available at: https://gumuslab.github.io/PhosNetVis/, Comment: Added new author, added references, changed fig1 and fig4

We introduce a novel definition for a small set R of k points being "representative" of a larger set in a metric space. Given a set V (e.g., documents or voters) to represent, and a set C of possible representatives, our criterion requires that for any subset S comprising a theta fraction of V, the average distance of S to their best theta*k points in R should not be more than a factor gamma compared to their average distance to the best theta*k points among all of C. This definition is a strengthening of proportional fairness and core fairness, but - different from those notions - requires that large cohesive clusters be represented proportionally to their size. Since there are instances for which - unless gamma is polynomially large - no solutions exist, we study this notion in a resource augmentation framework, implicitly stating the constraints for a set R of size k as though its size were only k/alpha, for alpha > 1. Furthermore, motivated by the application to elections, we mostly focus on the "ordinal" model, where the algorithm does not learn the actual distances; instead, it learns only for each point v in V and each candidate pairs c, c' which of c, c' is closer to v. Our main result is that the Expanding Approvals Rule (EAR) of Aziz and Lee is (alpha, gamma) representative with gamma <= 1 + 6.71 * (alpha)/(alpha-1). Our results lead to three notable byproducts. First, we show that the EAR achieves constant proportional fairness in the ordinal model, giving the first positive result on metric proportional fairness with ordinal information. Second, we show that for the core fairness objective, the EAR achieves the same asymptotic tradeoff between resource augmentation and approximation as the recent results of Li et al., which used full knowledge of the metric. Finally, our results imply a very simple single-winner voting rule with metric distortion at most 44., Comment: 24 pages, Accepted to AAAI 24

Motivated by the growing interest in correlation-robust stochastic optimization, we investigate stochastic selection problems beyond independence. Specifically, we consider the instructive case of pairwise-independent priors and matroid constraints. We obtain essentially-optimal bounds for contention resolution and prophet inequalities. The impetus for our work comes from the recent work of Caragiannis et al., who derived a constant-approximation for the single-choice prophet inequality with pairwise-independent priors. For general matroids, our results are tight and largely negative. For both contention resolution and prophet inequalities, our impossibility results hold for the full linear matroid over a finite field. We explicitly construct pairwise-independent distributions which rule out an omega(1/Rank)-balanced offline CRS and an omega(1/log Rank)-competitive prophet inequality against the (usual) oblivious adversary. For both results, we employ a generic approach for constructing pairwise-independent random vectors -- one which unifies and generalizes existing pairwise-independence constructions from the literature on universal hash functions and pseudorandomness. Specifically, our approach is based on our observation that random linear maps turn linear independence into stochastic independence. We then examine the class of matroids which satisfy the so-called partition property -- these include most common matroids encountered in optimization. We obtain positive results for both online contention resolution and prophet inequalities with pairwise-independent priors on such matroids, approximately matching the corresponding guarantees for fully independent priors. These algorithmic results hold against the almighty adversary for both problems., Comment: 44 pages, 2 figures, Accepted to STOC 24. In the metadata, mathematical expressions have been converted to plain text for simplicity and clarity

We study one generator quasi-cyclic codes and four-circulant codes, which are also quasi-cyclic but have two generators. We state the hull dimensions for both classes of codes in terms of the polynomials in their generating elements. We prove results such as the hull dimension of a four-circulant code is even and one-dimensional hull for double-circulant codes, which are special one generator codes, is not possible when the alphabet size $q$ is congruent to 3 mod 4. We also characterize linear complementary pairs among both classes of codes. Computational results on the code families in consideration are provided as well., Comment: 16 pages, 8 tables

The Euclidean hull of a linear code $C$ is defined as $C\cap C^{\perp}$, where $C^\perp$ denotes the dual of $C$ under the Euclidean inner product. A linear code with zero hull dimension is called a linear complementary dual (LCD) code. A pair $(C, D)$ of linear codes of length $n$ over $\mathbb{F}_q$ is called a linear complementary pair (LCP) of codes if $C\oplus D=\mathbb{F}_q^n$. In this paper, we give a characterization of LCD and LCP of cyclic codes of length $q^m-1$, $m \geq 1$, over the finite field $\mathbb{F}_q$ in terms of their basic dual zeros and their trace representations. We also formulate the hull dimension of a cyclic code of arbitrary length over $\mathbb{F}_q$ with respect to its basic dual zero. Moreover, we provide a general formula for the dimension of the intersection of two cyclic codes of arbitrary length over $\mathbb{F}_q$ based on their basic dual zeros.

Motivated by recent progress on stochastic matching with few queries, we embark on a systematic study of the sparsification of stochastic packing problems (SPP) more generally. Specifically, we consider SPPs where elements are independently active with a probability p, and ask whether one can (non-adaptively) compute a sparse set of elements guaranteed to contain an approximately optimal solution to the realized (active) subproblem. We seek structural and algorithmic results of broad applicability to such problems. Our focus is on computing sparse sets containing on the order of d feasible solutions to the packing problem, where d is linear or at most poly. in 1/p. Crucially, we require d to be independent of the any parameter related to the ``size'' of the packing problem. We refer to d as the degree of the sparsifier, as is consistent with graph theoretic degree in the special case of matching. First, we exhibit a generic sparsifier of degree 1/p based on contention resolution. This sparsifier's approximation ratio matches the best contention resolution scheme (CRS) for any packing problem for additive objectives, and approximately matches the best monotone CRS for submodular objectives. Second, we embark on outperforming this generic sparsifier for matroids, their intersections and weighted matching. These improved sparsifiers feature different algorithmic and analytic approaches, and have degree linear in 1/p. In the case of a single matroid, our sparsifier tends to the optimal solution. For weighted matching, we combine our contention-resolution-based sparsifier with technical approaches of prior work to improve the state of the art ratio from 0.501 to 0.536. Third, we examine packing problems with submodular objectives. We show that even the simplest such problems do not admit sparsifiers approaching optimality., Comment: 43 pages, 2 figures