Showing 1–25 of 25 results for author: Narayanan, B

Decomposing the Doer Effect in Programming Practice: Code Writing Stands Out Among Active Practice

Authors: Arun Balajiee Lekshmi Narayanan, Gillian Gold, Jordan Barria-Pineda, Quinn K Wolter, Peter Brusilovsky, Paulo Carvalho

Abstract: The "doer effect" suggests that actively doing practice activities is more strongly associated with learning outcomes than passively viewing content. In the doer effect literature, "doing" refers specifically to active practice. However, this categorization treats different forms of active practice as equivalent, leaving open whether some types of active practice are more effective than others. In… ▽ More The "doer effect" suggests that actively doing practice activities is more strongly associated with learning outcomes than passively viewing content. In the doer effect literature, "doing" refers specifically to active practice. However, this categorization treats different forms of active practice as equivalent, leaving open whether some types of active practice are more effective than others. In this paper, we investigate whether the doer effect extends to computer science instruction and whether some forms of doing stand out compared to other forms. We analyze log data from 334 students across 11 semesters of introductory and intermediate Java who used an interactive practice system with five content types: Code Writing, Code Tracing, Code Completion, Code Visualizations, and Code Explanations. Consistent with prior doer effect work, we find that active practice activities were associated with 3.2 times better learning outcomes than passive activities. Interestingly, among the active practice, code writing was the most strongly associated with improved posttest performance, while no other activity type showed a comparable association. These results highlight the importance of challenging, feedback-supported practice activities, such as code writing problems. △ Less

Submitted 3 August, 2026; originally announced August 2026.

Automated Recommendation of Programming Learning Content Using Pattern-based Knowledge Components

Authors: Muntasir Hoq, Griffin Pitts, Zhangqi Duan, Arun Balajiee Lekshmi Narayanan, Mohammad Hassany, Andrew Lan, Peter Brusilovsky, Bita Akram

Abstract: Introductory programming instruction relies on hands-on practice and short learning activities to support mastery of foundational concepts. Although many such learning resources exist, organizing and linking these items in instructionally meaningful ways is challenging without time-intensive expert curation. This study investigates the use of pattern-based Knowledge Components (KCs) to automatical… ▽ More Introductory programming instruction relies on hands-on practice and short learning activities to support mastery of foundational concepts. Although many such learning resources exist, organizing and linking these items in instructionally meaningful ways is challenging without time-intensive expert curation. This study investigates the use of pattern-based Knowledge Components (KCs) to automatically identify code-based learning resources targeting similar concepts. In our approach, pattern-based KCs are extracted from each code sample, and related activities are identified by measuring similarity between the KC sets associated with each activity. By leveraging alignment at the level of semantically important programming patterns, this method supports contextually appropriate and pedagogically useful recommendations. We evaluate our approach on an expert-organized corpus of introductory Python materials in which instructors grouped items into bundles based on conceptual similarity. Results show that our pattern-based KC approach retrieves resources that align with this expert organization, and outperformed representative KC- and embedding-based baselines across standard ranking evaluations. Overall, the framework supports targeted, concept-oriented guidance for programming learners and can help instructors organize, bundle, and recommend instructional content at scale. △ Less

Submitted 9 June, 2026; originally announced July 2026.

Comments: Paper accepted to the 10th Educational Data Mining in Computer Science Education (CSEDM) Workshop in Seoul, Korea

Automated Knowledge Component Generation for Interpretable Knowledge Tracing in Coding Problems

Authors: Zhangqi Duan, Nigel Fernandez, Arun Balajiee Lekshmi Narayanan, Mohammad Hassany, Rafaella Sampaio de Alencar, Peter Brusilovsky, Bita Akram, Andrew Lan

Abstract: Knowledge components (KCs) mapped to problems help model student learning, tracking their mastery levels on fine-grained skills thereby facilitating personalized learning and feedback in online learning platforms. However, crafting and tagging KCs to problems, traditionally performed by human domain experts, is highly labor intensive. We present an automated, LLM-based pipeline for KC generation a… ▽ More Knowledge components (KCs) mapped to problems help model student learning, tracking their mastery levels on fine-grained skills thereby facilitating personalized learning and feedback in online learning platforms. However, crafting and tagging KCs to problems, traditionally performed by human domain experts, is highly labor intensive. We present an automated, LLM-based pipeline for KC generation and tagging for open-ended programming problems. We also develop an LLM-based knowledge tracing (KT) framework to leverage these LLM-generated KCs, which we refer to as KCGen-KT. We conduct extensive quantitative and qualitative evaluations on two real-world student code submission datasets in different programming languages.We find that KCGen-KT outperforms existing KT methods and human-written KCs on future student response prediction. We investigate the learning curves of generated KCs and show that LLM-generated KCs result in a better fit than human written KCs under a cognitive model. We also conduct a human evaluation with course instructors to show that our pipeline generates reasonably accurate problem-KC mappings. △ Less

