Showing 1–35 of 35 results for author: Nandi, A

Simple Augmentations of Logical Rules for Neuro-Symbolic Knowledge Graph Completion

Authors: Ananjan Nandi, Navdeep Kaur, Parag Singla, Mausam

Abstract: High-quality and high-coverage rule sets are imperative to the success of Neuro-Symbolic Knowledge Graph Completion (NS-KGC) models, because they form the basis of all symbolic inferences. Recent literature builds neural models for generating rule sets, however, preliminary experiments show that they struggle with maintaining high coverage. In this work, we suggest three simple augmentations to ex… ▽ More High-quality and high-coverage rule sets are imperative to the success of Neuro-Symbolic Knowledge Graph Completion (NS-KGC) models, because they form the basis of all symbolic inferences. Recent literature builds neural models for generating rule sets, however, preliminary experiments show that they struggle with maintaining high coverage. In this work, we suggest three simple augmentations to existing rule sets: (1) transforming rules to their abductive forms, (2) generating equivalent rules that use inverse forms of constituent relations and (3) random walks that propose new rules. Finally, we prune potentially low quality rules. Experiments over four datasets and five ruleset-baseline settings suggest that these simple augmentations consistently improve results, and obtain up to 7.1 pt MRR and 8.5 pt Hits@1 gains over using rules without augmentations. △ Less

Submitted 2 July, 2024; originally announced July 2024.

Comments: 12 pages, 15 tables Published in ACL 2023

Roleplay-doh: Enabling Domain-Experts to Create LLM-simulated Patients via Eliciting and Adhering to Principles

Authors: Ryan Louie, Ananjan Nandi, William Fang, Cheng Chang, Emma Brunskill, Diyi Yang

Abstract: Recent works leverage LLMs to roleplay realistic social scenarios, aiding novices in practicing their social skills. However, simulating sensitive interactions, such as in mental health, is challenging. Privacy concerns restrict data access, and collecting expert feedback, although vital, is laborious. To address this, we develop Roleplay-doh, a novel human-LLM collaboration pipeline that elicits… ▽ More Recent works leverage LLMs to roleplay realistic social scenarios, aiding novices in practicing their social skills. However, simulating sensitive interactions, such as in mental health, is challenging. Privacy concerns restrict data access, and collecting expert feedback, although vital, is laborious. To address this, we develop Roleplay-doh, a novel human-LLM collaboration pipeline that elicits qualitative feedback from a domain-expert, which is transformed into a set of principles, or natural language rules, that govern an LLM-prompted roleplay. We apply this pipeline to enable senior mental health supporters to create customized AI patients for simulated practice partners for novice counselors. After uncovering issues in GPT-4 simulations not adhering to expert-defined principles, we also introduce a novel principle-adherence prompting pipeline which shows 30% improvements in response quality and principle following for the downstream task. Via a user study with 25 counseling experts, we demonstrate that the pipeline makes it easy and effective to create AI patients that more faithfully resemble real patients, as judged by creators and third-party counselors. See our project website at https://roleplay-doh.github.io/ for code and data. △ Less

Submitted 14 July, 2024; v1 submitted 30 June, 2024; originally announced July 2024.

Comments: 34 pages, 24 figures, 11 Tables

Noise-Aware Training of Layout-Aware Language Models

Authors: Ritesh Sarkhel, Xiaoqi Ren, Lauro Beltrao Costa, Guolong Su, Vincent Perot, Yanan Xie, Emmanouil Koukoumidis, Arnab Nandi

Abstract: A visually rich document (VRD) utilizes visual features along with linguistic cues to disseminate information. Training a custom extractor that identifies named entities from a document requires a large number of instances of the target document type annotated at textual and visual modalities. This is an expensive bottleneck in enterprise scenarios, where we want to train custom extractors for tho… ▽ More A visually rich document (VRD) utilizes visual features along with linguistic cues to disseminate information. Training a custom extractor that identifies named entities from a document requires a large number of instances of the target document type annotated at textual and visual modalities. This is an expensive bottleneck in enterprise scenarios, where we want to train custom extractors for thousands of different document types in a scalable way. Pre-training an extractor model on unlabeled instances of the target document type, followed by a fine-tuning step on human-labeled instances does not work in these scenarios, as it surpasses the maximum allowable training time allocated for the extractor. We address this scenario by proposing a Noise-Aware Training method or NAT in this paper. Instead of acquiring expensive human-labeled documents, NAT utilizes weakly labeled documents to train an extractor in a scalable way. To avoid degradation in the model's quality due to noisy, weakly labeled samples, NAT estimates the confidence of each training sample and incorporates it as uncertainty measure during training. We train multiple state-of-the-art extractor models using NAT. Experiments on a number of publicly available and in-house datasets show that NAT-trained models are not only robust in performance -- it outperforms a transfer-learning baseline by up to 6% in terms of macro-F1 score, but it is also more label-efficient -- it reduces the amount of human-effort required to obtain comparable performance by up to 73%. △ Less

Submitted 30 March, 2024; originally announced April 2024.

Margin Propagation based XOR-SAT Solvers for Decoding of LDPC Codes

Authors: Ankita Nandi, Shantanu Chakrabartty, Chetan Singh Thakur

Abstract: Decoding of Low-Density Parity Check (LDPC) codes can be viewed as a special case of XOR-SAT problems, for which low-computational complexity bit-flipping algorithms have been proposed in the literature. However, a performance gap exists between the bit-flipping LDPC decoding algorithms and the benchmark LDPC decoding algorithms, such as the Sum-Product Algorithm (SPA). In this paper, we propose a… ▽ More Decoding of Low-Density Parity Check (LDPC) codes can be viewed as a special case of XOR-SAT problems, for which low-computational complexity bit-flipping algorithms have been proposed in the literature. However, a performance gap exists between the bit-flipping LDPC decoding algorithms and the benchmark LDPC decoding algorithms, such as the Sum-Product Algorithm (SPA). In this paper, we propose an XOR-SAT solver using log-sum-exponential functions and demonstrate its advantages for LDPC decoding. This is then approximated using the Margin Propagation formulation to attain a low-complexity LDPC decoder. The proposed algorithm uses soft information to decide the bit-flips that maximize the number of parity check constraints satisfied over an optimization function. The proposed solver can achieve results that are within $0.1$dB of the Sum-Product Algorithm for the same number of code iterations. It is also at least 10x lesser than other Gradient-Descent Bit Flipping decoding algorithms, which are also bit-flipping algorithms based on optimization functions. The approximation using the Margin Propagation formulation does not require any multipliers, resulting in significantly lower computational complexity than other soft-decision Bit-Flipping LDPC decoders. △ Less

Submitted 7 February, 2024; originally announced February 2024.

Comments: 12 pages, 7 figures, Paper submitted to IEEE Transactions on Communications

DynaSemble: Dynamic Ensembling of Textual and Structure-Based Models for Knowledge Graph Completion

Authors: Ananjan Nandi, Navdeep Kaur, Parag Singla, Mausam

