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

19th InternationalWorkshop on Fast Software Encryption (FSE)

作者： Bogdanov, Andrey Wang, Meiqin Katholieke Univ Leuven ESAT COSIC Leuven Belgium IBBT Ghent Belgium Shandong Univ Minist Educ Key Lab Cryptol Technol & Informat Secur Jinan 250100 Shandong Peoples R China

ISBN: (纸本)9783642340475

Zero correlation linear cryptanalysis is a novel key recovery technique for block ciphers proposed in [5]. It is based on linear approximations with probability of exactly 1/2 (which corresponds to the zero correlation). Some block ciphers turn out to have multiple linear approximations with correlation zero for each key over a considerable number of rounds. Zero correlation linear cryptanalysis is the counterpart of impossible differential cryptanalysis in the domain of linear cryptanalysis, though having many technical distinctions and sometimes resulting in stronger attacks. In this paper, we propose a statistical technique to significantly reduce the data complexity using the high number of zero correlation linear approximations available. We also identify zero correlation linear approximations for 14 and 15 rounds of TEA and XTEA. Those result in key-recovery attacks for 21-round TEA and 25-round XTEA, while requiring less data than the full code book. In the single secret key setting, these are structural attacks breaking the highest number of rounds for both ciphers. The findings of this paper demonstrate that the prohibitive data complexity requirements are not inherent in the zero correlation linear cryptanalysis and can be overcome. Moreover, our results suggest that zero correlation linear cryptanalysis can actually break more rounds than the best known impossible differential cryptanalysis does for relevant block ciphers. This might make a security re-evaluation of some ciphers necessary in the view of the new attack.

关键词： block ciphers key recovery linear cryptanalysis zero correlation linear cryptanalysis data complexity TEA XTEA

来源：评论

学校读者我要写书评

暂无评论

Capacity and data complexity in Multidimensional Linear Attack 35th

Capacity and Data Complexity in Multidimensional Linear Atta...

引用

35th Annual International Cryptology Conference (CRYPTO)

作者： Huang, Jialin Vaudenay, Serge Lai, Xuejia Nyberg, Kaisa Tech Univ Darmstadt Darmstadt Germany Shanghai Jiao Tong Univ Shanghai 200030 Peoples R China Ecole Polytech Fed Lausanne CH-1015 Lausanne Switzerland Aalto Univ Espoo Finland

ISBN: (纸本)9783662479896;9783662479889

Multidimensional linear attacks are one of the most powerful variants of linear cryptanalytic techniques now. However, there is no knowledge on the key-dependent capacity and data complexity so far. Their values were assumed to be close to the average value for a vast majority of keys. This assumption is not accurate. In this paper, under a reasonable condition, we explicitly formulate the capacity as a Gamma distribution and the data complexity as an Inverse Gamma distribution, in terms of the average linear probability and the dimension. The capacity distribution is experimentally verified on the 5-round PRESENT. Regarding to complexity, we solve the problem of estimating the average data complexity, which was difficult to estimate because of the existence of zero correlations. We solve the problem of using the median complexity in multidimensional linear attacks, which is an open problem since proposed in Eurocrypt 2011. We also evaluate the difference among the median complexity, the average complexity and a lower bound of the average complexity - the reciprocal of average capacity. In addition, we estimate more accurately the key equivalent hypothesis, and reveal the fact that the average complexity only provides an accurate estimate for less than half of the keys no matter how many linear approximations are involved. Finally, we revisit the so far best attack on PRESENT based on our theoretical result.

关键词： Multidimensional linear attack Capacity data complexity Linear hull effect Linear probability

来源：评论

学校读者我要写书评

暂无评论

The data complexity of Answering Instance Queries in FL₀ 18

The Data Complexity of Answering Instance Queries in <i>FL</...

引用

27th World Wide Web (WWW) Conference

作者： Baader, Franz Marantidis, Pavlos Pensel, Maximilian Tech Univ Dresden Chair Automata Theory Dresden Germany

