Showing 1–50 of 65 results for author: Chakraborty, M

Analysis and Optimization of RIS-Assisted Cell-Free Massive MIMO NOMA Systems

Authors: Malay Chakraborty, Ekant Sharma, Himal A. Suraweera, Hien Quoc Ngo

Abstract: We consider a reconfigurable intelligent surface (RIS) assisted cell-free massive multiple-input multiple-output non-orthogonal multiple access (NOMA) system, where each access point (AP) serves all the users with the aid of the RIS. We practically model the system by considering imperfect instantaneous channel state information (CSI) and employing imperfect successive interference cancellation at… ▽ More We consider a reconfigurable intelligent surface (RIS) assisted cell-free massive multiple-input multiple-output non-orthogonal multiple access (NOMA) system, where each access point (AP) serves all the users with the aid of the RIS. We practically model the system by considering imperfect instantaneous channel state information (CSI) and employing imperfect successive interference cancellation at the users end. We first obtain the channel estimates using linear minimum mean square error approach considering the spatial correlation at the RIS and then derive a closed-form downlink spectral efficiency (SE) expression using the statistical CSI. We next formulate a joint optimization problem to maximize the sum SE of the system. We first introduce a novel successive Quadratic Transform (successive-QT) algorithm to optimize the transmit power coefficients using the concept of block optimization along with quadratic transform and then use the particle swarm optimization technique to design the RIS phase shifts. Note that most of the existing works on RIS-aided cell-free systems are specific instances of the general scenario studied in this work. We numerically show that i) the RIS-assisted link is more advantageous at lower transmit power regions where the direct link between AP and user is weak, ii) NOMA outperforms orthogonal multiple access schemes in terms of SE, and iii) the proposed joint optimization framework significantly improves the sum SE of the system. △ Less

Submitted 4 July, 2024; originally announced July 2024.

An Empirical Study of Using ChatGPT for Fact Verification Task

Authors: Mohna Chakraborty, Adithya Kulkarni, Qi Li

Abstract: ChatGPT has recently emerged as a powerful tool for performing diverse NLP tasks. However, ChatGPT has been criticized for generating nonfactual responses, raising concerns about its usability for sensitive tasks like fact verification. This study investigates three key research questions: (1) Can ChatGPT be used for fact verification tasks? (2) What are different prompts performance using ChatGPT… ▽ More ChatGPT has recently emerged as a powerful tool for performing diverse NLP tasks. However, ChatGPT has been criticized for generating nonfactual responses, raising concerns about its usability for sensitive tasks like fact verification. This study investigates three key research questions: (1) Can ChatGPT be used for fact verification tasks? (2) What are different prompts performance using ChatGPT for fact verification tasks? (3) For the best-performing prompt, what common mistakes does ChatGPT make? Specifically, this study focuses on conducting a comprehensive and systematic analysis by designing and comparing the performance of three different prompts for fact verification tasks on the benchmark FEVER dataset using ChatGPT. △ Less

Submitted 11 November, 2023; originally announced November 2023.

Exploring Large Language Models for Code Explanation

Authors: Paheli Bhattacharya, Manojit Chakraborty, Kartheek N S N Palepu, Vikas Pandey, Ishan Dindorkar, Rakesh Rajpurohit, Rishabh Gupta

Abstract: Automating code documentation through explanatory text can prove highly beneficial in code understanding. Large Language Models (LLMs) have made remarkable strides in Natural Language Processing, especially within software engineering tasks such as code generation and code summarization. This study specifically delves into the task of generating natural-language summaries for code snippets, using… ▽ More Automating code documentation through explanatory text can prove highly beneficial in code understanding. Large Language Models (LLMs) have made remarkable strides in Natural Language Processing, especially within software engineering tasks such as code generation and code summarization. This study specifically delves into the task of generating natural-language summaries for code snippets, using various LLMs. The findings indicate that Code LLMs outperform their generic counterparts, and zero-shot methods yield superior results when dealing with datasets with dissimilar distributions between training and testing sets. △ Less

Submitted 25 October, 2023; originally announced October 2023.

Comments: Accepted at the Forum for Information Retrieval Evaluation 2023 (IRSE Track)

ACM Class: D.2.3; I.7

Counter Turing Test CT^2: AI-Generated Text Detection is Not as Easy as You May Think -- Introducing AI Detectability Index

Authors: Megha Chakraborty, S. M Towhidul Islam Tonmoy, S M Mehedi Zaman, Krish Sharma, Niyar R Barman, Chandan Gupta, Shreya Gautam, Tanay Kumar, Vinija Jain, Aman Chadha, Amit P. Sheth, Amitava Das

Abstract: With the rise of prolific ChatGPT, the risk and consequences of AI-generated text has increased alarmingly. To address the inevitable question of ownership attribution for AI-generated artifacts, the US Copyright Office released a statement stating that 'If a work's traditional elements of authorship were produced by a machine, the work lacks human authorship and the Office will not register it'.… ▽ More With the rise of prolific ChatGPT, the risk and consequences of AI-generated text has increased alarmingly. To address the inevitable question of ownership attribution for AI-generated artifacts, the US Copyright Office released a statement stating that 'If a work's traditional elements of authorship were produced by a machine, the work lacks human authorship and the Office will not register it'. Furthermore, both the US and the EU governments have recently drafted their initial proposals regarding the regulatory framework for AI. Given this cynosural spotlight on generative AI, AI-generated text detection (AGTD) has emerged as a topic that has already received immediate attention in research, with some initial methods having been proposed, soon followed by emergence of techniques to bypass detection. This paper introduces the Counter Turing Test (CT^2), a benchmark consisting of techniques aiming to offer a comprehensive evaluation of the robustness of existing AGTD techniques. Our empirical findings unequivocally highlight the fragility of the proposed AGTD methods under scrutiny. Amidst the extensive deliberations on policy-making for regulating AI development, it is of utmost importance to assess the detectability of content generated by LLMs. Thus, to establish a quantifiable spectrum facilitating the evaluation and ranking of LLMs according to their detectability levels, we propose the AI Detectability Index (ADI). We conduct a thorough examination of 15 contemporary LLMs, empirically demonstrating that larger LLMs tend to have a higher ADI, indicating they are less detectable compared to smaller LLMs. We firmly believe that ADI holds significant value as a tool for the wider NLP community, with the potential to serve as a rubric in AI-related policy-making. △ Less

Submitted 23 October, 2023; v1 submitted 8 October, 2023; originally announced October 2023.

Comments: EMNLP 2023 Main

Overview of Memotion 3: Sentiment and Emotion Analysis of Codemixed Hinglish Memes

Authors: Shreyash Mishra, S Suryavardan, Megha Chakraborty, Parth Patwa, Anku Rani, Aman Chadha, Aishwarya Reganti, Amitava Das, Amit Sheth, Manoj Chinnakotla, Asif Ekbal, Srijan Kumar

Abstract: Analyzing memes on the internet has emerged as a crucial endeavor due to the impact this multi-modal form of content wields in shaping online discourse. Memes have become a powerful tool for expressing emotions and sentiments, possibly even spreading hate and misinformation, through humor and sarcasm. In this paper, we present the overview of the Memotion 3 shared task, as part of the DeFactify 2… ▽ More Analyzing memes on the internet has emerged as a crucial endeavor due to the impact this multi-modal form of content wields in shaping online discourse. Memes have become a powerful tool for expressing emotions and sentiments, possibly even spreading hate and misinformation, through humor and sarcasm. In this paper, we present the overview of the Memotion 3 shared task, as part of the DeFactify 2 workshop at AAAI-23. The task released an annotated dataset of Hindi-English code-mixed memes based on their Sentiment (Task A), Emotion (Task B), and Emotion intensity (Task C). Each of these is defined as an individual task and the participants are ranked separately for each task. Over 50 teams registered for the shared task and 5 made final submissions to the test set of the Memotion 3 dataset. CLIP, BERT modifications, ViT etc. were the most popular models among the participants along with approaches such as Student-Teacher model, Fusion, and Ensembling. The best final F1 score for Task A is 34.41, Task B is 79.77 and Task C is 59.82. △ Less

Submitted 12 September, 2023; originally announced September 2023.

Comments: Defactify2 @AAAI 2023

Deep Ear Biometrics for Gender Classification

Authors: Ritwiz Singh, Keshav Kashyap, Rajesh Mukherjee, Asish Bera, Mamata Dalui Chakraborty

Abstract: Human gender classification based on biometric features is a major concern for computer vision due to its vast variety of applications. The human ear is popular among researchers as a soft biometric trait, because it is less affected by age or changing circumstances, and is non-intrusive. In this study, we have developed a deep convolutional neural network (CNN) model for automatic gender classifi… ▽ More Human gender classification based on biometric features is a major concern for computer vision due to its vast variety of applications. The human ear is popular among researchers as a soft biometric trait, because it is less affected by age or changing circumstances, and is non-intrusive. In this study, we have developed a deep convolutional neural network (CNN) model for automatic gender classification using the samples of ear images. The performance is evaluated using four cutting-edge pre-trained CNN models. In terms of trainable parameters, the proposed technique requires significantly less computational complexity. The proposed model has achieved 93% accuracy on the EarVN1.0 ear dataset. △ Less

Submitted 17 August, 2023; originally announced August 2023.

Comments: 10 pages, 4 figures, 2 tables

Findings of Factify 2: Multimodal Fake News Detection

Authors: S Suryavardan, Shreyash Mishra, Megha Chakraborty, Parth Patwa, Anku Rani, Aman Chadha, Aishwarya Reganti, Amitava Das, Amit Sheth, Manoj Chinnakotla, Asif Ekbal, Srijan Kumar