Abstract: We consider two popular approaches to Knowledge Graph Completion (KGC): textual models that rely on textual entity descriptions, and structure-based models that exploit the connectivity structure of the Knowledge Graph (KG). Preliminary experiments show that these approaches have complementary strengths: structure-based models perform exceptionally well when the gold answer is easily reachable fro… ▽ More We consider two popular approaches to Knowledge Graph Completion (KGC): textual models that rely on textual entity descriptions, and structure-based models that exploit the connectivity structure of the Knowledge Graph (KG). Preliminary experiments show that these approaches have complementary strengths: structure-based models perform exceptionally well when the gold answer is easily reachable from the query head in the KG, while textual models exploit descriptions to give good performance even when the gold answer is not easily reachable. In response, we propose DynaSemble, a novel method for learning query-dependent ensemble weights to combine these approaches by using the distributions of scores assigned by the models in the ensemble to all candidate entities. DynaSemble achieves state-of-the-art results on three standard KGC datasets, with up to 6.8 pt MRR and 8.3 pt Hits@1 gains over the best baseline model for the WN18RR dataset. △ Less

Submitted 2 July, 2024; v1 submitted 7 November, 2023; originally announced November 2023.

Comments: 12 pages, 2 figures, 15 tables Accepted to ACL 2024

ACM Class: I.2.7

TEC-Net: Vision Transformer Embrace Convolutional Neural Networks for Medical Image Segmentation

Authors: Rui Sun, Tao Lei, Weichuan Zhang, Yong Wan, Yong Xia, Asoke K. Nandi

Abstract: The hybrid architecture of convolution neural networks (CNN) and Transformer has been the most popular method for medical image segmentation. However, the existing networks based on the hybrid architecture suffer from two problems. First, although the CNN branch can capture image local features by using convolution operation, the vanilla convolution is unable to achieve adaptive extraction of imag… ▽ More The hybrid architecture of convolution neural networks (CNN) and Transformer has been the most popular method for medical image segmentation. However, the existing networks based on the hybrid architecture suffer from two problems. First, although the CNN branch can capture image local features by using convolution operation, the vanilla convolution is unable to achieve adaptive extraction of image features. Second, although the Transformer branch can model the global information of images, the conventional self-attention only focuses on the spatial self-attention of images and ignores the channel and cross-dimensional self-attention leading to low segmentation accuracy for medical images with complex backgrounds. To solve these problems, we propose vision Transformer embrace convolutional neural networks for medical image segmentation (TEC-Net). Our network has two advantages. First, dynamic deformable convolution (DDConv) is designed in the CNN branch, which not only overcomes the difficulty of adaptive feature extraction using fixed-size convolution kernels, but also solves the defect that different inputs share the same convolution kernel parameters, effectively improving the feature expression ability of CNN branch. Second, in the Transformer branch, a (shifted)-window adaptive complementary attention module ((S)W-ACAM) and compact convolutional projection are designed to enable the network to fully learn the cross-dimensional long-range dependency of medical images with few parameters and calculations. Experimental results show that the proposed TEC-Net provides better medical image segmentation results than SOTA methods including CNN and Transformer networks. In addition, our TEC-Net requires fewer parameters and computational costs and does not rely on pre-training. The code is publicly available at https://github.com/SR0920/TEC-Net. △ Less

Submitted 19 December, 2023; v1 submitted 6 June, 2023; originally announced June 2023.

Comments: arXiv admin note: substantial text overlap with arXiv:2306.03373

CiT-Net: Convolutional Neural Networks Hand in Hand with Vision Transformers for Medical Image Segmentation

Authors: Tao Lei, Rui Sun, Xuan Wang, Yingbo Wang, Xi He, Asoke Nandi

Abstract: The hybrid architecture of convolutional neural networks (CNNs) and Transformer are very popular for medical image segmentation. However, it suffers from two challenges. First, although a CNNs branch can capture the local image features using vanilla convolution, it cannot achieve adaptive feature learning. Second, although a Transformer branch can capture the global features, it ignores the chann… ▽ More The hybrid architecture of convolutional neural networks (CNNs) and Transformer are very popular for medical image segmentation. However, it suffers from two challenges. First, although a CNNs branch can capture the local image features using vanilla convolution, it cannot achieve adaptive feature learning. Second, although a Transformer branch can capture the global features, it ignores the channel and cross-dimensional self-attention, resulting in a low segmentation accuracy on complex-content images. To address these challenges, we propose a novel hybrid architecture of convolutional neural networks hand in hand with vision Transformers (CiT-Net) for medical image segmentation. Our network has two advantages. First, we design a dynamic deformable convolution and apply it to the CNNs branch, which overcomes the weak feature extraction ability due to fixed-size convolution kernels and the stiff design of sharing kernel parameters among different inputs. Second, we design a shifted-window adaptive complementary attention module and a compact convolutional projection. We apply them to the Transformer branch to learn the cross-dimensional long-term dependency for medical images. Experimental results show that our CiT-Net provides better medical image segmentation results than popular SOTA methods. Besides, our CiT-Net requires lower parameters and less computational costs and does not rely on pre-training. The code is publicly available at https://github.com/SR0920/CiT-Net. △ Less

Submitted 19 December, 2023; v1 submitted 5 June, 2023; originally announced June 2023.

Comments: 9 pages, 3 figures, 3 tables

Journal ref: The 32nd International Joint Conference on Artificial Intelligence, IJCAI2023, MACAO

Lightweight Structure-aware Transformer Network for VHR Remote Sensing Image Change Detection

Authors: Tao Lei, Yetong Xu, Hailong Ning, Zhiyong Lv, Chongdan Min, Yaochu Jin, Asoke K. Nandi

Abstract: Popular Transformer networks have been successfully applied to remote sensing (RS) image change detection (CD) identifications and achieve better results than most convolutional neural networks (CNNs), but they still suffer from two main problems. First, the computational complexity of the Transformer grows quadratically with the increase of image spatial resolution, which is unfavorable to very h… ▽ More Popular Transformer networks have been successfully applied to remote sensing (RS) image change detection (CD) identifications and achieve better results than most convolutional neural networks (CNNs), but they still suffer from two main problems. First, the computational complexity of the Transformer grows quadratically with the increase of image spatial resolution, which is unfavorable to very high-resolution (VHR) RS images. Second, these popular Transformer networks tend to ignore the importance of fine-grained features, which results in poor edge integrity and internal tightness for largely changed objects and leads to the loss of small changed objects. To address the above issues, this Letter proposes a Lightweight Structure-aware Transformer (LSAT) network for RS image CD. The proposed LSAT has two advantages. First, a Cross-dimension Interactive Self-attention (CISA) module with linear complexity is designed to replace the vanilla self-attention in visual Transformer, which effectively reduces the computational complexity while improving the feature representation ability of the proposed LSAT. Second, a Structure-aware Enhancement Module (SAEM) is designed to enhance difference features and edge detail information, which can achieve double enhancement by difference refinement and detail aggregation so as to obtain fine-grained features of bi-temporal RS images. Experimental results show that the proposed LSAT achieves significant improvement in detection accuracy and offers a better tradeoff between accuracy and computational costs than most state-of-the-art CD methods for VHR RS images. △ Less

Submitted 2 June, 2023; originally announced June 2023.

Cross-Modal Entity Matching for Visually Rich Documents

Authors: Ritesh Sarkhel, Arnab Nandi