ISBN: (纸本)9781450356404

Ontology-mediated query answering can be used to access large data sets through a mediating ontology. It has drawn considerable attention in the Description Logic (DL) community where both the complexity of query answering and practical query answering approaches based on rewriting were investigated in detail. Surprisingly, there is still a gap in what is known about the data complexity of query answering w.r.t. ontologies formulated in the inexpressive DL FL0. While it is known that the data complexity of answering conjunctive queries w.r.t. FL0 ontologies is coNP-complete, the exact complexity of answering instance queries was open until now. In the present paper, we show that answering instance queries w.r.t. FL0 ontologies is in P for data complexity. Together with the known lower bound of P-completeness for a fragment of FL0, this closes the gap mentioned above.

关键词： Ontology-Mediated Query Answering data complexity Description Logic FL0

来源：评论

学校读者我要写书评

暂无评论

CODE: A data complexity Framework for Imbalanced datasets

CODE: A Data Complexity Framework for Imbalanced Datasets

引用

13th Pacific-Asia Conference on Knowledge Discovery and data Mining

作者： Weng, Cheng G. Poon, Josiah Univ Sydney Sch Informat Technol Sydney NSW 2006 Australia

ISBN: (纸本)9783642146398

Imbalanced datasets occur in many domains, such as fraud detection, cancer detection and web;and in such domains, the class of interest often concerns the rare occurring events. Thus it is important to have a good performance on these classes while maintaining a reasonable overall accuracy. Although imbalanced data,sets can be difficult to learn, but in the previous researches, the skewed class distribution has been suggested to not necessarily being the one that poses problems for learning. Therefore, when the learning of the rare class becomes problematic, it does not imply that the skewed class distribution is the cause to blame, but rather that the imbalanced distribution may just be a byproduct of some other hidden intrinsic difficulties. This paper tries to shade some light on this issue of learning from imbalanced dataset. We propose to use data complexity models to profile datasets in order to make connections with imbalanced clatasets;this can potentially lead to better learning approaches. We have extended from our previous work with an improved implementation of the CODE framework in order to tackle a more difficult learning challenge. Despite the increased difficulty, CODE still enables a reasonable performance on profiling the data complexity of imbalanced datasets.

关键词： Imbalanced datasets data complexity

来源：评论

学校读者我要写书评

暂无评论

data complexity: An FCA-based approach

引用

INTERNATIONAL JOURNAL OF APPROXIMATE REASONING 2024年 165卷

作者： Buzmakov, Alexey Dudyrev, Egor Kuznetsov, Sergei O. Makhalova, Tatiana Napoli, Amedeo HSE Univ Perm 614070 Russia HSE Univ Moscow 109028 Russia Univ Lorraine CNRS LORIA F-54000 Nancy France

In this paper we propose different indices for measuring the complexity of a dataset in terms of Formal Concept Analysis (FCA). We extend the lines of the research about the "closure structure" and the "closure index" based on minimum generators of intents (aka closed itemsets). We would try to capture statistical properties of a dataset, not just extremal characteristics, such as the size of a passkey. For doing so we introduce an alternative approach where we measure the complexity of a dataset w.r.t. five significant elements that can be computed in a concept lattice, namely intents (closed sets of attributes), pseudo-intents, proper premises, keys (minimal generators), and passkeys (minimum generators). Then we define several original indices allowing us to estimate the complexity of a dataset. Moreover we study the distribution of all these different elements and indices in various real-world and synthetic datasets. Finally, we investigate the relations existing between these significant elements and indices, and as well the relations with implications and association rules.

关键词： Formal concept analysis data complexity Closed set and generator Linearity index Distributivity index Real-world and synthetic dataset

来源：评论

学校读者我要写书评

暂无评论

data complexity-based dynamic ensembling of SVMs in classification

引用

EXPERT SYSTEMS WITH APPLICATIONS 2023年第1期216卷