Abstract: With social media usage growing exponentially in the past few years, fake news has also become extremely prevalent. The detrimental impact of fake news emphasizes the need for research focused on automating the detection of false information and verifying its accuracy. In this work, we present the outcome of the Factify 2 shared task, which provides a multi-modal fact verification and satire news… ▽ More With social media usage growing exponentially in the past few years, fake news has also become extremely prevalent. The detrimental impact of fake news emphasizes the need for research focused on automating the detection of false information and verifying its accuracy. In this work, we present the outcome of the Factify 2 shared task, which provides a multi-modal fact verification and satire news dataset, as part of the DeFactify 2 workshop at AAAI'23. The data calls for a comparison based approach to the task by pairing social media claims with supporting documents, with both text and image, divided into 5 classes based on multi-modal relations. In the second iteration of this task we had over 60 participants and 9 final test-set submissions. The best performances came from the use of DeBERTa for text and Swinv2 and CLIP for image. The highest F1 score averaged for all five classes was 81.82%. △ Less

Submitted 12 September, 2023; v1 submitted 19 July, 2023; originally announced July 2023.

Comments: Defactify2 @AAAI 2023

FACTIFY3M: A Benchmark for Multimodal Fact Verification with Explainability through 5W Question-Answering

Authors: Megha Chakraborty, Khushbu Pahwa, Anku Rani, Shreyas Chatterjee, Dwip Dalal, Harshit Dave, Ritvik G, Preethi Gurumurthy, Adarsh Mahor, Samahriti Mukherjee, Aditya Pakala, Ishan Paul, Janvita Reddy, Arghya Sarkar, Kinjal Sensharma, Aman Chadha, Amit P. Sheth, Amitava Das

Abstract: Combating disinformation is one of the burning societal crises -- about 67% of the American population believes that disinformation produces a lot of uncertainty, and 10% of them knowingly propagate disinformation. Evidence shows that disinformation can manipulate democratic processes and public opinion, causing disruption in the share market, panic and anxiety in society, and even death during cr… ▽ More Combating disinformation is one of the burning societal crises -- about 67% of the American population believes that disinformation produces a lot of uncertainty, and 10% of them knowingly propagate disinformation. Evidence shows that disinformation can manipulate democratic processes and public opinion, causing disruption in the share market, panic and anxiety in society, and even death during crises. Therefore, disinformation should be identified promptly and, if possible, mitigated. With approximately 3.2 billion images and 720,000 hours of video shared online daily on social media platforms, scalable detection of multimodal disinformation requires efficient fact verification. Despite progress in automatic text-based fact verification (e.g., FEVER, LIAR), the research community lacks substantial effort in multimodal fact verification. To address this gap, we introduce FACTIFY 3M, a dataset of 3 million samples that pushes the boundaries of the domain of fact verification via a multimodal fake news dataset, in addition to offering explainability through the concept of 5W question-answering. Salient features of the dataset include: (i) textual claims, (ii) ChatGPT-generated paraphrased claims, (iii) associated images, (iv) stable diffusion-generated additional images (i.e., visual paraphrases), (v) pixel-level image heatmap to foster image-text explainability of the claim, (vi) 5W QA pairs, and (vii) adversarial fake news stories. △ Less

Submitted 30 October, 2023; v1 submitted 22 May, 2023; originally announced June 2023.

Comments: arXiv admin note: text overlap with arXiv:2305.04329

Beryllium: Neural Search for Algorithm Implementations

Authors: Adithya Kulkarni, Mohna Chakraborty, Yonas Sium, Sai Charishma Valluri, Wei Le, Qi Li

Abstract: In this paper, we explore the feasibility of finding algorithm implementations from code. Successfully matching code and algorithms can help understand unknown code, provide reference implementations, and automatically collect data for learning-based program synthesis. To achieve the goal, we designed a new language named p-language to specify the algorithms and a static analyzer for the p-languag… ▽ More In this paper, we explore the feasibility of finding algorithm implementations from code. Successfully matching code and algorithms can help understand unknown code, provide reference implementations, and automatically collect data for learning-based program synthesis. To achieve the goal, we designed a new language named p-language to specify the algorithms and a static analyzer for the p-language to automatically extract control flow, math, and natural language information from the algorithm descriptions. We embedded the output of p-language (p-code) and source code in a common vector space using self-supervised machine learning methods to match algorithm with code without any manual annotation. We developed a tool named Beryllium. It takes pseudo code as a query and returns a list of ranked code snippets that likely match the algorithm query. Our evaluation on Stony Brook Algorithm Repository and popular GitHub projects show that Beryllium significantly outperformed the state-of-the-art code search tools in both C and Java. Specifically, for 98.5%, 93.8%, and 66.2% queries, we found the algorithm implementations in the top 25, 10, and 1 ranked list, respectively. Given 87 algorithm queries, we found implementations for 74 algorithms in the GitHub projects where we did not know the algorithms before. △ Less

Submitted 1 July, 2023; v1 submitted 24 May, 2023; originally announced May 2023.

Zero-shot Approach to Overcome Perturbation Sensitivity of Prompts

Authors: Mohna Chakraborty, Adithya Kulkarni, Qi Li

Abstract: Recent studies have demonstrated that natural-language prompts can help to leverage the knowledge learned by pre-trained language models for the binary sentence-level sentiment classification task. Specifically, these methods utilize few-shot learning settings to fine-tune the sentiment classification model using manual or automatically generated prompts. However, the performance of these methods… ▽ More Recent studies have demonstrated that natural-language prompts can help to leverage the knowledge learned by pre-trained language models for the binary sentence-level sentiment classification task. Specifically, these methods utilize few-shot learning settings to fine-tune the sentiment classification model using manual or automatically generated prompts. However, the performance of these methods is sensitive to the perturbations of the utilized prompts. Furthermore, these methods depend on a few labeled instances for automatic prompt generation and prompt ranking. This study aims to find high-quality prompts for the given task in a zero-shot setting. Given a base prompt, our proposed approach automatically generates multiple prompts similar to the base prompt employing positional, reasoning, and paraphrasing techniques and then ranks the prompts using a novel metric. We empirically demonstrate that the top-ranked prompts are high-quality and significantly outperform the base prompt and the prompts generated using few-shot learning for the binary sentence-level sentiment classification task. △ Less

Submitted 1 July, 2023; v1 submitted 24 May, 2023; originally announced May 2023.

IMAGINATOR: Pre-Trained Image+Text Joint Embeddings using Word-Level Grounding of Images

Authors: Varuna Krishna, S Suryavardan, Shreyash Mishra, Sathyanarayanan Ramamoorthy, Parth Patwa, Megha Chakraborty, Aman Chadha, Amitava Das, Amit Sheth

Abstract: Word embeddings, i.e., semantically meaningful vector representation of words, are largely influenced by the distributional hypothesis "You shall know a word by the company it keeps" (Harris, 1954), whereas modern prediction-based neural network embeddings rely on design choices and hyperparameter optimization. Word embeddings like Word2Vec, GloVe etc. well capture the contextuality and real-world… ▽ More Word embeddings, i.e., semantically meaningful vector representation of words, are largely influenced by the distributional hypothesis "You shall know a word by the company it keeps" (Harris, 1954), whereas modern prediction-based neural network embeddings rely on design choices and hyperparameter optimization. Word embeddings like Word2Vec, GloVe etc. well capture the contextuality and real-world analogies but contemporary convolution-based image embeddings such as VGGNet, AlexNet, etc. do not capture contextual knowledge. The popular king-queen analogy does not hold true for most commonly used vision embeddings. In this paper, we introduce a pre-trained joint embedding (JE), named IMAGINATOR, trained on 21K distinct image objects level from 1M image+text pairs. JE is a way to encode multimodal data into a vector space where the text modality serves as the ground-ing key, which the complementary modality (in this case, the image) is anchored with. IMAGINATOR encapsulates three individual representations: (i) object-object co-location, (ii) word-object co-location, and (iii) word-object correlation. These three ways capture complementary aspects of the two modalities which are further combined to obtain the final JEs. Generated JEs are intrinsically evaluated to assess how well they capture the contextuality and real-world analogies. We also evaluate pre-trained IMAGINATOR JEs on three downstream tasks: (i) image captioning, (ii) Image2Tweet, and (iii) text-based image retrieval. IMAGINATOR establishes a new standard on the aforementioned down-stream tasks by outperforming the current SoTA on all the selected tasks. IMAGINATOR will be made publicly available. The codes are available at https://github.com/varunakk/IMAGINATOR △ Less

Submitted 12 May, 2023; originally announced May 2023.

A Survey on Multi-Objective based Parameter Optimization for Deep Learning

Authors: Mrittika Chakraborty, Wreetbhas Pal, Sanghamitra Bandyopadhyay, Ujjwal Maulik

Abstract: Deep learning models form one of the most powerful machine learning models for the extraction of important features. Most of the designs of deep neural models, i.e., the initialization of parameters, are still manually tuned. Hence, obtaining a model with high performance is exceedingly time-consuming and occasionally impossible. Optimizing the parameters of the deep networks, therefore, requires… ▽ More Deep learning models form one of the most powerful machine learning models for the extraction of important features. Most of the designs of deep neural models, i.e., the initialization of parameters, are still manually tuned. Hence, obtaining a model with high performance is exceedingly time-consuming and occasionally impossible. Optimizing the parameters of the deep networks, therefore, requires improved optimization algorithms with high convergence rates. The single objective-based optimization methods generally used are mostly time-consuming and do not guarantee optimum performance in all cases. Mathematical optimization problems containing multiple objective functions that must be optimized simultaneously fall under the category of multi-objective optimization sometimes referred to as Pareto optimization. Multi-objective optimization problems form one of the alternatives yet useful options for parameter optimization. However, this domain is a bit less explored. In this survey, we focus on exploring the effectiveness of multi-objective optimization strategies for parameter optimization in conjunction with deep neural networks. The case studies used in this study focus on how the two methods are combined to provide valuable insights into the generation of predictions and analysis in multiple applications. △ Less

Submitted 17 May, 2023; originally announced May 2023.

Comments: The paper has been accepted for publication in Computer Science journal: http://journals.agh.edu.pl/csci

FACTIFY-5WQA: 5W Aspect-based Fact Verification through Question Answering

Authors: Anku Rani, S. M Towhidul Islam Tonmoy, Dwip Dalal, Shreya Gautam, Megha Chakraborty, Aman Chadha, Amit Sheth, Amitava Das