Abstract: Visually rich documents (e.g. leaflets, banners, magazine articles) are physical or digital documents that utilize visual cues to augment their semantics. Information contained in these documents are ad-hoc and often incomplete. Existing works that enable structured querying on these documents do not take this into account. This makes it difficult to contextualize the information retrieved from qu… ▽ More Visually rich documents (e.g. leaflets, banners, magazine articles) are physical or digital documents that utilize visual cues to augment their semantics. Information contained in these documents are ad-hoc and often incomplete. Existing works that enable structured querying on these documents do not take this into account. This makes it difficult to contextualize the information retrieved from querying these documents and gather actionable insights from them. We propose Juno -- a cross-modal entity matching framework to address this limitation. It augments heterogeneous documents with supplementary information by matching a text span in the document with semantically similar tuples from an external database. Our main contribution in this is a deep neural network with attention that goes beyond traditional keyword-based matching and finds matching tuples by aligning text spans and relational tuples on a multimodal encoding space without any prior knowledge about the document type or the underlying schema. Exhaustive experiments on multiple real-world datasets show that Juno generalizes to heterogeneous documents with diverse layouts and formats. It outperforms state-of-the-art baselines by more than 6 F1 points with up to 60% less human-labeled samples. Our experiments further show that Juno is a computationally robust framework. We can train it only once, and then adapt it dynamically for multiple resource-constrained environments without sacrificing its downstream performance. This makes it suitable for on-device deployment in various edge-devices. To the best of our knowledge, ours is the first work that investigates the information incompleteness of visually rich documents and proposes a generalizable, performant and computationally robust framework to address it in an end-to-end way. △ Less

Submitted 30 March, 2024; v1 submitted 1 March, 2023; originally announced March 2023.

Measuring arousal and stress physiology on Esports, a League of Legends case study

Authors: David Berga, Alexandre Pereda, Eleonora De Filippi, Arijit Nandi, Eulalia Febrer, Marta Reverte, Lautaro Russo

Abstract: Esports gaming is an area in which videogame players need to cooperate and compete with each other, influencing their cognitive load, processing, stress, and social skills. Here it is unknown to which extent competitive videogame play using a desktop setting can affect the physiological responses of players' autonomic nervous system. For such, we propose a study where we have measured distinct ele… ▽ More Esports gaming is an area in which videogame players need to cooperate and compete with each other, influencing their cognitive load, processing, stress, and social skills. Here it is unknown to which extent competitive videogame play using a desktop setting can affect the physiological responses of players' autonomic nervous system. For such, we propose a study where we have measured distinct electrodermal and cardiac activity metrics over competitive players during several League of Legends gameplay sessions in a Esports stadium. We mainly found that game performance (whether winning or losing the game) significantly affects both electrodermal and cardiac activity, where players who lost the game showed higher stress-related physiological responses, as compared to winning players. We also found that important specific in-game events such as "Killing", "Dying" or "Destroying Turret" significantly increased both electrodermal and cardiac activity over players more than other less-relevant events such as "Placing Wards" or "Destroying Turret Plates". Finally, by analyzing activity over player roles we found different trends of activity on these measurements, this could foster the exploration on human physiology with a higher set of participants in future Esports studies. △ Less

Submitted 22 May, 2023; v1 submitted 27 February, 2023; originally announced February 2023.

Comments: 10 pages, 6 tables

A Dynamic Weighted Federated Learning for Android Malware Classification

Authors: Ayushi Chaudhuri, Arijit Nandi, Buddhadeb Pradhan

Abstract: Android malware attacks are increasing daily at a tremendous volume, making Android users more vulnerable to cyber-attacks. Researchers have developed many machine learning (ML)/ deep learning (DL) techniques to detect and mitigate android malware attacks. However, due to technological advancement, there is a rise in android mobile devices. Furthermore, the devices are geographically dispersed, re… ▽ More Android malware attacks are increasing daily at a tremendous volume, making Android users more vulnerable to cyber-attacks. Researchers have developed many machine learning (ML)/ deep learning (DL) techniques to detect and mitigate android malware attacks. However, due to technological advancement, there is a rise in android mobile devices. Furthermore, the devices are geographically dispersed, resulting in distributed data. In such scenario, traditional ML/DL techniques are infeasible since all of these approaches require the data to be kept in a central system; this may provide a problem for user privacy because of the massive proliferation of Android mobile devices; putting the data in a central system creates an overhead. Also, the traditional ML/DL-based android malware classification techniques are not scalable. Researchers have proposed federated learning (FL) based android malware classification system to solve the privacy preservation and scalability with high classification performance. In traditional FL, Federated Averaging (FedAvg) is utilized to construct the global model at each round by merging all of the local models obtained from all of the customers that participated in the FL. However, the conventional FedAvg has a disadvantage: if one poor-performing local model is included in global model development for each round, it may result in an under-performing global model. Because FedAvg favors all local models equally when averaging. To address this issue, our main objective in this work is to design a dynamic weighted federated averaging (DW-FedAvg) strategy in which the weights for each local model are automatically updated based on their performance at the client. The DW-FedAvg is evaluated using four popular benchmark datasets, Melgenome, Drebin, Kronodroid and Tuandromd used in android malware classification research. △ Less

Submitted 23 November, 2022; originally announced November 2022.

Comments: Accepted in SoCTA 2022

Report number: Lecture Notes in Networks and Systems book series (LNNS,volume 627)-978-981-19-9857-7

Journal ref: 25 April 2023

MDEAW: A Multimodal Dataset for Emotion Analysis through EDA and PPG signals from wireless wearable low-cost off-the-shelf Devices

Authors: Arijit Nandi, Fatos Xhafa, Laia Subirats, Santi Fort

Abstract: We present MDEAW, a multimodal database consisting of Electrodermal Activity (EDA) and Photoplethysmography (PPG) signals recorded during the exams for the course taught by the teacher at Eurecat Academy, Sabadell, Barcelona in order to elicit the emotional reactions to the students in a classroom scenario. Signals from 10 students were recorded along with the students' self-assessment of their af… ▽ More We present MDEAW, a multimodal database consisting of Electrodermal Activity (EDA) and Photoplethysmography (PPG) signals recorded during the exams for the course taught by the teacher at Eurecat Academy, Sabadell, Barcelona in order to elicit the emotional reactions to the students in a classroom scenario. Signals from 10 students were recorded along with the students' self-assessment of their affective state after each stimulus, in terms of 6 basic emotion states. All the signals were captured using portable, wearable, wireless, low-cost, and off-the-shelf equipment that has the potential to allow the use of affective computing methods in everyday applications. A baseline for student-wise affect recognition using EDA and PPG-based features, as well as their fusion, was established through ReMECS, Fed-ReMECS, and Fed-ReMECS-U. These results indicate the prospects of using low-cost devices for affective state recognition applications. The proposed database will be made publicly available in order to allow researchers to achieve a more thorough evaluation of the suitability of these capturing devices for emotion state recognition applications. △ Less

Submitted 14 July, 2022; originally announced July 2022.

Process, Bias and Temperature Scalable CMOS Analog Computing Circuits for Machine Learning

Authors: Pratik Kumar, Ankita Nandi, Shantanu Chakrabartty, Chetan Singh Thakur