作者： Sowkarthika, B. Gyanchandani, Manasi Wadhvani, Rajesh Shukla, Sanyam MANIT Bhopal 462007 Madhya Pradesh India Maulana Azad Natl Inst Technol Bhopal 462007 Madhya Pradesh India

Ensemble-based techniques are deployed to yield better performance than individual classifiers. Existing ensembling approaches fail to consider data complexity during their design. This work presents an ensemble -based approach for resolving complex patterns in real-world classification problems. A novel Minimum Spanning Tree (MST)-based approach is employed for decomposing the original problem into subproblems with reduced data complexity, and SVM is utilized for the development of component classifiers for these subproblems. A novel dynamic ensemble-based technique is utilized to generate the outcome. This work is evaluated by using 28 datasets retrieved from the KEEL dataset repository. Additionally, statistical tests are performed to illustrate a significant difference in the performance of the proposed model compared to the state-of-art classification models and two recently proposed dynamic ensembling approaches.

关键词： data complexity Classification model Minimum spanning tree Ensemble

来源：评论

学校读者我要写书评

暂无评论

Feature Elimination through data complexity for Error-Correcting Output Codes based micro-expression recognition

引用

SIGNAL PROCESSING-IMAGE COMMUNICATION 2023年第1期115卷

作者： Sun, Meng-Xin Chen, Li-Yan Liu, Kun-Hong Liong, Sze-Teng Wu, Qing-Qiang Xiamen Univ Sch Film Dept Digital Media Technol Xiamen Fujian Peoples R China Feng Chia Univ Dept Elect Engn Taichung Taiwan Tencent Mus Entertainment Grp Qq Mus Business Line Shenzhen Peoples R China

Micro-Expression (ME) is a kind of short-lived and uncontrollable facial expressions. The MEs recognition task poses a great challenge to both the psychological and computer vision research communities. In this study, a Feature Elimination through data complexity-based Error-Correcting Output Codes (FEDC-ECOC) algorithm is proposed. In the generation of the coding matrix, a set of data complexity measures are utilized as the division criteria to form a coding matrix. Meanwhile, the sliding window and the greedy search algorithm are applied to improve the discriminative ability of the coding matrix for various emotion types. On the other hand, this study proposes a feature selection algorithm to identify essential features to enhance the performance of classifiers. Comprehensive experiments are conducted, and the results confirm the robustness and effectiveness of our FEDC-ECOC. Detailed analysis is given to further provide insights of the proposed method.

关键词： Error-Correcting Output Codes (ECOC) Micro-Expression recognition data complexity Feature elimination

来源：评论

学校读者我要写书评

暂无评论

A method to measure data complexity of a complicated medical data set

引用

INTERNATIONAL JOURNAL OF IMAGING SYSTEMS AND TECHNOLOGY 2022年第6期32卷 1822-1831页

作者： Juhola, Martti Joutsijoki, Henry Penttinen, Kirsi Shah, Disheet Aalto-Setala, Katriina Tampere Univ Fac Informat Technol & Commun Sci Tampere 33014 Finland Tampere Univ Fac Med & Hlth Technol Tampere Finland Northwestern Univ Dept Pharmacol Chicago IL 60611 USA Tampere Univ Hosp Ctr Heart Tampere Finland

