检索结果-内蒙古大学图书馆

45th Annual ACM Symposium on the Theory of Computing (STOC)

作者： Feldman, Vitaly Grigorescu, Elena Reyzin, Lev Vempala, Santosh S. Xiao, Ying IBM Corp Almaden Res Ctr San Jose CA 95120 USA Purdue Univ Dept Comp Sci W Lafayette IN 47907 USA Univ Illinois Dept Math Chicago IL 60607 USA Georgia Inst Technol Sch Comp Sci Atlanta GA 30332 USA

ISBN: (纸本)9781450320290

We introduce a framework for proving lower bounds on computational problems over distributions, based on a class of algorithms called statistical algorithms. For such algorithms, access to the input distribution is limited to obtaining an estimate of the expectation of any given function on a sample drawn randomly from the input distribution, rather than directly accessing samples. Most natural algorithms of interest in theory and in practice, e.g., moments-based methods, local search, standard iterative methods for convex optimization, MCMC and simulated annealing, are statistical algorithms or have statistical counterparts. Our framework is inspired by and generalize the statistical query model in learning theory [34]. Our main application is a nearly optimal lower bound on the complexity of any statistical algorithm for detecting planted bipartite clique distributions (or planted dense subgraph distributions) when the planted clique has size 0(n1/2-6) for any constant (5 > 0. Variants of these problems have been assumed to be hard to prove hardness for other problems and for cryptographic applications. Our lower bounds provide concrete evidence of hardness, thus supporting these assumptions.

关键词： statistical algorithms Lower bounds Planted clique statistical query

来源：评论

学校读者我要写书评

暂无评论

statistical algorithms and a Lower Bound for Detecting Planted Cliques

引用

JOURNAL OF THE ACM 2017年第2期64卷 8-8页

作者： Feldman, Vitaly Grigorescu, Elena Reyzin, Lev Vempala, Santosh S. Xiao, Ying IBM Corp Almaden Res Ctr San Jose CA 95120 USA Purdue Univ Dept Comp Sci W Lafayette IN 47907 USA Univ Illinois Dept Math Stat & Comp Sci Chicago IL 60607 USA Georgia Tech Atlanta GA USA Palantir Technol Palo Alto CA USA Georgia Inst Technol Sch Comp Sci Atlanta GA 30332 USA

We introduce a framework for proving lower bounds on computational problems over distributions against algorithms that can be implemented using access to a statistical query oracle. For such algorithms, access to the input distribution is limited to obtaining an estimate of the expectation of any given function on a sample drawn randomly from the input distribution rather than directly accessing samples. Most natural algorithms of interest in theory and in practice, for example, moments-based methods, local search, standard iterative methods for convex optimization, MCMC, and simulated annealing, can be implemented in this framework. Our framework is based on, and generalizes, the statistical query model in learning theory [Kearns 1998]. Our main application is a nearly optimal lower bound on the complexity of any statistical query algorithm for detecting planted bipartite clique distributions (or planted dense subgraph distributions) when the planted clique has size O(n(1/2)-delta) for any constant delta > 0. The assumed hardness of variants of these problems has been used to prove hardness of several other problems and as a guarantee for security in cryptographic applications. Our lower bounds provide concrete evidence of hardness, thus supporting these assumptions.

关键词： Learning theory statistical algorithms planted clique statistical dimension lower bounds

来源：评论

学校读者我要写书评

暂无评论

statistical pattern recognition algorithms for autofluorescence imaging

Statistical pattern recognition algorithms for autofluoresce...

引用

Conference on Multimodal Biomedical Imaging IV

作者： Kulas, Zbigniew Beres-Pawlik, Elzbieta Wierzbicki, Jaroslaw Warsaw Univ Technol Inst Telecommun Teleinformat & Acoust PL-00661 Warsaw Poland

ISBN: (纸本)9780819474179

In cancer diagnostics the most important problems are the early identification and estimation of the tumor growth and spread in order to determine the area to be operated. The aim of the work was to design of statistical algorithms helping doctors to objectively estimate pathologically changed areas and to assess the disease advancement. In the research, algorithms for classifying endoscopic autofluorescence images of larynx and intestine were used. The results show that the statistical pattern recognition offers new possibilities for endoscopic diagnostics and can be of a tremendous help in assessing the area of the pathological changes.

关键词： autofluorescence imaging medical imaging oncology statistical algorithms

来源：评论

学校读者我要写书评

暂无评论

iODA: An integrated tool for analysis of cancer pathway consistency from heterogeneous multi-omics data

引用

JOURNAL OF BIOMEDICAL INFORMATICS 2020年 112卷 103605-103605页

作者： Yu, Chunjiang Qi, Xin Lin, Yuxin Li, Yin Shen, Bairong Suzhou Ind Pk Inst Serv Outsourcing Sch Biotechnol Suzhou Peoples R China Suzhou Univ Sci & Technol Sch Chem Biol & Mat Engn Suzhou Peoples R China Soochow Univ Ctr Syst Biol Suzhou Peoples R China Sichuan Univ West China Hosp Frontiers Sci Ctr Dis Related Mol Network Inst Syst Genet Chengdu 610041 Peoples R China

The latest advances in the next generation sequencing technology have greatly facilitated the extensive research of genomics and transcriptomics, thereby promoting the decoding of carcinogenesis with unprecedented resolution. Considering the contribution of analyzing high-throughput multi-omics data to the exploration of cancer molecular mechanisms, an integrated tool for heterogeneous multi-omics data analysis (iODA) is proposed for the systems-level interpretation of multi-omics data, i.e., transcriptomic profiles (mRNA or miRNA expression data) and protein-DNA interactions (ChIP-Seq data). Considering the data heterogeneity, iODA can compare six statistical algorithms in differential analysis for the selected sample data and assist users in choosing the globally optimal one for dysfunctional mRNA or miRNA identification. Since molecular signatures are more consistent at the pathway level than at the gene level, the tool is able to enrich the identified dysfunctional molecules onto the KEGG pathways and extracted the consistent items as key components for further pathogenesis investigation. Compared with other tools, iODA is multi-functional for the systematic analysis of different level of omics data, and its analytical power was demonstrated through case studies of single and cross-level prostate cancer omics data. iODA is open source under GNU GPL and can be downloaded from http://***/iODA.

关键词： Next generation sequencing Omics data statistical algorithms Integrative analysis Pathway

来源：评论

学校读者我要写书评

暂无评论

Segmentation of natural images based on super pixel and graph merging

引用

IET COMPUTER VISION 2021年第1期15卷 1-11页

作者： Mukherjee, Aritra Sarkar, Soumik Saha, Sanjoy K. Jadavpur Univ Dept Comp Sci & Engn Kolkata India Jadavpur Univ Dept Informat Technol Kolkata India

The task of natural image segmentation is one of the most researched topics of computer vision. There are mainly two principal approaches for the task, the statistical approach and the supervised approach. The proposed methodology segments natural images combining a set of statistical algorithms. First, the image is preprocessed to enhance the edges. Weighted average of the denoised image and its derivatives is the preprocessed output. Thereafter, an energy based super pixelation is applied to over segment the image. Finally, a connectivity graph is built where nodes correspond to super pixels and edges connect the adjacent super pixels. The adjacent super pixels are merged based on the confidence value defined in terms of their textural and colour similarity. Proposed methodology has been applied on the images of BSDS500 dataset. Performance of the proposed work has been compared with that of other works based on detected edge maps. Few works generate ultrametric contour maps (UCM). To compare the performance with those works, UCM is also generated by the proposed methodology. To do so images at multiple scales are considered. It is observed that the output of segmentation is better in case of the proposed methodology. Proposed methodology is much faster than others. Thus, makes it suitable for real time application in robot vision.

关键词： robot vision researched topics image denoising super pixel computer vision natural image segmentation methodology segments natural images principal approaches statistical algorithms supervised approach connectivity graph edge detection super pixelation preprocessed output denoised image image segmentation detected edge maps graph theory adjacent super pixels statistical approach

来源：评论

学校读者我要写书评

暂无评论

Theoretical Analysis of Straightness Errors in Coordinate Measuring Machines (CMM) with Three Linear Axes

引用

INTERNATIONAL JOURNAL OF PRECISION ENGINEERING AND MANUFACTURING 2021年第1期22卷 63-72页

作者： Patricio, Franco Jodar, Jose Univ Politecn Cartagena Dept Mat & Mfg Engn Escuela Tecn Super Ingn Ind C Doctor Fleming S-N Cartagena 30202 Spain Univ Politecn Cartagena Dept Appl Phys Escuela Tecn Super Ingn Ind C Doctor Fleming S-N Cartagena 30202 Spain

Diverse studies were developed in last years about the precision of coordinate measuring machines (CMMs) in order to enhance the calibration method for these testing devices or their application for dimensional verification of manufactured parts, but new research works are needed to identify the effect of the different types of geometric errors that exists in CMMs and deduce the measuring conditions that allow the optimization of CMM performance. The aim of this work consist of analyzing the influence of some of these machine errors such as the straightness errors and position errors associated to the CMM axis displacement, with the purpose of deducing the specific contribution of these errors inside the global uncertainty of these testing devices. This study was focused on coordinate measuring machines with a configuration type FXYZ, and it was carried out using a simplified model that is restricted to the effect of the straightness errors and position errors, without considering the contribution of the rest of CMM geometric errors. The unexpected variations that can be originated in the machine errors between the successive calibration points were described by the numerical model, and their influence on the CMM measuring accuracy were also discussed.

关键词： Axis displacement errors Coordinate measure machines (CMMs) Position errors statistical algorithms Straightness errors Theoretical modelling

来源：评论

学校读者我要写书评

暂无评论

Maximum likelihood restoration and choice of smoothing parameter in deconvolution of image data subject to Poisson noise

引用

COMPUTATIONAL STATISTICS & DATA ANALYSIS 1998年第4期26卷 393-410页

作者： Hudson, HM Lee, TCM Macquarie Univ Dept Stat SEFS N Ryde NSW 2109 Australia

Image degradation by blurring is a well-known phenomenon often described by the mathematical operation of convolution. Fourier methods are well developed for recovery, or restoration, of the true image from an observed image affected by convolution blur and additive constant variance Gaussian noise. One focus of this paper is to describe another statistical restoration method which is available when the image data exhibits Poisson variability. This is a common situation when counts of recorded activity from the image, as in medical imaging contexts. We apply Maximum Likelihood (ML) and Maximum Penalized Likelihood (MPL) procedures to deconvolve image data which has been degraded by blurring and Poisson variability in recorded activity. A second focus is formulation and comparison of automated selection procedures for regularization (smoothing) parameters in this context. (C) 1998 Elsevier Science B.V. All rights reserved.

关键词： cross-validation deconvolution fast computation regularization statistical algorithms

来源：评论

学校读者我要写书评

暂无评论

Performance Assessment of Pre-processing Filters for Infrared Search and Track Applications

引用

DEFENCE SCIENCE JOURNAL 2011年第3期61卷 251-256页

作者： Srivastava, Hari Babu Kumar, Vinod Verma, H. K. Sundaram, S. S. Instruments Res & Dev Estab Dehra Dun 248008 India Indian Inst Technol Dept Elect Engn Roorkee 247667 Uttar Pradesh India Indian Inst Technol Continuing Educ Ctr Roorkee 247667 Uttar Pradesh India Indian Inst Technol Qual Improvement Ctr Roorkee 247667 Uttar Pradesh India

To enhance detection probability and to reduce false alarms, infrared imagery is pre-processed before subjecting it to detection algorithms in infrared search and track systems. Pre-processing algorithms are used to predict the complex background and then to subtract the predicted background from the original image. The difference image is passed to the detection algorithm to further distinguish between the target and the background and/or noise more accurately. A number of pre-processing algorithms have been reported in literature, with their relative advantages and disadvantages. This paper brings out the computational complexities and simulation results of various algorithms for assessing their relative performances. Based on these parameters, statistical algorithms in general and max-min algorithms in particular, are recommended to be used for infrared search and track systems.

关键词： Contrast sensitivity point targets pre-processing algorithms infrared search and track morphological filters statistical filters statistical algorithms max-min algorithms small target detection false alarms post-processing algorithms

来源：评论

学校读者我要写书评

暂无评论

ON THE COMPLEXITY OF RANDOM SATISFIABILITY PROBLEMS WITH PLANTED SOLUTIONS

引用

SIAM JOURNAL ON COMPUTING 2018年第4期47卷 1294-1338页

作者： Feldman, Vitaly Perkins, Will Vempala, Santosh Google Brain Mountain View CA 94035 USA Univ Birmingham Sch Math Birmingham B15 2TT W Midlands England Georgia Tech Atlanta GA 30332 USA

The problem of identifying a planted assignment given a random k-satisfiability (k-SAT) formula consistent with the assignment exhibits a large algorithmic gap: while the planted solution becomes unique and can be identified given a formula with O(n log n) clauses, there are distributions over clauses for which the best-known efficient algorithms require n(k/2) clauses. We propose and study a unified model for planted k-SAT, which captures well-known special cases. An instance is described by a planted assignment sigma and a distribution on clauses with k literals. We define its distribution complexity as the largest r for which the distribution is not r-wise independent (1 <= r <= k for any distribution with a planted assignment). Our main result is an unconditional lower bound, tight up to logarithmic factors, for statistical (query) algorithms [M. Kearns, J. ACM, 45 (1998), pp. 983{1006;V. Feldman, E. Grigorescu, L. Reyzin, S. S. Vempala, and Y. Xiao, J. ACM, 64 (2017), pp. 8:1{8:37], matching known upper bounds, which, as we show, can be implemented using a statistical algorithm. Since known approaches for problems over distributions have statistical analogues (spectral, Markov Chain Monte Carlo, gradient-based, convex optimization, etc.), this lower bound provides a rigorous explanation of the observed algorithmic gap. The proof introduces a new general technique for the analysis of statistical query algorithms. It also points to a geometric paring phenomenon in the space of all planted assignments. We describe consequences of our lower bounds to Feige's refutation hypothesis [U. Feige, Proceedings of the ACM Symposium on Theory of Computing, 2002, pp. 534{543] and to lower bounds on general convex programs that solve planted k-SAT. Our bounds also extend to other planted k-CSP models and, in particular, provide concrete evidence for the security of Goldreich's one-way function and the associated pseudorandom generator when used with a sufficiently hard predica

关键词： planted satisfiability statistical algorithms k-SAT hypergraph partitioning

来源：评论

学校读者我要写书评

暂无评论

Numerical Analysis of Stochastic Oscillators on Supercomputers

引用

NUMERICAL ANALYSIS AND APPLICATIONS 2012年第1期5卷 25-35页

作者： Artemiev, S. S. Ivanov, A. A. Korneev, V. D. Russian Acad Sci Inst Computat Math & Math Geophys Siberian Branch Pr Akad Lavrenteva 6 Novosibirsk 630090 Russia Novosibirsk State Univ Novosibirsk 630090 Russia

The problem of numerical analysis of stochastic differential equations (SDEs) with oscillating solutions is investigated. The expectation and variance of SDE numerical solutions are shown as functions of the mesh size of integrating the generalized Euler method. Results of some numerical experiments on the simulation of linear and nonlinear stochastic oscillators on the supercomputer of the Siberian Supercomputer Center are presented.

关键词： stochastic differential equations statistical algorithms parallelization super-computer cluster van der Pol equation phase trajectory stochastic oscillators

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：