Abstract: Analog computing is attractive compared to digital computing due to its potential for achieving higher computational density and higher energy efficiency. However, unlike digital circuits, conventional analog computing circuits cannot be easily mapped across different process nodes due to differences in transistor biasing regimes, temperature variations and limited dynamic range. In this work, we… ▽ More Analog computing is attractive compared to digital computing due to its potential for achieving higher computational density and higher energy efficiency. However, unlike digital circuits, conventional analog computing circuits cannot be easily mapped across different process nodes due to differences in transistor biasing regimes, temperature variations and limited dynamic range. In this work, we generalize the previously reported margin-propagation-based analog computing framework for designing novel \textit{shape-based analog computing} (S-AC) circuits that can be easily cross-mapped across different process nodes. Similar to digital designs S-AC designs can also be scaled for precision, speed, and power. As a proof-of-concept, we show several examples of S-AC circuits implementing mathematical functions that are commonly used in machine learning (ML) architectures. Using circuit simulations we demonstrate that the circuit input/output characteristics remain robust when mapped from a planar CMOS 180nm process to a FinFET 7nm process. Also, using benchmark datasets we demonstrate that the classification accuracy of a S-AC based neural network remains robust when mapped across the two processes and to changes in temperature. △ Less

Submitted 4 January, 2023; v1 submitted 11 May, 2022; originally announced May 2022.

Comments: 14 Pages, 15 Figures, 5 Tables. This work has been accepted in IEEE for publication. Copyright may be transferred without notice, after which this version may no longer be accessible

Bias-Scalable Near-Memory CMOS Analog Processor for Machine Learning

Authors: Pratik Kumar, Ankita Nandi, Shantanu Chakrabartty, Chetan Singh Thakur

Abstract: Bias-scalable analog computing is attractive for implementing machine learning (ML) processors with distinct power-performance specifications. For instance, ML implementations for server workloads are focused on higher computational throughput for faster training, whereas ML implementations for edge devices are focused on energy-efficient inference. In this paper, we demonstrate the implementation… ▽ More Bias-scalable analog computing is attractive for implementing machine learning (ML) processors with distinct power-performance specifications. For instance, ML implementations for server workloads are focused on higher computational throughput for faster training, whereas ML implementations for edge devices are focused on energy-efficient inference. In this paper, we demonstrate the implementation of bias-scalable approximate analog computing circuits using the generalization of the margin-propagation principle called shape-based analog computing (S-AC). The resulting S-AC core integrates several near-memory compute elements, which include: (a) non-linear activation functions; (b) inner-product compute circuits; and (c) a mixed-signal compressive memory, all of which can be scaled for performance or power while preserving its functionality. Using measured results from prototypes fabricated in a 180nm CMOS process, we demonstrate that the performance of computing modules remains robust to transistor biasing and variations in temperature. In this paper, we also demonstrate the effect of bias-scalability and computational accuracy on a simple ML regression task. △ Less

Submitted 4 January, 2023; v1 submitted 10 February, 2022; originally announced February 2022.

Comments: 11 pages, 11 figures, 2 Tables

Non-Euclidean Differentially Private Stochastic Convex Optimization: Optimal Rates in Linear Time

Authors: Raef Bassily, Cristóbal Guzmán, Anupama Nandi

Abstract: Differentially private (DP) stochastic convex optimization (SCO) is a fundamental problem, where the goal is to approximately minimize the population risk with respect to a convex loss function, given a dataset of $n$ i.i.d. samples from a distribution, while satisfying differential privacy with respect to the dataset. Most of the existing works in the literature of private convex optimization foc… ▽ More Differentially private (DP) stochastic convex optimization (SCO) is a fundamental problem, where the goal is to approximately minimize the population risk with respect to a convex loss function, given a dataset of $n$ i.i.d. samples from a distribution, while satisfying differential privacy with respect to the dataset. Most of the existing works in the literature of private convex optimization focus on the Euclidean (i.e., $\ell_2$) setting, where the loss is assumed to be Lipschitz (and possibly smooth) w.r.t. the $\ell_2$ norm over a constraint set with bounded $\ell_2$ diameter. Algorithms based on noisy stochastic gradient descent (SGD) are known to attain the optimal excess risk in this setting. In this work, we conduct a systematic study of DP-SCO for $\ell_p$-setups under a standard smoothness assumption on the loss. For $1< p\leq 2$, under a standard smoothness assumption, we give a new, linear-time DP-SCO algorithm with optimal excess risk. Previously known constructions with optimal excess risk for $1< p <2$ run in super-linear time in $n$. For $p=1$, we give an algorithm with nearly optimal excess risk. Our result for the $\ell_1$-setup also extends to general polyhedral norms and feasible sets. Moreover, we show that the excess risk bounds resulting from our algorithms for $1\leq p \leq 2$ are attained with high probability. For $2 < p \leq \infty$, we show that existing linear-time constructions for the Euclidean setup attain a nearly optimal excess risk in the low-dimensional regime. As a consequence, we show that such constructions attain a nearly optimal excess risk for $p=\infty$. Our work draws upon concepts from the geometry of normed spaces, such as the notions of regularity, uniform convexity, and uniform smoothness. △ Less

Submitted 4 May, 2022; v1 submitted 1 March, 2021; originally announced March 2021.

Comments: This version contains several extensions to the conference paper that appeared at COLT 2021 (and to the earlier arXiv version: arXiv:2103.01278v1). This version contains new, linear-time constructions with optimal, high-probability risk guarantees

Medical Image Segmentation Using Deep Learning: A Survey

Authors: Risheng Wang, Tao Lei, Ruixia Cui, Bingtao Zhang, Hongying Meng, Asoke K. Nandi

Abstract: Deep learning has been widely used for medical image segmentation and a large number of papers has been presented recording the success of deep learning in the field. In this paper, we present a comprehensive thematic survey on medical image segmentation using deep learning techniques. This paper makes two original contributions. Firstly, compared to traditional surveys that directly divide litera… ▽ More Deep learning has been widely used for medical image segmentation and a large number of papers has been presented recording the success of deep learning in the field. In this paper, we present a comprehensive thematic survey on medical image segmentation using deep learning techniques. This paper makes two original contributions. Firstly, compared to traditional surveys that directly divide literatures of deep learning on medical image segmentation into many groups and introduce literatures in detail for each group, we classify currently popular literatures according to a multi-level structure from coarse to fine. Secondly, this paper focuses on supervised and weakly supervised learning approaches, without including unsupervised approaches since they have been introduced in many old surveys and they are not popular currently. For supervised learning approaches, we analyze literatures in three aspects: the selection of backbone networks, the design of network blocks, and the improvement of loss functions. For weakly supervised learning approaches, we investigate literature according to data augmentation, transfer learning, and interactive segmentation, separately. Compared to existing surveys, this survey classifies the literatures very differently from before and is more convenient for readers to understand the relevant rationale and will guide them to think of appropriate improvements in medical image segmentation based on deep learning approaches. △ Less

Submitted 22 December, 2021; v1 submitted 28 September, 2020; originally announced September 2020.

Learning from Mixtures of Private and Public Populations

Authors: Raef Bassily, Shay Moran, Anupama Nandi