Submitted 16 May, 2026; v1 submitted 25 February, 2025; originally announced February 2025.

Comments: Findings of ACL 2026: The 64th Annual Meeting of the Association for Computational Linguistics

Towards Scalable Automated Grading: Leveraging Large Language Models for Conceptual Question Evaluation in Engineering

Authors: Rujun Gao, Xiaosu Guo, Xiaodi Li, Arun Balajiee Lekshmi Narayanan, Naveen Thomas, Arun R. Srinivasa

Abstract: This study explores the feasibility of using large language models (LLMs), specifically GPT-4o (ChatGPT), for automated grading of conceptual questions in an undergraduate Mechanical Engineering course. We compared the grading performance of GPT-4o with that of human teaching assistants (TAs) on ten quiz problems from the MEEN 361 course at Texas A&M University, each answered by approximately 225… ▽ More This study explores the feasibility of using large language models (LLMs), specifically GPT-4o (ChatGPT), for automated grading of conceptual questions in an undergraduate Mechanical Engineering course. We compared the grading performance of GPT-4o with that of human teaching assistants (TAs) on ten quiz problems from the MEEN 361 course at Texas A&M University, each answered by approximately 225 students. Both the LLM and TAs followed the same instructor-provided rubric to ensure grading consistency. We evaluated performance using Spearman's rank correlation coefficient and Root Mean Square Error (RMSE) to assess the alignment between rankings and the accuracy of scores assigned by GPT-4o and TAs under zero- and few-shot grading settings. In the zero-shot setting, GPT-4o demonstrated a strong correlation with TA grading, with Spearman's rank correlation coefficient exceeding 0.6 in seven out of ten datasets and reaching a high of 0.9387. Our analysis reveals that GPT-4o performs well when grading criteria are straightforward but struggles with nuanced answers, particularly those involving synonyms not present in the rubric. The model also tends to grade more stringently in ambiguous cases compared to human TAs. Overall, ChatGPT shows promise as a tool for grading conceptual questions, offering scalability and consistency. △ Less

Submitted 5 November, 2024; originally announced November 2024.

Comments: 21 pages, 21 figures

PalmBench: A Comprehensive Benchmark of Compressed Large Language Models on Mobile Platforms

Authors: Yilong Li, Jingyu Liu, Hao Zhang, M Badri Narayanan, Utkarsh Sharma, Shuai Zhang, Pan Hu, Yijing Zeng, Jayaram Raghuram, Suman Banerjee

Abstract: Deploying large language models (LLMs) locally on mobile devices is advantageous in scenarios where transmitting data to remote cloud servers is either undesirable due to privacy concerns or impractical due to network connection. Recent advancements (MLC, 2023a; Gerganov, 2023) have facilitated the local deployment of LLMs. However, local deployment also presents challenges, particularly in balanc… ▽ More Deploying large language models (LLMs) locally on mobile devices is advantageous in scenarios where transmitting data to remote cloud servers is either undesirable due to privacy concerns or impractical due to network connection. Recent advancements (MLC, 2023a; Gerganov, 2023) have facilitated the local deployment of LLMs. However, local deployment also presents challenges, particularly in balancing quality (generative performance), latency, and throughput within the hardware constraints of mobile devices. In this paper, we introduce our lightweight, all-in-one automated benchmarking framework that allows users to evaluate LLMs on mobile devices. We provide a comprehensive benchmark of various popular LLMs with different quantization configurations (both weights and activations) across multiple mobile platforms with varying hardware capabilities. Unlike traditional benchmarks that assess full-scale models on high-end GPU clusters, we focus on evaluating resource efficiency (memory and power consumption) and harmful output for compressed models on mobile devices. Our key observations include i) differences in energy efficiency and throughput across mobile platforms; ii) the impact of quantization on memory usage, GPU execution time, and power consumption; and iii) accuracy and performance degradation of quantized models compared to their non-quantized counterparts; and iv) the frequency of hallucinations and toxic content generated by compressed LLMs on mobile devices. △ Less

Submitted 8 January, 2025; v1 submitted 4 October, 2024; originally announced October 2024.

Comments: 10 pages

Evaluating the Quality of Code Comments Generated by Large Language Models for Novice Programmers

Authors: Aysa Xuemo Fan, Arun Balajiee Lekshmi Narayanan, Mohammad Hassany, Jiaze Ke