In this article, we consider data complexity in the context of calcium transient signal data collected from induced pluripotent stem cell-derived cardiomyocytes. We present a novel way to measure data complexity based on the nearest neighbour searching method. data complexity here is seen as overlapping and mixed data classes in addition to a relatively great number of data cases. complexity affects classification results, which were run with nearest neighbour searching, feedforward artificial neural networks and random forests for seven genetic cardiological disease classes and healthy controls. The data are obtained from individuals carrying mutations for genetic cardiac diseases with induced pluripotent stem cell (iPSC) technology and the diseases include hypertrophic cardiomyopathy with two different founder gene mutations, dilated cardiomyopathy, long QT syndrome type 1 and 2, Brugada syndrome, a severe genetic ventricular arrhythmia (CPVT) and healthy controls. The data are from calcium transients from spontaneously beating iPSC-derived cardiomyocytes cultured in a biotechnology laboratory. When the genotype of the iPSC-derived cardiomyocytes is the same as the donor of the tissue sample and based on the characteristics of the calcium transients, it was possible to classify the seven diseases and healthy controls with machine learning. Peak data first detected before actual pre-processing from calcium transient signals corresponded to beats (repeating excitation-contraction coupling) of induced stem cell-derived cardiomyocytes and formed the basis of classification. During pre-processing of the calcium transient signals, we found that such techniques among others as even strong outlier cleaning or class size balancing by generating artificial cases improved only slightly or not at all classification accuracies. Therefore, the current data set was sufficiently complicated for our data complexity study. Random forests produced the best classification accuracies,

关键词： calcium transient signals classification data complexity genetic cardiac cardiomyocytes induced pluripotent stem cell-derived cardiomyocytes machine learning

来源：评论

学校读者我要写书评

暂无评论

complexity curve: a graphical measure of data complexity and classifier performance

引用

PEERJ COMPUTER SCIENCE 2016年第8期2016卷

作者： Zubek, Julian Plewczynski, Dariusz M. Univ Warsaw Ctr New Technol Warsaw Poland Polish Acad Sci Inst Comp Sci Warsaw Poland

We describe a method for assessing data set complexity based on the estimation of the underlining probability distribution and Hellinger distance. In contrast to some popular complexity measures, it is not focused on the shape of a decision boundary in a classification task but on the amount of available data with respect to the attribute structure. complexity is expressed in terms of graphical plot, which we call complexity curve. It demonstrates the relative increase of available information with the growth of sample size. We perform theoretical and experimental examination of properties of the introduced complexity measure and show its relation to the variance component of classification error. We then compare it with popular data complexity measures on 81 diverse data sets and show that it can contribute to explaining performance of specific classifiers on these sets. We also apply our methodology to a panel of simple benchmark data sets, demonstrating how it can be used in practice to gain insights into data characteristics. Moreover, we show that the complexity curve is an effective tool for reducing the size of the training set (data pruning), allowing to significantly speed up the learning process without compromising classification accuracy. The associated code is available to download at: https://***/zubekj/complexity_curve (open source Python implementation).

关键词： Learning curves data complexity data pruning Hellinger distance Bias-variance decomposition Performance measures

来源：评论

学校读者我要写书评

暂无评论

Expressive power and data complexity of nonrecursive query languages for lists and trees (extended abstract) 00

Expressive power and data complexity of nonrecursive query l...

引用

Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems

作者： Evgeny Dantsin Andrei Voronkov St.Petersburg Institute of Mathematics and University of Manchester University of Manchester

ISBN: (纸本)9781581132144

We extend the traditional query languages by primitives for handling lists and trees. Our main results characterize the expressive power and data complexity of the following extended languages: (1) relational algebra with lists and trees, (2) nonrecursive datalog@@@@ with lists and trees, (3) nonrecursive Prolog with lists and trees, (4) first-order logic over lists and *** (2)-(4) turn out to have the same expressive power; their range-restricted fragments have the same expressive power as (1). Every query in these languages is a boolean combination of range-restricted *** also prove that these query languages have polynomial data complexity under any “reasonable” encoding of inputs. Furthermore, under a natural encoding of inputs, languages (2)-(4) have the same expressive power as first-order logic over finite structures, therefore their data complexity is in A Co. Thus, the use of lists and trees in nonrecursive query languages gives no gain in the expressiveness. This contrasts with a huge difference between the nonelementary program complexity of extended languages (2)-(4) and the PSPA CE program complexity of their relational *** results partly explain why lists and trees are not so widely used in nonrecursive query languages as other collection types.

关键词： data complexity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：