Abstract: We initiate the study of a new model of supervised learning under privacy constraints. Imagine a medical study where a dataset is sampled from a population of both healthy and unhealthy individuals. Suppose healthy individuals have no privacy concerns (in such case, we call their data "public") while the unhealthy individuals desire stringent privacy protection for their data. In this example, the… ▽ More We initiate the study of a new model of supervised learning under privacy constraints. Imagine a medical study where a dataset is sampled from a population of both healthy and unhealthy individuals. Suppose healthy individuals have no privacy concerns (in such case, we call their data "public") while the unhealthy individuals desire stringent privacy protection for their data. In this example, the population (data distribution) is a mixture of private (unhealthy) and public (healthy) sub-populations that could be very different. Inspired by the above example, we consider a model in which the population $\mathcal{D}$ is a mixture of two sub-populations: a private sub-population $\mathcal{D}_{\sf priv}$ of private and sensitive data, and a public sub-population $\mathcal{D}_{\sf pub}$ of data with no privacy concerns. Each example drawn from $\mathcal{D}$ is assumed to contain a privacy-status bit that indicates whether the example is private or public. The goal is to design a learning algorithm that satisfies differential privacy only with respect to the private examples. Prior works in this context assumed a homogeneous population where private and public data arise from the same distribution, and in particular designed solutions which exploit this assumption. We demonstrate how to circumvent this assumption by considering, as a case study, the problem of learning linear classifiers in $\mathbb{R}^d$. We show that in the case where the privacy status is correlated with the target label (as in the above example), linear classifiers in $\mathbb{R}^d$ can be learned, in the agnostic as well as the realizable setting, with sample complexity which is comparable to that of the classical (non-private) PAC-learning. It is known that this task is impossible if all the data is considered private. △ Less

Submitted 1 August, 2020; originally announced August 2020.

Interpretable Multi-Headed Attention for Abstractive Summarization at Controllable Lengths

Authors: Ritesh Sarkhel, Moniba Keymanesh, Arnab Nandi, Srinivasan Parthasarathy

Abstract: Abstractive summarization at controllable lengths is a challenging task in natural language processing. It is even more challenging for domains where limited training data is available or scenarios in which the length of the summary is not known beforehand. At the same time, when it comes to trusting machine-generated summaries, explaining how a summary was constructed in human-understandable term… ▽ More Abstractive summarization at controllable lengths is a challenging task in natural language processing. It is even more challenging for domains where limited training data is available or scenarios in which the length of the summary is not known beforehand. At the same time, when it comes to trusting machine-generated summaries, explaining how a summary was constructed in human-understandable terms may be critical. We propose Multi-level Summarizer (MLS), a supervised method to construct abstractive summaries of a text document at controllable lengths. The key enabler of our method is an interpretable multi-headed attention mechanism that computes attention distribution over an input document using an array of timestep independent semantic kernels. Each kernel optimizes a human-interpretable syntactic or semantic property. Exhaustive experiments on two low-resource datasets in the English language show that MLS outperforms strong baselines by up to 14.70% in the METEOR score. Human evaluation of the summaries also suggests that they capture the key concepts of the document at various length-budgets. △ Less

Submitted 27 November, 2020; v1 submitted 18 February, 2020; originally announced February 2020.

Comments: 9 pages, 5 figures

Journal ref: International Conference on Computational Linguistics (COLING) 2020

Privately Answering Classification Queries in the Agnostic PAC Model

Authors: Anupama Nandi, Raef Bassily

Abstract: We revisit the problem of differentially private release of classification queries. In this problem, the goal is to design an algorithm that can accurately answer a sequence of classification queries based on a private training set while ensuring differential privacy. We formally study this problem in the agnostic PAC model and derive a new upper bound on the private sample complexity. Our results… ▽ More We revisit the problem of differentially private release of classification queries. In this problem, the goal is to design an algorithm that can accurately answer a sequence of classification queries based on a private training set while ensuring differential privacy. We formally study this problem in the agnostic PAC model and derive a new upper bound on the private sample complexity. Our results improve over those obtained in a recent work [BTT18] for the agnostic PAC setting. In particular, we give an improved construction that yields a tighter upper bound on the sample complexity. Moreover, unlike [BTT18], our accuracy guarantee does not involve any blow-up in the approximation error associated with the given hypothesis class. Given any hypothesis class with VC-dimension $d$, we show that our construction can privately answer up to $m$ classification queries with average excess error $α$ using a private sample of size $\approx \frac{d}{α^2}\,\max\left(1, \sqrt{m}\,α^{3/2}\right)$. Using recent results on private learning with auxiliary public data, we extend our construction to show that one can privately answer any number of classification queries with average excess error $α$ using a private sample of size $\approx \frac{d}{α^2}\,\max\left(1, \sqrt{d}\,α\right)$. When $α=O\left(\frac{1}{\sqrt{d}}\right)$, our private sample complexity bound is essentially optimal. △ Less

Submitted 3 December, 2019; v1 submitted 31 July, 2019; originally announced July 2019.

Comments: Made a a small tweak in the analysis to save a factor of $1/ε$

Accuracy Improvement of Neural Network Training using Particle Swarm Optimization and its Stability Analysis for Classification

Authors: Arijit Nandi, Nanda Dulal Jana

Abstract: Supervised classification is the most active and emerging research trends in today's scenario. In this view, Artificial Neural Network (ANN) techniques have been widely employed and growing interest to the researchers day by day. ANN training aims to find the proper setting of parameters such as weights ($\textbf{W}$) and biases ($b$) to properly classify the given data samples. The training proce… ▽ More Supervised classification is the most active and emerging research trends in today's scenario. In this view, Artificial Neural Network (ANN) techniques have been widely employed and growing interest to the researchers day by day. ANN training aims to find the proper setting of parameters such as weights ($\textbf{W}$) and biases ($b$) to properly classify the given data samples. The training process is formulated in an error minimization problem which consists of many local optima in the search landscape. In this paper, an enhanced Particle Swarm Optimization is proposed to minimize the error function for classifying real-life data sets. A stability analysis is performed to establish the efficiency of the proposed method for improving classification accuracy. The performance measurement such as confusion matrix, $F$-measure and convergence graph indicates the significant improvement in the classification accuracy. △ Less

Submitted 15 May, 2019; v1 submitted 11 May, 2019; originally announced May 2019.

Adaptive Morphological Reconstruction for Seeded Image Segmentation

Authors: Tao Lei, Xiaohong Jia, Tongliang Liu, Shigang Liu, Hongying Meng, Asoke K. Nandi

Abstract: Morphological reconstruction (MR) is often employed by seeded image segmentation algorithms such as watershed transform and power watershed as it is able to filter seeds (regional minima) to reduce over-segmentation. However, MR might mistakenly filter meaningful seeds that are required for generating accurate segmentation and it is also sensitive to the scale because a single-scale structuring el… ▽ More Morphological reconstruction (MR) is often employed by seeded image segmentation algorithms such as watershed transform and power watershed as it is able to filter seeds (regional minima) to reduce over-segmentation. However, MR might mistakenly filter meaningful seeds that are required for generating accurate segmentation and it is also sensitive to the scale because a single-scale structuring element is employed. In this paper, a novel adaptive morphological reconstruction (AMR) operation is proposed that has three advantages. Firstly, AMR can adaptively filter useless seeds while preserving meaningful ones. Secondly, AMR is insensitive to the scale of structuring elements because multiscale structuring elements are employed. Finally, AMR has two attractive properties: monotonic increasingness and convergence that help seeded segmentation algorithms to achieve a hierarchical segmentation. Experiments clearly demonstrate that AMR is useful for improving algorithms of seeded image segmentation and seed-based spectral segmentation. Compared to several state-of-the-art algorithms, the proposed algorithms provide better segmentation results requiring less computing time. Source code is available at https://github.com/SUST-reynole/AMR. △ Less

