* Mündler et al. (2024) Niels Mündler, Jingxuan He, Slobodan Jenko, and Martin Vechev. 2024.  Self-contradictory Hallucinations of Large Language Models: Evaluation, Detection and Mitigation.  In _Proceedings of the 12th International Conference on Learning Representations_ , Vienna, Austria.
  * OpenAI (2022) OpenAI. 2022.  Introducing ChatGPT.  _OpenAI blog_.
  * Oquab et al. (2024) Maxime Oquab, Timothée Darcet, Théo Moutakanni, Huy V. Vo, Marc Szafraniec, Vasil Khalidov, Pierre Fernandez, Daniel HAZIZA, Francisco Massa, Alaaeldin El-Nouby, et al. 2024.  DINOv2: Learning Robust Visual Features without Supervision.  _Transactions on Machine Learning Research_.
  * Pacchiardi et al. (2024) Lorenzo Pacchiardi, Alex James Chan, Sören Mindermann, Ilan Moscovitz, Alexa Yue Pan, Yarin Gal, Owain Evans, and Jan M. Brauner. 2024.  How to Catch an AI Liar: Lie Detection in Black-Box LLMs by Asking Unrelated Questions.  In _Proceedings of the 12th International Conference on Learning Representations_ , Vienna, Austria.
  * Park et al. (2024) Jeongeun Park, Seungwon Lim, Joonhyung Lee, Sangbeom Park, Minsuk Chang, Youngjae Yu, and Sungjoon Choi. 2024.  CLARA: Classifying and Disambiguating User Commands for Reliable Interactive Robotic Agents.  _IEEE Robotics and Automation Letters_ , 9(2):1059–1066.
  * Park et al. (2023) Joon Sung Park, Joseph O’Brien, Carrie Jun Cai, Meredith Ringel Morris, Percy Liang, and Michael S. Bernstein. 2023.  Generative Agents: Interactive Simulacra of Human Behavior.  In _Proceedings of the 36th Annual ACM Symposium on User Interface Software and Technology_ , New York, NY, USA. Association for Computing Machinery.
  * Peng et al. (2023) Baolin Peng, Michel Galley, Pengcheng He, Hao Cheng, Yujia Xie, Yu Hu, Qiuyuan Huang, Lars Liden, Zhou Yu, Weizhu Chen, and Jianfeng Gao. 2023.  Check Your Facts and Try Again: Improving Large Language Models with External Knowledge and Automated Feedback.  _arXiv preprint arXiv:2302.12813_.
  * Puig et al. (2018) Xavier Puig, Kevin Ra, Marko Boben, Jiaman Li, Tingwu Wang, Sanja Fidler, and Antonio Torralba. 2018.  Virtualhome: Simulating household activities via programs.  In _Proceedings of the 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 8494–8502, Salt Lake City, UT, USA. Institute of Electrical and Electronics Engineers.
  * Puthumanaillam et al. (2024) Gokul Puthumanaillam, Manav Vora, Pranay Thangeda, and Melkior Ornik. 2024.  A Moral Imperative: The Need for Continual Superalignment of Large Language Models.  _arXiv preprint arXiv:2403.14683_.
  * Qian et al. (2024) Tianwen Qian, Jingjing Chen, Linhai Zhuo, Yang Jiao, and Yu-Gang Jiang. 2024.  NuScenes-QA: A Multi-modal Visual Question Answering Benchmark for Autonomous Driving Scenario.  _arXiv preprint arXiv:2305.14836_.
  * Qiu et al. (2023) Huachuan Qiu, Shuai Zhang, Anqi Li, Hongliang He, and Zhenzhong Lan. 2023.  Latent Jailbreak: A Benchmark for Evaluating Text Safety and Output Robustness of Large Language Models.  _arXiv preprint arXiv:2307.08487_.
  * Quach et al. (2024) Victor Quach, Adam Fisch, Tal Schuster, Adam Yala, Jae Ho Sohn, Tommi S. Jaakkola, and Regina Barzilay. 2024.  Conformal Language Modeling.  In _Proceedings of the 12th International Conference on Learning Representations_ , Vienna, Austria.
  * Radford et al. (2021) Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. 2021.  Learning Transferable Visual Models From Natural Language Supervision.  In _Proceedings of the 38th International Conference on Machine Learning_ , volume 139 of _Proceedings of Machine Learning Research_ , pages 8748–8763. PMLR.
  * Radford et al. (2019) Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. 2019.  Language models are unsupervised multitask learners.  _OpenAI blog_.
  * Rajpurkar et al. (2016) Pranav Rajpurkar, Jian Zhang, Konstantin Lopyrev, and Percy Liang. 2016.  SQuAD: 100,000+ Questions for Machine Comprehension of Text.  In _Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing_ , pages 2383–2392, Austin, TX, USA. Association for Computational Linguistics.
  * Rawte et al. (2023) Vipula Rawte, Amit Sheth, and Amitava Das. 2023.  A Survey of Hallucination in Large Foundation Models.  _arXiv preprint arXiv:2309.05922_.
  * Ren et al. (2023) Allen Z. Ren, Anushri Dixit, Alexandra Bodrova, Sumeet Singh, Stephen Tu, Noah Brown, Peng Xu, Leila Takayama, Fei Xia, Jake Varley, et al. 2023.  Robots That Ask For Help: Uncertainty Alignment for Large Language Model Planners.  In _Proceedings of The 7th Conference on Robot Learning_ , volume 229 of _Proceedings of Machine Learning Research_ , pages 661–682, Atlanta, GA, USA. PMLR.
  * Rohrbach et al. (2018) Anna Rohrbach, Lisa Anne Hendricks, Kaylee Burns, Trevor Darrell, and Kate Saenko. 2018.  Object Hallucination in Image Captioning.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 4035–4045, Brussels, Belgium. Association for Computational Linguistics.
  * Schramowski et al. (2023) Patrick Schramowski, Manuel Brack, Björn Deiseroth, and Kristian Kersting. 2023.  Safe Latent Diffusion: Mitigating Inappropriate Degeneration in Diffusion Models.  In _Proceedings of the 2023 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 22522–22531, Vancouver, Canada. Institute of Electrical and Electronics Engineers.
  * Schreiber et al. (2023) Andre Schreiber, Tianchen Ji, D. Livingston McPherson, and Katherine Driggs-Campbell. 2023.  An Attentional Recurrent Neural Network for Occlusion-Aware Proactive Anomaly Detection in Field Robot Navigation.  In _Proceedings of the 2023 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , pages 8038–8045, Detroit, MI, USA. Institute of Electrical and Electronics Engineers.
  * Schwenk et al. (2022) Dustin Schwenk, Apoorv Khandelwal, Christopher Clark, Kenneth Marino, and Roozbeh Mottaghi. 2022.  A-OKVQA: A Benchmark for Visual Question Answering Using World Knowledge.  In _Proceedings of the 17th European Conference on Computer Vision (ECCV)_ , pages 146–162, Tel Aviv, Israel. Springer Nature Switzerland.
  * Shafer and Vovk (2008) Glenn Shafer and Vladimir Vovk. 2008.  A Tutorial on Conformal Prediction.  _Journal of Machine Learning Research_ , 9(12):371–421.
  * Shah et al. (2023) Dhruv Shah, Błażej Osiński, Brian Ichter, and Sergey Levine. 2023.  LM-Nav: Robotic Navigation with Large Pre-Trained Models of Language, Vision, and Action.  In _Proceedings of The 6th Conference on Robot Learning_ , volume 205 of _Proceedings of Machine Learning Research_ , pages 492–504, Atlanta, GA, USA. PMLR.
  * Shinn et al. (2023) Noah Shinn, Federico Cassano, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao. 2023.  Reflexion: language agents with verbal reinforcement learning.  In _Proceedings of the 2023 Conference on Neural Information Processing Systems_ , pages 8634–8652, New Orleans, LA, USA. Curran Associates, Inc.
  * Shridhar et al. (2020) Mohit Shridhar, Jesse Thomason, Daniel Gordon, Yonatan Bisk, Winson Han, Roozbeh Mottaghi, Luke Zettlemoyer, and Dieter Fox. 2020.  ALFRED: A Benchmark for Interpreting Grounded Instructions for Everyday Tasks.  In _Proceedings of the 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 10737–10746. Institute of Electrical and Electronics Engineers.
  * Shridhar et al. (2021) Mohit Shridhar, Xingdi Yuan, Marc-Alexandre Cote, Yonatan Bisk, Adam Trischler, and Matthew Hausknecht. 2021.  ALFWorld: Aligning Text and Embodied Environments for Interactive Learning.  In _Proceedings of the 9th International Conference on Learning Representations_.
  * Sima et al. (2023) Chonghao Sima, Katrin Renz, Kashyap Chitta, Li Chen, Hanxue Zhang, Chengen Xie, Ping Luo, Andreas Geiger, and Hongyang Li. 2023.  DriveLM: Driving with Graph Visual Question Answering.  _arXiv preprint arXiv:2312.14150_.
  * Singer and Cohen (2021) Gonen Singer and Yuval Cohen. 2021.  A framework for smart control using machine-learning modeling for processes with closed-loop control in Industry 4.0.  _Engineering Applications of Artificial Intelligence_ , 102:104236.
  * Singh et al. (2023) Ishika Singh, Valts Blukis, Arsalan Mousavian, Ankit Goyal, Danfei Xu, Jonathan Tremblay, Dieter Fox, Jesse Thomason, and Animesh Garg. 2023.  ProgPrompt: Generating Situated Robot Task Plans using Large Language Models.  In _Proceedings of the 2023 IEEE International Conference on Robotics and Automation (ICRA)_ , pages 11523–11530, London, England. Institute of Electrical and Electronics Engineers.
  * Song et al. (2023) Da Song, Xuan Xie, Jiayang Song, Derui Zhu, Yuheng Huang, Felix Juefei-Xu, and Lei Ma. 2023.  LUNA: A Model-Based Universal Analysis Framework for Large Language Models.  _arXiv preprint arXiv:2310.14211_.
  * Soori et al. (2023) Mohsen Soori, Behrooz Arezoo, and Roza Dastres. 2023.  Artificial intelligence, machine learning and deep learning in advanced robotics, a review.  _Cognitive Robotics_ , 3:54–70.
  * Srivastava et al. (2023) Aarohi Srivastava, Abhinav Rastogi, Abhishek Rao, Abu Awal Md Shoeb, Abubakar Abid, Adam Fisch, Adam R. Brown, Adam Santoro, Aditya Gupta, Adrià Garriga-Alonso, et al. 2023.  Beyond the Imitation Game: Quantifying and extrapolating the capabilities of language models.  _Transactions on Machine Learning Research_.
  * Suganuma and Yoneda (2022) Naoki Suganuma and Keisuke Yoneda. 2022.  Current Status and Issues of Traffic Light Recognition Technology in Autonomous Driving System.  _IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences_ , E105.A(5):763–769.
  * Thorne et al. (2018) James Thorne, Andreas Vlachos, Christos Christodoulopoulos, and Arpit Mittal. 2018.  FEVER: a Large-scale Dataset for Fact Extraction and VERification.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers)_ , pages 809–819, New Orleans, Louisiana. Association for Computational Linguistics.
  * Touvron et al. (2023a) Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. 2023a.  LLaMA: Open and Efficient Foundation Language Models.  _arXiv preprint arXiv:2302.13971_.
  * Touvron et al. (2023b) Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. 2023b.  Llama 2: Open Foundation and Fine-Tuned Chat Models.  _arXiv preprint arXiv:2307.09288_.
  * Trivedi et al. (2017) Priyansh Trivedi, Gaurav Maheshwari, Mohnish Dubey, and Jens Lehmann. 2017.  LC-QuAD: A Corpus for Complex Question Answering over Knowledge Graphs.  In _Proceedings of the 2017 International Semantic Web Conference_ , pages 210–218, Vienna, Austria. Springer International Publishing.
  * Varshney et al. (2023) Neeraj Varshney, Wenlin Yao, Hongming Zhang, Jianshu Chen, and Dong Yu. 2023.  A Stitch in Time Saves Nine: Detecting and Mitigating Hallucinations of LLMs by Validating Low-Confidence Generation.  _arXiv preprint arXiv:2307.03987_.
  * Wang et al. (2023a) Boxin Wang, Weixin Chen, Hengzhi Pei, Chulin Xie, Mintong Kang, Chenhui Zhang, Chejian Xu, Zidi Xiong, Ritik Dutta, Rylan Schaeffer, et al. 2023a.  DecodingTrust: A Comprehensive Assessment of Trustworthiness in GPT Models.  In _Proceedings of the 37th Conference on Neural Information Processing Systems Datasets and Benchmarks Track_ , New Orleans, LA, USA.
  * Wang et al. (2023b) Guanzhi Wang, Yuqi Xie, Yunfan Jiang, Ajay Mandlekar, Chaowei Xiao, Yuke Zhu, Linxi Fan, and Anima Anandkumar. 2023b.  Voyager: An Open-Ended Embodied Agent with Large Language Models.  _arXiv preprint arXiv:2305.16291_.
  * Wang et al. (2024) Jun Wang, Jiaming Tong, Kaiyuan Tan, Yevgeniy Vorobeychik, and Yiannis Kantaros. 2024.  Conformal Temporal Logic Planning using Large Language Models.  _arXiv preprint arXiv:2309.10092_.
  * Wegener et al. (2008) Axel Wegener, Michał Piórkowski, Maxim Raya, Horst Hellbrück, Stefan Fischer, and Jean-Pierre Hubaux. 2008.  TraCI: an interface for coupling road traffic and network simulators.  In _Proceedings of the 11th Communications and Networking Simulation Symposium_ , page 155–163, New York, NY, USA. Association for Computing Machinery.
  * Wei et al. (2022) Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed Chi, Quoc V Le, and Denny Zhou. 2022.  Chain-of-Thought Prompting Elicits Reasoning in Large Language Models.  In _Proceedings of the 2022 Conference on Neural Information Processing Systems_ , pages 24824–24837, New Orleans, LA, USA. Curran Associates, Inc.
  * Wen et al. (2024) Licheng Wen, Daocheng Fu, Xin Li, Xinyu Cai, Tao MA, Pinlong Cai, Min Dou, Botian Shi, Liang He, and Yu Qiao. 2024.  DiLu: A Knowledge-Driven Approach to Autonomous Driving with Large Language Models.  In _Proceedings of the 12th International Conference on Learning Representations_ , Vienna, Austria.
  * Wen et al. (2023) Licheng Wen, Xuemeng Yang, Daocheng Fu, Xiaofeng Wang, Pinlong Cai, Xin Li, Tao Ma, Yingxuan Li, Linran Xu, Dengke Shang, et al. 2023.  On the Road with GPT-4V(ision): Early Explorations of Visual-Language Model on Autonomous Driving.  _arXiv preprint arXiv:2311.05332_.
  * Williams (1992) Ronald J. Williams. 1992.  Simple statistical gradient-following algorithms for connectionist reinforcement learning.  _Machine Learning_ , 8(3–4):229–256.
  * Wu et al. (2023a) Dongming Wu, Wencheng Han, Tiancai Wang, Xingping Dong, Xiangyu Zhang, and Jianbing Shen. 2023a.  Referring Multi-Object Tracking.  In _Proceedings of the 2023 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 14633–14642, Vancouver, Canada. Institute of Electrical and Electronics Engineers.
  * Wu et al. (2023b) Dongming Wu, Wencheng Han, Tiancai Wang, Yingfei Liu, Xiangyu Zhang, and Jianbing Shen. 2023b.  Language Prompt for Autonomous Driving.  _arXiv preprint arXiv:2309.04379_.
  * Xiong et al. (2024) Miao Xiong, Zhiyuan Hu, Xinyang Lu, YIFEI LI, Jie Fu, Junxian He, and Bryan Hooi. 2024.  Can LLMs Express Their Uncertainty? An Empirical Evaluation of Confidence Elicitation in LLMs.  In _Proceedings of the 12th International Conference on Learning Representations_ , Vienna, Austria.
  * Xu et al. (2024) Zhenhua Xu, Yujia Zhang, Enze Xie, Zhen Zhao, Yong Guo, Kwan-Yee. K. Wong, Zhenguo Li, and Hengshuang Zhao. 2024.  DriveGPT4: Interpretable End-to-end Autonomous Driving via Large Language Model.  _arXiv preprint arXiv:2310.01412_.
  * Yang et al. (2024) Jingfeng Yang, Hongye Jin, Ruixiang Tang, Xiaotian Han, Qizhang Feng, Haoming Jiang, Shaochen Zhong, Bing Yin, and Xia Hu. 2024.  Harnessing the Power of LLMs in Practice: A Survey on ChatGPT and Beyond.  _ACM Transactions on Knowledge Discovery from Data_.
  * Yang et al. (2023a) Yuqing Yang, Ethan Chern, Xipeng Qiu, Graham Neubig, and Pengfei Liu. 2023a.  Alignment for Honesty.  _arXiv preprint arXiv:2312.07000_.
  * Yang et al. (2023b) Zhenjie Yang, Xiaosong Jia, Hongyang Li, and Junchi Yan. 2023b.  LLM4Drive: A Survey of Large Language Models for Autonomous Driving.  _arXiv preprint arXiv:2311.01043_.
  * Yang et al. (2018) Zhilin Yang, Peng Qi, Saizheng Zhang, Yoshua Bengio, William Cohen, Ruslan Salakhutdinov, and Christopher D. Manning. 2018.  HotpotQA: A Dataset for Diverse, Explainable Multi-hop Question Answering.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 2369–2380, Brussels, Belgium. Association for Computational Linguistics.
  * Yao et al. (2023a) Jia-Yu Yao, Kun-Peng Ning, Zhen-Hui Liu, Mu-Nan Ning, and Li Yuan. 2023a.  LLM Lies: Hallucinations are not Bugs, but Features as Adversarial Examples.  _arXiv preprint arXiv:2310.01469_.
  * Yao et al. (2023b) Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik R Narasimhan, and Yuan Cao. 2023b.  ReAct: Synergizing Reasoning and Acting in Language Models.  In _Proceedings of the 11th International Conference on Learning Representations_ , Kigali, Rwanda.
  * Ye et al. (2023) Hongbin Ye, Tong Liu, Aijia Zhang, Wei Hua, and Weiqiang Jia. 2023.  Cognitive Mirage: A Review of Hallucinations in Large Language Models.  _arXiv preprint arXiv:2309.06794_.
  * Yu et al. (2023) Xiaodong Yu, Hao Cheng, Xiaodong Liu, Dan Roth, and Jianfeng Gao. 2023.  Automatic Hallucination Assessment for Aligned Large Language Models via Transferable Adversarial Attacks.  _arXiv preprint arXiv:2310.12516_.
  * Yuan et al. (2021) Weizhe Yuan, Graham Neubig, and Pengfei Liu. 2021.  BARTScore: Evaluating Generated Text as Text Generation.  In _Proceedings of the 2021 Conference on Neural Information Processing Systems_ , pages 27263–27277. Curran Associates, Inc.
  * Zeng et al. (2021) Andy Zeng, Pete Florence, Jonathan Tompson, Stefan Welker, Jonathan Chien, Maria Attarian, Travis Armstrong, Ivan Krasin, Dan Duong, Vikas Sindhwani, and Johnny Lee. 2021.  Transporter Networks: Rearranging the Visual World for Robotic Manipulation.  In _Proceedings of the 4th Conference on Robot Learning_ , volume 155 of _Proceedings of Machine Learning Research_ , pages 726–747. PMLR.
  * Zeng et al. (2023) Fanlong Zeng, Wensheng Gan, Yongheng Wang, Ning Liu, and Philip S. Yu. 2023.  Large Language Models for Robotics: A Survey.  _arXiv preprint arXiv:2311.07226_.
  * Zha et al. (2023) Yuheng Zha, Yichi Yang, Ruichen Li, and Zhiting Hu. 2023.  AlignScore: Evaluating Factual Consistency with A Unified Alignment Function.  In _Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 11328–11348, Toronto, Canada. Association for Computational Linguistics.
  * Zhang et al. (2023a) Ceng Zhang, Junxin Chen, Jiatong Li, Yanhong Peng, and Zebing Mao. 2023a.  Large language models for human-robot interaction: A review.  _Biomimetic Intelligence and Robotics_ , 3(4):100131.
  * Zhang et al. (2023b) Muru Zhang, Ofir Press, William Merrill, Alisa Liu, and Noah A. Smith. 2023b.  How Language Model Hallucinations Can Snowball.  _arXiv preprint arXiv:2305.13534_.
  * Zhang et al. (2023c) Shuo Zhang, Liangming Pan, Junzhou Zhao, and William Yang Wang. 2023c.  The Knowledge Alignment Problem: Bridging Human and External Knowledge for Large Language Models.  _arXiv preprint arXiv:2305.13669_.
  * Zhang et al. (2020) Tianyi Zhang, Varsha Kishore, Felix Wu, Kilian Q. Weinberger, and Yoav Artzi. 2020.  BERTScore: Evaluating Text Generation with BERT.  In _Proceedings of the 8th International Conference on Learning Representations_.
  * Zhang et al. (2023d) Yue Zhang, Yafu Li, Leyang Cui, Deng Cai, Lemao Liu, Tingchen Fu, Xinting Huang, Enbo Zhao, Yu Zhang, Yulong Chen, et al. 2023d.  Siren’s Song in the AI Ocean: A Survey on Hallucination in Large Language Models.  _arXiv preprint arXiv:2309.01219_.
  * Zhao et al. (2023) Wayne Xin Zhao, Kun Zhou, Junyi Li, Tianyi Tang, Xiaolei Wang, Yupeng Hou, Yingqian Min, Beichen Zhang, Junjie Zhang, Zican Dong, et al. 2023.  A Survey of Large Language Models.  _arXiv preprint arXiv:2303.18223_.
  * Zhao et al. (2024) Zhiyuan Zhao, Bin Wang, Linke Ouyang, Xiaoyi Dong, Jiaqi Wang, and Conghui He. 2024.  Beyond Hallucinations: Enhancing LVLMs through Hallucination-Aware Direct Preference Optimization.  _arXiv preprint arXiv:2311.16839_.
  * Zhou et al. (2023) Ce Zhou, Qian Li, Chen Li, Jun Yu, Yixin Liu, Guangjing Wang, Kai Zhang, Cheng Ji, Qiben Yan, Lifang He, et al. 2023.  A Comprehensive Survey on Pretrained Foundation Models: A History from BERT to ChatGPT.  _arXiv preprint arXiv:2302.09419_.
  * Zhou et al. (2024) Yiyang Zhou, Chenhang Cui, Jaehong Yoon, Linjun Zhang, Zhun Deng, Chelsea Finn, Mohit Bansal, and Huaxiu Yao. 2024.  Analyzing and Mitigating Object Hallucination in Large Vision-Language Models.  In _Proceedings of the 12th International Conference on Learning Representations_ , Vienna, Austria.