Abstract: Automatic fact verification has received significant attention recently. Contemporary automatic fact-checking systems focus on estimating truthfulness using numerical scores which are not human-interpretable. A human fact-checker generally follows several logical steps to verify a verisimilitude claim and conclude whether its truthful or a mere masquerade. Popular fact-checking websites follow a c… ▽ More Automatic fact verification has received significant attention recently. Contemporary automatic fact-checking systems focus on estimating truthfulness using numerical scores which are not human-interpretable. A human fact-checker generally follows several logical steps to verify a verisimilitude claim and conclude whether its truthful or a mere masquerade. Popular fact-checking websites follow a common structure for fact categorization such as half true, half false, false, pants on fire, etc. Therefore, it is necessary to have an aspect-based (delineating which part(s) are true and which are false) explainable system that can assist human fact-checkers in asking relevant questions related to a fact, which can then be validated separately to reach a final verdict. In this paper, we propose a 5W framework (who, what, when, where, and why) for question-answer-based fact explainability. To that end, we present a semi-automatically generated dataset called FACTIFY-5WQA, which consists of 391, 041 facts along with relevant 5W QAs - underscoring our major contribution to this paper. A semantic role labeling system has been utilized to locate 5Ws, which generates QA pairs for claims using a masked language model. Finally, we report a baseline QA system to automatically locate those answers from evidence documents, which can serve as a baseline for future research in the field. Lastly, we propose a robust fact verification system that takes paraphrased claims and automatically validates them. The dataset and the baseline model are available at https: //github.com/ankuranii/acl-5W-QA △ Less

Submitted 28 May, 2023; v1 submitted 7 May, 2023; originally announced May 2023.

Comments: Accepted at ACL main conference 2023

Factify 2: A Multimodal Fake News and Satire News Dataset

Authors: S Suryavardan, Shreyash Mishra, Parth Patwa, Megha Chakraborty, Anku Rani, Aishwarya Reganti, Aman Chadha, Amitava Das, Amit Sheth, Manoj Chinnakotla, Asif Ekbal, Srijan Kumar

Abstract: The internet gives the world an open platform to express their views and share their stories. While this is very valuable, it makes fake news one of our society's most pressing problems. Manual fact checking process is time consuming, which makes it challenging to disprove misleading assertions before they cause significant harm. This is he driving interest in automatic fact or claim verification.… ▽ More The internet gives the world an open platform to express their views and share their stories. While this is very valuable, it makes fake news one of our society's most pressing problems. Manual fact checking process is time consuming, which makes it challenging to disprove misleading assertions before they cause significant harm. This is he driving interest in automatic fact or claim verification. Some of the existing datasets aim to support development of automating fact-checking techniques, however, most of them are text based. Multi-modal fact verification has received relatively scant attention. In this paper, we provide a multi-modal fact-checking dataset called FACTIFY 2, improving Factify 1 by using new data sources and adding satire articles. Factify 2 has 50,000 new data instances. Similar to FACTIFY 1.0, we have three broad categories - support, no-evidence, and refute, with sub-categories based on the entailment of visual and textual data. We also provide a BERT and Vison Transformer based baseline, which achieves 65% F1 score in the test set. The baseline codes and the dataset will be made available at https://github.com/surya1701/Factify-2.0. △ Less

Submitted 2 October, 2023; v1 submitted 7 April, 2023; originally announced April 2023.

Comments: Defactify2 @AAAI2023

Memotion 3: Dataset on Sentiment and Emotion Analysis of Codemixed Hindi-English Memes

Authors: Shreyash Mishra, S Suryavardan, Parth Patwa, Megha Chakraborty, Anku Rani, Aishwarya Reganti, Aman Chadha, Amitava Das, Amit Sheth, Manoj Chinnakotla, Asif Ekbal, Srijan Kumar

Abstract: Memes are the new-age conveyance mechanism for humor on social media sites. Memes often include an image and some text. Memes can be used to promote disinformation or hatred, thus it is crucial to investigate in details. We introduce Memotion 3, a new dataset with 10,000 annotated memes. Unlike other prevalent datasets in the domain, including prior iterations of Memotion, Memotion 3 introduces Hi… ▽ More Memes are the new-age conveyance mechanism for humor on social media sites. Memes often include an image and some text. Memes can be used to promote disinformation or hatred, thus it is crucial to investigate in details. We introduce Memotion 3, a new dataset with 10,000 annotated memes. Unlike other prevalent datasets in the domain, including prior iterations of Memotion, Memotion 3 introduces Hindi-English Codemixed memes while prior works in the area were limited to only the English memes. We describe the Memotion task, the data collection and the dataset creation methodologies. We also provide a baseline for the task. The baseline code and dataset will be made available at https://github.com/Shreyashm16/Memotion-3.0 △ Less

Submitted 2 October, 2023; v1 submitted 17 March, 2023; originally announced March 2023.

Comments: Defactify2 @AAAI

Mathematical Model of Quantum Channel Capacity

Authors: Mouli Chakraborty, Harun Siljak, Indrakshi Dey, Nicola Marchetti

Abstract: In this article, we are proposing a closed-form solution for the capacity of the single quantum channel. The Gaussian distributed input has been considered for the analytical calculation of the capacity. In our previous couple of papers, we invoked models for joint quantum noise and the corresponding received signals; in this current research, we proved that these models are Gaussian mixtures dist… ▽ More In this article, we are proposing a closed-form solution for the capacity of the single quantum channel. The Gaussian distributed input has been considered for the analytical calculation of the capacity. In our previous couple of papers, we invoked models for joint quantum noise and the corresponding received signals; in this current research, we proved that these models are Gaussian mixtures distributions. In this paper, we showed how to deal with both of cases, namely (I)the Gaussian mixtures distribution for scalar variables and (II) the Gaussian mixtures distribution for random vectors. Our target is to calculate the entropy of the joint noise and the entropy of the received signal in order to calculate the capacity expression of the quantum channel. The main challenge is to work with the function type of the Gaussian mixture distribution. The entropy of the Gaussian mixture distributions cannot be calculated in the closed-form solution due to the logarithm of a sum of exponential functions. As a solution, we proposed a lower bound and a upper bound for each of the entropies of joint noise and the received signal, and finally upper inequality and lower inequality lead to the upper bound for the mutual information and hence the maximum achievable data rate as the capacity. In this paper reader will able to visualize an closed-form capacity experssion which make this paper distinct from our previous works. These capacity experssion and coresses ponding bounds are calculated for both the cases: the Gaussian mixtures distribution for scalar variables and the Gaussian mixtures distribution for random vectors as well. △ Less

Submitted 16 February, 2023; v1 submitted 9 February, 2023; originally announced February 2023.

Comments: Needs further modifications

Exploiting Extensive-Form Structure in Empirical Game-Theoretic Analysis

Authors: Christine Konicki, Mithun Chakraborty, Michael P. Wellman

Abstract: Empirical game-theoretic analysis (EGTA) is a general framework for reasoning about complex games using agent-based simulation. Data from simulating select strategy profiles is employed to estimate a cogent and tractable game model approximating the underlying game. To date, EGTA methodology has focused on game models in normal form; though the simulations play out in sequential observations and d… ▽ More Empirical game-theoretic analysis (EGTA) is a general framework for reasoning about complex games using agent-based simulation. Data from simulating select strategy profiles is employed to estimate a cogent and tractable game model approximating the underlying game. To date, EGTA methodology has focused on game models in normal form; though the simulations play out in sequential observations and decisions over time, the game model abstracts away this temporal structure. Richer models of \textit{extensive-form games} (EFGs) provide a means to capture temporal patterns in action and information, using tree representations. We propose \textit{tree-exploiting EGTA} (TE-EGTA), an approach to incorporate EFG models into EGTA\@. TE-EGTA constructs game models that express observations and temporal organization of activity, albeit at a coarser grain than the underlying agent-based simulation model. The idea is to exploit key structure while maintaining tractability. We establish theoretically and experimentally that exploiting even a little temporal structure can vastly reduce estimation error in strategy-profile payoffs compared to the normal-form model. Further, we explore the implications of EFG models for iterative approaches to EGTA, where strategy spaces are extended incrementally. Our experiments on several game instances demonstrate that TE-EGTA can also improve performance in the iterative setting, as measured by the quality of equilibrium approximation as the strategy spaces are expanded. △ Less

Submitted 2 February, 2023; originally announced February 2023.

Comments: This paper has been slightly revised from the original version published at WINE 2022; to wit, the proof included in the appendices of our key theoretical result has been expanded

Journal ref: Web and Internet Economics: 18th International Conference (WINE 2022), Proceedings. 132--149

An Empirical Study on the Bugs Found while Reusing Pre-trained Natural Language Processing Models

Authors: Rangeet Pan, Sumon Biswas, Mohna Chakraborty, Breno Dantas Cruz, Hridesh Rajan

Abstract: In NLP, reusing pre-trained models instead of training from scratch has gained popularity; however, NLP models are mostly black boxes, very large, and often require significant resources. To ease, models trained with large corpora are made available, and developers reuse them for different problems. In contrast, developers mostly build their models from scratch for traditional DL-related problems.… ▽ More In NLP, reusing pre-trained models instead of training from scratch has gained popularity; however, NLP models are mostly black boxes, very large, and often require significant resources. To ease, models trained with large corpora are made available, and developers reuse them for different problems. In contrast, developers mostly build their models from scratch for traditional DL-related problems. By doing so, they have control over the choice of algorithms, data processing, model structure, tuning hyperparameters, etc. Whereas in NLP, due to the reuse of the pre-trained models, NLP developers are limited to little to no control over such design decisions. They either apply tuning or transfer learning on pre-trained models to meet their requirements. Also, NLP models and their corresponding datasets are significantly larger than the traditional DL models and require heavy computation. Such reasons often lead to bugs in the system while reusing the pre-trained models. While bugs in traditional DL software have been intensively studied, the nature of extensive reuse and black-box structure motivates us to understand the different types of bugs that occur while reusing NLP models? What are the root causes of those bugs? How do these bugs affect the system? To answer these questions, We studied the bugs reported while reusing the 11 popular NLP models. We mined 9,214 issues from GitHub repositories and identified 984 bugs. We created a taxonomy with bug types, root causes, and impacts. Our observations led to several findings, including limited access to model internals resulting in a lack of robustness, lack of input validation leading to the propagation of algorithmic and data bias, and high-resource consumption causing more crashes, etc. Our observations suggest several bug patterns, which would greatly facilitate further efforts in reducing bugs in pre-trained models and code reuse. △ Less