Abstract: Large Language Models (LLMs) show promise in generating code comments for novice programmers, but their educational effectiveness remains under-evaluated. This study assesses the instructional quality of code comments produced by GPT-4, GPT-3.5-Turbo, and Llama2, compared to expert-developed comments, focusing on their suitability for novices. Analyzing a dataset of ``easy'' level Java solutions f… ▽ More Large Language Models (LLMs) show promise in generating code comments for novice programmers, but their educational effectiveness remains under-evaluated. This study assesses the instructional quality of code comments produced by GPT-4, GPT-3.5-Turbo, and Llama2, compared to expert-developed comments, focusing on their suitability for novices. Analyzing a dataset of ``easy'' level Java solutions from LeetCode, we find that GPT-4 exhibits comparable quality to expert comments in aspects critical for beginners, such as clarity, beginner-friendliness, concept elucidation, and step-by-step guidance. GPT-4 outperforms Llama2 in discussing complexity (chi-square = 11.40, p = 0.001) and is perceived as significantly more supportive for beginners than GPT-3.5 and Llama2 with Mann-Whitney U-statistics = 300.5 and 322.5, p = 0.0017 and 0.0003). This study highlights the potential of LLMs for generating code comments tailored to novice programmers. △ Less

Submitted 22 September, 2024; originally announced September 2024.

Human-AI Co-Creation of Worked Examples for Programming Classes

Authors: Mohammad Hassany, Peter Brusilovsky, Jiaze Ke, Kamil Akhuseyinoglu, Arun Balajiee Lekshmi Narayanan

Abstract: Worked examples (solutions to typical programming problems presented as a source code in a certain language and are used to explain the topics from a programming class) are among the most popular types of learning content in programming classes. Most approaches and tools for presenting these examples to students are based on line-by-line explanations of the example code. However, instructors rarel… ▽ More Worked examples (solutions to typical programming problems presented as a source code in a certain language and are used to explain the topics from a programming class) are among the most popular types of learning content in programming classes. Most approaches and tools for presenting these examples to students are based on line-by-line explanations of the example code. However, instructors rarely have time to provide line-by-line explanations for a large number of examples typically used in a programming class. In this paper, we explore and assess a human-AI collaboration approach to authoring worked examples for Java programming. We introduce an authoring system for creating Java worked examples that generates a starting version of code explanations and presents it to the instructor to edit if necessary.We also present a study that assesses the quality of explanations created with this approach △ Less

Submitted 29 February, 2024; v1 submitted 25 February, 2024; originally announced February 2024.

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

Authoring Worked Examples for Java Programming with Human-AI Collaboration

Authors: Mohammad Hassany, Peter Brusilovsky, Jiaze Ke, Kamil Akhuseyinoglu, Arun Balajiee Lekshmi Narayanan

Abstract: Worked examples (solutions to typical programming problems presented as a source code in a certain language and are used to explain the topics from a programming class) are among the most popular types of learning content in programming classes. Most approaches and tools for presenting these examples to students are based on line-by-line explanations of the example code. However, instructors rarel… ▽ More Worked examples (solutions to typical programming problems presented as a source code in a certain language and are used to explain the topics from a programming class) are among the most popular types of learning content in programming classes. Most approaches and tools for presenting these examples to students are based on line-by-line explanations of the example code. However, instructors rarely have time to provide line-by-line explanations for a large number of examples typically used in a programming class. In this paper, we explore and assess a human-AI collaboration approach to authoring worked examples for Java programming. We introduce an authoring system for creating Java worked examples that generates a starting version of code explanations and presents it to the instructor to edit if necessary. We also present a study that assesses the quality of explanations created with this approach. △ Less

Submitted 4 December, 2023; originally announced December 2023.

Comments: 2 papers both same content

Enhancing Programming eTextbooks with ChatGPT Generated Counterfactual-Thinking-Inspired Questions

Authors: Arun Balajiee Lekshmi Narayanan, Rully Agus Hendrawan, Venktesh V

Abstract: Digital textbooks have become an integral part of everyday learning tasks. In this work, we consider the use of digital textbooks for programming classes. Generally, students struggle with utilizing textbooks on programming to the maximum, with a possible reason being that the example programs provided as illustration of concepts in these textbooks don't offer sufficient interactivity for students… ▽ More Digital textbooks have become an integral part of everyday learning tasks. In this work, we consider the use of digital textbooks for programming classes. Generally, students struggle with utilizing textbooks on programming to the maximum, with a possible reason being that the example programs provided as illustration of concepts in these textbooks don't offer sufficient interactivity for students, and thereby not sufficiently motivating to explore or understand these programming examples better. In our work, we explore the idea of enhancing the navigability of intelligent textbooks with the use of ``counterfactual'' questions, to make students think critically about these programs and enhance possible program comprehension. Inspired from previous works on nudging students on counter factual thinking, we present the possibility to enhance digital textbooks with questions generated using GPT. △ Less

Submitted 6 June, 2023; v1 submitted 1 June, 2023; originally announced June 2023.

Comments: Paper Under Review

GenQ: Automated Question Generation to Support Caregivers While Reading Stories with Children

Authors: Arun Balajiee Lekshmi Narayanan, Ligia E. Gomez, Martha Michelle Soto Fernandez, Tri Nguyen, Chris Blais, M. Adelaida Restrepo, Art Glenberg