# Hypergraph Turán densities can have arbitrarily large algebraic degree

Xizhi Liu Research was supported by ERC Advanced Grant 101020255. Email:
<EMAIL_ADDRESS>Mathematics Institute and DIMAP,
University of Warwick,
Coventry, CV4 7AL, UK  Oleg Pikhurko Research was supported by ERC Advanced
Grant 101020255 and Leverhulme Research Project Grant RPG-2018-424. Email:
<EMAIL_ADDRESS>Mathematics Institute and DIMAP,
University of Warwick,
Coventry, CV4 7AL, UK

###### Abstract

Grosu [Journal of Combinatorial Theory (B), 118 (2016) 137–185] asked if there
exist an integer $r\geq 3$ and a finite family of $r$-graphs whose Turán
density, as a real number, has (algebraic) degree greater than $r-1$. In this
note we show that, for all integers $r\geq 3$ and $d$, there exists a finite
family of $r$-graphs whose Turán density has degree at least $d$, thus
answering Grosu’s question in a strong form.

##  1 Introduction

For an integer $r\geq 2$, an _$r$ -uniform hypergraph_ (henceforth, an _$r$
-graph_) $H$ is a collection of $r$-subsets of some finite set $V$. Given a
family $\mathcal{F}$ of $r$-graphs, we say $H$ is _$\mathcal{F}$ -free_ if it
does not contain any member of $\mathcal{F}$ as a subgraph. The Turán number
$\mathrm{ex}(n,\mathcal{F})$ of $\mathcal{F}$ is the maximum number of edges
in an $\mathcal{F}$-free $r$-graph on $n$ vertices. The Turán density
$\pi(\mathcal{F})$ of $\mathcal{F}$ is defined as
$\pi(\mathcal{F}):=\lim_{n\to\infty}\mathrm{ex}(n,\mathcal{F})/{n\choose r}$;
the existence of the limit was established in [12]. The study of
$\mathrm{ex}(n,\mathcal{F})$ is one of the central topic in extremal graph and
hypergraph theory. For the hypergraph Turán problem (i.e. the case $r\geq 3$),
we refer the reader to the surveys by Keevash [13] and Sidorenko [18].