Submitted 8 April, 2019; originally announced April 2019.

Short and Long-term Pattern Discovery Over Large-Scale Geo-Spatiotemporal Data

Authors: Sobhan Moosavi, Mohammad Hossein Samavatian, Arnab Nandi, Srinivasan Parthasarathy, Rajiv Ramnath

Abstract: Pattern discovery in geo-spatiotemporal data (such as traffic and weather data) is about finding patterns of collocation, co-occurrence, cascading, or cause and effect between geospatial entities. Using simplistic definitions of spatiotemporal neighborhood (a common characteristic of the existing general-purpose frameworks) is not semantically representative of geo-spatiotemporal data. We therefor… ▽ More Pattern discovery in geo-spatiotemporal data (such as traffic and weather data) is about finding patterns of collocation, co-occurrence, cascading, or cause and effect between geospatial entities. Using simplistic definitions of spatiotemporal neighborhood (a common characteristic of the existing general-purpose frameworks) is not semantically representative of geo-spatiotemporal data. We therefore introduce a new geo-spatiotemporal pattern discovery framework which defines a semantically correct definition of neighborhood; and then provides two capabilities, one to explore propagation patterns and the other to explore influential patterns. Propagation patterns reveal common cascading forms of geospatial entities in a region. Influential patterns demonstrate the impact of temporally long-term geospatial entities on their neighborhood. We apply this framework on a large dataset of traffic and weather data at countrywide scale, collected for the contiguous United States over two years. Our important findings include the identification of 90 common propagation patterns of traffic and weather entities (e.g., rain --> accident --> congestion), which results in identification of four categories of states within the US; and interesting influential patterns with respect to the "location", "duration", and "type" of long-term entities (e.g., a major construction --> more traffic incidents). These patterns and the categorization of the states provide useful insights on the driving habits and infrastructure characteristics of different regions in the US, and could be of significant value for applications such as urban planning and personalized insurance. △ Less

Submitted 17 May, 2019; v1 submitted 13 February, 2019; originally announced February 2019.

Comments: In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

To Ship or Not to (Function) Ship (Extended version)

Authors: Feilong Liu, Niranjan Kamat, Spyros Blanas, Arnab Nandi

Abstract: Sampling is often used to reduce query latency for interactive big data analytics. The established parallel data processing paradigm relies on function shipping, where a coordinator dispatches queries to worker nodes and then collects the results. The commoditization of high-performance networking makes data shipping possible, where the coordinator directly reads data in the workers' memory using… ▽ More Sampling is often used to reduce query latency for interactive big data analytics. The established parallel data processing paradigm relies on function shipping, where a coordinator dispatches queries to worker nodes and then collects the results. The commoditization of high-performance networking makes data shipping possible, where the coordinator directly reads data in the workers' memory using RDMA while workers process other queries. In this work, we explore when to use function shipping or data shipping for interactive query processing with sampling. Whether function shipping or data shipping should be preferred depends on the amount of data transferred, the current CPU utilization, the sampling method and the number of queries executed over the data set. The results show that data shipping is up to 6.5x faster when performing clustered sampling with heavily-utilized workers. △ Less

Submitted 29 July, 2018; originally announced July 2018.

Comments: 4 pages, 3 figures

Bribery Games on Interdependent Complex Networks

Authors: Prateek Verma, Anjan K. Nandi, Supratim Sengupta

Abstract: Bribe demands present a social conflict scenario where decisions have wide-ranging economic and ethical consequences. Nevertheless, such incidents occur daily in many countries across the globe. Harassment bribery constitute a significant sub-set of such bribery incidents where a government official demands a bribe for providing a service to a citizen legally entitled to it. We employ an evolution… ▽ More Bribe demands present a social conflict scenario where decisions have wide-ranging economic and ethical consequences. Nevertheless, such incidents occur daily in many countries across the globe. Harassment bribery constitute a significant sub-set of such bribery incidents where a government official demands a bribe for providing a service to a citizen legally entitled to it. We employ an evolutionary game-theoretic framework to analyse the evolution of corrupt and honest strategies in structured populations characterized by an interdependent complex network. The effects of changing network topology, average number of links and asymmetry in size of the citizen and officer population on the proliferation of incidents of bribery are explored. A complex network topology is found to be beneficial for the dominance of corrupt strategies over a larger region of phase space when compared with the outcome for a regular network, for equal citizen and officer population sizes. However, the extent of the advantage depends critically on the network degree and topology. A different trend is observed when there is a difference between the citizen and officer population sizes. Under those circumstances, increasing randomness of the underlying citizen network can be beneficial to the fixation of honest officers up to a certain value of the network degree. Our analysis reveals how the interplay between network topology, connectivity and strategy update rules can affect population level outcomes in such asymmetric games. △ Less

Submitted 25 April, 2018; originally announced April 2018.

Comments: 24 pages, 7 figures, 5 supplementary figures; version to appear in Journal of Theoretical Biology

Discovery of Driving Patterns by Trajectory Segmentation

Authors: Sobhan Moosavi, Arnab Nandi, Rajiv Ramnath

Abstract: Telematics data is becoming increasingly available due to the ubiquity of devices that collect data during drives, for different purposes, such as usage based insurance (UBI), fleet management, navigation of connected vehicles, etc. Consequently, a variety of data-analytic applications have become feasible that extract valuable insights from the data. In this paper, we address the especially chall… ▽ More Telematics data is becoming increasingly available due to the ubiquity of devices that collect data during drives, for different purposes, such as usage based insurance (UBI), fleet management, navigation of connected vehicles, etc. Consequently, a variety of data-analytic applications have become feasible that extract valuable insights from the data. In this paper, we address the especially challenging problem of discovering behavior-based driving patterns from only externally observable phenomena (e.g. vehicle's speed). We present a trajectory segmentation approach capable of discovering driving patterns as separate segments, based on the behavior of drivers. This segmentation approach includes a novel transformation of trajectories along with a dynamic programming approach for segmentation. We apply the segmentation approach on a real-word, rich dataset of personal car trajectories provided by a major insurance company based in Columbus, Ohio. Analysis and preliminary results show the applicability of approach for finding significant driving patterns. △ Less

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

Comments: Accepted in the 3rd PhD workshop, ACM SIGSPATIAL 2016

Characterizing Driving Context from Driver Behavior

Authors: Sobhan Moosavi, Behrooz Omidvar-Tehrani, R. Bruce Craig, Arnab Nandi, Rajiv Ramnath

Abstract: Because of the increasing availability of spatiotemporal data, a variety of data-analytic applications have become possible. Characterizing driving context, where context may be thought of as a combination of location and time, is a new challenging application. An example of such a characterization is finding the correlation between driving behavior and traffic conditions. This contextual informat… ▽ More Because of the increasing availability of spatiotemporal data, a variety of data-analytic applications have become possible. Characterizing driving context, where context may be thought of as a combination of location and time, is a new challenging application. An example of such a characterization is finding the correlation between driving behavior and traffic conditions. This contextual information enables analysts to validate observation-based hypotheses about the driving of an individual. In this paper, we present DriveContext, a novel framework to find the characteristics of a context, by extracting significant driving patterns (e.g., a slow-down), and then identifying the set of potential causes behind patterns (e.g., traffic congestion). Our experimental results confirm the feasibility of the framework in identifying meaningful driving patterns, with improvements in comparison with the state-of-the-art. We also demonstrate how the framework derives interesting characteristics for different contexts, through real-world examples. △ Less

Submitted 17 November, 2017; v1 submitted 13 October, 2017; originally announced October 2017.

Comments: Accepted to be published at The 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL 2017)