Abstract: When caregivers ask open--ended questions to motivate dialogue with children, it facilitates the child's reading comprehension skills.Although there is scope for use of technological tools, referred here as "intelligent tutoring systems", to scaffold this process, it is currently unclear whether existing intelligent systems that generate human--language like questions is beneficial. Additionally,… ▽ More When caregivers ask open--ended questions to motivate dialogue with children, it facilitates the child's reading comprehension skills.Although there is scope for use of technological tools, referred here as "intelligent tutoring systems", to scaffold this process, it is currently unclear whether existing intelligent systems that generate human--language like questions is beneficial. Additionally, training data used in the development of these automated question generation systems is typically sourced without attention to demographics, but people with different cultural backgrounds may ask different questions. As a part of a broader project to design an intelligent reading support app for Latinx children, we crowdsourced questions from Latinx caregivers and noncaregivers as well as caregivers and noncaregivers from other demographics. We examine variations in question--asking within this dataset mediated by individual, cultural, and contextual factors. We then design a system that automatically extracts templates from this data to generate open--ended questions that are representative of those asked by Latinx caregivers. △ Less

Submitted 25 September, 2023; v1 submitted 26 May, 2023; originally announced May 2023.

Antichain Codes

Authors: Benjamin Gunby, Xiaoyu He, Bhargav Narayanan, Sam Spiro

Abstract: A family of sets $A$ is said to be an antichain if $x\not\subset y$ for all distinct $x,y\in A$, and it is said to be a distance-$r$ code if every pair of distinct elements of $A$ has Hamming distance at least $r$. Here, we prove that if $A\subset 2^{[n]}$ is both an antichain and a distance-$(2r+1)$ code, then $|A| = O_r(2^n n^{-r-1/2})$. This result, which is best-possible up to the implied cons… ▽ More A family of sets $A$ is said to be an antichain if $x\not\subset y$ for all distinct $x,y\in A$, and it is said to be a distance-$r$ code if every pair of distinct elements of $A$ has Hamming distance at least $r$. Here, we prove that if $A\subset 2^{[n]}$ is both an antichain and a distance-$(2r+1)$ code, then $|A| = O_r(2^n n^{-r-1/2})$. This result, which is best-possible up to the implied constant, is a purely combinatorial strengthening of a number of results in Littlewood--Offord theory; for example, our result gives a short combinatorial proof of Hálasz's theorem, while all previously known proofs of this result are Fourier-analytic. △ Less

Submitted 16 December, 2022; originally announced December 2022.

Comments: 8 pages

A Counterexample to a Directed KKL Inequality

Authors: Quentin Dubroff, Shivam Nadimpalli, Bhargav Narayanan

Abstract: We show that the natural directed analogues of the KKL theorem [KKL88] and the Eldan--Gross inequality [EG20] from the analysis of Boolean functions fail to hold. This is in contrast to several other isoperimetric inequalities on the Boolean hypercube (such as the Poincare inequality, Margulis's inequality [Mar74] and Talagrand's inequality [Tal93]) for which directed strengthenings have recently… ▽ More We show that the natural directed analogues of the KKL theorem [KKL88] and the Eldan--Gross inequality [EG20] from the analysis of Boolean functions fail to hold. This is in contrast to several other isoperimetric inequalities on the Boolean hypercube (such as the Poincare inequality, Margulis's inequality [Mar74] and Talagrand's inequality [Tal93]) for which directed strengthenings have recently been established. △ Less

Submitted 5 October, 2022; originally announced October 2022.

Comments: 5 pages. Comments welcome

Utilizing unsupervised learning to improve sward content prediction and herbage mass estimation

Authors: Paul Albert, Mohamed Saadeldin, Badri Narayanan, Brian Mac Namee, Deirdre Hennessy, Aisling H. O'Connor, Noel E. O'Connor, Kevin McGuinness

Abstract: Sward species composition estimation is a tedious one. Herbage must be collected in the field, manually separated into components, dried and weighed to estimate species composition. Deep learning approaches using neural networks have been used in previous work to propose faster and more cost efficient alternatives to this process by estimating the biomass information from a picture of an area of p… ▽ More Sward species composition estimation is a tedious one. Herbage must be collected in the field, manually separated into components, dried and weighed to estimate species composition. Deep learning approaches using neural networks have been used in previous work to propose faster and more cost efficient alternatives to this process by estimating the biomass information from a picture of an area of pasture alone. Deep learning approaches have, however, struggled to generalize to distant geographical locations and necessitated further data collection to retrain and perform optimally in different climates. In this work, we enhance the deep learning solution by reducing the need for ground-truthed (GT) images when training the neural network. We demonstrate how unsupervised contrastive learning can be used in the sward composition prediction problem and compare with the state-of-the-art on the publicly available GrassClover dataset collected in Denmark as well as a more recent dataset from Ireland where we tackle herbage mass and height estimation. △ Less

Submitted 20 April, 2022; originally announced April 2022.

Comments: 3 pages. Accepted at the 29th EGF General Meeting 2022