For $r\geq 3$, determining the value of $\pi(\mathcal{F})$ for a given
$r$-graph family $\mathcal{F}$ is very difficult in general, and there are
only a few known results. For example, the problem of determining
$\pi(K_{\ell}^{r})$ raised by Turán [19] in 1941, where $K_{\ell}^{r}$ is the
complete $r$-graph on $\ell$ vertices, is wide open and the $\$500$ prize of
Erdős for solving it for at least one pair $\ell>r\geq 3$ is still unclaimed.

For every integer $r\geq 2$, define

$\displaystyle\Pi_{\mathrm{fin}}^{(r)}$
$\displaystyle:=\left\\{\pi(\mathcal{F})\colon\text{$\mathcal{F}$ is a finite
family of $r$-graphs}\right\\},\quad\text{and}$
$\displaystyle\Pi_{\infty}^{(r)}$
$\displaystyle:=\left\\{\pi(\mathcal{F})\colon\text{$\mathcal{F}$ is a
(possibly infinite) family of $r$-graphs}\right\\}.$

For $r=2$ the celebrated Erdős–Stone–Simonovits theorem [6, 7] determines the
Turán density for every family $\mathcal{F}$ of graphs; in particular, it
holds that

$\displaystyle\Pi_{\infty}^{(2)}=\Pi_{\mathrm{fin}}^{(r)}=\\{1\\}\cup\left\\{1-{1}/{k}\colon\mbox{integer
$k\geq 1$}\right\\}.$

The problem of understanding the sets $\Pi_{\mathrm{fin}}^{(r)}$ and
$\Pi_{\infty}^{(r)}$ of possible $r$-graph Turán densities for $r\geq 3$ has
attracted a lot of attention. One of the earliest results here is the theorem
of Erdős [5] from the 1960s that
$\Pi_{\infty}^{(r)}\cap(0,r!/r^{r})=\emptyset$ for every integer $r\geq 3$.
However, our understanding of the locations and the lengths of other maximal
intervals avoiding $r$-graph Turán densities and the right accumulation points
of $\Pi_{\infty}^{(r)}$ (the so-called _jump problem_) is very limited; for
some results in this direction see e.g. [1, 8, 9, 17, 21].

It is known that the set $\Pi_{\infty}^{(r)}$ is the topological closure of
$\Pi_{\mathrm{fin}}^{(r)}$ (and thus the former set is easier to understand)
and that $\Pi_{\infty}^{(r)}$ has cardinality of continuum (and thus is
strictly larger than the countable set $\Pi_{\mathrm{fin}}^{(r)}$), see
respectively Proposition 1 and Theorem 2 in [16].

For a while it was open whether $\Pi_{\mathrm{fin}}^{(r)}$ can contain an
irrational number (see the conjecture of Chung and Graham in [3, Page 95]),
until such examples were independently found by Baber and Talbot [2] and by
the second author [16]. However, the question of Jacob Fox ([16, Question 27])
whether $\Pi_{\mathrm{fin}}^{(r)}$ can contain a transcendental number remains
open.

Grosu [11] initiated a systematic study of algebraic properties of the sets
$\Pi_{\mathrm{fin}}^{(r)}$ and $\Pi_{\infty}^{(r)}$. He proved a number of
general results that, in particular, directly give further examples of
irrational Turán densities.

Recall that the _(algebraic) degree_ of a real number $\alpha$ is the minimum
degree of a non-zero polynomial $p$ with integer coefficients that vanishes on
$\alpha$; it is defined to be $\infty$ if no such $p$ exists (that is, if the
real $\alpha$ is transcendental). In the same paper, Grosu [11, Problem 3]
posed the following question.

######  Problem 1.1 (Grosu).

Does there exist an integer $r\geq 3$ such that $\Pi_{\mathrm{fin}}^{(r)}$
contains an algebraic number $\alpha$ of degree strictly larger than $r-1$?

Apparently, all $r$-graph Turán densities that Grosu knew or could produce
with his machinery had degree at most $r-1$, explaining this expression in his
question. His motivation for asking this question was that if, on input
$\mathcal{F}$, we can compute an upper bound on the degree of
$\pi(\mathcal{F})$ as well as on the absolute values of the coefficients of
its minimal polynomial, then we can compute $\pi(\mathcal{F})$ exactly, see
the discussion in [11, Page 140].

In this short note we answer Grosu’s question in the following stronger form.

######  Theorem 1.2.

For every integer $r\geq 3$ and for every integer $d$ there exists an
algebraic number in $\Pi_{\mathrm{fin}}^{(r)}$ whose minimal polynomial has
degree at least $d$.

Our proof for Theorem 1.2 is constructive; in particular, for $r=3$ we will
show that the following infinite sequence is contained in
$\Pi_{\mathrm{fin}}^{(3)}$:

$\displaystyle\frac{1}{\sqrt{3}},\quad\frac{1}{\sqrt{3-\frac{2}{\sqrt{3}}}},\quad\frac{1}{\sqrt{3-\frac{2}{\sqrt{3-\frac{2}{\sqrt{3}}}}}},\quad\frac{1}{\sqrt{3-\frac{2}{\sqrt{3-\frac{2}{\sqrt{3-\frac{2}{\sqrt{3}}}}}}}},\quad\ldots\quad.$
(1)

##  2 Preliminaries

In this section, we introduce some preliminary definitions and results that
will be used later.

For an integer $r\geq 2$, an ($r$-uniform) _pattern_ is a pair
$P=(m,\mathcal{E})$, where $m$ is a positive integer, $\mathcal{E}$ is a
collection of $r$-multisets on $[m]:=\\{1,\ldots,m\\}$, where by an _$r$
-multiset_ we mean an unordered collection of $r$ elements with repetitions
allowed. Let $V_{1},\dots,V_{m}$ be disjoint sets and let
$V=V_{1}\cup\dots\cup V_{m}$. The _profile_ of an $r$-set $R\subseteq V$ (with
respect to $V_{1},\dots,V_{m}$) is the $r$-multiset on $[m]$ that contains
element $i$ with multiplicity $|R\cap V_{i}|$ for every $i\in[m]$. For an
$r$-multiset $S\subseteq[m]$, let $S(\\!(V_{1},\dots,V_{m})\\!)$ consist of
all $r$-subsets of $V$ whose profile is $S$. We call this $r$-graph the
_blowup_ of $S$ and the $r$-graph

$\mathcal{E}(\\!(V_{1},\dots,V_{m})\\!):=\bigcup_{S\in\mathcal{E}}S(\\!(V_{1},\dots,V_{m})\\!)$

is called the _blowup_ of $\mathcal{E}$ (with respect to $V_{1},\dots,V_{m}$).
We say that an $r$-graph $H$ is a _$P$ -construction_ if it is a blowup of
$\mathcal{E}$. Note that these are special cases of the more general
definitions from [16].

It is easy to see that the notion of a pattern is a generalization of a
hypergraph, since every $r$-graph is a pattern in which $\mathcal{E}$ is a
collection of (ordinary) $r$-sets. For most families $\mathcal{F}$ whose Turán
problem was resolved, the extremal $\mathcal{F}$-free constructions are
blowups of some simple pattern. For example, let
$P_{B}:=(2,\left\\{\\{\\{\hskip 1.00006pt1,2,2\hskip
1.00006pt\\}\\},\\{\\{\hskip 1.00006pt1,1,2\hskip 1.00006pt\\}\\}\right\\})$,
where we use $\\{\\{\hskip 1.00006pt\hskip 1.00006pt\\}\\}$ to distinguish
multisets from ordinary sets. Then a $P_{B}$-construction is a $3$-graph $H$
whose vertex set can be partitioned into two parts $V_{1}$ and $V_{2}$ such
that $H$ consists of all triples that have nonempty intersections with both
$V_{1}$ and $V_{2}$. A famous result in the hypergraph Turán theory is that
the pattern $P_{B}$ characterizes the structure of all maximum 3-graphs of
sufficiently large order that do not contain a Fano plane (see [4, 10, 14]).

For a pattern $P=(m,\mathcal{E})$, let the _Lagrange polynomial_ of
$\mathcal{E}$ be

$\displaystyle\lambda_{\mathcal{E}}(x_{1},\dots,x_{m}):=r!\,\sum_{E\in\mathcal{E}}\;\prod_{i=1}^{m}\;\frac{x_{i}^{E(i)}}{E(i)!},$

where $E(i)$ is the multiplicity of $i$ in the $r$-multiset $E$. In other
words, $\lambda_{\mathcal{E}}$ gives the asymptotic edge density of a large
blowup of $\mathcal{E}$, given its relative part sizes $x_{i}$.

The _Lagrangian_ of $P$ is defined as follows:

$\displaystyle\lambda(P):=\sup\left\\{\lambda_{\mathcal{E}}(x_{1},\dots,x_{m})\colon(x_{1},\dots,x_{m})\in\Delta_{m-1}\right\\},$

where $\Delta_{m-1}:=\\{(x_{1},\dots,x_{m})\in[0,1]^{m}\colon
x_{1}+\ldots+x_{m}=1\\}$ is the standard $(m-1)$-dimensional simplex in
$\mathbb{R}^{m}$. Since we maximise a polynomial (a continuous function) on a
compact space, the supremum is in fact the maximum and we call the vectors in
$\Delta_{m-1}$ attaining it _$P$ -optimal_. Note that the Lagrangian of a
pattern is a generalization of the well-known _hypergraph Lagrangian_ that has
been successfully applied to Turán-type problems (see e.g. [1, 9, 20]), with
the basic idea going back to Motzkin and Straus [15].

For $i\in[m]$ let $P-i$ be the pattern obtained from $P$ by _removing index
$i$_, that is, we remove $i$ from $[m]$ and delete all multisets containing
$i$ from $E$ (and relabel the remaining indices to form the set $[m-1]$). We
call $P$ _minimal_ if $\lambda(P-i)$ is strictly smaller than $\lambda(P)$ for
every $i\in[m]$, or equivalently if no $P$-optimal vector has a zero entry.
For example, the 2-graph pattern $P:=(3,\\{\,\\{\\{\hskip 1.00006pt1,2\hskip
1.00006pt\\}\\},\\{\\{\hskip 1.00006pt1,3\hskip 1.00006pt\\}\\}\,\\})$ is not
minimal as $\lambda(P)=\lambda(P-3)=1/2$.

In [16], the second author studied the relations between possible hyrergraph
Turán densities and patterns. One of the main results from [16] is as follows.

######  Theorem 2.1 ([16]).

For every minimal pattern $P$ there exists a finite family $\mathcal{F}$ of
$r$-graphs such that $\pi(\mathcal{F})=\lambda(P)$, and moreover, every
maximum $\mathcal{F}$-free $r$-graph is a $P$-construction.

Let $r\geq 3$ and $s\geq 1$ be two integers. Given an $r$-uniform pattern
$P=(m,\mathcal{E})$, one can create an $(r+s)$-uniform pattern
$P+s:=(m+s,\hat{\mathcal{E}})$ in the following way: for every
$E\in\mathcal{E}$ we insert the $s$-set $\\{m+1,\ldots,m+s\\}$ into $E$, and
let $\hat{\mathcal{E}}$ denote the resulting family of $(r+s)$-multisets. For
example, if $P=(3,\left\\{\\{\\{\hskip 1.00006pt1,2,3\hskip
1.00006pt\\}\\},\\{\\{\hskip 1.00006pt1,3,3\hskip 1.00006pt\\}\\},\\{\\{\hskip
1.00006pt2,3,3\hskip 1.00006pt\\}\\}\right\\})$, then
$P+1=(4,\left\\{\\{\\{\hskip 1.00006pt1,2,3,4\hskip
1.00006pt\\}\\},\\{\\{\hskip 1.00006pt1,3,3,4\hskip
1.00006pt\\}\\},\\{\\{\hskip 1.00006pt2,3,3,4\hskip
1.00006pt\\}\\}\right\\})$.

The following observation follows easily from the definitions.

######  Observation 2.2.

If $P$ is a minimal pattern, then $P+s$ is a minimal pattern for every integer
$s\geq 1$.

For the Lagrangian of $P+s$ we have the following result.

######  Proposition 2.3.

Suppose that $r\geq 2$ is an integer and $P$ is an $r$-uniform pattern. Then
for every integer $s\geq 1$ we have

$\lambda(P+s)=\frac{r^{r}(s+r)!}{(r+s)^{r+s}r!}\,\lambda(P).$

In particular, the real numbers $\lambda(P+s)$ and $\lambda(P)$ have the same
degree.

###### Proof.

Assume that $P=(m,\mathcal{E})$. Let
$\hat{P}:=P+s=(m+s,\widehat{\mathcal{E}})$. Let
$(x_{1},\ldots,x_{m+s})\in\Delta_{m+s-1}$ be a $\hat{P}$-optimal vector. Note
from the definition of Lagrange polynomial that

$\lambda(\hat{P})=\lambda_{\hat{\mathcal{E}}}(x_{1},\ldots,x_{m+s})=\frac{(r+s)!}{r!}\,\lambda_{\mathcal{E}}(x_{1},\ldots,x_{m})\prod_{i=m+1}^{m+s}x_{i}.$

Let $x:=\frac{1}{s}\,\sum_{i=m+1}^{m+s}x_{i}$ and note that
$\sum_{i=1}^{m}x_{i}=1-sx$. Since $\lambda_{{\mathcal{E}}}$ is a homogenous
polynomial of degree $r$, we have

$\displaystyle\lambda_{{\mathcal{E}}}(x_{1},\ldots,x_{m})=\lambda_{\mathcal{E}}\left(\frac{x_{1}}{1-sx},\ldots,\frac{x_{m}}{1-sx}\right)(1-sx)^{r}\leq\lambda(P)(1-sx)^{r}.$

This and the AM-GM inequality give that

$\displaystyle\lambda(\hat{P})=\frac{(r+s)!}{r!}\,\lambda_{\mathcal{E}}(x_{1},\ldots,x_{m})\prod_{i=m+1}^{m+s}x_{i}\leq\frac{(r+s)!}{r!}\,\lambda(P)(1-sx)^{r}x^{s}.$

For $x\in[0,1/s]$, the function $(1-sx)^{r}(rx)^{s}$, as the product of $s+r$
non-negative terms summing to $r$, is maximized when all terms are equal, that
is, at $x=\frac{1}{r+s}$. So

$\displaystyle\lambda(\hat{P})\leq\frac{(r+s)!}{r!}\,\lambda(P)(1-sx)^{r}x^{s}\leq\frac{r^{r}(s+r)!}{(r+s)^{r+s}r!}\,\lambda(P).$