Submitted 30 November, 2022; originally announced December 2022.

Comments: 12 pages, 12 figures

MSC Class: 68T50 ACM Class: D.6; D.2.5; D.2.13

Joint Modelling of Quantum and Classical Noise over Unity Quantum Channel

Authors: Mouli Chakraborty, Harun Siljak, Indrakshi Dey, Nicola Marchetti

Abstract: For a continuous-input-continuous-output arbitrarily distributed quantum channel carrying classical information, the channel capacity can be computed in terms of the distribution of the channel envelope, received signal strength over a quantum propagation field and the noise spectral density. If the channel envelope is considered to be unity with unit received signal strength, the factor controlli… ▽ More For a continuous-input-continuous-output arbitrarily distributed quantum channel carrying classical information, the channel capacity can be computed in terms of the distribution of the channel envelope, received signal strength over a quantum propagation field and the noise spectral density. If the channel envelope is considered to be unity with unit received signal strength, the factor controlling the capacity is the noise. Quantum channel carrying classical information will suffer from the combination of classical and quantum noise. Assuming additive Gaussian-distributed classical noise and Poisson-distributed quantum noise, we formulate a hybrid noise model by deriving a joint Gaussian- Poisson distribution in this letter. For the transmitted signal, we consider the mean of signal sample space instead of considering a particular distribution and study how the maximum mutual information varies over such mean value. Capacity is estimated by maximizing the mutual information over unity channel envelope. △ Less

Submitted 8 June, 2022; originally announced June 2022.

Automatic Root Cause Quantification for Missing Edges in JavaScript Call Graphs (Extended Version)

Authors: Madhurima Chakraborty, Renzo Olivares, Manu Sridharan, Behnaz Hassanshahi

Abstract: Building sound and precise static call graphs for real-world JavaScript applications poses an enormous challenge, due to many hard-to-analyze language features. Further, the relative importance of these features may vary depending on the call graph algorithm being used and the class of applications being analyzed. In this paper, we present a technique to automatically quantify the relative importa… ▽ More Building sound and precise static call graphs for real-world JavaScript applications poses an enormous challenge, due to many hard-to-analyze language features. Further, the relative importance of these features may vary depending on the call graph algorithm being used and the class of applications being analyzed. In this paper, we present a technique to automatically quantify the relative importance of different root causes of call graph unsoundness for a set of target applications. The technique works by identifying the dynamic function data flows relevant to each call edge missed by the static analysis, correctly handling cases with multiple root causes and inter-dependent calls. We apply our approach to perform a detailed study of the recall of a state-of-the-art call graph construction technique on a set of framework-based web applications. The study yielded a number of useful insights. We found that while dynamic property accesses were the most common root cause of missed edges across the benchmarks, other root causes varied in importance depending on the benchmark, potentially useful information for an analysis designer. Further, with our approach, we could quickly identify and fix a recall issue in the call graph builder we studied, and also quickly assess whether a recent analysis technique for Node.js-based applications would be helpful for browser-based code. All of our code and data is publicly available, and many components of our technique can be re-used to facilitate future studies. △ Less

Submitted 13 May, 2022; originally announced May 2022.

Comments: Extended version of ECOOP'22 paper (with appendix)

Open Source Software Sustainability: Combining Institutional Analysis and Socio-Technical Networks

Authors: Likang Yin, Mahasweta Chakraborty, Charles Schweik, Seth Frey, Vladimir Filkov

Abstract: Open Source Software (OSS) forms much of the fabric of our digital society, especially successful and sustainable ones. But many OSS projects do not become sustainable, resulting in abandonment and even risks for the world's digital infrastructure. Prior work has looked at the reasons for this mainly from two very different perspectives. In software engineering, the focus has been on understanding… ▽ More Open Source Software (OSS) forms much of the fabric of our digital society, especially successful and sustainable ones. But many OSS projects do not become sustainable, resulting in abandonment and even risks for the world's digital infrastructure. Prior work has looked at the reasons for this mainly from two very different perspectives. In software engineering, the focus has been on understanding success and sustainability from the socio-technical perspective: the OSS programmers' day-to-day activities and the artifacts they create. In institutional analysis, on the other hand, emphasis has been on institutional designs (e.g., policies, rules, and norms) that structure governance. Even though each is necessary for a comprehensive understanding of OSS projects, the connection and interaction between the two approaches have been barely explored. In this paper, we make the first effort toward understanding OSS project sustainability using a dual-view analysis, by combining institutional analysis with socio-technical systems analysis. In particular, we (i) use linguistic approaches to extract institutional rules and norms from OSS contributors' communications to represent the evolution of their governance systems, and (ii) construct socio-technical networks based on longitudinal collaboration records to represent each project's organizational structure. We combined the two methods and applied them to a dataset of developer traces from 253 nascent OSS projects within the Apache Software Foundation (ASF) incubator. We find that the socio-technical and institutional features relate to each other, and provide complementary views into the progress of the ASF's OSS projects. Refining these combined analyses can help provide a more precise understanding of the synchronization between the evolution of institutional governance and organizational structure. △ Less

Submitted 7 March, 2022; originally announced March 2022.

Texture Aware Autoencoder Pre-training And Pairwise Learning Refinement For Improved Iris Recognition

Authors: Manashi Chakraborty, Aritri Chakraborty, Prabir Kumar Biswas, Pabitra Mitra

Abstract: This paper presents a texture aware end-to-end trainable iris recognition system, specifically designed for datasets like iris having limited training data. We build upon our previous stagewise learning framework with certain key optimization and architectural innovations. First, we pretrain a Stage-1 encoder network with an unsupervised autoencoder learning optimized with an additional data relat… ▽ More This paper presents a texture aware end-to-end trainable iris recognition system, specifically designed for datasets like iris having limited training data. We build upon our previous stagewise learning framework with certain key optimization and architectural innovations. First, we pretrain a Stage-1 encoder network with an unsupervised autoencoder learning optimized with an additional data relation loss on top of usual reconstruction loss. The data relation loss enables learning better texture representation which is pivotal for a texture rich dataset such as iris. Robustness of Stage-1 feature representation is further enhanced with an auxiliary denoising task. Such pre-training proves beneficial for effectively training deep networks on data constrained iris datasets. Next, in Stage-2 supervised refinement, we design a pairwise learning architecture for an end-to-end trainable iris recognition system. The pairwise learning includes the task of iris matching inside the training pipeline itself and results in significant improvement in recognition performance compared to usual offline matching. We validate our model across three publicly available iris datasets and the proposed model consistently outperforms both traditional and deep learning baselines for both Within-Dataset and Cross-Dataset configurations △ Less

Submitted 15 February, 2022; originally announced February 2022.

Weighted Fairness Notions for Indivisible Items Revisited

Authors: Mithun Chakraborty, Erel Segal-Halevi, Warut Suksompong

Abstract: We revisit the setting of fairly allocating indivisible items when agents have different weights representing their entitlements. First, we propose a parameterized family of relaxations for weighted envy-freeness and the same for weighted proportionality; the parameters indicate whether smaller-weight or larger-weight agents should be given a higher priority. We show that each notion in these fami… ▽ More We revisit the setting of fairly allocating indivisible items when agents have different weights representing their entitlements. First, we propose a parameterized family of relaxations for weighted envy-freeness and the same for weighted proportionality; the parameters indicate whether smaller-weight or larger-weight agents should be given a higher priority. We show that each notion in these families can always be satisfied, but any two cannot necessarily be fulfilled simultaneously. We then introduce an intuitive weighted generalization of maximin share fairness and establish the optimal approximation of it that can be guaranteed. Furthermore, we characterize the implication relations between the various weighted fairness notions introduced in this and prior work, and relate them to the lower and upper quota axioms from apportionment. △ Less

Submitted 30 June, 2024; v1 submitted 8 December, 2021; originally announced December 2021.

Comments: Appears in the 36th AAAI Conference on Artificial Intelligence (AAAI), 2022

Causal Analysis and Classification of Traffic Crash Injury Severity Using Machine Learning Algorithms

Authors: Meghna Chakraborty, Timothy Gates, Subhrajit Sinha

Abstract: Causal analysis and classification of injury severity applying non-parametric methods for traffic crashes has received limited attention. This study presents a methodological framework for causal inference, using Granger causality analysis, and injury severity classification of traffic crashes, occurring on interstates, with different machine learning techniques including decision trees (DT), rand… ▽ More Causal analysis and classification of injury severity applying non-parametric methods for traffic crashes has received limited attention. This study presents a methodological framework for causal inference, using Granger causality analysis, and injury severity classification of traffic crashes, occurring on interstates, with different machine learning techniques including decision trees (DT), random forest (RF), extreme gradient boosting (XGBoost), and deep neural network (DNN). The data used in this study were obtained for traffic crashes on all interstates across the state of Texas from a period of six years between 2014 and 2019. The output of the proposed severity classification approach includes three classes for fatal and severe injury (KA) crashes, non-severe and possible injury (BC) crashes, and property damage only (PDO) crashes. While Granger Causality helped identify the most influential factors affecting crash severity, the learning-based models predicted the severity classes with varying performance. The results of Granger causality analysis identified the speed limit, surface and weather conditions, traffic volume, presence of workzones, workers in workzones, and high occupancy vehicle (HOV) lanes, among others, as the most important factors affecting crash severity. The prediction performance of the classifiers yielded varying results across the different classes. Specifically, while decision tree and random forest classifiers provided the greatest performance for PDO and BC severities, respectively, for the KA class, the rarest class in the data, deep neural net classifier performed superior than all other algorithms, most likely due to its capability of approximating nonlinear models. This study contributes to the limited body of knowledge pertaining to causal analysis and classification prediction of traffic crash injury severity using non-parametric approaches. △ Less