InfiniViz: Interactive Visual Exploration using Progressive Bin Refinement

Authors: Niranjan Kamat, Arnab Nandi

Abstract: Interactive visualizations can accelerate the data analysis loop through near-instantaneous feedback. To achieve interactivity, techniques such as data cubes and sampling are typically employed. While data cubes can speedup querying for moderate-sized datasets, they are ineffective at doing so at a larger scales due to the size of the materialized data cubes. On the other hand, while sampling can… ▽ More Interactive visualizations can accelerate the data analysis loop through near-instantaneous feedback. To achieve interactivity, techniques such as data cubes and sampling are typically employed. While data cubes can speedup querying for moderate-sized datasets, they are ineffective at doing so at a larger scales due to the size of the materialized data cubes. On the other hand, while sampling can help scale to large datasets, it adds sampling error and the associated issues into the process. While increasing accuracy by looking at more data may sometimes be valuable, providing result minutiae might not be necessary if they do not impart additional significant information. Indeed, such details not only incur a higher \emph{computational} cost, but also tax the \emph{cognitive} load of the analyst with worthless trivia. To reduce both the computational and cognitive expenses, we introduce \emph{InfiniViz}. Through a novel result refinement-based querying paradigm, \emph{InfiniViz} provides error-free results for large datasets by increasing bin resolutions progressively over time. Through real and simulated workloads over real and benchmark datasets, we evaluate and demonstrate \emph{InfiniViz}'s utility at reducing both cognitive and computational costs, while minimizing information loss. △ Less

Submitted 4 October, 2017; originally announced October 2017.

Heavy-Tailed Analogues of the Covariance Matrix for ICA

Authors: Joseph Anderson, Navin Goyal, Anupama Nandi, Luis Rademacher

Abstract: Independent Component Analysis (ICA) is the problem of learning a square matrix $A$, given samples of $X=AS$, where $S$ is a random vector with independent coordinates. Most existing algorithms are provably efficient only when each $S_i$ has finite and moderately valued fourth moment. However, there are practical applications where this assumption need not be true, such as speech and finance. Algo… ▽ More Independent Component Analysis (ICA) is the problem of learning a square matrix $A$, given samples of $X=AS$, where $S$ is a random vector with independent coordinates. Most existing algorithms are provably efficient only when each $S_i$ has finite and moderately valued fourth moment. However, there are practical applications where this assumption need not be true, such as speech and finance. Algorithms have been proposed for heavy-tailed ICA, but they are not practical, using random walks and the full power of the ellipsoid algorithm multiple times. The main contributions of this paper are: (1) A practical algorithm for heavy-tailed ICA that we call HTICA. We provide theoretical guarantees and show that it outperforms other algorithms in some heavy-tailed regimes, both on real and synthetic data. Like the current state-of-the-art, the new algorithm is based on the centroid body (a first moment analogue of the covariance matrix). Unlike the state-of-the-art, our algorithm is practically efficient. To achieve this, we use explicit analytic representations of the centroid body, which bypasses the use of the ellipsoid method and random walks. (2) We study how heavy tails affect different ICA algorithms, including HTICA. Somewhat surprisingly, we show that some algorithms that use the covariance matrix or higher moments can successfully solve a range of ICA instances with infinite second moment. We study this theoretically and experimentally, with both synthetic and real-world heavy-tailed data. △ Less

Submitted 22 February, 2017; originally announced February 2017.

Comments: 16 Pages, 9 Figures, AAAI 2017

Graphical Perception in Animated Bar Charts

Authors: Eugene Wu, Lilong Jiang, Larry Xu, Arnab Nandi

Abstract: Interactive visual applications create animations that encode changes in the data. For example, cross-filtering dynamically updates linked visualizations based on the user's continuous brushing actions. The animated effects resulting from these interactions depends both on how interaction (e.g., brushing speed) controls properties of the animation such as frame rate, as well as how the data that i… ▽ More Interactive visual applications create animations that encode changes in the data. For example, cross-filtering dynamically updates linked visualizations based on the user's continuous brushing actions. The animated effects resulting from these interactions depends both on how interaction (e.g., brushing speed) controls properties of the animation such as frame rate, as well as how the data that is being explored dictates the data encoded in the animation. Past work has found that frame rate matters to general perception, however a critical question is which of these animation and data properties affects the perceptual accuracy of judgement tasks, and to what extent. Although graphical perception has been well studied for static data visualizations, it is ripe for exploration in the animated setting. We designed two animated judgment tasks of a target bar in an animated bar chart and empirically evaluate the effects of 2 animations properties - highlighting of the target bar and frame rate - as well as 3 data properties that affect the target bar's value throughout the animation. In short, we find that the rate and timing of animation changes is easier detected in larger values; that encodings such as color are easier to detect than shapes; and that timing is important - earlier changes were harder to perceive as compared to later changes in the animation. Our results are an initial step to understanding perceptual accuracy for animated data visualizations, both for presentations and ultimately as part of interactive applications. △ Less

Submitted 31 March, 2016; originally announced April 2016.

Comments: 10 pages

ACM Class: H.5.2; I.2.10; I.3.6

Perfect and Maximum Randomness in Stratified Sampling over Joins

Authors: Niranjan Kamat, Arnab Nandi

Abstract: Supporting sampling in the presence of joins is an important problem in data analysis, but is inherently challenging due to the need to avoid correlation between output tuples. Current solutions provide either correlated or non-correlated samples. Sampling might not always be feasible in the non-correlated sampling-based approaches -- the sample size or intermediate data size might be exceedingly… ▽ More Supporting sampling in the presence of joins is an important problem in data analysis, but is inherently challenging due to the need to avoid correlation between output tuples. Current solutions provide either correlated or non-correlated samples. Sampling might not always be feasible in the non-correlated sampling-based approaches -- the sample size or intermediate data size might be exceedingly large. On the other hand, a correlated sample may not be representative of the join. This paper presents a \emph{unified} strategy towards join sampling, while considering sample correlation every step of the way. We provide two key contributions. First, in the case where a \emph{correlated} sample is \emph{acceptable}, we provide techniques, for all join types, to sample base relations so that their join is \emph{as random as possible}. Second, in the case where a correlated sample is \emph{not acceptable}, we provide enhancements to the state-of-the-art algorithms to reduce their execution time and intermediate data size. △ Less

Submitted 14 February, 2017; v1 submitted 19 January, 2016; originally announced January 2016.

Mimir: Bringing CTables into Practice

Authors: Arindam Nandi, Ying Yang, Oliver Kennedy, Boris Glavic, Ronny Fehling, Zhen Hua Liu, Dieter Gawlick

