Consider the following prediction problem. Assume that there is a block box that produces bits according to some unknown computable distribution on the binary tree. We know first $n$ bits $x_1 x_2 \ldots x_n$. We want to know the probability of the event that that the next bit is equal to $1$. Solomonoff suggested to use universal semimeasure $m$ for solving this task. He proved that for every computable distribution $P$ and for every $b \in \{0,1\}$ the following holds: $$\sum_{n=1}^{\infty}\sum_{x: l(x)=n} P(x) (P(b | x) - m(b | x))^2 < \infty\ .$$ However, Solomonoff's method has a negative aspect: Hutter and Muchnik proved that there are an universal semimeasure $m$, computable distribution $P$ and a random (in Martin-L{\"o}f sense) sequence $x_1 x_2\ldots$ such that $\lim_{n \to \infty} P(x_{n+1} | x_1\ldots x_n) - m(x_{n+1} | x_1\ldots x_n) \nrightarrow 0$. We suggest a new way for prediction. For every finite string $x$ we predict the new bit according to the best (in some sence) distribution for $x$. We prove the similar result as Solomonoff theorem for our way of prediction. Also we show that our method of prediction has no that negative aspect as Solomonoff's method.
相關內容
Markov proved that there exists an unrecognizable 4-manifold, that is, a 4-manifold for which the homeomorphism problem is undecidable. In this paper we consider the question how close we can get to S^4 with an unrecognizable manifold. One of our achievements is that we show a way to remove so-called Markov's trick from the proof of existence of such a manifold. This trick contributes to the complexity of the resulting manifold. We also show how to decrease the deficiency (or the number of relations) in so-called Adian-Rabin set which is another ingredient that contributes to the complexity of the resulting manifold. Altogether, our approach allows to show that the connected sum #_9(S^2 x S^2) is unrecognizable while the previous best result is the unrecognizability of #_12(S^2 x S^2) due to Gordon.
In situations where both extreme and non-extreme data are of interest, modelling the whole data set accurately is important. In a univariate framework, modelling the bulk and tail of a distribution has been extensively studied before. However, when more than one variable is of concern, models that aim specifically at capturing both regions correctly are scarce in the literature. A dependence model that blends two copulas with different characteristics over the whole range of the data support is proposed. One copula is tailored to the bulk and the other to the tail, with a dynamic weighting function employed to transition smoothly between them. Tail dependence properties are investigated numerically and simulation is used to confirm that the blended model is sufficiently flexible to capture a wide variety of structures. The model is applied to study the dependence between temperature and ozone concentration at two sites in the UK and compared with a single copula fit. The proposed model provides a better, more flexible, fit to the data, and is also capable of capturing complex dependence structures.
Private synthetic data sharing is preferred as it keeps the distribution and nuances of original data compared to summary statistics. The state-of-the-art methods adopt a select-measure-generate paradigm, but measuring large domain marginals still results in much error and allocating privacy budget iteratively is still difficult. To address these issues, our method employs a partition-based approach that effectively reduces errors and improves the quality of synthetic data, even with a limited privacy budget. Results from our experiments demonstrate the superiority of our method over existing approaches. The synthetic data produced using our approach exhibits improved quality and utility, making it a preferable choice for private synthetic data sharing.
A connected matching in a graph G consists of a set of pairwise disjoint edges whose covered vertices induce a connected subgraph of G. While finding a connected matching of maximum cardinality is a well-solved problem, it is NP-hard to determine an optimal connected matching in an edge-weighted graph, even in the planar bipartite case. We present two mixed integer programming formulations and a sophisticated branch-and-cut scheme to find weighted connected matchings in general graphs. The formulations explore different polyhedra associated to this problem, including strong valid inequalities both from the matching polytope and from the connected subgraph polytope. We conjecture that one attains a tight approximation of the convex hull of connected matchings using our strongest formulation, and report encouraging computational results over DIMACS Implementation Challenge benchmark instances. The source code of the complete implementation is also made available.
While well-established methods for time-to-event data are available when the proportional hazards assumption holds, there is no consensus on the best inferential approach under non-proportional hazards (NPH). However, a wide range of parametric and non-parametric methods for testing and estimation in this scenario have been proposed. To provide recommendations on the statistical analysis of clinical trials where non proportional hazards are expected, we conducted a comprehensive simulation study under different scenarios of non-proportional hazards, including delayed onset of treatment effect, crossing hazard curves, subgroups with different treatment effect and changing hazards after disease progression. We assessed type I error rate control, power and confidence interval coverage, where applicable, for a wide range of methods including weighted log-rank tests, the MaxCombo test, summary measures such as the restricted mean survival time (RMST), average hazard ratios, and milestone survival probabilities as well as accelerated failure time regression models. We found a trade-off between interpretability and power when choosing an analysis strategy under NPH scenarios. While analysis methods based on weighted logrank tests typically were favorable in terms of power, they do not provide an easily interpretable treatment effect estimate. Also, depending on the weight function, they test a narrow null hypothesis of equal hazard functions and rejection of this null hypothesis may not allow for a direct conclusion of treatment benefit in terms of the survival function. In contrast, non-parametric procedures based on well interpretable measures as the RMST difference had lower power in most scenarios. Model based methods based on specific survival distributions had larger power, however often gave biased estimates and lower than nominal confidence interval coverage.
The moderate deviation regime is concerned with the finite block length trade-off between communication cost and error for information processing tasks in the asymptotic regime, where the communication cost approaches a capacity-like quantity and the error vanishes at the same time. We find exact characterisations of these trade-offs for a variety of fully quantum communication tasks, including quantum source coding, quantum state splitting, entanglement-assisted quantum channel coding, and entanglement-assisted quantum channel simulation. The main technical tool we derive is a tight relation between the partially smoothed max-information and the hypothesis testing relative entropy. This allows us to obtain the expansion of the partially smoothed max-information for i.i.d. states in the moderate deviation regime.
Stress testing refers to the application of adverse financial or macroeconomic scenarios to a portfolio. For this purpose, financial or macroeconomic risk factors are linked with asset returns, typically via a factor model. We expand the range of risk factors by adapting dimension-reduction techniques from unsupervised learning, namely PCA and autoencoders. This results in aggregated risk factors, encompassing a global factor, factors representing broad geographical regions, and factors specific to cyclical and defensive industries. As the adapted PCA and autoencoders provide an interpretation of the latent factors, this methodology is also valuable in other areas where dimension-reduction and explainability are crucial.
We couple the L1 discretization of the Caputo fractional derivative in time with the Galerkin scheme to devise a linear numerical method for the semilinear subdiffusion equation. Two important points that we make are: nonsmooth initial data and time-dependent diffusion coefficient. We prove the stability and convergence of the method under weak assumptions concerning regularity of the diffusivity. We find optimal pointwise in space and global in time errors, which are verified with several numerical experiments.
The elliptic curve discrete logarithm problem is of fundamental importance in public-key cryptography. It is in use for a long time. Moreover, it is an interesting challenge in computational mathematics. Its solution is supposed to provide interesting research directions. In this paper, we explore ways to solve the elliptic curve discrete logarithm problem. Our results are mostly computational. However, it seems, the methods that we develop and directions that we pursue can provide a potent attack on this problem. This work follows our earlier work, where we tried to solve this problem by finding a zero minor in a matrix over the same finite field on which the elliptic curve is defined. This paper is self-contained.
The goal of explainable Artificial Intelligence (XAI) is to generate human-interpretable explanations, but there are no computationally precise theories of how humans interpret AI generated explanations. The lack of theory means that validation of XAI must be done empirically, on a case-by-case basis, which prevents systematic theory-building in XAI. We propose a psychological theory of how humans draw conclusions from saliency maps, the most common form of XAI explanation, which for the first time allows for precise prediction of explainee inference conditioned on explanation. Our theory posits that absent explanation humans expect the AI to make similar decisions to themselves, and that they interpret an explanation by comparison to the explanations they themselves would give. Comparison is formalized via Shepard's universal law of generalization in a similarity space, a classic theory from cognitive science. A pre-registered user study on AI image classifications with saliency map explanations demonstrate that our theory quantitatively matches participants' predictions of the AI.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191