Submitted 30 November, 2021; originally announced December 2021.

Causal Analysis and Prediction of Human Mobility in the U.S. during the COVID-19 Pandemic

Authors: Subhrajit Sinha, Meghna Chakraborty

Abstract: Since the increasing outspread of COVID-19 in the U.S., with the highest number of confirmed cases and deaths in the world as of September 2020, most states in the country have enforced travel restrictions resulting in sharp reductions in mobility. However, the overall impact and long-term implications of this crisis to travel and mobility remain uncertain. To this end, this study develops an anal… ▽ More Since the increasing outspread of COVID-19 in the U.S., with the highest number of confirmed cases and deaths in the world as of September 2020, most states in the country have enforced travel restrictions resulting in sharp reductions in mobility. However, the overall impact and long-term implications of this crisis to travel and mobility remain uncertain. To this end, this study develops an analytical framework that determines and analyzes the most dominant factors impacting human mobility and travel in the U.S. during this pandemic. In particular, the study uses Granger causality to determine the important predictors influencing daily vehicle miles traveled and utilize linear regularization algorithms, including Ridge and LASSO techniques, to model and predict mobility. State-level time-series data were obtained from various open-access sources for the period starting from March 1, 2020 through June 13, 2020 and the entire data set was divided into two parts for training and testing purposes. The variables selected by Granger causality were used to train the three different reduced order models by ordinary least square regression, Ridge regression, and LASSO regression algorithms. Finally, the prediction accuracy of the developed models was examined on the test data. The results indicate that the factors including the number of new COVID cases, social distancing index, population staying at home, percent of out of county trips, trips to different destinations, socioeconomic status, percent of people working from home, and statewide closure, among others, were the most important factors influencing daily VMT. Also, among all the modeling techniques, Ridge regression provides the most superior performance with the least error, while LASSO regression also performed better than the ordinary least square model. △ Less

Submitted 24 November, 2021; originally announced November 2021.

Solving Structured Hierarchical Games Using Differential Backward Induction

Authors: Zun Li, Feiran Jia, Aditya Mate, Shahin Jabbari, Mithun Chakraborty, Milind Tambe, Yevgeniy Vorobeychik

Abstract: From large-scale organizations to decentralized political systems, hierarchical strategic decision making is commonplace. We introduce a novel class of structured hierarchical games (SHGs) that formally capture such hierarchical strategic interactions. In an SHG, each player is a node in a tree, and strategic choices of players are sequenced from root to leaves, with root moving first, followed by… ▽ More From large-scale organizations to decentralized political systems, hierarchical strategic decision making is commonplace. We introduce a novel class of structured hierarchical games (SHGs) that formally capture such hierarchical strategic interactions. In an SHG, each player is a node in a tree, and strategic choices of players are sequenced from root to leaves, with root moving first, followed by its children, then followed by their children, and so on until the leaves. A player's utility in an SHG depends on its own decision, and on the choices of its parent and all the tree leaves. SHGs thus generalize simultaneous-move games, as well as Stackelberg games with many followers. We leverage the structure of both the sequence of player moves as well as payoff dependence to develop a gradient-based back propagation-style algorithm, which we call Differential Backward Induction (DBI), for approximating equilibria of SHGs. We provide a sufficient condition for convergence of DBI and demonstrate its efficacy in finding approximate equilibrium solutions to several SHG models of hierarchical policy-making problems. △ Less

Submitted 27 June, 2022; v1 submitted 8 June, 2021; originally announced June 2021.

Comments: The short version of this paper appears in the proceedings of UAI-22

Picking Sequences and Monotonicity in Weighted Fair Division

Authors: Mithun Chakraborty, Ulrike Schmidt-Kraepelin, Warut Suksompong

Abstract: We study the problem of fairly allocating indivisible items to agents with different entitlements, which captures, for example, the distribution of ministries among political parties in a coalition government. Our focus is on picking sequences derived from common apportionment methods, including five traditional divisor methods and the quota method. We paint a complete picture of these methods in… ▽ More We study the problem of fairly allocating indivisible items to agents with different entitlements, which captures, for example, the distribution of ministries among political parties in a coalition government. Our focus is on picking sequences derived from common apportionment methods, including five traditional divisor methods and the quota method. We paint a complete picture of these methods in relation to known envy-freeness and proportionality relaxations for indivisible items as well as monotonicity properties with respect to the resource, population, and weights. In addition, we provide characterizations of picking sequences satisfying each of the fairness notions, and show that the well-studied maximum Nash welfare solution fails resource- and population-monotonicity even in the unweighted setting. Our results serve as an argument in favor of using picking sequences in weighted fair division problems. △ Less

Submitted 9 August, 2021; v1 submitted 29 April, 2021; originally announced April 2021.

Comments: Appears in the 30th International Joint Conference on Artificial Intelligence (IJCAI), 2021

Journal ref: Artificial Intelligence, 301:103578 (2021)

Detection of Fake Users in SMPs Using NLP and Graph Embeddings

Authors: Manojit Chakraborty, Shubham Das, Radhika Mamidi

Abstract: Social Media Platforms (SMPs) like Facebook, Twitter, Instagram etc. have large user base all around the world that generates huge amount of data every second. This includes a lot of posts by fake and spam users, typically used by many organisations around the globe to have competitive edge over others. In this work, we aim at detecting such user accounts in Twitter using a novel approach. We show… ▽ More Social Media Platforms (SMPs) like Facebook, Twitter, Instagram etc. have large user base all around the world that generates huge amount of data every second. This includes a lot of posts by fake and spam users, typically used by many organisations around the globe to have competitive edge over others. In this work, we aim at detecting such user accounts in Twitter using a novel approach. We show how to distinguish between Genuine and Spam accounts in Twitter using a combination of Graph Representation Learning and Natural Language Processing techniques. △ Less

Submitted 27 April, 2021; originally announced April 2021.

Comments: 5 pages, 3 figures

Vec2GC -- A Graph Based Clustering Method for Text Representations

Authors: Rajesh N Rao, Manojit Chakraborty

Abstract: NLP pipelines with limited or no labeled data, rely on unsupervised methods for document processing. Unsupervised approaches typically depend on clustering of terms or documents. In this paper, we introduce a novel clustering algorithm, Vec2GC (Vector to Graph Communities), an end-to-end pipeline to cluster terms or documents for any given text corpus. Our method uses community detection on a weig… ▽ More NLP pipelines with limited or no labeled data, rely on unsupervised methods for document processing. Unsupervised approaches typically depend on clustering of terms or documents. In this paper, we introduce a novel clustering algorithm, Vec2GC (Vector to Graph Communities), an end-to-end pipeline to cluster terms or documents for any given text corpus. Our method uses community detection on a weighted graph of the terms or documents, created using text representation learning. Vec2GC clustering algorithm is a density based approach, that supports hierarchical clustering as well. △ Less

Submitted 12 April, 2023; v1 submitted 15 April, 2021; originally announced April 2021.

Comments: 5 pages, 1 figure

A Game-Theoretic Approach for Hierarchical Epidemic Control

Authors: Feiran Jia, Aditya Mate, Zun Li, Shahin Jabbari, Mithun Chakraborty, Milind Tambe, Michael Wellman, Yevgeniy Vorobeychik

Abstract: We design and analyze a multi-level game-theoretic model of hierarchical policy interventions for epidemic control, such as those in response to the COVID-19 pandemic. Our model captures the potentially mismatched priorities among a hierarchy of policy-makers (e.g., federal, state, and local governments) with respect to two cost components that have opposite dependence on the policy strength -- po… ▽ More We design and analyze a multi-level game-theoretic model of hierarchical policy interventions for epidemic control, such as those in response to the COVID-19 pandemic. Our model captures the potentially mismatched priorities among a hierarchy of policy-makers (e.g., federal, state, and local governments) with respect to two cost components that have opposite dependence on the policy strength -- post-intervention infection rates and the socio-economic cost of policy implementation. Additionally, our model includes a crucial third factor in decisions: a cost of non-compliance with the policy-maker immediately above in the hierarchy, such as non-compliance of counties with state-level policies. We propose two novel algorithms for approximating solutions to such games. The first is based on best response dynamics (BRD), and exploits the tree structure of the game. The second combines quadratic integer programming (QIP), which enables us to collapse the two lowest levels of the game, with best response dynamics. Through extensive experiments, we show that our QIP-based approach significantly outperforms the BRD algorithm both in running time and the quality of equilibrium solutions. Finally, we apply the QIP-based algorithm to experiments based on both synthetic and real-world data under various parameter configurations and analyze the resulting (approximate) equilibria to gain insight into the impact of decentralization on overall welfare (measured as the negative sum of costs) as well as emergent properties like free-riding and fairness in cost distribution among policy-makers. △ Less

Submitted 3 August, 2022; v1 submitted 21 February, 2021; originally announced February 2021.

A Two Stage Generalized Block Orthogonal Matching Pursuit (TSGBOMP) Algorithm

Authors: Samrat Mukhopadhyay, Mrityunjoy Chakraborty

Abstract: Recovery of an unknown sparse signal from a few of its projections is the key objective of compressed sensing. Often one comes across signals that are not ordinarily sparse but are sparse blockwise. Existing block sparse recovery algorithms like BOMP make the assumption of uniform block size and known block boundaries, which are, however, not very practical in many applications. This paper address… ▽ More Recovery of an unknown sparse signal from a few of its projections is the key objective of compressed sensing. Often one comes across signals that are not ordinarily sparse but are sparse blockwise. Existing block sparse recovery algorithms like BOMP make the assumption of uniform block size and known block boundaries, which are, however, not very practical in many applications. This paper addresses this problem and proposes a two step procedure, where the first stage is a coarse block location identification stage while the second stage carries out finer localization of a non-zero cluster within the window selected in the first stage. A detailed convergence analysis of the proposed algorithm is carried out by first defining the so-called pseudoblock-interleaved block RIP of the given generalized block sparse signal and then imposing upper bounds on the corresponding RIC. We also extend the analysis for complex vector as well as matrix entries where it turns out that the extension is non-trivial and requires special care. Furthermore, assuming real Gaussian sensing matrix entries, we find a lower bound on the probability that the derived recovery bounds are satisfied. The lower bound suggests that there are sets of parameters such that the derived bound is satisfied with high probability. Simulation results confirm significantly improved performance of the proposed algorithm as compared to BOMP. △ Less