Unsupervised domain adaptation and super resolution on drone images for autonomous dry herbage biomass estimation

Authors: Paul Albert, Mohamed Saadeldin, Badri Narayanan, Jaime Fernandez, Brian Mac Namee, Deirdre Hennessey, Noel E. O'Connor, Kevin McGuinness

Abstract: Herbage mass yield and composition estimation is an important tool for dairy farmers to ensure an adequate supply of high quality herbage for grazing and subsequently milk production. By accurately estimating herbage mass and composition, targeted nitrogen fertiliser application strategies can be deployed to improve localised regions in a herbage field, effectively reducing the negative impacts of… ▽ More Herbage mass yield and composition estimation is an important tool for dairy farmers to ensure an adequate supply of high quality herbage for grazing and subsequently milk production. By accurately estimating herbage mass and composition, targeted nitrogen fertiliser application strategies can be deployed to improve localised regions in a herbage field, effectively reducing the negative impacts of over-fertilization on biodiversity and the environment. In this context, deep learning algorithms offer a tempting alternative to the usual means of sward composition estimation, which involves the destructive process of cutting a sample from the herbage field and sorting by hand all plant species in the herbage. The process is labour intensive and time consuming and so not utilised by farmers. Deep learning has been successfully applied in this context on images collected by high-resolution cameras on the ground. Moving the deep learning solution to drone imaging, however, has the potential to further improve the herbage mass yield and composition estimation task by extending the ground-level estimation to the large surfaces occupied by fields/paddocks. Drone images come at the cost of lower resolution views of the fields taken from a high altitude and requires further herbage ground-truth collection from the large surfaces covered by drone images. This paper proposes to transfer knowledge learned on ground-level images to raw drone images in an unsupervised manner. To do so, we use unpaired image style translation to enhance the resolution of drone images by a factor of eight and modify them to appear closer to their ground-level counterparts. We then ... ~\url{www.github.com/PaulAlbert31/Clover_SSL}. △ Less

Submitted 18 April, 2022; originally announced April 2022.

Comments: 11 pages, 5 figures. Accepted at the Agriculture-Vision CVPR 2022 Workshop

Applications of Random Algebraic Constructions to Hardness of Approximation

Authors: Boris Bukh, Karthik C. S., Bhargav Narayanan

Abstract: In this paper, we show how one may (efficiently) construct two types of extremal combinatorial objects whose existence was previously conjectural. (*) Panchromatic Graphs: For fixed integer k, a k-panchromatic graph is, roughly speaking, a balanced bipartite graph with one partition class equipartitioned into k colour classes in which the common neighbourhoods of panchromatic k-sets of vertices… ▽ More In this paper, we show how one may (efficiently) construct two types of extremal combinatorial objects whose existence was previously conjectural. (*) Panchromatic Graphs: For fixed integer k, a k-panchromatic graph is, roughly speaking, a balanced bipartite graph with one partition class equipartitioned into k colour classes in which the common neighbourhoods of panchromatic k-sets of vertices are much larger than those of k-sets that repeat a colour. The question of their existence was raised by Karthik and Manurangsi [Combinatorica 2020]. (*) Threshold Graphs: For fixed integer k, a k-threshold graph is, roughly speaking, a balanced bipartite graph in which the common neighbourhoods of k-sets of vertices on one side are much larger than those of (k+1)-sets. The question of their existence was raised by Lin [JACM 2018]. As applications of our constructions, we show the following conditional time lower bounds on the parameterized set intersection problem where, given a collection of n sets over universe [n] and a parameter k, the goal is to find k sets with the largest intersection. (*) Assuming ETH, for any computable function F, no $n^{o(k)}$-time algorithm can approximate the parameterized set intersection problem up to factor F(k). This improves considerably on the previously best-known result under ETH due to Lin [JACM 2018], who ruled out any $n^{o(\sqrt{k})}$ time approximation algorithm for this problem. (*) Assuming SETH, for every $\varepsilon>0$ and any computable function F, no $n^{k-\varepsilon}$-time algorithm can approximate the parameterized set intersection problem up to factor F(k). No result of comparable strength was previously known under SETH, even for solving this problem exactly. △ Less

Submitted 9 November, 2021; originally announced November 2021.

Comments: Abstract in metadata shortened to meet arxiv requirements

Semi-supervised dry herbage mass estimation using automatic data and synthetic images

Authors: Paul Albert, Mohamed Saadeldin, Badri Narayanan, Brian Mac Namee, Deirdre Hennessy, Aisling O'Connor, Noel O'Connor, Kevin McGuinness