Abstract: The present state of the art in analytics requires high upfront investment of human effort and computational resources to curate datasets, even before the first query is posed. So-called pay-as-you-go data curation techniques allow these high costs to be spread out, first by enabling queries over uncertain and incomplete data, and then by assessing the quality of the query results. We describe the… ▽ More The present state of the art in analytics requires high upfront investment of human effort and computational resources to curate datasets, even before the first query is posed. So-called pay-as-you-go data curation techniques allow these high costs to be spread out, first by enabling queries over uncertain and incomplete data, and then by assessing the quality of the query results. We describe the design of a system, called Mimir, around a recently introduced class of probabilistic pay-as-you-go data cleaning operators called Lenses. Mimir wraps around any deterministic database engine using JDBC, extending it with support for probabilistic query processing. Queries processed through Mimir produce uncertainty-annotated result cursors that allow client applications to quickly assess result quality and provenance. We also present a GUI that provides analysts with an interactive tool for exploring the uncertainty exposed by the system. Finally, we present optimizations that make Lenses scalable, and validate this claim through experimental evidence. △ Less

Submitted 1 January, 2016; originally announced January 2016.

Comments: Under submission; The first two authors should be considered a joint first-author

A Closer Look at Variance Implementations in Modern Database Systems

Authors: Niranjan Kamat, Arnab Nandi

Abstract: Variance is a popular and often necessary component of sampled aggregation queries. It is typically used as a secondary measure to ascertain statistical properties of the result such as its error. Yet, it is more expensive to compute than simple, primary measures such as \texttt{SUM}, \texttt{MEAN}, and \texttt{COUNT}. There exist numerous techniques to compute variance. While the definition of… ▽ More Variance is a popular and often necessary component of sampled aggregation queries. It is typically used as a secondary measure to ascertain statistical properties of the result such as its error. Yet, it is more expensive to compute than simple, primary measures such as \texttt{SUM}, \texttt{MEAN}, and \texttt{COUNT}. There exist numerous techniques to compute variance. While the definition of variance is considered to require multiple passes on the data, other mathematical representations can compute the value in a single pass. Some single-pass representations, however, can suffer from severe precision loss, especially for large number of data points. In this paper, we study variance implementations in various real-world systems and find that major database systems such as PostgreSQL 9.4 and most likely System X, a major commercially used closed-source database, use a representation that is efficient, but suffers from floating point precision loss resulting from catastrophic cancellation. We note deficiencies in another popular representation, used by databases such as MySQL and Impala, that suffers from not being distributive and therefore cannot take advantage of modern parallel computational resources. We review literature over the past five decades on variance calculation in both the statistics and database communities, and summarize recommendations on implementing variance functions in various settings, such as approximate query processing and large-scale distributed aggregation. △ Less

Submitted 23 December, 2016; v1 submitted 14 September, 2015; originally announced September 2015.

Heavy-tailed Independent Component Analysis

Authors: Joseph Anderson, Navin Goyal, Anupama Nandi, Luis Rademacher

Abstract: Independent component analysis (ICA) is the problem of efficiently recovering a matrix $A \in \mathbb{R}^{n\times n}$ from i.i.d. observations of $X=AS$ where $S \in \mathbb{R}^n$ is a random vector with mutually independent coordinates. This problem has been intensively studied, but all existing efficient algorithms with provable guarantees require that the coordinates $S_i$ have finite fourth mo… ▽ More Independent component analysis (ICA) is the problem of efficiently recovering a matrix $A \in \mathbb{R}^{n\times n}$ from i.i.d. observations of $X=AS$ where $S \in \mathbb{R}^n$ is a random vector with mutually independent coordinates. This problem has been intensively studied, but all existing efficient algorithms with provable guarantees require that the coordinates $S_i$ have finite fourth moments. We consider the heavy-tailed ICA problem where we do not make this assumption, about the second moment. This problem also has received considerable attention in the applied literature. In the present work, we first give a provably efficient algorithm that works under the assumption that for constant $γ> 0$, each $S_i$ has finite $(1+γ)$-moment, thus substantially weakening the moment requirement condition for the ICA problem to be solvable. We then give an algorithm that works under the assumption that matrix $A$ has orthogonal columns but requires no moment assumptions. Our techniques draw ideas from convex geometry and exploit standard properties of the multivariate spherical Gaussian distribution in a novel way. △ Less

Submitted 2 September, 2015; originally announced September 2015.

Comments: 30 pages

Diffusion map for clustering fMRI spatial maps extracted by independent component analysis

Authors: Tuomo Sipola, Fengyu Cong, Tapani Ristaniemi, Vinoo Alluri, Petri Toiviainen, Elvira Brattico, Asoke K. Nandi

Abstract: Functional magnetic resonance imaging (fMRI) produces data about activity inside the brain, from which spatial maps can be extracted by independent component analysis (ICA). In datasets, there are n spatial maps that contain p voxels. The number of voxels is very high compared to the number of analyzed spatial maps. Clustering of the spatial maps is usually based on correlation matrices. This usua… ▽ More Functional magnetic resonance imaging (fMRI) produces data about activity inside the brain, from which spatial maps can be extracted by independent component analysis (ICA). In datasets, there are n spatial maps that contain p voxels. The number of voxels is very high compared to the number of analyzed spatial maps. Clustering of the spatial maps is usually based on correlation matrices. This usually works well, although such a similarity matrix inherently can explain only a certain amount of the total variance contained in the high-dimensional data where n is relatively small but p is large. For high-dimensional space, it is reasonable to perform dimensionality reduction before clustering. In this research, we used the recently developed diffusion map for dimensionality reduction in conjunction with spectral clustering. This research revealed that the diffusion map based clustering worked as well as the more traditional methods, and produced more compact clusters when needed. △ Less

Submitted 27 September, 2013; v1 submitted 6 June, 2013; originally announced June 2013.

Comments: 6 pages. 8 figures. Copyright (c) 2013 IEEE. Published at 2013 IEEE International Workshop on Machine Learning for Signal Processing

Qunits: queried units in database search

Authors: Arnab Nandi, H V Jagadish

Abstract: Keyword search against structured databases has become a popular topic of investigation, since many users find structured queries too hard to express, and enjoy the freedom of a ``Google-like'' query box into which search terms can be entered. Attempts to address this problem face a fundamental dilemma. Database querying is based on the logic of predicate evaluation, with a precisely defined ans… ▽ More Keyword search against structured databases has become a popular topic of investigation, since many users find structured queries too hard to express, and enjoy the freedom of a ``Google-like'' query box into which search terms can be entered. Attempts to address this problem face a fundamental dilemma. Database querying is based on the logic of predicate evaluation, with a precisely defined answer set for a given query. On the other hand, in an information retrieval approach, ranked query results have long been accepted as far superior to results based on boolean query evaluation. As a consequence, when keyword queries are attempted against databases, relatively ad-hoc ranking mechanisms are invented (if ranking is used at all), and there is little leverage from the large body of IR literature regarding how to rank query results. Our proposal is to create a clear separation between ranking and database querying. This divides the problem into two parts, and allows us to address these separately. The first task is to represent the database, conceptually, as a collection of independent ``queried units'', or ``qunits'', each of which represents the desired result for some query against the database. The second task is to evaluate keyword queries against a collection of qunits, which can be treated as independent documents for query purposes, thereby permitting the use of standard IR techniques. We provide insights that encourage the use of this query paradigm, and discuss preliminary investigations into the efficacy of a qunits-based framework based on a prototype implementation. △ Less

Submitted 9 September, 2009; originally announced September 2009.

Comments: CIDR 2009