To prove the other direction of this inequality, observe that if we take
$(x_{1},\ldots,x_{m})=\frac{r}{r+s}\,(y_{1},\ldots,y_{m})$, where
$(y_{1},\ldots,y_{m})\in\Delta_{m-1}$ is $P$-optimal, and take
$x_{m+1}=\cdots=x_{m+s}=\frac{1}{r+s}$, then all inequalities above hold with
equalities.

##  3 Proof of Theorem 1.2

In this section we prove Theorem 1.2. By Theorem 2.1, it suffices to find a
sequence of $r$-uniform minimal patterns $(P_{k})_{k=1}^{\infty}$ such that
the degree of the real number $\lambda(P_{k})$ goes to infinity as $k$ goes to
infinity. Furthermore, by Observation 2.2 and Proposition 2.3, it suffices to
find such a sequence for $r=3$. So we will assume that $r=3$ in the rest of
this note.

$P_{1}$-construction$P_{2}$-construction$V_{1}$$V_{2}$$V_{3}$$V_{1}$$V_{2}$$V_{3}$$V_{4}$$V_{5}$
Figure 1: Constructions with one level and two levels.

To start with, we let $P_{1}:=\left(3,\left\\{\\{\\{\hskip
1.00006pt1,2,3\hskip 1.00006pt\\}\\},\\{\\{\hskip 1.00006pt1,3,3\hskip
1.00006pt\\}\\},\\{\\{\hskip 1.00006pt2,3,3\hskip
1.00006pt\\}\\}\right\\}\right)$. Recall that a $3$-graph $H$ is a
$P_{1}$-construction (see Figure 1) if there exists a partition
$V(H)=V_{1}\cup V_{2}\cup V_{3}$ such that the edge set of $H$ consists of

  1. (a)

all triples that have one vertex in each $V_{i}$,

  2. (b)

all triples that have one vertex in $V_{1}$ and two vertices in $V_{3}$, and

  3. (c)

all triples that have one vertex in $V_{2}$ and two vertices in $V_{3}$.

The pattern $P_{1}$ was studied by Yan and Peng in [20], where they proved
that there exists a single $3$-graph whose Turán density is given by
$P_{1}$-constructions which, by $\lambda(P_{1})=1/\sqrt{3}$, is an irrational
number. It seems that some other patterns could be used to prove Theorem 1.2;
however, the obtained sequence of Turán densities (i.e. the sequence in (1))
produced by using $P_{1}$ is nicer than those produced by the other patterns
that we tried.

Next, we define the pattern $P_{k+1}=(2k+3,\mathcal{E}_{k+1})$ for every
$k\geq 1$ inductively. It is easier to define what a $P_{k+1}$-construction is
rather than to write down the definition of $P_{k+1}$: for every integer
$k\geq 1$ a $3$-graph $H$ is a _$P_{k+1}$ -construction_ if there exists a
partition $V(H)=V_{1}\cup V_{2}\cup V_{3}$ such that

  1. (a)

the induced subgraph $H[V_{3}]$ is a $P_{k}$-construction, and

  2. (b)

$H\setminus H[V_{3}]$ consists of all triples whose profile is in
$\left\\{\\{\\{\hskip 1.00006pt1,2,3\hskip 1.00006pt\\}\\},\\{\\{\hskip
1.00006pt1,3,3\hskip 1.00006pt\\}\\},\\{\\{\hskip 1.00006pt2,3,3\hskip
1.00006pt\\}\\}\right\\}$.

The pattern $P_{k}$ can be written down explicitly, although this is not
necessary for our proof later. For example, $P_{2}=(5,\mathcal{E}_{2})$ (see
Figure 1), where

$\displaystyle\mathcal{E}_{2}=$ $\displaystyle\left\\{\\{\\{\hskip
1.00006pt1,2,3\hskip 1.00006pt\\}\\},\\{\\{\hskip 1.00006pt1,2,4\hskip
1.00006pt\\}\\},\\{\\{\hskip 1.00006pt1,2,5\hskip 1.00006pt\\}\\},\\{\\{\hskip
1.00006pt1,3,3\hskip 1.00006pt\\}\\},\\{\\{\hskip 1.00006pt1,3,4\hskip
1.00006pt\\}\\},\\{\\{\hskip 1.00006pt1,3,5\hskip 1.00006pt\\}\\},\right.$
$\displaystyle\quad\\{\\{\hskip 1.00006pt1,4,4\hskip
1.00006pt\\}\\},\\{\\{\hskip 1.00006pt1,4,5\hskip 1.00006pt\\}\\},\\{\\{\hskip
1.00006pt1,5,5\hskip 1.00006pt\\}\\},\\{\\{\hskip 1.00006pt2,3,3\hskip
1.00006pt\\}\\},\\{\\{\hskip 1.00006pt2,3,4\hskip 1.00006pt\\}\\},\\{\\{\hskip
1.00006pt2,3,5\hskip 1.00006pt\\}\\},$ $\displaystyle\quad\left.\\{\\{\hskip
1.00006pt2,4,4\hskip 1.00006pt\\}\\},\\{\\{\hskip 1.00006pt2,4,5\hskip
1.00006pt\\}\\},\\{\\{\hskip 1.00006pt2,5,5\hskip 1.00006pt\\}\\},\\{\\{\hskip
1.00006pt3,4,5\hskip 1.00006pt\\}\\},\\{\\{\hskip 1.00006pt3,5,5\hskip
1.00006pt\\}\\},\\{\\{\hskip 1.00006pt4,5,5\hskip 1.00006pt\\}\\}\right\\}.$

Our first result determines the Lagrangian of $P_{k}$ for every $k\geq 1$. For
convenience, we set $P_{0}:=(1,\\{\emptyset\\})$ and $\lambda_{0}:=0$.

######  Proposition 3.1.

For every integer $k\geq 0$, we have
$\lambda(P_{k+1})={1}/{\sqrt{3-2\lambda(P_{k})}}$ and the pattern $P_{k+1}$ is
minimal. In particular, $\left(\lambda(P_{k})\right)_{k=1}^{\infty}$ is the
sequence in (1).

###### Proof.

We use induction on $k$ where the base $k=0$ is easy to check directly (or can
be derived by adapting the forthcoming induction step to work for $k=0$). Let
$k\geq 1$.

Let us prove that $\lambda(P_{k+1})={1}/{\sqrt{3-2\lambda(P_{k})}}$. Recall
that $P_{k}=(2k+1,\mathcal{E}_{k})$ and $P_{k+1}=(2k+3,\mathcal{E}_{k+1})$.
Let $(x_{1},\ldots,x_{2k+3})\in\Delta_{2k+2}$ be a $P_{k+1}$-optimal vector.
Let $x:=\sum_{i=3}^{2k+3}x_{i}=1-x_{1}-x_{2}$. It follows from the definitions
of $P_{k+1}$ and the Lagrange polynomial that

$\displaystyle\lambda(P_{k+1})=\lambda_{\mathcal{E}_{k+1}}(x_{1},\ldots,x_{2k+3})=6\left(x_{1}x_{2}x+(x_{1}+x_{2})\frac{x^{2}}{2}\right)+\lambda_{\mathcal{E}_{k}}(x_{3},\ldots,x_{2k+3}).$
(2)

Since $\lambda_{\mathcal{E}_{k}}(x_{3},\ldots,x_{2k+3})$ is a homogeneous
polynomial of degree $3$, we have

$\displaystyle\lambda_{\mathcal{E}_{k}}(x_{3},\ldots,x_{2k+3})=\lambda_{\mathcal{E}_{k}}\left(\frac{x_{3}}{x},\ldots,\frac{x_{2k+3}}{x}\right)x^{3}\leq\lambda(P_{k})x^{3}.$

So it follows from (2) and the 2-variable AM-GM inequality that

$\displaystyle\lambda(P_{k+1})$ $\displaystyle\leq
6\left(\left(\frac{x_{1}+x_{2}}{2}\right)^{2}x+(x_{1}+x_{2})\frac{x^{2}}{2}\right)+\lambda(P_{k})x^{3}$
$\displaystyle=6\left(\left(\frac{1-x}{2}\right)^{2}x+(1-x)\frac{x^{2}}{2}\right)+\lambda(P_{k})x^{3}=\frac{3x-\left(3-2\lambda(P_{k})\right)x^{3}}{2}.$

Since $0\leq\lambda(P_{k})\leq 1$, one can easily show by taking the
derivative that the maximum of the function
$\left(3x-\left(3-2\lambda(P_{k})\right)x^{3}\right)/2$ on $[0,1]$ is achieved
if and only if $x={1}/{\sqrt{3-2\lambda(P_{k})}}$, and the maximum value is
${1}/{\sqrt{3-2\lambda(P_{k})}}$. This proves that
$\lambda(P_{k+1})\leq{1}/{\sqrt{3-2\lambda(P_{k})}}$.

To prove the other direction of this inequality, one just need to observe that
when we choose

$\displaystyle
x_{1}=x_{2}=\frac{1}{2}-\frac{1}{2\sqrt{3-2\lambda(P_{k})}}\quad\text{and}\quad(x_{3},\ldots,x_{2k+3})=\frac{1}{\sqrt{3-2\lambda(P_{k})}}\,(y_{1},\ldots,y_{2k+1})$
(3)

where $(y_{1},\ldots,y_{2k+1})\in\Delta_{2k}$ is a $P_{k}$-optimal vector,
then all inequalities above hold with equality. Therefore,
$\lambda(P_{k+1})={1}/{\sqrt{3-2\lambda(P_{k})}}$.