Abstract: Monitoring species-specific dry herbage biomass is an important aspect of pasture-based milk production systems. Being aware of the herbage biomass in the field enables farmers to manage surpluses and deficits in herbage supply, as well as using targeted nitrogen fertilization when necessary. Deep learning for computer vision is a powerful tool in this context as it can accurately estimate the dry… ▽ More Monitoring species-specific dry herbage biomass is an important aspect of pasture-based milk production systems. Being aware of the herbage biomass in the field enables farmers to manage surpluses and deficits in herbage supply, as well as using targeted nitrogen fertilization when necessary. Deep learning for computer vision is a powerful tool in this context as it can accurately estimate the dry biomass of a herbage parcel using images of the grass canopy taken using a portable device. However, the performance of deep learning comes at the cost of an extensive, and in this case destructive, data gathering process. Since accurate species-specific biomass estimation is labor intensive and destructive for the herbage parcel, we propose in this paper to study low supervision approaches to dry biomass estimation using computer vision. Our contributions include: a synthetic data generation algorithm to generate data for a herbage height aware semantic segmentation task, an automatic process to label data using semantic segmentation maps, and a robust regression network trained to predict dry biomass using approximate biomass labels and a small trusted dataset with gold standard labels. We design our approach on a herbage mass estimation dataset collected in Ireland and also report state-of-the-art results on the publicly released Grass-Clover biomass estimation dataset from Denmark. Our code is available at https://git.io/J0L2a △ Less

Submitted 26 October, 2021; originally announced October 2021.

Comments: Published at CVPPA 2021, ICCVW 2021

Extracting Pasture Phenotype and Biomass Percentages using Weakly Supervised Multi-target Deep Learning on a Small Dataset

Authors: Badri Narayanan, Mohamed Saadeldin, Paul Albert, Kevin McGuinness, Brian Mac Namee

Abstract: The dairy industry uses clover and grass as fodder for cows. Accurate estimation of grass and clover biomass yield enables smart decisions in optimizing fertilization and seeding density, resulting in increased productivity and positive environmental impact. Grass and clover are usually planted together, since clover is a nitrogen-fixing plant that brings nutrients to the soil. Adjusting the right… ▽ More The dairy industry uses clover and grass as fodder for cows. Accurate estimation of grass and clover biomass yield enables smart decisions in optimizing fertilization and seeding density, resulting in increased productivity and positive environmental impact. Grass and clover are usually planted together, since clover is a nitrogen-fixing plant that brings nutrients to the soil. Adjusting the right percentages of clover and grass in a field reduces the need for external fertilization. Existing approaches for estimating the grass-clover composition of a field are expensive and time consuming - random samples of the pasture are clipped and then the components are physically separated to weigh and calculate percentages of dry grass, clover and weeds in each sample. There is growing interest in developing novel deep learning based approaches to non-destructively extract pasture phenotype indicators and biomass yield predictions of different plant species from agricultural imagery collected from the field. Providing these indicators and predictions from images alone remains a significant challenge. Heavy occlusions in the dense mixture of grass, clover and weeds make it difficult to estimate each component accurately. Moreover, although supervised deep learning models perform well with large datasets, it is tedious to acquire large and diverse collections of field images with precise ground truth for different biomass yields. In this paper, we demonstrate that applying data augmentation and transfer learning is effective in predicting multi-target biomass percentages of different plant species, even with a small training dataset. The scheme proposed in this paper used a training set of only 261 images and provided predictions of biomass percentages of grass, clover, white clover, red clover, and weeds with mean absolute error of 6.77%, 6.92%, 6.21%, 6.89%, and 4.80% respectively. △ Less

Submitted 8 January, 2021; originally announced January 2021.

Journal ref: Irish Machine Vision and Image Processing Conference (2020) 21-28

BLAST: Bridging Length/time scales via Atomistic Simulation Toolkit

Authors: Henry Chan, Badri Narayanan, Mathew Cherukara, Troy D. Loeffler, Michael G. Sternberg, Anthony Avarca, Subramanian K. R. S. Sankaranarayanan

Abstract: The ever-increasing power of supercomputers coupled with highly scalable simulation codes have made molecular dynamics an indispensable tool in applications ranging from predictive modeling of materials to computational design and discovery of new materials for a broad range of applications. Multi-fidelity scale bridging between the various flavors of molecular dynamics i.e. ab-initio, classical a… ▽ More The ever-increasing power of supercomputers coupled with highly scalable simulation codes have made molecular dynamics an indispensable tool in applications ranging from predictive modeling of materials to computational design and discovery of new materials for a broad range of applications. Multi-fidelity scale bridging between the various flavors of molecular dynamics i.e. ab-initio, classical and coarse-grained models has remained a long-standing challenge. Here, we introduce our framework BLAST (Bridging Length/time scales via Atomistic Simulation Toolkit) that leverages machine learning principles to address this challenge. BLAST is a multi-fidelity scale bridging framework that provide users with the capabilities to train and develop their own classical atomistic and coarse-grained interatomic potentials (force fields) for molecular simulations. BLAST is designed to address several long-standing problems in the molecular simulations community, such as unintended misuse of existing force fields due to knowledge gap between developers and users, bottlenecks in traditional force field development approaches, and other issues relating to the accuracy, efficiency, and transferability of force fields. Here, we discuss several important aspects in force field development and highlight features in BLAST that enable its functionalities and ease of use. △ Less