Submitted 18 August, 2020; originally announced August 2020.

Comments: 18 pages, 5 figures

Antarjami: Exploring psychometric evaluation through a computer-based game

Authors: Anirban Lahiri, Utanko Mitra, Sunreeta Sen, Mrinal Chakraborty, Max Kleiman-Weiner, Rajlakshmi Guha, Pabitra Mitra, Anupam Basu, Partha Pratim Chakraborty

Abstract: A number of questionnaire based psychometric testing frameworks are globally for example OCEAN (Five factor) indicator, MBTI (Myers Brigg Type Indicator) etc. However, questionnaire based psychometric tests have some known shortcomings. This work explores whether these shortcomings can be mitigated through computer-based gaming platforms for evaluating psychometric parameters. A computer based psy… ▽ More A number of questionnaire based psychometric testing frameworks are globally for example OCEAN (Five factor) indicator, MBTI (Myers Brigg Type Indicator) etc. However, questionnaire based psychometric tests have some known shortcomings. This work explores whether these shortcomings can be mitigated through computer-based gaming platforms for evaluating psychometric parameters. A computer based psychometric game framework called Antarjami has been developed for evaluating OCEAN (Five factor) indicators. It investigates the feasibility of extracting psychometric parameters through computer-based games, utilizing underlying improvements in the area of modern artificial intelligence. The candidates for the test are subjected to a number scenarios as part of the computer based game and their reactions/responses are used to evaluate their psychometric parameters. As part of the study, the parameters obtained from the game were compared with those evaluated using paper based tests and scores given by a panel of psychologists. The achieved results were very promising. △ Less

Submitted 16 July, 2020; originally announced July 2020.

Comments: Submitted to CogSci 2020

Graph Neural Network Based Coarse-Grained Mapping Prediction

Authors: Zhiheng Li, Geemi P. Wellawatte, Maghesree Chakraborty, Heta A. Gandhi, Chenliang Xu, Andrew D. White

Abstract: The selection of coarse-grained (CG) mapping operators is a critical step for CG molecular dynamics (MD) simulation. It is still an open question about what is optimal for this choice and there is a need for theory. The current state-of-the art method is mapping operators manually selected by experts. In this work, we demonstrate an automated approach by viewing this problem as supervised learning… ▽ More The selection of coarse-grained (CG) mapping operators is a critical step for CG molecular dynamics (MD) simulation. It is still an open question about what is optimal for this choice and there is a need for theory. The current state-of-the art method is mapping operators manually selected by experts. In this work, we demonstrate an automated approach by viewing this problem as supervised learning where we seek to reproduce the mapping operators produced by experts. We present a graph neural network based CG mapping predictor called DEEP SUPERVISED GRAPH PARTITIONING MODEL(DSGPM) that treats mapping operators as a graph segmentation problem. DSGPM is trained on a novel dataset, Human-annotated Mappings (HAM), consisting of 1,206 molecules with expert annotated mapping operators. HAM can be used to facilitate further research in this area. Our model uses a novel metric learning objective to produce high-quality atomic features that are used in spectral clustering. The results show that the DSGPM outperforms state-of-the-art methods in the field of graph segmentation. Finally, we find that predicted CG mapping operators indeed result in good CG MD models when used in simulation. △ Less

Submitted 19 August, 2021; v1 submitted 24 June, 2020; originally announced July 2020.

Modified Hard Thresholding Pursuit with Regularization Assisted Support Identification

Authors: Samrat Mukhopadhyay, Mrityunjoy Chakraborty

Abstract: Hard thresholding pursuit (HTP) is a recently proposed iterative sparse recovery algorithm which is a result of combination of a support selection step from iterated hard thresholding (IHT) and an estimation step from the orthogonal matching pursuit (OMP). HTP has been seen to enjoy improved recovery guarantee along with enhanced speed of convergence. Much of the success of HTP can be attributed t… ▽ More Hard thresholding pursuit (HTP) is a recently proposed iterative sparse recovery algorithm which is a result of combination of a support selection step from iterated hard thresholding (IHT) and an estimation step from the orthogonal matching pursuit (OMP). HTP has been seen to enjoy improved recovery guarantee along with enhanced speed of convergence. Much of the success of HTP can be attributed to its improved support selection capability due to the support selection step from IHT. In this paper, we propose a generalized HTP algorithm, called regularized HTP (RHTP), where the support selection step of HTP is replaced by a IHT-type support selection where the cost function is replaced by a regularized cost function, while the estimation step continues to use the least squares function. With decomposable regularizer, satisfying certain regularity conditions, the RHTP algorithm is shown to produce a sequence dynamically equivalent to a sequence evolving according to a HTP-like evolution, where the identification stage has a gradient premultiplied with a time-varying diagonal matrix. RHTP is also proven, both theoretically, and numerically, to enjoy faster convergence vis-a-vis HTP with both noiseless and noisy measurement vectors. △ Less

Submitted 2 June, 2020; originally announced June 2020.

Comments: 10 pages, 5 figures

Finding Fair and Efficient Allocations When Valuations Don't Add Up

Authors: Nawal Benabbou, Mithun Chakraborty, Ayumi Igarashi, Yair Zick

Abstract: In this paper, we present new results on the fair and efficient allocation of indivisible goods to agents whose preferences correspond to {\em matroid rank functions}. This is a versatile valuation class with several desirable properties (such as monotonicity and submodularity), which naturally lends itself to a number of real-world domains. We use these properties to our advantage; first, we show… ▽ More In this paper, we present new results on the fair and efficient allocation of indivisible goods to agents whose preferences correspond to {\em matroid rank functions}. This is a versatile valuation class with several desirable properties (such as monotonicity and submodularity), which naturally lends itself to a number of real-world domains. We use these properties to our advantage; first, we show that when agent valuations are matroid rank functions, a socially optimal (i.e. utilitarian social welfare-maximizing) allocation that achieves envy-freeness up to one item (EF1) exists and is computationally tractable. We also prove that the Nash welfare-maximizing and the leximin allocations both exhibit this fairness/efficiency combination, by showing that they can be achieved by minimizing any symmetric strictly convex function over utilitarian optimal outcomes. To the best of our knowledge, this is the first valuation function class not subsumed by additive valuations for which it has been established that an allocation maximizing Nash welfare is EF1. Moreover, for a subclass of these valuation functions based on maximum (unweighted) bipartite matching, we show that a leximin allocation can be computed in polynomial time. Additionally, we explore possible extensions of our results to fairness criteria other than EF1 as well as to generalizations of the above valuation classes. △ Less

Submitted 18 June, 2021; v1 submitted 16 March, 2020; originally announced March 2020.

Unsupervised Pre-trained, Texture Aware And Lightweight Model for Deep Learning-Based Iris Recognition Under Limited Annotated Data

Authors: Manashi Chakraborty, Mayukh Roy, Prabir Kumar Biswas, Pabitra Mitra

Abstract: In this paper, we present a texture aware lightweight deep learning framework for iris recognition. Our contributions are primarily three fold. Firstly, to address the dearth of labelled iris data, we propose a reconstruction loss guided unsupervised pre-training stage followed by supervised refinement. This drives the network weights to focus on discriminative iris texture patterns. Next, we prop… ▽ More In this paper, we present a texture aware lightweight deep learning framework for iris recognition. Our contributions are primarily three fold. Firstly, to address the dearth of labelled iris data, we propose a reconstruction loss guided unsupervised pre-training stage followed by supervised refinement. This drives the network weights to focus on discriminative iris texture patterns. Next, we propose several texture aware improvisations inside a Convolution Neural Net to better leverage iris textures. Finally, we show that our systematic training and architectural choices enable us to design an efficient framework with upto 100X fewer parameters than contemporary deep learning baselines yet achieve better recognition performance for within and cross dataset evaluations. △ Less

Submitted 20 February, 2020; originally announced February 2020.

Comments: Under review at ICIP2020

Restricted Rules of Inference and Paraconsistency

Authors: Sankha S. Basu, Mihir K. Chakraborty

Abstract: In this paper, we study two companions to a logic, viz., the left variable inclusion companion and the restricted rules companion, their nature and interrelations, especially in connection with paraconsistency. A sufficient condition for the two companions to coincide has also been proved. Two new logical systems - Intuitionistic Paraconsistent Weak Kleene logic (IPWK) and Paraconsistent Pre-Rough… ▽ More In this paper, we study two companions to a logic, viz., the left variable inclusion companion and the restricted rules companion, their nature and interrelations, especially in connection with paraconsistency. A sufficient condition for the two companions to coincide has also been proved. Two new logical systems - Intuitionistic Paraconsistent Weak Kleene logic (IPWK) and Paraconsistent Pre-Rough logic (PPRL) - are presented here as examples of logics of left variable inclusion. IPWK is the left variable inclusion companion of Intuitionistic Propositional logic (IPC) and is also the restricted rules companion of it. PPRL, on the other hand, is the left variable inclusion companion of Pre-Rough logic (PRL) but differs from the restricted rules companion of it. We have discussed algebraic semantics for these logics in terms of Płonka sums. This amounts to introducing a contaminating truth value, intended to denote a state of indeterminacy. △ Less

Submitted 13 July, 2021; v1 submitted 4 January, 2020; originally announced January 2020.

