ISI Digital Commons (Indian Statistical Institute )
Not a member yet
7571 research outputs found
Sort by
Transfer Learning for Latent Variable Network Models
No full textWe study transfer learning for estimation in latent variable network models. In our setting, the conditional edge probability matrices given the latent variables are represented by P for the source and Q for the target. We wish to estimate Q given two kinds of data: (1) edge data from a subgraph induced by an o(1) fraction of the nodes of Q, and (2) edge data from all of P. If the source P has no relation to the target Q, the estimation error must be Ω(1). However, we show that if the latent variables are shared, then vanishing error is possible. We give an efficient algorithm that utilizes the ordering of a suitably defined graph distance. Our algorithm achieves o(1) error and does not assume a parametric form on the source or target networks. Next, for the specific case of Stochastic Block Models we prove a minimax lower bound and show that a simple algorithm achieves this rate. Finally, we empirically demonstrate our algorithm\u27s use on real-world and simulated network estimation problems
Weighted Sum of Segmented Correlation: an Efficient Method for Spectra Matching in Hyperspectral Images
No full textMatching a target spectrum with known spectra in a spectral library is a common method for material identification in hyperspectral imaging research. Hyperspectral spectra exhibit precise absorption features across different wavelength segments, and the unique shapes and positions of these absorptions create distinct spectral signatures for each material, aiding in their identification. Therefore, only the specific positions can be considered for material identification. This study introduces the Weighted Sum of Segmented Correlation method, which calculates correlation indices between various segments of a library and a test spectrum, and derives a matching index, favoring positive correlations and penalizing negative correlations using assigned weights. The effectiveness of this approach is evaluated for mineral identification in hyperspectral images from both Earth and Martian surfaces
Infant, Neonatal and Maternal Mortality in ASEAN Countries: A Panel Data Analysis
No full textThe purpose of this study is to explore the fertility differentials of Bangladesh by considering some socioeconomic and demographic factors using BDHS 2018 data. Differentials of fertility are examined by some selected background variables: age at marriage, education, place of residence, religion, region, work status of women,, women\u27s participation in nongovernmental organizations (NGOs), husband\u27s education, husband\u27s occupation, and birth status of women of Bangladesh. The average number of children ever-born per ever-married woman of different age groups from \u3c20 to 45+ is used as the measurement technique of the differentials of fertility to the selected variables. The results have been presented that the current scenario of fertility differentials of the selected variables have positive or negative indirect effects on the reproductive behavior of Bangladesh. The analysis reveals that age at marriage has a reducing effect on fertility furthermore the increase in the age at marriage and level of education may effectively reduce the reproductive performance of the women in Bangladesh. Again, the urban–rural differentials of fertility show that the rural fertility is higher than the urban. Besides these socioeconomic variables, women\u27s and men\u27s labor force participation influences fertility negatively. It is usually seen that those who are engaged in non-manual (mental) work have less number of children, as compared with those who are in manual (physical) work. There are eight administrative divisions in Bangladesh, which are Barishal, Chittagong, Dhaka, Khulna, Rajshahi, Rangpur, Mymensingh, and Sylhet. Regional differentials of fertility have reflected that fertility is higher in Sylhet, Chittagong, and Mymensingh divisions with the average number of children ever-born per woman being 2.968, 2.844, and 2.873. Fertility is lowest in Khulna (2.075), Rajshahi (2.198), and Rangpur (2.208). Dhaka and Barisal have intermediate levels of fertility, with an average of 2.355 and 2.438 children per woman. The regional differentials reveal the regional variation in fertility and those may be the result of education, occupation, religion, urbanization, and economic condition of that area
Discriminative Deep Joint Subspace Analysis for Multi-View Data:
No full textOver the past few years, multi-view data analysis has emerged as an inevitable method for identifying sample categories. In multi-view data classification problem, it is expected that the joint subspace is learned from the given input views in such a way that the similarity in the latent space implies the similarity in the corresponding concepts. Since each view has different statistical properties, the joint subspace should be able to reflect the intrinsic properties of each of the input views. Another important aspect is the coherent knowledge of the multiple views. It is required that the learning objective of the multi-view model efficiently captures the non-linear correlated structures across different views. Cross-view dependency is also an essential attribute of multi-view learning in which the primary focus to discover the dependency shared between the pairs of input views. If one or more input views correspond to images, then then joint subspace should be learned in such a way that the topological properties of the image views are properly preserved along with the inherent chracteristics of the rest of the views. In this regard, the thesis addresses the classification problem of multi-view data, where the primary objective is to identify and analyze the inherent structures or patterns of the data, relevant to classify the given observations into different categories. In order to evaluate the relevance of a view in differentiating observations from a particular class from the observations belonging to the rest of the classes, a novel framework is developed by judiciously integrating the theory of rough sets with the Bayes decision theory. While rough set theory deals with the uncertainty due to incompleteness in class definition, the probabilistic model addresses the uncertainty due to overlapping classes by measuring the belongingness of an observation to a specific class. In multi-view learning, it is essential that a joint subspace is learned from the given input views which can efficiently encapsulate the underlying non-linear data distribution of the given observations. In this regard, the thesis develops deep predictive models based on the framework of deep Boltzmann machine for discriminability, correlation, and dependency analysis. In discriminability analysis, the class nodes are incorporated into the deep architecture where the supervised information is clamped. Through proper learning of the weights associated with the class nodes, the discriminative ability of the latent subspace is enhanced. In correlation analysis, the learning objective of the deep architecture is judiciously integrated with canonical correlation analysis such that given the input views, the joint subspace is learned from maximally correlated subspaces. In dependency analysis, the relationship between each pair of views is assumed to be unique. Hence, a view-pair specific approach is developed based on the concept of Hilbert-Schmidt independence criterion to efficiently encapsulate the cross-view dependency in terms of consensus and/or complementary knowledge from the input pairs of views. Based on the Bayes error analysis, an upper bound on the error probability of the proposed deep model is estimated in terms of the model architecture. It facilitates determining the optimal architecture of the proposed model for each database considered. Combining information from multiple views is particularly challenging when the input views involve both image and non-image information. In case of multi-view data analysis, it is essential that descriptive and comprehensive information is efficiently extracted from all the views of the given input data. If one or more input views correspond to image information, then it should be ensured that the innate topological properties of each of the input image views are appropriately reflected in the joint subspace. In this regard, a geometrically motivated deep predictive model is developed, which can process multiple image and non-image views simultaneously. In order to recognize and represent the geometric structures of the image manifolds, embedded in the high- dimensional ambient space, the theory of Laplacian eigenmap is judiciously integrated with the learning objective of the deep predictive model. An approximate common eigenbasis of the Laplacians is computed to consolidate the intrinsic geometric structures of the manifolds, corresponding to each of the input image view
Message Efficient Fault-Tolerant Distributed Computations
No full textThe thesis focuses on exploring the message complexity of some fundamental problems – leader election, agreement, and graph realization. Leader Election and Agreement problems are widely applicable in various domains such as sensor networks, IoT networks, grid computing, peer-to-peer networks, and cloud computing. Achieving low-cost and scalable leader election and agreement protocols with probabilistic guarantees is often desirable in large-scale distributed networks. Fur- thermore, the rise of permissionless distributed systems has made it necessary to design protocols that can tolerate an arbitrary number of faulty nodes. On the other hand, graph realization problems deal with constructing graphs that satisfy certain predefined properties (such as a degree sequence) in the presence of crashes. Despite intensive research, there has yet to be a practical solution to fault-tolerant problems for large-scale networks. One key reason for this is the large message complexity of currently known protocols. In this thesis, we focus on two main questions: (1) How efficiently leader election, agreement, and graph realization can be computed in a distributed network? (2) What can be the resilience of the network and how does it affect the complexity? In this thesis, we study four problems to address the above questions: (i) Leader election and agreement under crash fault (ii) Byzantine agreement (BA) (iii) Distributed graph realization, and (iv) Leader election in diameter-two networks. We present randomized (Monte Carlo) algorithms for leader election and agreement problems that achieve sublinear (in n, number of nodes) message complexity in the implicit version of the two problems when tolerating more than a constant frac- tion of the faulty nodes. Our algorithms tolerate any number of faulty nodes up to (n − polylog n) which is compensated by the increased complexity. The message complexity (and also the time complexity) of our algorithms is optimal (up to a polylog n factor). Further, we study the message complexity of authenticated Byzantine agreements under an honest majority. We focus on the “im- plicit” Byzantine agreement problem and show that a sublinear message complexity BA protocol under honest majority is possible in the standard PKI model when the nodes have access to an unbiased global coin and hash function. Our algorithm is optimal (up to a polylog n factor) and works in anonymous networks, where nodes do not know each other. We further study the graph realization problem in the Congested Clique model of distributed computing under crash faults. Our main result is a O(f )-round deterministic algorithm for the degree-sequence realization prob- lem in a n-node Congested Clique, of which f nodes could be faulty (f \u3c n). The algorithm uses O(n2) messages. Our results are optimal in both the models with or without the knowledge of the neighbors (a.k.a. KT1 and KT0 model) w.r.t the number of rounds and the messages simultane- ously. Later, we investigate the leader election problem in diameter-two networks. We present a O(log n)-round deterministic leader election algorithm which incurs optimal O(n log n) messages without the knowledge of n
Tight Security of PMAC-type and CBC-type Message Authentication Codes
No full textMessage Authentication Codes (or MACs) are symmetric-key primitives that ensure the authenticity as well as the integrity of messages. The sender generates an authen- tication tag (based on a message and a secret key) which can be verified on the re- ceiver’s end. Two paradigms for building block cipher based MACs of the form Hash- then-PRP: 1) Parallelizable or PMAC-type, 2) Sequential or CBC-type. PMAC, sPMAC, PMAC1, LightMAC etc. are examples of PMAC-type MACs. Whereas OMAC, XCBC, TMAC, GCBC are examples of CBC-type MACs. Obtaining length independent (tight) bounds for these constructions has been a challenging problem. The goal of this thesis is to obtain length independent (tight) bounds for as many important constructions as possible and devise a novel technique that can be employed for various constructions and has a scope of generalization. PMAC-TYPE MACS: Firstly, in chapter 3, we demonstrate why a claim about tight se- curity of a PMAC variant proposed by Naito is wrong. Together with that, we state a necessary and sufficient condition to correctly establish that claim. Secondly, in the same chapter, we propose a variant of PMAC1 which has tight security for a rea- sonable range of message lengths. Then we prove the tight security of sPMAC for a weaker notion of independence (of hash). Next, in chapter 4, we analyze secu- rity bounds for LightMAC: We show tight security of 1k-LightMAC (single-key version of the original LightMAC) which holds for a range of lengths (both upper and lower bounded). Moreover, we show an attack on 1k-LightMAC for sufficiently small-length messages. Besides we propose two new variants of 1k-LightMAC, namely, LightMAC- swp and LightMAC-ds, both of which achieve length independent tight security for a fairly good range of lengths. Here we employ a novel sampling technique, dubbed “Reset-sampling”, as a subroutine of H-coefficient setup. It helps get tight bounds. Then, in the last chapter (5) of this part, we try to get a generalized view of the PMAC family. We develop technical concepts necessary to cover a large class of parallelizable MACs of the form hash-then-PRP. As the main results of this chapter, we prove the se- curity bound in terms of the collision probability of the underlying hash function, both for independent keys and single-keyed versions of a generic member of the PMAC family. As a corollary to this, we apply this result to get birthday-bound security for a simplified version of PMAC+, under some assumptions. Moreover, a similar bound for 1k-LightMAC as well follows directly from the main result. CBC-TYPE MACS: In chapter 6, we obtain O( q2 2n + qℓ2 2n ) bound for OMAC using reset- sampling . This is the best-known bound for it. Although it is not “length independent” in an exact sense, it behaves almost like a birthday bound with some consideration. We obtain similar bounds for XCBC and TMAC also. In this way, we become successful in establishing tight security for all CBC-MAC variants, except the original one
Some Studies on Mathematical Morphology in Remotely Sensed Data Analysis
No full textThe application of Mathematical Morphology (MM) techniques has proven to be beneficial in the extraction of shapebased and texture-based features during remote sensing image analysis. The characteristics of these techniques, such as nonlinear adaptability and comprehensive lattice structure, make them useful for contextual spatial feature analysis. Despite the advancements, there are still persistent challenges, including the curse of dimensionality, maintaining spatial correlation, and the adaptability of morphological operators in higher dimensions. The focus of this thesis is to explore the potential of MM-based methods to analyse spatial features in addressing these challenges, specifically in the context of spatialcontextual feature analysis of hyperspectral images and Digital Elevation Models. This thesis explores the power of morphological distance in capturing spatial relationships and proposes a modified definition called Dilation Distance to address the Dimensionality Curse in hyperspectral images. By employing dilation-based distances, spatially separated objects can be identified, reducing redundancy and enhancing efficiency. Experimental trials demonstrate the superiority of the proposed approach. Additionally, the thesis introduces a new approach using morphological interpolation for terrain surface interpolation, preserving geometric structure while providing a smooth surface. The extension of conventional univariate morphological tools to hyperspectral images in a multivariate way is also explored, ensuring the concurrent application of operators while preserving the multivariate nature of the data. To achieve that a vector ordering strategy is proposed. Overall, these techniques have a profound impact on the progress of mathematical morphology in remotely sensed image analysis, offering valuable insights
A Conformable Moments-Based Deep Learning System for Forged Handwriting Detection
No full textDetecting forged handwriting is important in a wide variety of machine learning applications, and it is challenging when the input images are degraded with noise and blur. This article presents a new model based on conformable moments (CMs) and deep ensemble neural networks (DENNs) for forged handwriting detection in noisy and blurry environments. Since CMs involve fractional calculus with the ability to model nonlinearities and geometrical moments as well as preserving spatial relationships between pixels, fine details in images are preserved. This motivates us to introduce a DENN classifier, which integrates stenographic kernels and spatial features to classify input images as normal (original, clean images), altered (handwriting changed through copy-paste and insertion operations), noisy (added noise to original image), blurred (added blur to original image), altered-noise (noise is added to the altered image), and altered-blurred (blur is added to the altered image). To evaluate our model, we use a newly introduced dataset, which comprises handwritten words altered at the character level, as well as several standard datasets, namely ACPR 2019, ICPR 2018-FDC, and the IMEI dataset. The first two of these datasets include handwriting samples that are altered at the character and word levels, and the third dataset comprises forged International Mobile Equipment Identity (IMEI) numbers. Experimental results demonstrate that the proposed method outperforms the existing methods in terms of classification rate
A Locally Weighted Linear Regression-Based Approach for Arbitrary Moving Shaky and Nonshaky Video Classification
No full textClassification and identification of objects are complex and challenging in pattern recognition and artificial intelligence if a shaky and nonshaky camera captures the videos at different distances during the day and nighttime. This work presents a model for classifying a given video as a static, uniform, or arbitrarily moving videos so that the complexity of the problem can be reduced. To avoid the threat of different distances between the objects and the camera, the proposed work introduces new steps for estimating the depth of the objects in the video frames. We explore locally weighted linear regression for feature extraction from depth information based on the notion that the regression line fits almost all the points for uniformity and does not fit for arbitrary moving. The extracted features are fed to a random forest classifier to classify static, uniform, or arbitrary moving video. The results on a large dataset, which includes videos captured day and night, show that the proposed method successfully classifies static, uniform and arbitrary videos with 0.86, 1.00 and 0.67 F-measures, respectively. Overall, our method obtains 87% accuracy for classification of static, uniform and arbitrary video, which is superior to the state-of-the-art methods
Coloring of Graphs with no Induced Six-Vertex path
No full textGraph coloring is one among the oldest and broadly studied topics in graph theory. A coloring of a graph G is an assignment of colors to the vertices of G such that no two adjacent vertices receive the same color, and the chromatic number of G (denoted by χ(G)) is the minimum number of colors needed to color G. The clique number of G (denoted by ω(G)) is the maximum number of mutually adjacent vertices in G. In this thesis, we focus on some problems on bounding the chromatic number in terms of clique number for certain special classes of graphs with no long induced paths, namely the class of Pt-free graphs, for t ≥ 5. A hereditary class of graphs G is said to be χ-bounded if there exists a function f : N → N with f(1) = 1 and f(x) ≥ x, for all x ∈ N (called a χ-binding function for G) such that χ(G) ≤ f(ω(G)), for each G ∈ G. The smallest χ-binding function f∗ for G is defined as f∗(x) := max{χ(G) : G ∈ G and ω(G) = x}. The class G is called polynomially χ-bounded if it admits a polynomial χ-binding function. An intriguing open question is whether the class of Pt-free graphs is polynomially χ-bounded or not. This problem is open even for t = 5 and seems to be difficult. So researchers are interested in finding (smallest) polynomial χ-binding functions for some subclasses of Pt-free graphs. Here, we explore the structure of some classes of P6-free graphs and obtain (smallest/linear) χ-binding functions for such classes of graphs. Our results generalize/improve several previously known results available in the literature. Chapter 1 consists of a brief introduction on χ-bounded graphs and a short survey on known χ-bounded P6-free graphs. We also provide motivations, algorithmic issues, and relations of χ-boundedness to other well-known/related conjectures in graph theory. In Chapter 2, we study the class of (P2 + P3, P2 + P3)-free graphs, and show that the function f : N → N defined by f(1) = 1, f(2) = 4, and f(x) = max x + 3, 3x 2 − 1 , for x ≥ 3, is the smallest χ-binding function for the class of (P2 + P3, P2 + P3)-free graphs. In Chapter 3, we are interested in the structure of (P5, 4-wheel)-free graphs, and in coloring of such graphs. Indeed, we first prove that if G is a connected (P5, 4-wheel)-free graph, then either G admits a clique cut-set, or G is a perfect graph, or G is a quasi-line graph, or G has three disjoint stable sets whose union meets each maximum clique of G at least twice and the other maximal cliques of G at least once. Using this result, we prove that every (P5, 4-wheel)-free graph G satisfies χ(G) ≤ 3 2ω(G). We also provide infinitely many (P5, 4-wheel)-free graphs H with χ(H) ≥ 10 7 ω(H). It is known that every (P5,K4)-free graph G satisfies χ(G) ≤ 5, and that the bound is tight. Both the class of (P5, flag)-free graphs and the class of (P5, K5 − e)-free graphs generalize the class of (P5,K4)-free graphs. In Chapter 4, we explore the structure and coloring of (P5, K5 − e)-free graphs. In particular, we prove that if G is a connected (P5,K5 − e)-free graph with ω(G) ≥ 7, then either G is the complement of a bipartite graph or G has a clique cut-set. From this result, we show that if G is a (P5,K5 − e)-free graph with ω(G) ≥ 4, then χ(G) ≤ max{7, ω(G)}. Moreover, the bound is tight when ω(G) /∈ {4, 5, 6}. In Chapter 5, we investigate the coloring of (P5, flag)-free graphs. We prove that every (P5, flag,K5)- free graph G that contains a K4 satisfies χ(G) ≤ 8, every (P5, flag,K6)-free graph G satisfies χ(G) ≤ 8, and that every (P5, flag,K7)-free graph G satisfies χ(G) ≤ 9. Moreover, we prove that every (P5, flag)- free graph G with ω(G) ≥ 4 satisfies χ(G) ≤ max{8, 2ω(G) − 3}, and that the bound is tight for ω(G) ∈ {4, 5, 6