Submitted 21 February, 2020; originally announced February 2020.

Understanding Deep Neural Network Predictions for Medical Imaging Applications

Authors: Barath Narayanan Narayanan, Manawaduge Supun De Silva, Russell C. Hardie, Nathan K. Kueterman, Redha Ali

Abstract: Computer-aided detection has been a research area attracting great interest in the past decade. Machine learning algorithms have been utilized extensively for this application as they provide a valuable second opinion to the doctors. Despite several machine learning models being available for medical imaging applications, not many have been implemented in the real-world due to the uninterpretable… ▽ More Computer-aided detection has been a research area attracting great interest in the past decade. Machine learning algorithms have been utilized extensively for this application as they provide a valuable second opinion to the doctors. Despite several machine learning models being available for medical imaging applications, not many have been implemented in the real-world due to the uninterpretable nature of the decisions made by the network. In this paper, we investigate the results provided by deep neural networks for the detection of malaria, diabetic retinopathy, brain tumor, and tuberculosis in different imaging modalities. We visualize the class activation mappings for all the applications in order to enhance the understanding of these networks. This type of visualization, along with the corresponding network performance metrics, would aid the data science experts in better understanding of their models as well as assisting doctors in their decision-making process. △ Less

Submitted 19 December, 2019; originally announced December 2019.

Comments: 20 pages, 28 Figures and 9 Tables

Thresholds versus fractional expectation-thresholds

Authors: Keith Frankston, Jeff Kahn, Bhargav Narayanan, Jinyoung Park

Abstract: Proving a conjecture of Talagrand, a fractional version of the 'expectation-threshold' conjecture of Kalai and the second author, we show for any increasing family $F$ on a finite set $X$ that $p_c (F) =O( q_f (F) \log \ell(F))$, where $p_c(F)$ and $q_f(F)$ are the threshold and 'fractional expectation-threshold' of $F$, and $\ell(F)$ is the largest size of a minimal member of $F$. This easily imp… ▽ More Proving a conjecture of Talagrand, a fractional version of the 'expectation-threshold' conjecture of Kalai and the second author, we show for any increasing family $F$ on a finite set $X$ that $p_c (F) =O( q_f (F) \log \ell(F))$, where $p_c(F)$ and $q_f(F)$ are the threshold and 'fractional expectation-threshold' of $F$, and $\ell(F)$ is the largest size of a minimal member of $F$. This easily implies several heretofore difficult results and conjectures in probabilistic combinatorics, including thresholds for perfect hypergraph matchings (Johansson--Kahn--Vu), bounded-degree spanning trees (Montgomery), and bounded-degree spanning graphs (new). We also resolve (and vastly extend) the 'axial' version of the random multi-dimensional assignment problem (earlier considered by Martin--Mézard--Rivoire and Frieze--Sorkin). Our approach builds on a recent breakthrough of Alweiss, Lovett, Wu and Zhang on the Erdős--Rado 'Sunflower Conjecture'. △ Less

Submitted 10 December, 2019; v1 submitted 29 October, 2019; originally announced October 2019.

Comments: 16 pages, submitted, now includes some discussion of applications

Disproportionate division

Authors: Logan Crew, Bhargav Narayanan, Sophie Spirkl

Abstract: We study the disproportionate version of the classical cake-cutting problem: how efficiently can we divide a cake, here $[0,1]$, among $n$ agents with different demands $α_1, α_2, \dots, α_n$ summing to $1$? When all the agents have equal demands of $α_1 = α_2 = \dots = α_n = 1/n$, it is well-known that there exists a fair division with $n-1$ cuts, and this is optimal. For arbitrary demands on the… ▽ More We study the disproportionate version of the classical cake-cutting problem: how efficiently can we divide a cake, here $[0,1]$, among $n$ agents with different demands $α_1, α_2, \dots, α_n$ summing to $1$? When all the agents have equal demands of $α_1 = α_2 = \dots = α_n = 1/n$, it is well-known that there exists a fair division with $n-1$ cuts, and this is optimal. For arbitrary demands on the other hand, folklore arguments from algebraic topology show that $O(n\log n)$ cuts suffice, and this has been the state of the art for decades. Here, we improve the state of affairs in two ways: we prove that disproportionate division may always be achieved with $3n-4$ cuts, and give an effective combinatorial procedure to construct such a division. We also offer a topological conjecture that implies that $2n-2$ cuts suffice in general, which would be optimal. △ Less

Submitted 16 September, 2019; originally announced September 2019.

Comments: 8 pages, submitted

MSC Class: 05D05 (Primary); 91B32 (Secondary)

Coppersmith's lattices and "focus groups": an attack on small-exponent RSA

Authors: Stephen D. Miller, Bhargav Narayanan, Ramarathnam Venkatesan