To prove that $P_{k+1}$ is minimal, take any $P_{k+1}$-optimal vector
$(x_{1},\ldots,x_{2k+3})\in\Delta_{2k+2}$; we have to show that it has no zero
entries. This vector attains equality in all our inequalities above, which
routinely implies that $(x_{1},\ldots,x_{2k+3})$ must satisfy (3), for some
$P_{k}$-optimal vector $(y_{1},\ldots,y_{2k+1})$. We see that $x_{1}=x_{2}$
are both non-zero because the sequence
$(\lambda(P_{0}),\ldots,\lambda(P_{k+1}))$ is strictly increasing (since
$x<1/\sqrt{3-2x}$ for all $x\in[0,1)$) and thus $\lambda(P_{k})<1$. The
remaining conclusion that $x_{3},\ldots,x_{2k+3}$ are non-zero follows from
the induction hypothesis on $(y_{1},\ldots,y_{2k+1})$.

In order to finish the proof of Theorem 1.2 it suffices to prove that the
degree of $\mu_{k}:=\lambda(P_{k})$ goes to infinity as $k\to\infty$. This is
achieved by the last claim of the following lemma.

######  Lemma 3.2.

Let $p_{1}(x):=3x^{2}-1$ and inductively for $k=1,2,\dots$ define

$p_{k+1}(x)=(2x^{2})^{2^{k}}p_{k}\left(\frac{3x^{2}-1}{2x^{2}}\right),\quad\mbox{for
$x\in\mathbb{R}$}.$

Then the following claims hold for each $k\in\mathbb{N}\colon$

  1. (a)

$p_{k}(\mu_{k})=0$;

  2. (b)

$p_{k}$ is a polynomial of degree at most $2^{k}$ with integer coefficients:
$p_{k}(x)=\sum_{i=0}^{2^{k}}c_{k,i}x^{i}$ for some $c_{k,i}\in\mathbb{Z}$;

  3. (c)

the integers $b_{k,i}:=c_{k,i}$ for even $k$ and $b_{k,i}:=c_{k,2^{k}-i}$ for
odd $k$ satisfy the following:

    1. (c.i)

for each integer $i$ with $0\leq i\leq 2^{k}$, $3$ divides $b_{k,i}$ if and
only if $i\not=2^{k}$;

    2. (c.ii)

$9$ does not divide $b_{k,0}$;

  4. (d)

the polynomial $p_{k}$ is irreducible of degree exactly $2^{k}$;

  5. (e)

the degree of $\mu_{k}$ is $2^{k}$.

###### Proof.

Let us use induction on $k$. All stated claims are clearly satisfied for
$k=1$, when $p_{1}(x)=3x^{2}-1$ and $\mu_{1}=1/\sqrt{3}$. Let us prove them
for $k+1$ assuming that they hold for some $k\geq 1$.

For Part (a), we have by Proposition 3.1 that

$\frac{3\mu_{k+1}^{2}-1}{2\mu_{k+1}^{2}}=\frac{3/(3-2\mu_{k})-1}{2/(3-2\mu_{k})}=\mu_{k}$

and thus $p_{k+1}(\mu_{k+1})=(2\mu_{k+1}^{2})^{2^{k}}p_{k}(\mu_{k})$, which is
0 by induction.

Part (b) also follows easily from the induction assumption:

$p_{k+1}(x)=(2x^{2})^{2^{k}}\sum_{i=0}^{2^{k}}c_{k,i}\left(\frac{3x^{2}-1}{2x^{2}}\right)^{i}=\sum_{i=0}^{2^{k}}c_{k,i}(3x^{2}-1)^{i}(2x^{2})^{2^{k}-i}.$
(4)

Let us turn to Part (c). The relation in (4) when taken modulo 3 reads that

$\sum_{j=0}^{2^{k+1}}c_{k+1,j}x^{j}\equiv\sum_{i=0}^{2^{k}}c_{k,i}x^{2^{k+1}-2i}\pmod{3}.$

Thus, $c_{k+1,j}\equiv c_{k,2^{k}-j/2}\pmod{3}$ for all even $j$ between $0$
and $2^{k+1}$, while $c_{k+1,j}\equiv 0\pmod{3}$ for odd $j$ (in fact,
$c_{k+1,j}=0$ for all odd $j$ since $p_{k+1}$ is an even function). In terms
of the sequences $(b_{\ell,j})_{j=0}^{2^{\ell}}$, this relation states that

$b_{k+1,j}\equiv b_{k,j/2}\pmod{3}\quad\mbox{for all even $j$ with $0\leq
j\leq 2^{k}$,}$

while $b_{k+1,j}\equiv 0\pmod{3}$ for all odd $j$. This implies Part (c)(c.i).
For Part (c)(c.ii), the relation in (4) when taken modulo 9 gives that
$c_{k+1,0}\equiv c_{k,2^{k}}$ and $c_{k+1,2^{k+1}}\equiv c_{k,0}\cdot
2^{2^{k}}+c_{k,1}\cdot 3\cdot 2^{2^{k}-1}$. Since $c_{k,1}$ is divisible by
$3$, we have in fact that $c_{k+1,2^{k+1}}\equiv c_{k,0}\cdot 2^{2^{k}}\equiv
c_{k,0}\pmod{9}$. By the induction hypothesis, this implies that $9$ does not
divide $b_{k+1,0}$.

By the argument above, $c_{k+1,2^{k+1}}$ is non-zero module $3$ for odd $k$
and non-zero module 9 for even $k$. Thus, regardless of the parity of $k$, the
degree of the polynomial $p_{k+1}$ is exactly $2^{k+1}$. Moreover, $p_{k+1}$
satisfies Eisenstein’s criterion for prime $q=3$ (namely, that $q$ divides all
coefficients, except exactly one at the highest power of $x$ or at the
constant term while the other of the two is not divisible by $q^{2}$). By the
criterion (whose proof can be found in e.g. [16, Section 4]), the polynomial
$p_{k+1}$ is irreducible, proving Part (d).

By putting the above claims together, we see that $\mu_{k+1}$ is a root of an
irreducible polynomial of degree $2^{k+1}$, establishing Part (e). This
completes the proof the lemma (and thus of Theorem 1.2)

##  4 Concluding remarks

Our proof of Theorem 1.2 shows that for every integer $d$ which is a power of
$2$ there exists a finite family $\mathcal{F}$ of $r$-graphs such that
$\pi(\mathcal{F})$ has algebraic degree $d$. It seems interesting to know
whether this is true for all positive integers.

######  Problem 4.1.

Let $r\geq 3$ be an integer. Is it true that for every positive integer $d$
there exists a finite family $\mathcal{F}$ of $r$-graphs such that
$\pi(\mathcal{F})$ has algebraic degree exactly $d$?

By considering other patterns, one can get Turán densities in
$\Pi_{\mathrm{fin}}^{(r)}$ whose algebraic degrees are not powers of $2$. For
example, the pattern $([3],\\{\\{\hskip 1.00006pt1,2,3\hskip
1.00006pt\\}\\},\\{1,2\\})$ with _recursive parts_ 1 and 2 (where we can take
blowups of the single edge $\\{\\{\hskip 1.00006pt1,2,3\hskip 1.00006pt\\}\\}$
and recursively repeat this step inside the first and the second parts of each
added blowup) gives a Turán density in $\Pi_{\mathrm{fin}}^{(3)}$ (by [16,
Theorem 3], a generalisation of Theorem 2.1) whose degree can be computed to
be $3$. However, we did not see any promising way of how to produce a pattern
whose Lagrangian has any given degree $d$.

## Acknowledgement

We would like to thank the referees for their helpful comments.

## References

  * [1] R. Baber and J. Talbot.  Hypergraphs do jump.  Combin. Probab. Comput., 20(2):161–171, 2011.
  * [2] R. Baber and J. Talbot.  New Turán densities for 3-graphs.  Electron. J. Combin., 19(2):Paper 22, 21, 2012.
  * [3] F. Chung and R. Graham.  Erdős on graphs: his legacy of unsolved problems.  A K Peters, Ltd., Wellesley, MA, 1998.
  * [4] D. De Caen and Z. Füredi.  The maximum size of 3-uniform hypergraphs not containing a Fano plane.  J. Combin. Theory Ser. B, 78(2):274–276, 2000.
  * [5] P. Erdős.  On extremal problems of graphs and generalized graphs.  Israel J. Math., 2:183–190, 1964.
  * [6] P. Erdős and M. Simonovits.  A limit theorem in graph theory.  Studia Sci. Math. Hungar., 1:51–57, 1966.
  * [7] P. Erdös and A. H. Stone.  On the structure of linear graphs.  Bull. Amer. Math. Soc., 52:1087–1091, 1946.
  * [8] P. Frankl, Y. Peng, V. Rödl, and J. Talbot.  A note on the jumping constant conjecture of Erdős.  J. Combin. Theory Ser. B, 97(2):204–216, 2007.
  * [9] P. Frankl and V. Rödl.  Hypergraphs do not jump.  Combinatorica, 4(2-3):149–159, 1984.
  * [10] Z. Füredi and M. Simonovits.  Triple systems not containing a Fano configuration.  Combin. Probab. Comput., 14(4):467–484, 2005.
  * [11] C. Grosu.  On the algebraic and topological structure of the set of Turán densities.  J. Combin. Theory Ser. B, 118:137–185, 2016.
  * [12] G. Katona, T. Nemetz, and M. Simonovits.  On a problem of Turán in the theory of graphs.  Mat. Lapok, 15:228–238, 1964.
  * [13] P. Keevash.  Hypergraph Turán problems.  In Surveys in combinatorics 2011, volume 392 of London Math. Soc. Lecture Note Ser., pages 83–139. Cambridge Univ. Press, Cambridge, 2011.
  * [14] P. Keevash and B. Sudakov.  The Turán number of the Fano plane.  Combinatorica, 25(5):561–574, 2005.
  * [15] T. S. Motzkin and E. G. Straus.  Maxima for graphs and a new proof of a theorem of Turán.  Canadian J. Math., 17:533–540, 1965.
  * [16] O. Pikhurko.  On possible Turán densities.  Israel J. Math., 201(1):415–454, 2014.
  * [17] O. Pikhurko.  The maximal length of a gap between $r$-graph Turán densities.  Electron. J. Combin., 22(4):Paper 4.15, 7, 2015.
  * [18] A. Sidorenko.  What we know and what we do not know about Turán numbers.  Graphs Combin., 11(2):179–199, 1995.
  * [19] P. Turán.  On an extremal problem in graph theory.  Mat. Fiz. Lapok, 48:436–452, 1941.
  * [20] Z. Yan and Y. Peng.  An irrational Lagrangian density of a single hypergraph.  SIAM J. Discrete Math., 36(1):786–822, 2022.
  * [21] Z. Yan and Y. Peng.  Non-jumping Turán densities of hypergraphs.  Discrete Math., 346(1):Paper No. 113195, 11, 2023.