Comments: The final version of this paper has been published online in Logic Journal of the IGPL (https://academic.oup.com/jigpal/advance-article/doi/10.1093/jigpal/jzab019/6299942). Minor typos fixed; Theorem 3.7 has been changed to Remark 3.7; other minor rearrangements of the material done; further justification added in Remark 4.28 (now Remark 4.27)

MSC Class: 03B53 (Primary); 03B50; 03G99 (Secondary)

Harnessing Evolution of Multi-Turn Conversations for Effective Answer Retrieval

Authors: Mohammad Aliannejadi, Manajit Chakraborty, Esteban Andrés Ríssola, Fabio Crestani

Abstract: With the improvements in speech recognition and voice generation technologies over the last years, a lot of companies have sought to develop conversation understanding systems that run on mobile phones or smart home devices through natural language interfaces. Conversational assistants, such as Google Assistant and Microsoft Cortana, can help users to complete various types of tasks. This requires… ▽ More With the improvements in speech recognition and voice generation technologies over the last years, a lot of companies have sought to develop conversation understanding systems that run on mobile phones or smart home devices through natural language interfaces. Conversational assistants, such as Google Assistant and Microsoft Cortana, can help users to complete various types of tasks. This requires an accurate understanding of the user's information need as the conversation evolves into multiple turns. Finding relevant context in a conversation's history is challenging because of the complexity of natural language and the evolution of a user's information need. In this work, we present an extensive analysis of language, relevance, dependency of user utterances in a multi-turn information-seeking conversation. To this aim, we have annotated relevant utterances in the conversations released by the TREC CaST 2019 track. The annotation labels determine which of the previous utterances in a conversation can be used to improve the current one. Furthermore, we propose a neural utterance relevance model based on BERT fine-tuning, outperforming competitive baselines. We study and compare the performance of multiple retrieval models, utilizing different strategies to incorporate the user's context. The experimental results on both classification and retrieval tasks show that our proposed approach can effectively identify and incorporate the conversation context. We show that processing the current utterance using the predicted relevant utterance leads to a 38% relative improvement in terms of nDCG@20. Finally, to foster research in this area, we have released the dataset of the annotations. △ Less

Submitted 31 January, 2020; v1 submitted 22 December, 2019; originally announced December 2019.

Comments: To appear in ACM CHIIR 2020, Vancouver, BC, Canada

Weighted Envy-Freeness in Indivisible Item Allocation

Authors: Mithun Chakraborty, Ayumi Igarashi, Warut Suksompong, Yair Zick

Abstract: We introduce and analyze new envy-based fairness concepts for agents with weights that quantify their entitlements in the allocation of indivisible items. We propose two variants of weighted envy-freeness up to one item (WEF1): strong, where envy can be eliminated by removing an item from the envied agent's bundle, and weak, where envy can be eliminated either by removing an item (as in the strong… ▽ More We introduce and analyze new envy-based fairness concepts for agents with weights that quantify their entitlements in the allocation of indivisible items. We propose two variants of weighted envy-freeness up to one item (WEF1): strong, where envy can be eliminated by removing an item from the envied agent's bundle, and weak, where envy can be eliminated either by removing an item (as in the strong version) or by replicating an item from the envied agent's bundle in the envying agent's bundle. We show that for additive valuations, an allocation that is both Pareto optimal and strongly WEF1 always exists and can be computed in pseudo-polynomial time; moreover, an allocation that maximizes the weighted Nash social welfare may not be strongly WEF1, but always satisfies the weak version of the property. Moreover, we establish that a generalization of the round-robin picking sequence algorithm produces in polynomial time a strongly WEF1 allocation for an arbitrary number of agents; for two agents, we can efficiently achieve both strong WEF1 and Pareto optimality by adapting the adjusted winner procedure. Our work highlights several aspects in which weighted fair division is richer and more challenging than its unweighted counterpart. △ Less

Submitted 6 March, 2021; v1 submitted 23 September, 2019; originally announced September 2019.

Comments: A preliminary version appears in Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2020

Journal ref: ACM Transactions on Economics and Computation, 9(3):18 (2021)

Fog Computing Vs. Cloud Computing

Authors: Moonmoon Chakraborty

Abstract: This article gives an overview of what Fog computing is, its uses and the comparison between Fog computing and Cloud computing. Cloud is performing well in todays World and boosting the ability to use the internet more than ever. Cloud computing gradually developed a method to use the benefits of it in most of the organizations. Fog computing can be apparent both in big data structures and large c… ▽ More This article gives an overview of what Fog computing is, its uses and the comparison between Fog computing and Cloud computing. Cloud is performing well in todays World and boosting the ability to use the internet more than ever. Cloud computing gradually developed a method to use the benefits of it in most of the organizations. Fog computing can be apparent both in big data structures and large cloud systems, making reference to the growing complications in retrieving the data accurately. Fog computing is outspreading cloud computing by transporting computation on the advantage of network systems such as cell phone devices or fixed nodes with in-built data storage. Fog provides important points of improved abilities, strong security controls, and processes, establish data transmission capabilities carefully and in a flexible manner. This paper gives an overview of the connections and attributes for both Fog computing and cloud varies by outline, preparation, directions, and strategies for associations and clients. This also explains how Fog computing is flexible and provide better service for data processing by overwhelming low network bandwidth instead of moving whole data to the cloud platform. △ Less

Submitted 24 March, 2019; originally announced April 2019.

Comments: 10 pages, 1 figure, 1 table

Deterministic and Randomized Diffusion based Iterative Generalized Hard Thresholding (DiFIGHT) for Distributed Sparse Signal Recovery

Authors: Samrat Mukhopadhyay, Mrityunjoy Chakraborty

Abstract: In this paper we propose a distributed iterated hard thresholding algorithm termed DiFIGHT over a network that is built on the diffusion mechanism and also propose a modification of the proposed algorithm, termed MoDiFIGHT, that has low complexity in terms of communication in the network. We additionally propose four different strategies termed RP, RNP, RGP$_r$, and RGNP$_r$ that are used to rando… ▽ More In this paper we propose a distributed iterated hard thresholding algorithm termed DiFIGHT over a network that is built on the diffusion mechanism and also propose a modification of the proposed algorithm, termed MoDiFIGHT, that has low complexity in terms of communication in the network. We additionally propose four different strategies termed RP, RNP, RGP$_r$, and RGNP$_r$ that are used to randomly select a subset of nodes that are subsequently activated to take part in the distributed algorithm, so as to reduce the mean number of communications during the run of the distributed algorithm. We present theoretical estimates of the long run communication per unit time for these different strategies, when used by the two proposed algorithms. Also, we present analysis of the two proposed algorithms and provide provable bounds on their recovery performance with or without using the random node selection strategies. Finally we use numerical studies to show that both when the random strategies are used as well as when they are not used, the proposed algorithms display performances far superior to distributed IHT algorithm using consensus mechanism . △ Less

Submitted 14 August, 2020; v1 submitted 23 April, 2018; originally announced April 2018.

Comments: 11 pages, 4 figures, Updated some analysis, Added a few more explanations

The Price of Quota-based Diversity in Assignment Problems

Authors: Nawal Benabbou, Mithun Chakraborty, Vinh Ho Xuan, Jakub Sliwinski, Yair Zick

Abstract: We introduce and analyze an extension to the matching problem on a weighted bipartite graph: Assignment with Type Constraints. The two parts of the graph are partitioned into subsets called types and blocks; we seek a matching with the largest sum of weights under the constraint that there is a pre-specified cap on the number of vertices matched in every type-block pair. Our primary motivation ste… ▽ More We introduce and analyze an extension to the matching problem on a weighted bipartite graph: Assignment with Type Constraints. The two parts of the graph are partitioned into subsets called types and blocks; we seek a matching with the largest sum of weights under the constraint that there is a pre-specified cap on the number of vertices matched in every type-block pair. Our primary motivation stems from the public housing program of Singapore, accounting for over 70% of its residential real estate. To promote ethnic diversity within its housing projects, Singapore imposes ethnicity quotas: each new housing development comprises blocks of flats and each ethnicity-based group in the population must not own more than a certain percentage of flats in a block. Other domains using similar hard capacity constraints include matching prospective students to schools or medical residents to hospitals. Limiting agents' choices for ensuring diversity in this manner naturally entails some welfare loss. One of our goals is to study the trade-off between diversity and social welfare in such settings. We first show that, while the classic assignment program is polynomial-time computable, adding diversity constraints makes it computationally intractable; however, we identify a $\tfrac{1}{2}$-approximation algorithm, as well as reasonable assumptions on the weights that permit poly-time algorithms. Next, we provide two upper bounds on the price of diversity -- a measure of the loss in welfare incurred by imposing diversity constraints -- as functions of natural problem parameters. We conclude the paper with simulations based on publicly available data from two diversity-constrained allocation problems -- Singapore Public Housing and Chicago School Choice -- which shed light on how the constrained maximization as well as lottery-based variants perform in practice. △ Less

Submitted 3 October, 2020; v1 submitted 28 November, 2017; originally announced November 2017.

Journal ref: TEAC 8.3.14 (2020) 1-32

Convergence Analysis of l0-RLS Adaptive Filter

Authors: B. K. Das, S. Mukhopadhyay, M. Chakraborty

Abstract: This paper presents first and second order convergence analysis of the sparsity aware l0-RLS adaptive filter. The theorems 1 and 2 state the steady state value of mean and mean square deviation of the adaptive filter weight vector. This paper presents first and second order convergence analysis of the sparsity aware l0-RLS adaptive filter. The theorems 1 and 2 state the steady state value of mean and mean square deviation of the adaptive filter weight vector. △ Less

Submitted 16 October, 2017; originally announced October 2017.

R-Rec: A rule-based system for contextual suggestion using tag-description similarity

Authors: Kshitij Singh, Manajit Chakraborty, C. Ravindranath Chowdary

Abstract: Contextual Suggestion deals with search techniques for complex information needs that are highly focused on context and user needs. In this paper, we propose \emph{R-Rec}, a novel rule-based technique to identify and recommend appropriate points-of-interest to a user given her past preferences. We try to embody the information that the user shares in the form of rating and tags of any previous poi… ▽ More Contextual Suggestion deals with search techniques for complex information needs that are highly focused on context and user needs. In this paper, we propose \emph{R-Rec}, a novel rule-based technique to identify and recommend appropriate points-of-interest to a user given her past preferences. We try to embody the information that the user shares in the form of rating and tags of any previous point(s)-of-interest and use it to rank the unrated candidate suggestions. The ranking function is computed based on the similarity between a suggestion and the places that the user like and the dissimilarity between the suggestion and the places disliked by the user. Experiments carried out on TREC-Contextual Suggestion 2015 dataset reveal the efficacy of our method. △ Less

Submitted 5 July, 2017; originally announced July 2017.

Signal Recovery in Uncorrelated and Correlated Dictionaries Using Orthogonal Least Squares

Authors: Samrat Mukhopadhyay, Prateek Vashishtha and, Mrityunjoy Chakraborty

Abstract: Though the method of least squares has been used for a long time in solving signal processing problems, in the recent field of sparse recovery from compressed measurements, this method has not been given much attention. In this paper we show that a method in the least squares family, known in the literature as Orthogonal Least Squares (OLS), adapted for compressed recovery problems, has competitiv… ▽ More Though the method of least squares has been used for a long time in solving signal processing problems, in the recent field of sparse recovery from compressed measurements, this method has not been given much attention. In this paper we show that a method in the least squares family, known in the literature as Orthogonal Least Squares (OLS), adapted for compressed recovery problems, has competitive recovery performance and computation complexity, that makes it a suitable alternative to popular greedy methods like Orthogonal Matching Pursuit (OMP). We show that with a slight modification, OLS can exactly recover a $K$-sparse signal, embedded in an $N$ dimensional space ($K<<N$) in $M=\mathcal{O}(K\log (N/K))$ no of measurements with Gaussian dictionaries. We also show that OLS can be easily implemented in such a way that it requires $\mathcal{O}(KMN)$ no of floating point operations similar to that of OMP. In this paper performance of OLS is also studied with sensing matrices with correlated dictionary, in which algorithms like OMP does not exhibit good recovery performance. We study the recovery performance of OLS in a specific dictionary called \emph{generalized hybrid dictionary}, which is shown to be a correlated dictionary, and show numerically that OLS has is far superior to OMP in these kind of dictionaries in terms of recovery performance. Finally we provide analytical justifications that corroborate the findings in the numerical illustrations. △ Less

Submitted 29 July, 2016; originally announced July 2016.

Comments: 18 Pages, 8 figures

Adaptive Combination of l0 LMS Adaptive Filters for Sparse System Identification in Fluctuating Noise Power

Authors: Bijit Kumar Das, Mrityunjoy Chakraborty

Abstract: Recently, the l0-least mean square (l0-LMS) algorithm has been proposed to identify sparse linear systems by employing a sparsity-promoting continuous function as an approximation of l0 pseudonorm penalty. However, the performance of this algorithm is sensitive to the appropriate choice of the some parameter responsible for the zero-attracting intensity. The optimum choice for this parameter depen… ▽ More Recently, the l0-least mean square (l0-LMS) algorithm has been proposed to identify sparse linear systems by employing a sparsity-promoting continuous function as an approximation of l0 pseudonorm penalty. However, the performance of this algorithm is sensitive to the appropriate choice of the some parameter responsible for the zero-attracting intensity. The optimum choice for this parameter depends on the signal-to-noise ratio (SNR) prevailing in the system. Thus, it becomes difficult to fix a suitable value for this parameter, particularly in a situation where SNR fluctuates over time. In this work, we propose several adaptive combinations of differently parameterized l0-LMS to get an overall satisfactory performance independent of the SNR, and discuss some issues relevant to these combination structures. We also demonstrate an efficient partial update scheme which not only reduces the number of computations per iteration, but also achieves some interesting performance gain compared with the full update case. Then, we propose a new recursive least squares (RLS)-type rule to update the combining parameter more efficiently. Finally, we extend the combination of two filters to a combination of M number adaptive filters, which manifests further improvement for M > 2. △ Less

Submitted 10 May, 2016; originally announced May 2016.

Comments: 15 pages, 15 figures

Performance Analysis of the Gradient Comparator LMS Algorithm

Authors: Bijit Kumar Das, Mrityunjoy Chakraborty

Abstract: The sparsity-aware zero attractor least mean square (ZA-LMS) algorithm manifests much lower misadjustment in strongly sparse environment than its sparsity-agnostic counterpart, the least mean square (LMS), but is shown to perform worse than the LMS when sparsity of the impulse response decreases. The reweighted variant of the ZA-LMS, namely RZA-LMS shows robustness against this variation in sparsi… ▽ More The sparsity-aware zero attractor least mean square (ZA-LMS) algorithm manifests much lower misadjustment in strongly sparse environment than its sparsity-agnostic counterpart, the least mean square (LMS), but is shown to perform worse than the LMS when sparsity of the impulse response decreases. The reweighted variant of the ZA-LMS, namely RZA-LMS shows robustness against this variation in sparsity, but at the price of increased computational complexity. The other variants such as the l 0 -LMS and the improved proportionate normalized LMS (IPNLMS), though perform satisfactorily, are also computationally intensive. The gradient comparator LMS (GC-LMS) is a practical solution of this trade-off when hardware constraint is to be considered. In this paper, we analyse the mean and the mean square convergence performance of the GC-LMS algorithm in detail. The analyses satisfactorily match with the simulation results. △ Less

Submitted 10 May, 2016; originally announced May 2016.

Comments: 5 pages, 2 figures

Counting in Practical Anonymous Dynamic Networks is Polynomial

Authors: Maitri Chakraborty, Alessia Milani, Miguel A. Mosteiro

Abstract: Anonymous Dynamic Networks is a harsh computational environment due to changing topology and lack of identifiers. Computing the size of the network, a problem known as Counting, is particularly challenging because messages received cannot be tagged to a specific sender. Previous works on Counting in Anonymous Dynamic Networks do not provide enough guarantees to be used in practice. Indeed, they ei… ▽ More Anonymous Dynamic Networks is a harsh computational environment due to changing topology and lack of identifiers. Computing the size of the network, a problem known as Counting, is particularly challenging because messages received cannot be tagged to a specific sender. Previous works on Counting in Anonymous Dynamic Networks do not provide enough guarantees to be used in practice. Indeed, they either compute only an upper bound on the network size that may be as bad as exponential, or guarantee only double-exponential running time, or do not terminate, or guarantee only eventual termination without running-time guarantees. Faster experimental protocols do not guarantee the correct count. Recently, we presented the first Counting protocol that computes the exact count with exponential running-time guarantees. The protocol requires the presence of one leader node and knowledge of any upper bound Delta on the maximum number of neighbors that any node will ever have. In the present work, we complement the latter theoretical study evaluating the performance of such protocol in practice. We tested a variety of network topologies that may appear in practice, including extremal cases such as trees, paths, and continuously changing topologies. We also tested networks that temporarily are not connected. Our simulations showed that the protocol is polynomial for all the inputs tested, paving the way to use it in practical applications where topology changes are predictable. The simulations also provided insight on the impact of topology changes on information dissemination. To the best of our knowledge, this is the first experimental study that shows the possibility of computing the exact count in polynomial time in a variety of Anonymous Dynamic Networks that are worse than expected in practice. △ Less

Submitted 17 March, 2016; originally announced March 2016.

MSC Class: 68W15

Performance Analysis of $l_0$ Norm Constrained Recursive Least Squares Algorithm

Authors: Samrat Mukhopadhyay, Bijit Kumar Das, Mrityunjoy Chakraborty

Abstract: Performance analysis of $l_0$ norm constrained Recursive least Squares (RLS) algorithm is attempted in this paper. Though the performance pretty attractive compared to its various alternatives, no thorough study of theoretical analysis has been performed. Like the popular $l_0$ Least Mean Squares (LMS) algorithm, in $l_0$ RLS, a $l_0$ norm penalty is added to provide zero tap attractions on the in… ▽ More Performance analysis of $l_0$ norm constrained Recursive least Squares (RLS) algorithm is attempted in this paper. Though the performance pretty attractive compared to its various alternatives, no thorough study of theoretical analysis has been performed. Like the popular $l_0$ Least Mean Squares (LMS) algorithm, in $l_0$ RLS, a $l_0$ norm penalty is added to provide zero tap attractions on the instantaneous filter taps. A thorough theoretical performance analysis has been conducted in this paper with white Gaussian input data under assumptions suitable for many practical scenarios. An expression for steady state MSD is derived and analyzed for variations of different sets of predefined variables. Also a Taylor series expansion based approximate linear evolution of the instantaneous MSD has been performed. Finally numerical simulations are carried out to corroborate the theoretical analysis and are shown to match well for a wide range of parameters. △ Less

Submitted 10 February, 2016; originally announced February 2016.

Comments: 15 pages, 5 figures

A Modified Multiple OLS (m$^2$OLS) Algorithm for Signal Recovery in Compressive Sensing

Authors: Samrat Mukhopadhyay, Siddhartha Satpathi, Mrityunjoy Chakraborty

Abstract: Orthogonal least square (OLS) is an important sparse signal recovery algorithm for compressive sensing, which enjoys superior probability of success over other well-known recovery algorithms under conditions of correlated measurement matrices. Multiple OLS (mOLS) is a recently proposed improved version of OLS which selects multiple candidates per iteration by generalizing the greedy selection prin… ▽ More Orthogonal least square (OLS) is an important sparse signal recovery algorithm for compressive sensing, which enjoys superior probability of success over other well-known recovery algorithms under conditions of correlated measurement matrices. Multiple OLS (mOLS) is a recently proposed improved version of OLS which selects multiple candidates per iteration by generalizing the greedy selection principle used in OLS and enjoys faster convergence than OLS. In this paper, we present a refined version of the mOLS algorithm where at each step of the iteration, we first preselect a submatrix of the measurement matrix suitably and then apply the mOLS computations to the chosen submatrix. Since mOLS now works only on a submatrix and not on the overall matrix, computations reduce drastically. Convergence of the algorithm, however, requires ensuring passage of true candidates through the two stages of preselection and mOLS based selection successively. This paper presents convergence conditions for both noisy and noise free signal models. The proposed algorithm enjoys faster convergence properties similar to mOLS, at a much reduced computational complexity. △ Less

Submitted 1 August, 2018; v1 submitted 27 November, 2015; originally announced November 2015.

Comments: 15 pages, 7 figures, journal, added new material, changed few figures, changed title, some minor changes in writing