Abstract: We present a principled technique for reducing the lattice and matrix size in some applications of Coppersmith's lattice method for finding roots of modular polynomial equations. Motivated by ideas from machine learning, it relies on extrapolating patterns from the actual behavior of Coppersmith's attack for smaller parameter sizes, which can be thought of as "focus group" testing. When applied to… ▽ More We present a principled technique for reducing the lattice and matrix size in some applications of Coppersmith's lattice method for finding roots of modular polynomial equations. Motivated by ideas from machine learning, it relies on extrapolating patterns from the actual behavior of Coppersmith's attack for smaller parameter sizes, which can be thought of as "focus group" testing. When applied to the small-exponent RSA problem, our technique reduces lattice dimensions and consequently running times, and hence can be applied to a wider range of exponents. Moreover, in many difficult examples our attack is not only faster but also more successful in recovering the RSA secret key. We include a discussion of subtleties concerning whether or not existing metrics (such as enabling condition bounds) are decisive in predicting the true efficacy of attacks based on Coppersmith's method. Finally, indications are given which suggest certain lattice basis reduction algorithms (such as Nguyen-Stehlé's L2) may be particularly well-suited for Coppersmith's method. △ Less

Submitted 16 December, 2020; v1 submitted 30 August, 2017; originally announced August 2017.

Comments: 21 pages, 5 figures

MSC Class: 11

Catching a fast robber on the grid

Authors: Paul Balister, Béla Bollobás, Bhargav Narayanan, Amy Shaw

Abstract: We study the problem of cops and robbers on the grid where the robber is allowed to move faster than the cops. It is well known that two cops are necessary and sufficient to catch the robber on any finite grid when the robber has unit speed. Here, we prove that when the speed of the robber is a sufficiently large constant, the number of cops needed to catch the robber on an $n \times n$ grid is… ▽ More We study the problem of cops and robbers on the grid where the robber is allowed to move faster than the cops. It is well known that two cops are necessary and sufficient to catch the robber on any finite grid when the robber has unit speed. Here, we prove that when the speed of the robber is a sufficiently large constant, the number of cops needed to catch the robber on an $n \times n$ grid is $\exp(Ω(\log n / \log \log n))$. △ Less

Submitted 5 June, 2017; v1 submitted 4 September, 2016; originally announced September 2016.

Comments: 15 pages, Journal of Combinatorial Theory, Series A

MSC Class: 05C57 (Primary) 05C35 (Secondary)

Fast GPGPU Data Rearrangement Kernels using CUDA

Authors: Michael Bader, Hans-Joachim Bungartz, Dheevatsa Mudigere, Srihari Narasimhan, Babu Narayanan

Abstract: Many high performance-computing algorithms are bandwidth limited, hence the need for optimal data rearrangement kernels as well as their easy integration into the rest of the application. In this work, we have built a CUDA library of fast kernels for a set of data rearrangement operations. In particular, we have built generic kernels for rearranging m dimensional data into n dimensions, including… ▽ More Many high performance-computing algorithms are bandwidth limited, hence the need for optimal data rearrangement kernels as well as their easy integration into the rest of the application. In this work, we have built a CUDA library of fast kernels for a set of data rearrangement operations. In particular, we have built generic kernels for rearranging m dimensional data into n dimensions, including Permute, Reorder, Interlace/De-interlace, etc. We have also built kernels for generic Stencil computations on a two-dimensional data using templates and functors that allow application developers to rapidly build customized high performance kernels. All the kernels built achieve or surpass best-known performance in terms of bandwidth utilization. △ Less

Submitted 15 November, 2010; originally announced November 2010.

Fast Histograms using Adaptive CUDA Streams

Authors: Sisir Koppaka, Dheevatsa Mudigere, Srihari Narasimhan, Babu Narayanan

Abstract: Histograms are widely used in medical imaging, network intrusion detection, packet analysis and other stream-based high throughput applications. However, while porting such software stacks to the GPU, the computation of the histogram is a typical bottleneck primarily due to the large impact on kernel speed by atomic operations. In this work, we propose a stream-based model implemented in CUDA, usi… ▽ More Histograms are widely used in medical imaging, network intrusion detection, packet analysis and other stream-based high throughput applications. However, while porting such software stacks to the GPU, the computation of the histogram is a typical bottleneck primarily due to the large impact on kernel speed by atomic operations. In this work, we propose a stream-based model implemented in CUDA, using a new adaptive kernel that can be optimized based on latency hidden CPU compute. We also explore the tradeoffs of using the new kernel vis-à-vis the stock NVIDIA SDK kernel, and discuss an intelligent kernel switching method for the stream based on a degeneracy criterion that is adaptively computed from the input stream. △ Less

Submitted 31 October, 2010; originally announced November 2010.

Comments: 5 pages, 5 figures, 4 tables, to appear in Student Research Symposium, High Performance Computing 2010, Goa, India (www.hipc.org)