# Deshadow-Anything: When Segment Anything Model Meets Zero-shot shadow
removal

###### Abstract

Segment Anything (SAM), an advanced universal image segmentation model trained
on an expansive visual dataset, has set a new benchmark in image segmentation
and computer vision. However, it faced challenges when it came to
distinguishing between shadows and their backgrounds. To address this, we
developed Deshadow-Anything, considering the generalization of large-scale
datasets, and we performed Fine-tuning on large-scale datasets to achieve
image shadow removal. The diffusion model can diffuse along the edges and
textures of an image, helping to remove shadows while preserving the details
of the image. Furthermore, we design Multi-Self-Attention Guidance (MSAG) and
adaptive input perturbation (DDPM-AIP) to accelerate the iterative training
speed of diffusion. Experiments on shadow removal tasks demonstrate that these
methods can effectively improve image restoration performance.

Index Terms—  Segment Anything Model, Shadow Removal, Multi-Self-Attention
Guidance

##  1 Introduction

Image restoration is a low-level vision task. It refers to the recovery of
degraded images. The quick advancement of computer vision in recent years has
made it possible to handle an increasing number of degradation tasks,
including image shadow removal, super-resolution, image defogging, etc.

Shadows are created by objects blocking light sources and are closely related
to factors such as texture, color, and lighting changes in the image. Existing
shadow removal methods are classified as supervised method [1, 2, 3, 4, 5, 6,
7, 8], semi-supervised method [9, 10], and unsupervised method [11, 12]. They
do not function well when faced with pure black occluded shadows for
inpainting tasks.

Recently, within foundational models, Segment Anything Model (SAM) stands out
as a universal image segmentation model trained on large-scale dataset. SAM
has been demonstrated to be successful at segmenting various scenes, marking a
breakthrough step in image segmentation and the related field of computer
vision. Therefore, we introduced SAM into the image shadow segmentation task,
which can solve the problem of hard and soft shadow segmentation. The most
significant challenge in current de-shadowing techniques is the wide variance
in shadows’ shape, size, color, and other features within an image. We explore
the diffusion approach, reevaluate its role in de-shadowing tasks, and then
propose Deshadow-Anything for image shadow removal on Large-scale Pre-
training.

To enhance the effectiveness and stability of blur guidance at a larger scale,
we delve into the self-attention mechanism employed by diffusion models.
Typically, modern diffusion models incorporate a self-attention module as a
fundamental component of their architecture.

Given our assertion that self-attention plays a pivotal role in capturing
crucial information throughout the generation process, we introduce a novel
concept known as Multi Self-Attention Guidance (MSAG). MSAG employs an
adversarial approach to deliberately blur regions containing salient
information, using the self-attention map derived from diffusion models.
Subsequently, it guides diffusion models by emphasizing the residual
information. By harnessing attention maps during the reverse process of
diffusion models, this approach can notably enhance quality and reduce
artifacts through self-conditioning, all without necessitating external data
or additional training efforts.

Fig. 1: Introduction of Deshadow-Anything, first point like ”200,200” input,
split shadow mask, then employ diffusion to remove shadows

The diffusion model provides a flexible, adaptive way to deal with shadows in
an image, and through an iterative approach, able to preserve detail while the
diffusion model can gradually improve the image and gradually mitigate the
effects of shadows. Additionally, during the de-shadowing process, the
Diffusion method suppresses noise in the propagation process, enhancing the
accuracy of the de-shadowing effect. Most notably, the Diffusion method
automatically adapts to local features within an image, such as texture and
color, leading to better de-shadowing outcomes in different regions.

To accelerate the iterative training speed of diffusion, we apply various
regularization techniques, all aimed at smoothing the prediction function.
Furthermore, we took to finetune on Large-scale Pre-training proved by Guided
Diffusion [13]. In summary, the main contributions of this work are:

  1. 1.

In this paper, we propose the Deshadow-Anything , where we apply fin-tuning on
a Large-scale Pre-training to achieve better image shadow removal, which
generates context-rich and spatially accurate outputs.

  2. 2.

To speed up the iterative training speed of diffusion, we design adaptive
input perturbation named DDPM-AIP, whose common goal is to smooth the
prediction function.

  3. 3.

To enhance the effectiveness and stability of blur guidance at a larger scale,
we delve into the Multi self-attention mechanism employed by diffusion models.

Fig. 2: The structure of Deshadow-Anything (The process can be divided into
two main steps. Step 1:We fine-tune our model on a pre-trained model (a large-
scale model provided by guided diffusion) while adding adaptive input
perturbations to accelerate convergence during training. In step 2, we input
the image into SAM to obtain a shadow segmentation mask, while the shadow
portion of the image is generated after sampling the diffusion in the unshaded
image. Finally, we merge the two images to obtain the de-shaded result. Fig.
3: The structure of Multi-Self-Attention Guided (MSAG)

##  2 The Proposed Method

In this paper, inspired by [14, 15], and the structure is shown in Fig. 2, we
denote the ground truth image by $f(x,y)$ and the image after degradation by
$g(x,y)$, and the degradation process can be divided into the degradation
function $h(x,y)$ as well as the noise $N(x,y)$ loaded on the image
representation, and the recovered image can be represented by $k(x,y)$.
Therefore, the whole mathematical model of image degradation is namely:

$\displaystyle g(x,y)$ $\displaystyle=h(x,y)*f(x,y)+n(x,y),$ (1)
$\displaystyle k(x,y)$ $\displaystyle=Recover(g(x,y)).$

Specific to the image shadow removal task, the above mathematical process can
be expressed as the following operations:

$m=SAM(x_{0})$ (2)

$\displaystyle x_{t-1}$ $\displaystyle=m\odot x_{t-1}^{\text{unmask
}}+(1-m)\odot x_{t-1}^{\text{mask}}.$ (3)

$m$ is the mask achieved by Segment anything model, and $x_{t-1}$ is equal to
$k(x,y)$ which in Eq. (1).

###  2.1 Multi Self Attention Guidance

Limited by the fact that its framework is still an unconditionally generated
DDPM model based on an iterative denoising process (i.e., not conditional on
the generation of information such as textual images or categories), we
therefore consider introducing self-attention bootstrapping, where the self-
attention bootstrapping mechanism is added to the forward process of the
diffusion model.

Specifically, the self-attention mechanism is used to compute the attentional
weights of each intermediate sample in the generation process in order to
capture the salient information in those samples. These attentional weights
are then used to blur the intermediate samples to remove some of the detail
information, thus making the intermediate samples more suitable for use in
generating high-quality images. Finally, the diffusion model uses these
blurred intermediate samples to generate high quality images. Self-attention
in diffusion models. Several works of diffusion models use the U-Net structure
with self attention at one or some of the intermediate layers. Moreover, very
recently, diffusion models using Transformers as the backbone has also been
pro posed. Specifically, for the height H and width W,given any feature map
$X_{t}\in R^{H\times W\times C}$ at a timestep t, the N-head self-attention is
defined as:

$\displaystyle Q_{t}^{h}=X_{t}W_{Q}^{h},\quad K_{t}^{h}=X_{t}W_{K}^{h},$ (4)
$\displaystyle
A_{t}^{h}=\operatorname{softmax}\left(Q_{t}^{h}\left(K_{t}^{h}\right)^{T}/\sqrt{d}\right),$
$x_{t}=x_{t}\cdot A_{t}^{h}+x_{t}\cdot(1-A_{t}^{h})$ (5)

Guassian fuzzy processing of inputs using Gaussian fuzzy operations as a
priori guidance.

$x_{t}=GaussianBlur(x_{t-1},\sigma=blur_{\sigma})$ (6)

###  2.2 Speed up training and sampling

In the context of the diffusion probabilistic model (DPM), a recent
improvement involves adding the product of the variance and classification
gradient term during the calculation of the mean value of the Gaussian
distribution. This improvement eliminates the need to retrain the diffusion
model and instead requires the training of an additional classifier to
effectively provide category guidance. However, since each backward process of
the diffusion model must pass through the network at least once, the overall
generation speed is typically slow. To address this, various regularization
methods are applied to smooth the prediction function, with input perturbation
(DDPM-IP) [14] being suggested as the best and simplest solution. We design
adaptive input perturbation to speed up the diffusion model named (DDPM-AIP).
It is worth mentioning that, after accelerating the iteration, our sampling
speed is increased by 1/4 compared to the guided-diffusion. DDPM-AIP is
performed as follows:

$\displaystyle\text{ n }=\gamma*N(\theta,I)$ (7)
$\displaystyle\mathbf{n}_{\text{new }}=\mathbf{n}+\gamma\cdot\mathbf{r}$
$\displaystyle\mathbf{x}_{\mathbf{t}}=Q\left(\mathbf{x}_{\text{start
}},t;\mathbf{n}_{\text{new }}\right)$

where $n$ is the current noise tensor, $\gamma$ is a scalar value that
controls the amount of noise to be added, N(0, I) is a tensor containing
random samples drawn from a standard normal distribution with mean 0 and
standard deviation 1. $x_{start}$ is the initial input tensor to the model, t
is the current time step, and $Q$ is a function that takes $x_{start}$, $t$,
and $n_{new}$ as inputs and returns the output tensor $x_{t}$.

Fig. 4: Abaltion study on Pretrained model and Fintune Table 1: Performance
comparison of results on ISTD and SRD dataset

Method | ISTD | SRD
---|---|---
|  RMSE $\downarrow$ |  SSIM $\downarrow$ |  PSNR $\downarrow$ |  RMSE $\uparrow$ |  SSIM $\uparrow$ |  PSNR $\uparrow$
Yang [16] |  15.63 | 14.83 | 19.82 | - | - | -
Guo [17] | 9.3 | 0.919 | 23.07 | 14.05 | - | -
Gong [18] | 8.53 | 0.908 | 24.07 | - | - | -
DeShadowNet[19] | 7.83 | - | - | 6.64 | - | -
STC-GAN [1] | 7.47 | 0.929 | 27.43 |  |  |
SID [2] | 7.96 | 0.948 | 25.01 |  |  |
DSC [3] | 6.67 | 0.845 | 26.62 | 17.43 | 0.648 | 20.65
RIS-GAN [4] | 6.62 | - | - |  |  |
Mask-ShadowGAN[9] | 7.63 | - | - |  |  |
DHAN [5] | 6.28 | 0.921 | 27.88 | 4.80 | 0.928 | 28.93
LG-shadow [10] | 6.67 | 0.906 | 25.83 |  |  |
Auto-Exp [20] | 5.88 | 0.845 | 27.19 | 6.75 | 0.856 | 26.72
G2R [11] | 7.84 | 0.932 | 24.72 | - | - | -
Bejetive [7] | 4.78 | 0.928 | 29.02 | 4.15 | 0.944 | 30.35
SpA-Former [8] | 6.86 | 0.931 | 27.73 | 6.86 | 0.931 | 27.73
ShadowFormer[6] | 4.21 | 0.985 | 30.46 | - | - | -
Deshadow-Anything | 3.75 | 0.944 | 33.51 | 4.23 | 0.949 | 32.28

##  3 Experiment

###  3.1 Implementation details and Comparison with State-of-the-Art Methods

Deshadow-Anything is implemented using PyTorch 1.8.0 and two NVIDIA GTX 3090
GPUs. In this paper, we chose three evaluation metrics, PSNR and SSIM, and
RMSE. The dataset used in this paper is ISTD [1] and SRD [3].

Fig. 5: Visual performance comparison of image shadow removal on SRD dataset

Our method is compared with existing methods including Yang [16], Guo [17],
Gong [18], DeShadowNet[19], STC-GAN [1], DSC [3], Mask-ShadowGAN [9], RIS-GAN
[4], DHAN [5], SID [2], LG-shadow [10], G2R [11], Auto-exp [20], SpA-Former
[8], CANet [21], Bejetive [7], ShadowFormer [6]. We adopt the root mean square
error (RMSE), structure similarity index (SSIM), and Peak Signal to Noise
Ratio (PSNR) in the LAB color space as evaluation metrics. The quantitative
comparison is shown in Table 1 and Fig. 5. The Deshadow-Anything model has
achieved the best performance regarding PSNR, whether the image is partially
shaded or non-partially shaded or has an unshaded region.

Table 2: Abaltion study of Deshadow-Anything’s finetune on ISTD dataset

Places2 | ISTD | ISTD finetune | PSNR $\uparrow$ | SSIM $\uparrow$ | RMSE $\downarrow$
---|---|---|---|---|---
✓ |  |  | 32.12 | 0.931 | 4.23
| ✓ |  | 31.63 | 0.915 | 4.54
|  | ✓ | 33.51 | 0.944 | 3.75

###  3.2 Ablation study on Deshadow-Anything

Quantitative comparisons on Pretrained model Places2. Guided diffusion was
utilized to fine-tune the pre-training model on the Places2 dataset, further
optimizing Deshadow-Anything for the shadow removal task and improving its
performance. The pre-trained model has already learned a significant amount of
general knowledge, meaning less labeled data is typically required to achieve
good results during fine-tuning. This greatly reduces the cost of data
collection and tagging. Moreover, fine-tuning with pre-trained models enables
faster experimentation and model development since, in many cases, only a few
modifications to the model are needed to adapt it to a specific task. The
ablation study of the pre-trained model on Places2 is presented in Table 2,
which includes:

1) Testing on Large-scale pre-trained model Places2, without fine-tuning.

2) Results of training on the ISTD/SRD dataset using guided diffusion without
fine-tuning.

3) Fine-tuning on the Large-scale pre-trained model of Place2 with dataset
ISTD/SRD.

After fine-tuning our model with the ISTD dataset, we observe a significant
improvement in the performance of Deshadow-Anything. The PSNR and SSIM values
demonstrate that the recovered images are perceptually realistic and that our
method outperforms existing techniques. The results also show that the fine-
tuning process successfully addresses the limitations of the pre-trained model
and greatly enhances the effectiveness of our approach.

##  4 Conclusion

In this paper, we propose a Deshadow-Anything model with fine-tuning on a
large-scale dataset for image shadow removal. specifically, we design Multi-
Self-Attention Guidance (MSAG) and adaptive input perturbation (DDPM-AIP) to
accelerate the iterative training speed of diffusion. We believe that in
today’s trend of Large-scale, low-level should be better combined with large-
scale to fine-tune and thus achieve its task.

## References

  * [1] Jifeng Wang, Xiang Li, and Jian Yang,  “Stacked conditional generative adversarial networks for jointly learning shadow detection and shadow removal,”  in Proceedings of the IEEE conference on computer vision and pattern recognition, 2018, pp. 1788–1797.

  * [2] Hieu Le and Dimitris Samaras,  “Shadow removal via shadow image decomposition,”  in Proceedings of the IEEE/CVF International Conference on Computer Vision, 2019, pp. 8578–8587.
  * [3] Xiaowei Hu, Chi-Wing Fu, Lei Zhu, Jing Qin, and Pheng-Ann Heng,  “Direction-aware spatial context features for shadow detection and removal,”  TPAMI, vol. 42, pp. 2795–2808, 2019.
  * [4] Ling Zhang, Chengjiang Long, Xiaolong Zhang, and Chunxia Xiao,  “Ris-gan: Explore residual and illumination with generative adversarial networks for shadow removal,”  in Proceedings of the AAAI Conference on Artificial Intelligence, 2020, vol. 34, pp. 12829–12836.
  * [5] Xiaodong Cun, Chi-Man Pun, and Cheng Shi,  “Towards ghost-free shadow removal via dual hierarchical aggregation network and shadow matting gan,”  in Proceedings of the AAAI Conference on Artificial Intelligence, 2020, vol. 34, pp. 10680–10687.
  * [6] Lanqing Guo, Siyu Huang, Ding Liu, Hao Cheng, and Bihan Wen,  “Shadowformer: Global context helps image shadow removal,”  arXiv preprint arXiv:2302.01650, 2023.
  * [7] Yurui Zhu, Jie Huang, Xueyang Fu, Feng Zhao, Qibin Sun, and Zheng-Jun Zha,  “Bijective mapping network for shadow removal,”  in Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2022, pp. 5627–5636.
  * [8] Xiaofeng Zhang, Yudi Zhao, Chaochen Gu, Changsheng Lu, and Shanying Zhu,  “Spa-former: An effective and lightweight transformer for image shadow removal,”  in International Joint Conference on Neural Networks, 2023, pp. 1–8.
  * [9] Xiaowei Hu, Yitong Jiang, Chi-Wing Fu, and Pheng-Ann Heng,  “Mask-shadowgan: Learning to remove shadows from unpaired data,”  in Proceedings of the IEEE/CVF international conference on computer vision, 2019, pp. 2472–2481.
  * [10] Zhihao Liu, Hui Yin, Yang Mi, Mengyang Pu, and Song Wang,  “Shadow removal by a lightness-guided network with training on unpaired data,”  TIP, vol. 30, 2021.
  * [11] Zhihao Liu, Hui Yin, Xinyi Wu, Zhenyao Wu, Yang Mi, and Song Wang,  “From shadow generation to shadow removal,”  in Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2021, pp. 4927–4936.
  * [12] Chao Tan and Xin Feng,  “Unsupervised shadow removal using target consistency generative adversarial network,”  arXiv preprint arXiv:2010.01291, 2020.
  * [13] Prafulla Dhariwal and Alexander Nichol,  “Diffusion models beat gans on image synthesis,”  Advances in neural information processing systems, vol. 34, pp. 8780–8794, 2021.
  * [14] Mang Ning, Enver Sangineto, Angelo Porrello, Simone Calderara, and Rita Cucchiara,  “Input perturbation reduces exposure bias in diffusion models,”  arXiv preprint arXiv:2301.11706, 2023.
  * [15] Tao Yu, Runseng Feng, Ruoyu Feng, Jinming Liu, Xin Jin, Wenjun Zeng, and Zhibo Chen,  “Inpaint anything: Segment anything meets image inpainting,”  arXiv preprint arXiv:2304.06790, 2023.
  * [16] Qingxiong Yang, Kar-Han Tan, and Narendra Ahuja,  “Shadow removal using bilateral filtering,”  TIP, vol. 21, pp. 4361–4368, 2012.
  * [17] Ruiqi Guo, Qieyun Dai, and Derek Hoiem,  “Paired regions for shadow detection and removal,”  TPAMI, vol. 35, pp. 2956–2967, 2012.
  * [18] Han Gong and Darren Cosker,  “Interactive shadow removal and ground truth for variable scene categories.,”  in Bmvc, 2014, pp. 1–11.
  * [19] Liangqiong Qu, Jiandong Tian, Shengfeng He, Yandong Tang, and Rynson WH Lau,  “Deshadownet: A multi-context embedding deep network for shadow removal,”  in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2017, pp. 4067–4075.
  * [20] Lan Fu, Changqing Zhou, Qing Guo, Felix Juefei-Xu, Hongkai Yu, Wei Feng, Yang Liu, and Song Wang,  “Auto-exposure fusion for single-image shadow removal,”  in Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, 2021, pp. 10571–10580.
  * [21] Zipei Chen, Chengjiang Long, Ling Zhang, and Chunxia Xiao,  “Canet: A context-aware network for shadow removal,”  in Proceedings of the IEEE/CVF international conference on computer vision, 2021, pp. 4743–4752.