# pymovements: A Python Package for Eye Movement Data Processing

Daniel G. Krakowczyk<EMAIL_ADDRESS>0009-0009-5100-0733
University of PotsdamPotsdamGermany ,  David R. Reich  david.reich@uni-
potsdam.de 0000-0002-3524-3788 University of PotsdamPotsdamGermany ,  Jakob
Chwastek<EMAIL_ADDRESS>0000-0001-7092-6245 University of
PotsdamPotsdamGermany ,  Deborah N. Jakobi<EMAIL_ADDRESS>0000-0002-9719-6673 University of ZurichZurichSwitzerland ,  Paul Prasse
<EMAIL_ADDRESS>0000-0003-1842-3645 University of
PotsdamPotsdamGermany ,  Assunta Süss<EMAIL_ADDRESS>0000-0002-9797-0278 University of PotsdamPotsdamGermany ,  Oleksii Turuta
<EMAIL_ADDRESS>0000-0002-0970-8617 Kharkiv National University of
Radio ElectronicsKharkivUkraine ,  Paweł Kasprowski<EMAIL_ADDRESS>0000-0002-2090-335X Silesian University of TechnologyGliwicePoland and  Lena
A. Jäger<EMAIL_ADDRESS>0000-0001-9018-9713 University of
ZurichZurichSwitzerland
University of PotsdamPotsdamGermany

###### Abstract.

We introduce _pymovements_ : a Python package for analyzing eye-tracking data
that follows best practices in software development, including rigorous
testing and adherence to coding standards. The package provides functionality
for key processes along the entire preprocessing pipeline. This includes
parsing of eye tracker data files, transforming positional data into velocity
data, detecting gaze events like saccades and fixations, computing event
properties like saccade amplitude and fixational dispersion and visualizing
data and results with several types of plotting methods. Moreover,
_pymovements_ also provides an easily accessible interface for downloading and
processing publicly available datasets. Additionally, we emphasize how
rigorous testing in scientific software packages is critical to the
reproducibility and transparency of research, enabling other researchers to
verify and build upon previous findings.

eye movements, preprocessing, event detection, software packages, scientific
computing

††ccs: Applied computing Psychology

##  1\. Introduction

Eye movements are a valuable tool in understanding viewers’ or readers’
cognitive processes, state of mind, or other characteristics as they are
considered “a window to the mind and brain” (Van Gompel et al., 2007). They
are widely used across disciplines, including cognitive psychology,
linguistics, neuroscience, and human-computer interaction. Hence, eye tracking
methodology in general and the processing and analysis of eye tracking data in
particular is an interdisciplinary field of research that is essential for the
above mentioned disciplines.

Due to its ease of use and flexibility, Python has become a popular choice
among researchers for processing and analyzing eye movement data. In this
paper, we introduce a new Python package called _pymovements_ that provides a
set of tools for the processing and analysis of eye movement data.

Data preprocessing functionality of the _pymovements_ package includes
conversion between positional and velocity gaze data and detection of gaze
events like fixations and saccades by using dispersion-based and velocity-
based methods. Users can also plot eye movement data using various
visualization functions, including heatmaps and trace plots.

The _pymovements_ package also contains a small library of publicly available
datasets that can be downloaded using an accessible interface. The package is
designed to be extensible, with additional datasets expected to be added in
the near future. The source code is available online at
https://github.com/aeye-lab/pymovements and is licensed under the MIT License.

##  2\. Related Work

There exist numerous other Python packages and tools that can be used to
process or analyze eye movement data (Acland et al., 2016; Sogo, 2019; Kübler,
2020; Ghose and Srinivasan, 2021; Doucette, 2019). However, all these packages
lack thorough testing and a comprehensive documentation which are
prerequisites for trustworthy results in scientific research. In contrast,
_pymovements_ applies a rigorous testing scheme following best practices in
software engineering including an extensive documentation with assisting
tutorials.

Moreover, none of these packages are specifically optimized for performance.
_pymovements_ on the other hand leverages features from the _Polars_ dataframe
package, which is programmed in Rust and one of the fastest dataframe software
available (Gorecki, 2021).

Finally, the initiative to provide and maintain a library of publicly
available datasets with eye movement data is a distinguishing feature of
_pymovements_.

##  3\. Package Design

_pymovements_ is structured around a central module, the dataset module, which
provides a unified interface for working with eye movement datasets. This
module makes it easy to load eye movement data and save relevant results for a
given eye movement study. The dataset class provides access to the key
functionality needed for preprocessing: from transforming positional signals
into velocity signals, over detecting gaze events such as (micro-)saccades and
fixations, up to analyzing specific properties for detected events, such as
saccade amplitude or fixational dispersion.

The dataset class is very flexible to allow for a seamless integration of own
local datasets. Each dataset object holds recording session parameters, gaze
dataframes for raw eye gaze signals and event dataframes, which contain the
detected events within the eye gaze signals. These dataframes are organized in
a consistent manner, making it easy to work with multiple datasets and compare
results across studies.

_pymovements_ also provides a simple interface to access publicly available
datasets. Except for an example toy dataset, all these public datasets are not
part of the _pymovements_ package, but are definitions on where to find
dataset resources online with additional details on how to load the input data
to be consistent across several datasets. This implementation is aimed to be
simple enough to facilitate the inclusion of additional datasets, even to
researchers without any Python programming experience. The _pymovements_
package then automatically takes care of downloading the particular dataset.

##  4\. Documentation

_pymovements_ comes with a comprehensive online documentation that explains
each function and module in detail along with examples of typical usage. In
addition to this, we provide detailed and comprehensive step-by-step tutorials
that guide users through the entire data processing pipeline enabling them to
use _pymovements_ to its full potential. These tutorials cover key use cases
in eye movement data processing and are accompanied by a small example toy
dataset. The documentation is automatically generated from the source code and
uploaded to the web hoster with each new update, such that it always reflects
the most recent state of the package. For each update all examples and
tutorials are verified to run successfully and to produce the expected
results.

##  5\. Testing

Testing is one of the most important software development processes to
maintain high quality and consistency of the software. _pymovements_ has a
robust testing pipeline to ensure that additions to the codebase are
thoroughly tested and reviewed before being accepted. Every proposed change
must have at least one approving review to be incorporated and must pass all
existing tests and checks of the testing pipeline. We enforce a 100% test
coverage and a consistent coding style by obligatory linting and type
checking.

##  6\. Integration with Existing Software

The _pymovements_ package supports native integration with other Python
libraries, such as _Polars_ , _Pandas_ , _NumPy_ , and _Matplotlib_. All of
the obtained data during processing can be easily exported into commonly used
file formats such as CSV and Feather files. Furthermore, _pymovements_ is
compatible with the R programming language through the _reticulate_ package.
This means that researchers can use _pymovements’_ functionality within the R
environment, allowing for seamless integration with R’s extensive library of
statistical tools and visualization packages.

##  7\. Future Work

_pymovements_ is an evolving package that is continuously being improved and
expanded to meet the needs of researchers. We plan to add functionality to
allow researchers to analyze reading behavior and expand the package’s
capabilities by including visual stimuli such as image and video data into the
analysis pipeline.

To increase the versatility of the package, we plan to add more event
detection algorithms and public dataset definitions. Additionally, we are
working on adding parsing support for more eye trackers, enabling researchers
to process and analyze data from a wider range of eye-tracking systems.

##  8\. Broader Impact

One of the key benefits of _pymovements_ is its ability to unify the work
across different research groups working with eye movement preprocessing
pipelines. By providing a standardized rigorously tested interface,
_pymovements_ helps to ensure that analyses can be easily reproduced and
verified by other researchers, increasing the transparency and reliability of
eye movement research. Due to its permissive open-source license researchers
can contribute their own methods and datasets, increasing both the visibility
of their own work and the feature set of the software. _pymovements_ has thus
the potential to have a broad impact on the field of eye movement research,
facilitating greater collaboration and reproducibility across different
research groups.

###### Acknowledgements.

This work was partially funded by the German Federal Ministry of Education and
Research (grant 01IS20043) and is based upon work from COST Action MultiplEYE,
CA21131, supported by COST (European Cooperation in Science and Technology).

## References

  * (1)
  * Acland et al. (2016) Ben Acland, Tom Wallis, and orthographic-pedant. 2016\.  _cili: Cili v0.5.4_.  https://doi.org/10.5281/zenodo.48843
  * Doucette (2019) Amanda Doucette. 2019\.  _sideeye v1.0.0a13_.  https://pypi.org/project/sideeye/
  * Ghose and Srinivasan (2021) Upamanyu Ghose and Arvind Srinivasan. 2021.  _PyTrack-NTU v1.1.1_.  https://pypi.org/project/PyTrack-NTU/
  * Gorecki (2021) Jan Gorecki. 2021\.  Database-like ops benchmark.  https://h2oai.github.io/db-benchmark/
  * Kübler (2020) Thomas Kübler. 2020\.  _Perception-Engineers-Toolbox v0.2.3_.  https://pypi.org/project/Perception-Engineers-Toolbox/
  * Sogo (2019) Hiroyuki Sogo. 2019\.  _GazeParser v0.11.1_.  https://pypi.org/project/GazeParser/
  * Van Gompel et al. (2007) Roger P. G. Van Gompel, Martin H. Fischer, Wayne S. Murray, and Robin Hill (Eds.). 2007.  _Eye Movements: A Window on Mind and Brain_.  Elsevier Science Limited.


https://replicantlife.com

#  Metacognition is all you need?
Using Introspection in Generative Agents to Improve Goal-directed Behavior

Jason Toy Jason Toy, somatic.io -<EMAIL_ADDRESS>
Phil Tabor
Josh MacAdam, obvi Josh MacAdam  and Phil Tabor

Figure 1: Zombie Apocalypse Simulation

##  1 Introduction

Metacognition refers to the higher-order cognitive processes that involve
thinking about one’s own thinking. It encompasses a range of mental activities
related to monitoring, regulating, and organizing cognitive processes to
achieve specific goals. Metacognitive abilities enable individuals to reflect
on their knowledge, problem-solving strategies, and learning experiences and
therefore play a crucial role in shaping and modifying one’s habits. For
example, if one is studying for an exam, metacognitive processes might involve
setting goals, choosing appropriate study strategies, monitoring their
comprehension, and adjusting their approach if they are not understanding the
material.

The concept of System 1 and System 2 thinking, popularized by psychologist
Daniel Kahneman, provides a framework for understanding metacognition[1].
System 1 represents fast, automatic, and intuitive thinking, while system 2
involves slower, deliberate, and reflective thinking. In this framework,
metacognition can be thought of as a specific System 2 process that examines
actions from both System 1 and System 2 processing. Another analogy is system
1 is subconscious thinking and system 2 is conscious thinking (the voice you
hear in your head). Metacognition is a slow, expensive, and methodical thought
process and is therefore better suited for introspective or strategic
thinking, rather than immediate problem solving.

Metacognition in essence is "thinking about thinking" and requires the ability
to look at one’s own thoughts and thought processes from different points of
view. Reflection, on the other hand, is typically characterized as looking at
past experiences and deriving insights for future actions. Metacognition
allows one to adjust their thought process and strategy based on asking
relevant questions. Due to the dynamic nature of metacognition, no one
strategy will be set in stone. Metacognition typically involves asking oneself
different questions as a probing mechanism to further understand. Some
questions one may see: "What do I know about this topic?", "Why do I want to
achieve this goal?", "How can I monitor my progress towards my goal?", "How
can I adjust my strategy to overcome current challenges?", "Metacognition is
all you need?" etc. Metacognition is often applied to different types of
thinking such as: problem solving, goal setting, reflection, learning,
monitoring and evaluation, emotional regulation and other types of cognitive
processes. As artificial agents are usually given a specific task, we focus on
metacognition related to problem solving, monitoring, and evaluating progress
towards their specific task.

Recent work with large language models has incorporated human cognitive
processes into simulations of interacting generative agents tasked with
cooperating to achieve strategic objectives [2]. In particular, planning,
memory, and reflection have been implemented in an effort to elicit human-like
behaviors such as long term planning and cooperation among agents [3]. The
success of this work raises the question of what role metacognition may play
in further enhancing the believability of behaviors of generative agents.

##  2 Large Language Models with Cognitive Modules as Generative Agents

Multiple experiments have incorporated metacognition into computational
frameworks. [4] outlines a general computational architecture in lisp. [5]
provides a framework for autonomous vehicles that adds a metacognition layer
to monitor safety violations on top of generic reward accumulation.

[6] created a generic deep reinforcement learning (DRL) framework that
incorporates metacognition into traditional reinforcement learning frameworks.

[3] demonstrated that LLMs equipped with reflection, observation, and planning
modules on agents can successfully mimic believable human behavior in a
simulated town environment. Seeding the idea of an agent wanting to host a
valentine’s party resulted in the agent successfully organizing a party which
other agents discussed and attended.

We propose a metacognize module which allows agents to broadly contemplate
their circumstances in order to create alternative strategies and improve
performance. This subsumes the more tactical reflect and plan functions as
presented in [3]. We show through ablation that agents can learn to
continually adapt their strategies depending on the situation. Their overall
strategy for dealing with problems affects the specific actions they take.

Figure 2: Graphical representation of metacognition process.

##  3 Architecture

We implement many of the same modules from [3], with the addition of a group
of modules dubbed meta_cognize. As an agent progresses through the simulation,
it accumulates a history of observations, memories, and thoughts. Agents are
given goals but can optionally be left blank. When an agent starts towards its
goal, it is not given an explicit strategy to follow. Instead, each agent
periodically evaluates how it is progressing towards its goals by reviewing
memories, thoughts, and past actions. The agent assigns itself a numeric score
as well as a text statement for its reasoning for providing that score. This
evaluation is stored in its memory as a meta-thought.

If the agent finds that it is not making enough progress, the agent calls its
meta_cognize module. When metacognition occurs, the agent asks itself how it
might improve its performace in light of what it has learned. Additionally,
the agent will periodically self-generate new introspective questions to think
about its goals from different perspectives. For example, in the zombie
apocalypse scenario, an agent initially starts with no goal or strategy, but
after some time, we observe an agent contemplate these thoughts:

> “How can I survive this zombie apocalypse? What resources do I need? Where
> should I go for safety? How can I learn from both successes and failures to
> improve survival strategies? "

Depending on the current task and goals of the agent, those questions will
change over time, influencing how the agent responds and acts in the
environment. Agents have memory that is stored outside of the LLM, where each
memory stores content, timestamp, location, importance score, and type of
memory. Each time an agent reviews memories for higher cogntive function,
memories are ranked by relevance to the speficic question it is considering.
Relevance is calculated by cosine similarity of the question and memory
embeddings.

Agents have two kinds of memories, a short term and long term memory. Short
term memory stores a maximum of seven recent memories and is forgotten after
approximately 30 seconds, modeled after human short term memory[7]. Long term
storage memory is essentially unlimited and stored in system RAM. Due to
limited context window sizes, agents cannot process every memory when making
decisions. This is similar to human memory where we may store large amounts of
data, but only certain memories can be recalled at a time.

Our memory recall system can be seen as an agent optimized version of
Retrieval-Augmented Generation (RAG) [8]. Anytime an agent makes a decision,
relevant memories are retrieved to prime the agent on what to do. There are
several memory types such as observance memories like “John saw a cat” and
conversation memories like “John said ’How are you doing Paul?”. We explicitly
store metacognition memories where an agent looks at its past memories and
actions and asks a meta-question. That thought is stored as a meta-memory and
inserted into the memory stream of the agent. In future actions and
conversations, these meta-memories are recalled along with other memories to
prime the agent to think about these meta-thoughts when in conversation and
taking action. For each step in the simulation, we allow the agent to choose
an action from a list of possible actions which also includes the meta_cognize
function.

Figure 3: Graphical representation of the generative agent’s cognitive map.

##  4 Simulation Framework

To conduct these experiments we built a framework dubbed ReplicantLife, where
agents can be run standalone or within a simulated town environment.
ReplicantLife has a pluggable architecture which allows can utilize any
popular LLM with an http interface, including locally hosted models through
ollama. There is preliminary support for concurrency using threads.
Concurrency is limited by GPUs and LLM calls, so max concurrency should be set
to the total available GPUs. Feature flags are provided to toggle various
functionality including LLM call limits.

Each simulation is created through two JSON environment files which constitute
the world and the senario. The world file contains the layout of the map,
where static objects are, and boundaries of structures. The scenario files
describes the agents, their personalities, goals, locations, meta questions,
interview questions, and other attributes. All atttributes can be left out and
agents will be initialized with randomized values. Adding a new situation to
simulate can be added by defining a new scenario file.

Interview questions are used to evaluate agents at the end of a simulation.
Interview questions can be directed to all agents or specific agents. Agents
are asked to evaluate their performance with questions such as: "Did you
accomplish your goal?", "Who do you suspect is the murderer?" or "What did you
learn recently?". Code for the framework can be obtained at
https://replicantlife.com.

##  5 Experiments

We tested our simulation framework in a variety of different situations
including a Christmas party, zombie apocalypse, and murder mystery. In the
Christmas party simulation agents hosted a party where multiple other agents
were invited and arrived at the specified time to attend. This is similar to
the earlier work in generative agents[3] where agents had to coordinate a
similar social activity.

In the zombie apocalypse simulation, zombies are non playable characters that
are allowed to kill non-zombie agents. Agents initially have no goal but can
develop them over time. Zombies randomly walk and move towards non-zombie
agents when seen. Survivors most often self-discovered a strategy of hiding in
zombie-free areas. We found that in 73% of zombie scenarios, agents would not
survive.

In the murder mystery scenario, one agent is a murderer tasked with killing as
many agents as possible. Another agent is a detective, and other agents are
common bystanders. We found when using gpt3.5-turbo and GPT4, we could not use
prompts relating to simulated murder without heavily modifying prompts to
bypass safety mechanisms [9]. When using Mistral 7B[10] and other open models,
we had no prompt blocking issue.

Performance of our cognitive models is shown through ablation. Evaluation
metrics are composed of five criteria: believability (how believable and human
sounding do the conversations look), learning (are the agents learning over
time), individual goal performance (are agents are able to achieve their
goals), higher level cognitive performance (are agents observations and
conversations converting to higher level thoughts), and overall scenario
performance (how many agents survived the zombie apocalypse). We expect the
agents to meet new agents, learn about their preferences, learn new locations,
and obtain new knowledge through conversations. Additionally, they should pick
up new insights, draw conclusions from previous memories, and use these
insights for future actions.

To measure the performance, we opted not to use full human evaluations due to
resources. Instead we opted to use LLMS to assist us in evaluating
performance, a technique similary described as LLM-as-a-Judge in [11]. In
their paper, they found that using an LLM to judge evaluations is 80% in
agreement with human judges. We found in our own spot checking of evaluations
that LLM performance was just as good as a human judge. The majority of our
tests were run using Mistral 7B[10], but we also did extensive testing with
Phi1[12], Phi2[13] Llama2[14], Mixtral [15], GPT-3.5-turbo, GPT4 [16], and
other models. We standardized on Mistral due to its combination of speed,
small model size, and excellent performance. While we did build support for
ChatGPT models, we primarily focused on local LLMs for cost and performance
reasons. We built out test infrastucture to spin up LLM nodes on public GPU
clouds when needed for faster simulations.

To measure performance of our cognitive modules, we ran our scenarios 3 times
each for 1000 steps with different cognitive modules turned on. Our
experiments show that the metacognition module outperforms all other modules
by 33

Figure 4: Comparison of different cognitive modules turned on

We also did experiments with realtime systems. With a single agent, we were
able to cut down runtime to 2 seconds to process a full request on an RTX 4090
making metacognition generative agents suitable for near realtime systems.
With multiple agents, time grows linearly and with 25 agents a single step in
game time takes 50 seconds. We believe that multiple agents can be run in near
realtime with further optimizations.

##  6 Discussion

LLMs are being widely applied across a variety of domains, especially with
interactive agents and chatbots. Agents can elicit disparate functional
strengths of LLMs, and their orchestration can result in further higher-order
capabilities. The combination of LLMs with a metacognition module allows
agents to monitor and adjust strategies to deal with changes that occur over
time. This allows for much more powerful agents.

###  6.1 Use Cases

These agents have been developed to work in simulation or used standalone. We
see generative agents having widespread use and potential as there is already
widespread testing of LLMs nearly every industry.

In the field of psychology, generative agents are being tested to assist
individuals in addressing personal problems through conversational
interactions. Educational applications involve chatbots that adapt to user
preferences, tailoring the learning experience over time. Several companies
have integrated chatbots into user-facing customer interactions, such as
support chats and customer success conversations.

Multiple organizations are testing generative agents to create friends,
companions, and romantic partners to interact with humans.

For generative agents to be successful, they must be believable by acting
smarter and able to make similar decisions to a human. Generative agents that
have access to their own internal thoughts to improve their actions could
potentially improve the realism of human-agent and agent-agent interactions.
Unlike humans, these agents operate within a constrained scope, deprived of
access to a substantial portion of human sensory data including the nuanced
sense of touch. Current integrations of LLMs including ours is a "text in,
text out" interface. So all interactions with the world must be converted to
text descriptions than an LLM can understand, and then output to a text format
that software can interpret. Moreover an absence of tactile perception
restricts their ability to comprehend and respond to the physical world in a
manner analogous to human experiences. Given these inherent limitations, it
becomes imperative to approach interactions with generative agents with a
discerning awareness of their boundaries. There is notable progress in
multimodal models being combined with vision such as GPT4-V and LLaVA [17]
that give LLMs the ability to process images along with text.

####  6.1.1 Interactive Media

As generative AI enters mainstream computation, their use in visual media and
video games is increasing rapidly. The integration of generative agents with
metacognition modules holds significant promise in interactive story telling
and video games to offer immersive and dynamic gaming experiences.

Incorporating generative agents with metacognition into non-player characters
(NPCs) can dynamically adapt their strategies within the gaming environment.
As players navigate through diverse and unpredictable scenarios, the agents
can observe and analyze their own decision-making processes, leading to real-
time adjustments in gameplay strategies and developing unique behaviors over
time. This adaptability enhances the overall gaming experience, making it more
challenging and engaging for players while also creating more immersive and
realistic virtual worlds. These dynamic responses also allow agents to
influence the storyline providing players with a dynamic and responsive
storytelling experience.

####  6.1.2 Simulation

Generative Agents inside a simulation engine can be used for testing and
simulating both personal and business cases. Generative agents can serve as
valuable tools in personal development simulations. Individuals can engage in
simulated conversations to enhance communication skills, receive constructive
feedback, and practice decision-making in various scenarios. The metacognition
module allows the agent to adapt its coaching strategies based on the user’s
progress, providing personalized and effective self-improvement experiences.

Agents could also be deployed as teachers for education and training purposes
where the agent tailors its teaching method based on the individual’s learning
style and progress.

For businesses, generative agents have a broad range of potential
applications. In one paper from [2], the authors create teams of generative
agents with the goal of simulating typical software development process.
Agents work together to write specifications, write software, and doing
quality assurance testing to build products for end users.

###  6.2 Future Directions

With our current metacognition implementation, we built a base framework that
shows increased performance of generative agents to achieve their tasks. We
believe our architect can be improved along several dimensions.

####  6.2.1 Improved memory retrieval

We found several issues with our memory structure that could be improved.
Through our experimentation, we observed that when employing cosine similarity
for vector comparison, numerous memories that should be related were, in fact,
not pertinent.

In high dimensional spaces, vectors that are similar may not be sementically
related. Returning irrelavent memories would effect the output of the LLM and
in turn the actions the agent takes. Cosine similarity is what is used in
almost all RAG[8] implementations and so many of these systems will
potentially have similar issues of non-relevant context being included.
Changing out embedding models could improve performance, but the cosine
similarity issue would still remain. As recently adopted in [18], improvements
can be made to relevance scoring by searching a database based on the LLM’s
output embedding and employing a K-nearest neighbors (KNN) search algorithm.
This process selectively adjusts the output embedding vector prior to token
generation. This reverse sequence of operations, wherein LLM embeddings are
utilized, has demonstrated superior performance compared to existing methods
like RAG, as reported in the literature. Retrieving more relevant memories
would likely improve performance in all elements of the system. Sometimes when
someone has a thought about a topic, other seemingly unrelated thoughts may
appear. So in some sense, this may not be a big problem. Further experiments
would have us test different memory augmentation and retrieval models.

Figure 5: Coordinate Representations in the Brain

####  6.2.2 Inference Speed

Testing with smaller models produced inferior results. We believe with time
spent on prompt tuning, smaller models may still work efficiently and provide
an improvement in inference speed. We would focus on Phi2 and TinyLLama [19],
as initial tests showed promising results.

We also explored different inference engines. We tested PowerInfer [20], an
inference engine that exploits high locality in LLM inference. The authors
convert common models that use ReLU into another format that uses another
predictive model to read the input query and selectively choose which neurons
to activate. In effect, this reduces the total amount of neurons and
computation needed to process a prompt. We did not see speed improvements on
the models we tested with. We also tested with vLLM from [21], an inference
engine that uses PagedAttention and saw a 35% speed increase when using
concurrency, but further testing is needed. We would want to continue testing
with other models, different concurrency systems, and inference speed up
techniques to get large simulations to run in realtime. Large groups of
simulated agents on non-cloud based machines could be interesting for sandbox
games and simulations.

####  6.2.3 Model optimization

Improving models is not just about performance: we are also interested in
accuracy and sophistication of responses. Better responses often require a
tradeoff with performance as sophisticated responses typically require more
data and larger context windows. We have been constrained by GPU memory as we
primarily tested on an RTX 4090 with 24 GB of RAM and would like to test with
larger models. Another future test would have us dynamically switch out models
for different tasks where we use as many smaller models as possible and
reserve larger computations for larger models. For example, Phi2, a 2.7
million parameter model uses only 1.7 GB of RAM. Phi2 could be used for
simpler prompts such as scoring memory importance, while a larger model such
as Llama2 could be reserved for metacognition functions. In [22], the authors
trained a hybrid LLM that is able to route queries to different LLMs resulting
in up to 40% fewer calls. Another approach is to finetune a smaller foundation
model that would be optimized for chat and simulations.

####  6.2.4 Broader Metacognition abilities

Our current model predominantly focuses on metacognition in the context of
immediate goal achievement. However, metacognitive processes extend well
beyond this scope, encompassing a diverse range of aspects such as emotional
wellbeing, balancing overarching life goals with immediate objectives,
knowledge management, effective time management, adapting to various learning
styles, among other aspects.

The complexity and diversity of metacognitive processes in humans are
evidenced by the extensive efforts dedicated to understanding and optimizing
these processes. This is exemplified by the growing self-help book industry,
which aims to aid individuals in developing effective mental frameworks for
improved life management.

Further research would be directed towards developing a more broader
metacognition framework that would enable an agent to inspect and modify any
part of its cognitive processes. We have laid the groundwork necessary to
allow the agent to focus on various metacognitive processes. Future
experiments would have us guide agents to use different metacognitive
processes and inspect if they adopt them sufficiently such as time management
in a busy schedule or decision making in the context of multiple conflicting
goals.

####  6.2.5 Metacognition directly in a LLM

Our current implementation of metacognition uses Python to essentially graft
on metacogntion on top of an LLM. Future investigations may delve into
building metacognition like capabilities directly into the LLM, allowing them
to introspect and enhance their own decision-making processes. This
introspective capability could contribute potentially paving the way for more
adaptive and self-aware systems. One interesting view of the human brain is as
a coordinate transformation engine: “A brain is a well-designed machine for
the frame conversion to internalize the external world” [23], “the egocentric
representations of the primary sensory cortical areas must be transformed into
an allocentric representation in the hippocampus, and then transformed back to
an egocentric motor representation for behavioral output” [24], and “Our
findings provide compelling evidence that the reference frame of neural
representations is not static and can be powerfully modulated by task
instructions.” [25]. The human brain has been found to store over 10 different
coordinate representations along with orientations or points of view, such as
allocentric and egocentric orientations.

Seen through this lens, metacognition can be thought of as neural synapse
activity being transformed to other coordinate systems for further inspection.
One interesting candidate for this type of computation is the grid cell,
located in the Entorhinal Cortex of mammals. The discovery of grid cells led
to a Nobel Prize in medicine in 2014. Grid cells exhibit scale-invariant
firing patterns, meaning that the same cells can represent generalization of
spatial and non-spatial information across various contexts[26].

Research by [27], [28], and others has sought to integrate grid cell
computation into neural network architectures. The transformer architecture
[29] is what powers LLMs. In a paper from [30], the authors have shown that
when a small modification is made to the transformer architecture, they learn
and act like grid cells.

Our hypothesis posits that by adapting the underlying architecture to
accommodate more dynamic representation transformations, a neural network can
be trained to facilitate metacognitive processes. Achieving this would likely
involve formulating a hybrid objective function wherein the model learns to
not only predict the next token, but also to evaluate the token’s quality in
relation to the input query.

##  7 Conclusion

We show that metacognition significantly improves performance for task
oriented generative agents. Furthermore, we illustrate the potency of
combining large language models with traditional programming methods as
effective tools for prototyping cognitive systems.

As generative agents integrated with metacogntive abilities approach ubiquity
in daily human life, taking on increasingly sophisticated tasks, their
proliferation across diverse domains marks a paradigm shift in both lay human-
computer interactions and programmer-computer interactions. This shift paves
the way for the emergence of more intelligent, adaptive, and context-aware
systems. With these advancements in mind, the strategic interplay of
metacognition, LLMs, and traditional programming methodologies emerges as a
powerful technique for the productionization of intelligent generative agents.

While metacognition and system 2 thinking are often hailed as the pinacle of
human intelligence, achieving human-level intelligence in computers remains an
elusive and unsolved goal. As humans are the sole known species capable of
metacognition, further exploration of this dynamic cognitive process becomes a
compelling and promising avenue for advancing progress in Artificial General
Intelligence.

## References

  * [1] Daniel Kahneman  “Thinking, fast and slow”  Macmillan, 2011
  * [2] Chen Qian et al.  “Communicative Agents for Software Development”, 2023  arXiv:2307.07924 [cs.SE]
  * [3] Joon Sung Park et al.  “Generative Agents: Interactive Simulacra of Human Behavior”, 2023  arXiv:2304.03442 [cs.HC]
  * [4] Michael Cox et al.  “Computational Metacognition”, 2022  arXiv:2201.12885 [cs.AI]
  * [5] Aquib Mustafa, Majid Mazouchi, Subramanya Nageshrao and Hamidreza Modares  “Assured Learning-enabled Autonomy: A Metacognitive Reinforcement Learning Framework”, 2021  arXiv:2103.12558 [cs.AI]
  * [6] Paul M. Krueger, Falk Lieder and Thomas L. Griffiths  “Enhancing metacognitive reinforcement learning using reward structures and feedback” These authors contributed equally.  In _Department of Psychology, University of California Berkeley_ , 2022  URL: https://cocosci.princeton.edu/papers/Accelerating_Metacognitive_RL-CameraReady.pdf
  * [7] George A. Miller  “The magical number seven plus or minus two: some limits on our capacity for processing information”, 1956  eprint: https://pubmed.ncbi.nlm.nih.gov/13310704/
  * [8] Patrick Lewis et al.  “Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks”, 2021  arXiv:2005.11401 [cs.CL]
  * [9] Pittawat Taveekitworachai et al.  “Breaking Bad: Unraveling Influences and Risks of User Inputs to ChatGPT for Game Story Generation”  In _Interactive Storytelling_ Cham: Springer Nature Switzerland, 2023, pp. 285–296
  * [10] Albert Q. Jiang et al.  “Mistral 7B”, 2023  arXiv:2310.06825 [cs.CL]
  * [11] Lianmin Zheng et al.  “Judging LLM-as-a-Judge with MT-Bench and Chatbot Arena”, 2023  arXiv:2306.05685 [cs.CL]
  * [12] Yuanzhi Li et al.  “Textbooks Are All You Need II: phi-1.5 technical report”, 2023  arXiv:2309.05463 [cs.CL]
  * [13] Marah Abdin et al.  “Phi-2: The surprising power of small language models” https://www.microsoft.com/en-us/research/blog/phi-2-the-surprising-power-of-small-language-models/ In _Microsoft Research Blog_ , 2023
  * [14] Hugo Touvron et al.  “Llama 2: Open Foundation and Fine-Tuned Chat Models”, 2023  arXiv:2307.09288 [cs.CL]
  * [15] Albert Q. Jiang et al.  “Mixtral of Experts”, 2024  arXiv:2401.04088 [cs.LG]
  * [16] OpenAI et al.  “GPT-4 Technical Report”, 2023  arXiv:2303.08774 [cs.CL]
  * [17] Haotian Liu, Chunyuan Li, Yuheng Li and Yong Jae Lee  “Improved Baselines with Visual Instruction Tuning”  arXiv:2310.03744, 2023
  * [18] Sewon Min et al.  “SILO Language Models: Isolating Legal Risk In a Nonparametric Datastore”, 2023  arXiv:2308.04430 [cs.CL]
  * [19] Peiyuan Zhang, Guangtao Zeng, Tianduo Wang and Wei Lu  “TinyLlama: An Open-Source Small Language Model”, 2024  arXiv:2401.02385 [cs.CL]
  * [20] Yixin Song, Zeyu Mi, Haotong Xie and Haibo Chen  “PowerInfer: Fast Large Language Model Serving with a Consumer-grade GPU”, 2023  arXiv:2312.12456 [cs.LG]
  * [21] Woosuk Kwon et al.  “Efficient Memory Management for Large Language Model Serving with PagedAttention”  In _Proceedings of the ACM SIGOPS 29th Symposium on Operating Systems Principles_ , 2023
  * [22] Anonymous  “Hybrid LLM: Cost-Efficient and Quality-Aware Query Routing” under review  In _Submitted to The Twelfth International Conference on Learning Representations_ , 2023  URL: https://openreview.net/forum?id=02f3mUtqnM
  * [23] Katsushi Arisaka  “Grand unified theory of mind and brain-part i: Space-time approach to dynamic connectomes of c. elegans and human brains by mepmos”, 2022
  * [24] Peter Byrne, Suzanna Becker and Neil Burgess  “Remembering the past and imagining the future: A neural model of spatial memory and imagery”  In _Psychological Review_ 114.2, 2007, pp. 340–375  DOI: 10.1037/0033-295X.114.2.340
  * [25] R. Sasaki, A. Anzai and D.. Angelaki  “Flexible coding of object motion in multiple reference frames by parietal cortex neurons”  In _Nature Neuroscience_ 23.8, 2020, pp. 1004–1015  DOI: 10.1038/s41593-020-0656-0
  * [26] Jason Toy  “Grid cells and their potential application in AI”, 2022  arXiv:2210.12068 [q-bio.NC]
  * [27] Andrea Banino et al.  “Vector-based navigation using grid-like representations in artificial agents”  In _Nature_ 557.7705, 2018, pp. 429–433
  * [28] Niels Leadholm, Marcus Lewis and Subutai Ahmad  “Grid Cell Path Integration For Movement-Based Visual Object Recognition”, 2021  arXiv:2102.09076 [cs.AI]
  * [29] Ashish Vaswani et al.  “Attention Is All You Need”, 2017  arXiv:1706.03762 [cs.CL]
  * [30] James C.. Whittington, Joseph Warren and Tim E.J. Behrens  “Relating transformers to models and neural representations of the hippocampal formation” One-sentence Summary: Transformers learn brain representations and they are algorithmically related to models of the hippocampal formation.  In _International Conference on Learning Representations (ICLR)_ , 2022  URL: https://openreview.net/forum?id=B8DVo9B1YE0


# A New Neural Network Architecture Invariant
to the Action of Symmetry Subgroups

Piotr Kicki  Piotr Skrzypczyński
Institute of Robotics and Machine Intelligence
Poznan University of Technology, Poznań, Poland
<EMAIL_ADDRESS>
&Mete Ozay
<EMAIL_ADDRESS>

###### Abstract

We propose a computationally efficient $G$-invariant neural network that
approximates functions invariant to the action of a given permutation subgroup
$G\leq S_{n}$ of the symmetric group on input data. The key element of the
proposed network architecture is a new $G$-invariant transformation module,
which produces a $G$-invariant latent representation of the input data.
Theoretical considerations are supported by numerical experiments, which
demonstrate the effectiveness and strong generalization properties of the
proposed method in comparison to other $G$-invariant neural networks.

##  1 Introduction

The design of probabilistic models which reflect symmetries existing in data
is considered an important task following the notable success of deep neural
networks, such as convolutional neural networks (CNNs) [3] and PointNet [7].
Models with superior performance can be obtained using prior knowledge about
data and desired properties of the models, such as permutation invariance [7].
Similarly, translation equivariance can be exploited for CNNs [2] to reduce
their model size.

Nevertheless, researchers have been working on developing a general approach
which enables to design architectures that are invariant and equivariant to
the actions of particular groups. Invariance and equivariance of learning
models to actions of various groups have been discussed in the literature [1,
4, 8, 10]. However, in this paper, we only consider invariance to permutation
groups $G$, which are the subgroups of the symmetric group $S_{n}$ of all
permutations on a finite set of $n$ elements, as it covers many interesting
applications.

Figure 1: An illustration of employment of the proposed $G$-invariant neural
network $\Gamma$ for estimation of area of quadrangles. If the consecutive
vertices are provided in the same order (e.g. $[C\,D\,B\,A]$ or
$[A\,B\,C\,D]$), then the network $\Gamma$ computes the same area $P_{1}$.
However, if the order changes (i.e. $[A\,C\,B\,D]$), then the network $\Gamma$
estimates a different area $P_{2}$.

Figure 2: An illustration of the proposed $G$-invariant neural network. An
input $x$ is processed by the $G$-invariant transformation (blue), which
produces a $G$-invariant representation of the input. Then, the $G$-invariant
representation is passed to the Multi Layer Perceptron which produces the
output vector $\Gamma(x)$.

An example of the employment of the proposed $G$-invariant network for a set
of quadrangles is illustrated in Figure 1. The network $\Gamma$ receives a
matrix representation of the quadrangles (i.e. a vector of 4 points on a
plane) and outputs the areas covered by those quadrangles. One can spot that,
no matter which point will be given first, if the consecutive vertices are
provided in the right order, then the area of the figure will remain the same.
Such a property can be described by $G$-invariance, where
$G=(1234)$111$G=(1234)$ denotes a group $G$ generated by the permutation
$(1234)$, in which the first element is replaced by the second, the second by
the third and so on, till the last element being replaced by the first one..

Recently, Maron et al. [5] proposed a $G$-invariant neural network
architecture for some finite subgroups $G\leq S_{n}$, and proved its
universality. Unfortunately, their solution is intractable for larger inputs
and groups, because of the rapidly growing size of tensors and the number of
operations needed for forward and backward passes in the network.

The aim of this paper is to propose a method that enables us to design a novel
$G$-invariant architecture for a given finite group $G\leq S_{n}$, which is
tractable and generalizes well.

##  2 Our Proposed G-invariant Neural Network Architecture

We introduce a novel $G$-invariant neural network architecture, which exploits
the theory of invariant polynomials to achieve a flexible scheme for
$G$-invariant transformation of data for some known and finite group $G\leq
S_{n}$, where $S_{n}$ is a symmetric group and $|G|=m$. We assume that an
input $x\in\mathbb{R}^{n\times n_{in}}$ to the proposed network is a
tensor222We use matrix notation to denote tensors in this paper.
$x=[x_{1}\,x_{2}\,\dots\,x_{n}]^{T}$ of $n$ vectors
$x_{i}\in\mathbb{R}^{n_{in}}$, ${i=1,2,\ldots,n}$. A function
$f:\mathbb{R}^{n\times n_{in}}\rightarrow\mathbb{R}$ is $G$-invariant if $f$
satisfies333$\displaystyle\mathop{{\forall}}_{y\in Y}P(Y)$ means that
“predicate $P(Y)$ is true for all $y\in Y$”.

$\displaystyle\mathop{{\forall}}_{x\in\mathbb{R}^{n\times
n_{in}}}\displaystyle\mathop{{\forall}}_{g\in G}\,f\left(g(x)\right)=f(x),$
(1)

where the action of the group element $g$ on $x$ is defined by

$g(x)=\\{x_{\sigma_{g}(1)},x_{\sigma_{g}(2)},\dots,x_{\sigma_{g}(n)}\\},$ (2)

where $\sigma_{g}(i)$ denotes the action of the group element $g$ on the
specific index $i$ and $x_{\sigma_{g}(i)}\in\mathbb{R}^{n_{in}}$.

Our proposed $G$-invariant neural network is illustrated in Figure 2, and
defined by a function ${\Gamma:\mathbb{R}^{n\times
n_{in}}\rightarrow\mathbb{R}^{n_{out}}}$ of the following form

$\Gamma(x)=f_{out}(\Sigma\Pi(f_{in}(x))),$ (3)

where $f_{in}$ is a $G$-equivariant input transformation function, $\Sigma\Pi$
is a function which comprises $G$-invariant transformation when combined with
$f_{in}$, and $f_{out}$ is an output transformation function. The general idea
of the proposed architecture is to define a $G$-invariant transformation,
which uses the sum of $G$-invariant polynomials ($\Sigma\Pi$) of $n$
variables, which are the outputs of $f_{in}$. This transformation produces a
$G$-invariant feature vector, which is processed by another function $f_{out}$
that is approximated by a Multi-Layer Perceptron.

First, let us define the $G$-equivariant input transformation function
$f_{in}:\mathbb{R}^{n\times n_{in}}\rightarrow\mathbb{R}^{n\times n\times
n_{mid}}$, where $n_{mid}$ is the size of the feature vector. This function
can be represented as a vector ${\Phi=[\phi_{1}\,\phi_{2}\,\dots\,\phi_{n}]}$
of neural networks, where each function
$\phi_{i}:\mathbb{R}^{n_{in}}\rightarrow\mathbb{R}^{n_{mid}}$ is applied on
all elements of the set of input vectors $\\{x_{i}\\}_{i=1}^{n}$, and
transforms them to the $n_{mid}$ dimensional vector. As a result, the
operation of the $f_{in}$ function can be formulated by

$f_{in}(x)=\begin{bmatrix}\Phi(x_{1})\\\ \Phi(x_{2})\\\ \vdots\\\
\Phi(x_{n})\\\
\end{bmatrix}=\begin{bmatrix}\phi_{1}(x_{1})&\ldots&\phi_{n}(x_{1})\\\
\vdots&\ddots&\vdots\\\ \phi_{1}(x_{n})&\ldots&\phi_{n}(x_{n})\\\
\end{bmatrix}.$ (4)

One can see that $f_{in}(x)$ is $G$-equivariant, since the action of the
vector $\Phi$ of functions is the same for each element of the vector $x$,
thus it transposes the rows of the matrix form (4) according to $g\in G$,
which is equivalent to transposing the rows after the calculation of
$f_{in}(x)$.

Second, we define the function $\Sigma\Pi:\mathbb{R}^{n\times n\times
n_{mid}}\rightarrow\mathbb{R}^{n_{mid}}$, which constructs $G$-invariant
polynomials of outputs obtained from $f_{in}$, by

$\Sigma\Pi(x)=\sum_{g\in G}\prod_{j=1}^{n}x_{\sigma_{g}(j),j}.$ (5)

To see the $G$-invariance of $\Sigma\Pi(f_{in}(x))$, we substitute $x$ from
(5) with (4) to obtain

$\Sigma\Pi(f_{in}(x))=\sum_{g\in
G}\prod_{j=1}^{n}\phi_{j}(x_{\sigma_{g}(j)}).$ (6)

Then, we can show that (6) is $G$-invariant by checking whether (1) holds for
any input $x$ and any group element $g^{\prime}\in G$ as follows:

$\Sigma\Pi(g^{\prime}(f_{in}(x)))=\sum_{g\in
G}\prod_{j=1}^{n}\phi_{j}(x_{\sigma_{g^{\prime}}(\sigma_{g}(j))})=\sum_{g\in
G}\prod_{j=1}^{n}\phi_{j}(x_{\sigma_{g}(j)})=\Sigma\Pi(f_{in}(x))$ (7)

since any group element acting on the group leads to the group itself. The
product operation employed in (5)-(7) is performed element-wise. We define the
output function $f_{out}:\mathbb{R}^{n_{mid}}\rightarrow\mathbb{R}^{n_{out}}$
following the structure of a typical fully connected neural network by

$f_{out}(x)=\sum_{i=1}^{N}c_{i}\sigma\left(\sum_{j=1}^{n_{mid}}w_{ij}x_{j}+h_{i}\right),$
(8)

where $N\in\mathbb{N}_{+}$ is a parameter, $\sigma$ is a non-polynomial
activation function and $c_{i},w_{ij},h_{i}\in\mathbb{R}$ are coefficients. We
elucidate the universality of our $G$-Invariant network in the next
proposition444The proof of the proposition is given in the supplemental
material..

######  Proposition 1.

The network function (3), can approximate any $G$-invariant function
$f:V\rightarrow\mathbb{R}$, where $V$ is a compact subset of
$\mathbb{R}^{n\times n_{in}}$ and $G\leq S_{n}$ is a finite group, as long as
number of features $n_{mid}$ obtained at the output of input transformation
network $f_{in}$ is greater than or equal to the size $N_{inv}$ of the
generating set $\mathcal{F}$ of polynomial $G$-invariants.

##  3 Experimental Analysis

We evaluate the accuracy of the proposed architecture and analyze its
invariance properties in the following two tasks555The code is available on
https://github.com/Kicajowyfreestyle/G-invariant:

(i) $G$-invariant Polynomial Regression: The goal of this task is to train a
model to approximate a $G$-invariant polynomial. In the experiments, we
consider various polynomials:
$P_{\mathbb{Z}_{k}},P_{S_{k}},P_{D_{2k}},P_{A_{k}}$ and $P_{S_{k}\times
S_{l}}$, which are invariant to the cyclic group $\mathbb{Z}_{k}$, permutation
group $S_{k}$, dihedral group $D_{2k}$, alternating group $A_{k}$ and direct
product of two permutation groups $S_{k}\times S_{l}$, respectively. To
examine generalization abilities of models of the proposed $G$-invariant
network architecture, they were trained using only 16 different random points
in $[0;1]^{5}$, whereas 480 and 4800 randomly generated points were used for
validation and testing, respectively.

(ii) Estimation of the Area of Convex Quadrangles: In this task, models are
trained to estimate areas of convex quadrangles. An input is a vector of 4
points lying in $\mathbb{R}^{4\times 2}$, each described by its $x$ and $y$
coordinates. The desired estimator is a simple example of the $G$-invariant
function, where $G$ is identified by $\mathbb{Z}_{4}=(1234)$. Both training
and validation set contains 256 examples (randomly generated convex
quadrangles with their areas), while the test dataset contains 1024 examples.

###  3.1 Compared Architectures and Models

All of the experiments presented below consider networks of different
architectures for which the number of weights was fixed at a similar level for
the given task for a fair comparison. The employed architectures are the
following:

  * •

FC $G$-avg: Fully connected (FC) neural network with group averaging,

  * •

Conv1D $G$-avg: 1D convolutional neural network with group averaging,

  * •

FC $G$-inv: $G$-invariant neural network (3) implementing $f_{in}$ using a FC
neural network,

  * •

Conv1D $G$-inv: $G$-invariant neural network (3) implementing $f_{in}$ using
1D CNN,

  * •

Maron: $G$-invariant network proposed in [5].

Table 1: Mean absolute errors (MAEs) [$10^{-2}$] of the compared $G$-invariant models for the task of $G$-invariant polynomial regression. Network | Train | Validation | Test |  #Weights [$10^{3}$]
---|---|---|---|---
FC $G$-avg |  15.15 $\pm$ 5.49 |  16.48 $\pm$ 0.73 |  16.89 $\pm$ 0.76 | 24.0
$G$-inv (ours) |  2.65 $\pm$ 0.91 |  7.32 $\pm$ 0.55 |  7.46 $\pm$ 0.56 | 24.0
Conv1D $G$-avg |  8.98 $\pm$ 6.39 |  11.43 $\pm$ 4.29 |  11.78 $\pm$ 4.79 | 24.0
Conv1D $G$-inv (ours) | 0.87 $\pm$ 0.12 | 2.57 $\pm$ 0.37 | 2.6 $\pm$ 0.4 | 24.0
Maron |  2.41 $\pm$ 0.82 |  5.74 $\pm$ 1.19 |  5.93 $\pm$ 1.18 | 24.2

###  3.2 Results for $\mathbb{Z}_{5}$-invariant Polynomial Regression

The accuracy of the examined models is given in Table 1. We observe that our
proposed Conv1D $G$-inv outperforms all of the other architectures on both
datasets. Both Maron and FC $G$-inv obtain worse MAE, but they significantly
outperform the Conv1D $G$-avg and FC $G$-avg. Moreover, those architectures
obtain large standard deviations for the training dataset, because sometimes
they converge to different error values. In contrast, the performance of the
$G$-inv based models and the Maron model is relatively stable under different
weight initialization. While the results are similar for our architecture and
the approach introduced in [5], the number of computations used by the Maron’s
model is significantly larger666See supplementary material for more detailed
analysis.. The inference time for both networks differs notably, and equals
$2.3\pm 0.4$ms for Conv1D $G$-inv and $21.4\pm 1.5$ms for Maron.

Table 2: Mean absolute errors (MAEs) [$10^{-3}\text{unit}^{2}$] of the compared $G$-invariant models for the task of convex quadrangle area estimation. Network | Train | Validation | Test | #Weights
---|---|---|---|---
FC $G$-avg |  7.0 $\pm$ 0.6 |  9.6 $\pm$ 1.0 |  9.4 $\pm$ 0.9 | 1765
$G$-inv (ours) |  7.4 $\pm$ 0.4 |  8.0 $\pm$ 0.3 |  8.3 $\pm$ 0.5 | 1785
Conv1D $G$-avg |  16.9 $\pm$ 7.7 |  16.8 $\pm$ 5.3 |  18.5 $\pm$ 6.8 | 1667
Conv1D $G$-inv (ours) | 6.0 $\pm$ 0.3 | 7.3 $\pm$ 0.3 | 7.5 $\pm$ 0.5 | 1673
Maron |  13.9 $\pm$ 0.9 |  22.3 $\pm$ 1.2 |  23.4 $\pm$ 1.3 | 1802

###  3.3 Results for Estimation of Areas of Convex Quadrangles

The accuracy of the examined models is reported in Table 2. The results show
that the model utilizing the approach presented in this paper obtains the best
performance on all three datasets. Furthermore, it generalizes much better to
the validation and test dataset than any other tested approach. We observe
that, besides the proposed $G$-invariant architecture, the only approach which
was able to reach a low level of MAE in the polynomial approximation task
(Maron) is unable to accurately estimate the area of the convex quadrangle.

##  4 Conclusion

In this paper, we have proposed a novel $G$-invariant neural network
architecture that uses two standard neural networks, connected with the
proposed Sum-Product Layer denoted by $\Sigma\Pi$. We conducted two
experiments to analyze the accuracy of the proposed $G$-invariant architecture
in comparison with the other $G$-invariant architectures proposed in the
literature. The results demonstrate that the proposed $G$-invariant neural
network outperforms all other approaches in both tasks. We believe that the
proposed $G$-invariant neural networks can be employed by researchers to learn
group invariant models efficiently in various applications in machine
learning, computer vision and robotics. In the future work, we plan to apply
the proposed networks for various tasks in computer vision and robot learning,
which require vector map processing using the geometric structure of data.

## Acknowledgments and Disclosure of Funding

This research was partially supported by TAILOR, a project funded by EU
Horizon 2020 research and innovation program under GA No. 952215.

## References

  * [1] Taco Cohen, Mario Geiger, and Maurice Weiler.  A general theory of equivariant cnns on homogeneous spaces.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 9142–9153. Curran Associates, Inc., 2019.
  * [2] Taco Cohen and Max Welling.  Group equivariant convolutional networks.  In Maria Florina Balcan and Kilian Q. Weinberger, editors, Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 2990–2999, New York, New York, USA, 20–22 Jun 2016. PMLR.
  * [3] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton.  Imagenet classification with deep convolutional neural networks.  In Advances in Neural Information Processing Systems 25, pages 1097–1105. Curran Associates, Inc., 2012.
  * [4] D. Laptev, N. Savinov, J. M. Buhmann, and M. Pollefeys.  Ti-pooling: Transformation-invariant pooling for feature learning in convolutional neural networks.  In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 289–297, 2016.
  * [5] Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman.  On the universality of invariant networks.  CoRR, abs/1901.09342, 2019.
  * [6] Allan Pinkus.  Approximation theory of the MLP model in neural networks.  Acta Numerica, 8:143–195, 1999.
  * [7] Charles R Qi, Hao Su, Kaichun Mo, and Leonidas J Guibas.  Pointnet: Deep learning on point sets for 3d classification and segmentation.  arXiv preprint arXiv:1612.00593, 2016.
  * [8] Siamak Ravanbakhsh, Jeff Schneider, and Barnabás Póczos.  Equivariance through parameter-sharing.  In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 2892–2901. PMLR, 06–11 Aug 2017\.
  * [9] Dmitry Yarotsky.  Universal approximations of invariant maps by neural networks.  CoRR, abs/1804.10306, 2018.
  * [10] Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander J Smola.  Deep sets.  In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems 30, pages 3391–3401. Curran Associates, Inc., 2017.

##  5 Supplementary Material

For consistency, we first provide our proposed G-invariant neural network
architecture in the next section. Then, we give the the proof the Proposition
1.

###  5.1 Our Proposed G-invariant Neural Network Architecture

We introduce a novel $G$-invariant neural network architecture, which exploits
the theory of invariant polynomials to achieve a flexible scheme for
$G$-invariant transformation of data for some known and finite group $G\leq
S_{n}$, where $S_{n}$ is a symmetric group and $|G|=m$.

We assume that an input $x\in\mathbb{R}^{n\times n_{in}}$ to the proposed
network is a tensor777We use matrix notation to denote tensors in this paper.
$x=[x_{1}\,x_{2}\,\dots\,x_{n}]^{T}$ of $n$ vectors
$x_{i}\in\mathbb{R}^{n_{in}},i=1,2,\ldots,n$. A function
$f:\mathbb{R}^{n\times n_{in}}\rightarrow\mathbb{R}$ is $G$-invariant if $f$
satisfies

$\displaystyle\mathop{{\forall}}_{x\in\mathbb{R}^{n\times
n_{in}}}\displaystyle\mathop{{\forall}}_{g\in G}\,f\left(g(x)\right)=f(x),$
(9)

where888$\displaystyle\mathop{{\forall}}_{y\in Y}P(Y)$ means that “predicate
$P(Y)$ is true for all $y\in Y$”. the action of the group element $g$ on $x$
is defined by

$g(x)=\\{x_{\sigma_{g}(1)},x_{\sigma_{g}(2)},\dots,x_{\sigma_{g}(n)}\\},$ (10)

where $\sigma_{g}(i)$ denotes the action of the group element $g$ on the
specific index $i$ and $x_{\sigma_{g}(i)}\in\mathbb{R}^{n_{in}}$.

Our proposed $G$-invariant neural network is defined by a function
${\Gamma:\mathbb{R}^{n\times n_{in}}\rightarrow\mathbb{R}^{n_{out}}}$ of the
following form

$\Gamma(x)=f_{out}(\Sigma\Pi(f_{in}(x))),$ (11)

where $f_{in}$ is a $G$-equivariant input transformation function, $\Sigma\Pi$
is a function which comprises $G$-invariant transformation when combined with
$f_{in}$, and $f_{out}$ is an output transformation function. The general idea
of the proposed architecture is to define a $G$-invariant transformation,
which uses the sum of $G$-invariant polynomials ($\Sigma\Pi$) of $n$
variables, which are the outputs of $f_{in}$. This transformation produces a
$G$-invariant feature vector, which is processed by another function $f_{out}$
that is approximated by a Multi-Layer Perceptron.

First, let us define the $G$-equivariant input transformation function
$f_{in}:\mathbb{R}^{n\times n_{in}}\rightarrow\mathbb{R}^{n\times n\times
n_{mid}}$, where $n_{mid}$ is the size of the feature vector. This function
can be represented as a vector ${\Phi=[\phi_{1}\,\phi_{2}\,\dots\,\phi_{n}]}$
of neural networks, where each function
$\phi_{i}:\mathbb{R}^{n_{in}}\rightarrow\mathbb{R}^{n_{mid}}$ is applied on
all elements of the set of input vectors $\\{x_{i}\\}_{i=1}^{n}$, and
transforms them to the $n_{mid}$ dimensional vector. As a result, the
operation of the $f_{in}$ function can be formulated by

$f_{in}(x)=\begin{bmatrix}\Phi(x_{1})\\\ \Phi(x_{2})\\\ \vdots\\\
\Phi(x_{n})\\\
\end{bmatrix}=\begin{bmatrix}\phi_{1}(x_{1})&\ldots&\phi_{n}(x_{1})\\\
\vdots&\ddots&\vdots\\\ \phi_{1}(x_{n})&\ldots&\phi_{n}(x_{n})\\\
\end{bmatrix}.$ (12)

One can see that $f_{in}(x)$ is $G$-equivariant, since the action of the
vector $\Phi$ of functions is the same for each element of the vector $x$,
thus it transposes the rows of the matrix form (12) according to $g\in G$,
which is equivalent to transposing the rows after the calculation of
$f_{in}(x)$.

Second, we define the function $\Sigma\Pi:\mathbb{R}^{n\times n\times
n_{mid}}\rightarrow\mathbb{R}^{n_{mid}}$, which constructs $G$-invariant
polynomials of outputs obtained from $f_{in}$, by

$\Sigma\Pi(x)=\sum_{g\in G}\prod_{j=1}^{n}x_{\sigma_{g}(j),j}.$ (13)

To see the $G$-invariance of $\Sigma\Pi(f_{in}(x))$, we substitute $x$ from
(13) with (12) to obtain

$\Sigma\Pi(f_{in}(x))=\sum_{g\in
G}\prod_{j=1}^{n}\phi_{j}(x_{\sigma_{g}(j)}).$ (14)

Then, we can show that (14) is $G$-invariant by checking whether (9) holds for
any input $x$ and any group element $g^{\prime}\in G$ as follows:

$\begin{split}\Sigma\Pi(g^{\prime}(f_{in}(x)))&=\sum_{g\in
G}\prod_{j=1}^{n}\phi_{j}(x_{\sigma_{g^{\prime}}(\sigma_{g}(j))})\\\
&=\sum_{g\in
G}\prod_{j=1}^{n}\phi_{j}(x_{\sigma_{g}(j)})=\Sigma\Pi(f_{in}(x))\end{split},$
(15)

since any group element acting on the group leads to the group itself. Last,
we define the output function
$f_{out}:\mathbb{R}^{n_{mid}}\rightarrow\mathbb{R}^{n_{out}}$ following the
structure of a typical fully connected neural network by

$f_{out}(x)=\sum_{i=1}^{N}c_{i}\sigma\left(\sum_{j=1}^{n_{mid}}w_{ij}x_{j}+h_{i}\right),$
(16)

where $N\in\mathbb{N}_{+}$ is a parameter, $\sigma$ is a non-polynomial
activation function and $c_{i},w_{ij},h_{i}\in\mathbb{R}$ are coefficients.

###  5.2 Proposition 1 and its Proof

######  Proposition 2.

The network function (11), can approximate any $G$-invariant function
$f:V\rightarrow\mathbb{R}$, where $V$ is a compact subset of
$\mathbb{R}^{n\times n_{in}}$ and $G\leq S_{n}$ is a finite group, as long as
number of features $n_{mid}$ at the output of input transformation network
$f_{in}$ is greater than or equal to the size $N_{inv}$ of the generating set
$\mathcal{F}$ of polynomial $G$-invariants.

###### Proof.

In the proof, without the loss of generality, we consider the case when
$n_{out}=1$, as the approach can be generalized for arbitrary $n_{out}$.
Moreover, we assume that

$0\notin V$ (17)

to avoid the change of sign when approximating polynomials of inputs, but it
is not a limitation because any compact set can be transformed to such a set
by a bijective function.

To prove the Proposition 2, we need to employ two theorems:

######  Theorem 1 ([9]).

Let $\sigma:\mathbb{R}\rightarrow\mathbb{R}$ be a continuous activation
function that is not a polynomial. Let $V=\mathbb{R}^{d}$ be a real finite
dimensional vector space. Then, any continuous map
${f:V\rightarrow\mathbb{R}}$ can be approximated, in the sense of uniform
convergence on compact sets, by

$\hat{f}(x_{1},x_{2},\dots,x_{d})=\sum_{i=1}^{N}c_{i}\sigma\left(\sum_{j=1}^{d}w_{ij}x_{j}+h_{i}\right)$
(18)

with a parameter $N\in\mathbb{N}_{+}$ and coefficients
$c_{i},w_{ij},h_{i}\in\mathbb{R}$.

The above version of the theorem comes from the work of [9], but it was proved
by [6].

######  Theorem 2 ([9]).

Let $\sigma:\mathbb{R}\rightarrow\mathbb{R}$ be a continuous activation
function that is not a polynomial, $G$ be a compact group, $W$ be a finite-
dimensional $G$-module and $f_{1},\ldots,f_{N_{inv}}:W\rightarrow\mathbb{R}$
be a finite generating set of polynomial invariants on $W$ (existing by
Hilbert’s theorem). Then, any continuous invariant map
$f:W\rightarrow\mathbb{R}$ can be approximated by an invariant map
$\hat{f}:W\rightarrow\mathbb{R}$ of the form

$\hat{f}(x)=\sum_{i=1}^{N}c_{i}\sigma\left(\sum_{j=1}^{N_{inv}}w_{ij}f_{j}(x)+h_{i}\right)$
(19)

with a parameter $N\in\mathbb{N}_{+}$ and coefficients
$c_{i},w_{ij},h_{i}\in\mathbb{R}$.

The accuracy of the approximation (19) has been proven to be $2\epsilon$ for
some arbitrarily small positive constant $\epsilon$. Note that the function
$f_{out}$ is of the same form as the function $\hat{f}$. Then, one can
accurately imitate the behavior of $\hat{f}$ using $f_{out}$, if the input to
both functions are equivalent.

######  Lemma 3.

For every element $f_{i}:V\rightarrow\mathbb{R}$ of the finite generating set
$\mathcal{F}=\\{f_{i}\\}_{i=1}^{N_{inv}}$ of polynomial $G$-invariants on $V$,
there exists an approximation of the form (14), linearly dependent on
$\epsilon$, where $G\leq S_{n}$ is an $m$ element subgroup of the $n$ element
permutation group and $\epsilon$ is an arbitrarily small positive constant.

###### Proof.

Any function $f_{i}\in\mathcal{F}$ has the following form

$f_{i}(x)=\sum_{g\in G}\psi(g(x)),$ (20)

where

$\psi(x)=\prod_{i=1}^{n}x_{i}^{b_{i}},$ (21)

and $b_{i}$ are fixed exponents. Combining (20) and (21), we obtain:

$f_{i}(x)=\sum_{g\in G}\prod_{i=1}^{n}x_{\sigma_{g}(i)}^{b_{i}},$ (22)

which has a similar form as (14). This resemblance is not accidental, but in
fact, $\Sigma\Pi(f_{in}(x))$ can approximate $n_{mid}$ functions belonging to
the set $\mathcal{F}$. Using Theorem 1 and the fact that $\phi_{i}$ is a
neural network satisfying (18), we observe that $\phi_{j}(x_{i})$ can
approximate any continuous function with $\epsilon$ precision. Thus, it can
approximate $x_{i}^{b_{i}}$ for some constant parameter $b_{i}$. It is
possible to provide an upper bound on the approximation error
$\left|f_{i}(x)-\Sigma\Pi_{i}(f_{in}(x))\right|$ by

$\begin{split}&\left|f_{i}(x)-\Sigma\Pi_{i}(f_{in}(x))\right|\stackrel{{\scriptstyle(\ref{eq:sup_mat_inv_f_i},\ref{eq:sup_mat_sigmapifin_G})}}{{=}}\\\
&\left|\sum_{g\in G}\prod_{i=1}^{n}x_{\sigma_{g}(i)}^{b_{i}}-\sum_{g\in
G}\prod_{j=1}^{n}\phi_{j}(x_{\sigma_{g}(j)})\right|\leq\\\ &\sum_{g\in
G}\left|\prod_{i=1}^{n}x_{\sigma_{g}(i)}^{b_{i}}-\prod_{j=1}^{n}\phi_{j}(x_{\sigma_{g}(j)})\right|\leq\\\
&\sum_{g\in
G}\left|\prod_{i=1}^{n}x_{\sigma_{g}(i)}^{b_{i}}-\prod_{j=1}^{n}(x_{\sigma_{g}(j)}^{b_{j}}-\epsilon)\right|\stackrel{{\scriptstyle(\ref{eq:sup_mat_V})}}{{\leq}}mn\epsilon\\\
\end{split},$ (23)

for some arbitrarily small positive constant $\epsilon$. ∎

Assuming that the number of features $n_{mid}$ at the output of input
transformation network $f_{in}$ is greater than or equal to the size of the
generating set $\mathcal{F}$, it is possible to estimate each of $f_{i}(x)$
using (14)999Size of the generating set $\mathcal{F}$ depends on the
complexity of the function (in terms of approximating it with the use of
polynomials). However, we conjecture that in practice the $n_{mid}$ can be
lower than the size of $\mathcal{F}$, as using neural networks to transform
the input features offers a much more flexible representation than only its
powers..

The last step for completing the proof of the Proposition 2, using Theorem 1,
Theorem 2, and the proposed Lemma 3, is to show that

$\left|f(x)-\Gamma(x)\right|\leq\epsilon c,$ (24)

where $c\in\mathbb{R}$ is a constant.

Let us consider the error

$\begin{split}&\left|f(x)-\Gamma(x)\right|\stackrel{{\scriptstyle(\ref{eq:sup_mat_Gamma})}}{{=}}\left|f(x)-\hat{f}(x)\right|+\\\
&+\left|\hat{f}(x)-f_{out}(\Sigma\Pi(f_{in}(x)))\right|\stackrel{{\scriptstyle\text{Thm.}\ref{thm:poly}}}{{=}}\\\
&2\epsilon+\left|\hat{f}(x)-f_{out}(\Sigma\Pi(f_{in}(x)))\right|=\\\
&\left.f_{out}(\mathcal{F}(x))-f_{out}(\Sigma\Pi(f_{in}(x)))\right|\leq\\\
&2\epsilon+\left|\hat{f}(x)-f_{out}(\mathcal{F}(x))\right|+\\\
&\left|f_{out}(\mathcal{F}(x))-f_{out}(\Sigma\Pi(f_{in}(x)))\right|\stackrel{{\scriptstyle\text{Thm.}\ref{thm:UAT},}}{{\leq}}\\\
&3\epsilon+\left|f_{out}(\mathcal{F}(x))-f_{out}(\Sigma\Pi(f_{in}(x)))\right|\end{split}.$
(25)

Several transformations presented in (25) result in the formula which is a sum
of $3\epsilon$ and the absolute difference of $f_{out}(\mathcal{F})$ and
$f_{out}(\Sigma\Pi(f_{in}(x)))$. From (23), we have that the difference of the
arguments is bounded by $mn\epsilon$. Consider then a ball $B_{mn\epsilon}(x)$
with radius $mn\epsilon$ centered at $x$. Since $f_{out}$ is a MLP (multi-
layer perceptron), which is at least locally Lipschitz continuous, we know
that its output for $x^{\prime}\in B_{mn\epsilon}(x)$ can change at most by
$kmn\epsilon$, where $k$ is a Lipschitz constant. From those facts, we can
provide an upper bound on the error (25) by

$\begin{split}&\left|f(x)-\Gamma(x)\right|=\\\
&3\epsilon+\left|f_{out}(\mathcal{F}(x))-f_{out}(\Sigma\Pi(f_{in}(x)))\right|\leq\\\
&3\epsilon+kmn\epsilon=\epsilon(3+kmn)=\epsilon c\\\ \end{split}.$ (26)

∎

###  5.3 Computational efficiency analysis

Having proved that the proposed approach is universal we elucidate its
computational and memory complexity.

The tensor with the largest size is obtained at the output of the $f_{in}$
function. The size of this tensor is equal to $n^{2}n_{mid}$, where we assume
that $n_{mid}\geq N_{inv}$ and it is a design parameter of the network. So,
the memory complexity is of the order $n^{2}n_{mid}$, which is polynomial.
However, the complexity of the method proposed by [5], is of the order
$n^{p}$, where $\frac{n-2}{2}\leq p\leq\frac{n(n-1)}{2}$ depending on the
group $G$.

In order to evaluate the function $\Sigma\Pi$, $m(n-1)n_{mid}$ multiplications
are needed, where $m=|G|$ and $n_{mid}$ is a parameter, but we should assure
that $n_{mid}\geq N_{inv}$ to ensure universality of the proposed method (see
Section 3.3). It is visible, that the growth of the number of computations is
linear with $m$. For smaller subgroups of $S_{n}$, such as $\mathbb{Z}_{n}$ or
$D_{2n}$, where $m\propto n$, the number of the multiplications is of order
$n^{2}$, which is a lot better than the number of multiplications performed by
the $G$-invariant neural networks proposed in [5], which is of order $n^{p}$.
However, for big groups, where $m$ approaches $n!$, the number of
multiplications increases. Although the proposed approach can work for all
subgroups of $S_{n}$ ($m$=$n!$), it suits the best for small and medium size
groups, yet not less important, such as cyclic groups $Z_{n}$, $D_{2n}$,
$S_{k}$ ($k<n$) or their direct products.

Moreover, the proposed $\Sigma\Pi$ can be implemented efficiently on GPUs
using a parallel implementation of matrix multiplication and reduction
operations in practice.

As in the proposed approach, we also conduct $m$ summation’s through all
elements of the group $G$, we would like to compare its efficiency to the
group averaging approach. However, note that in case of group averaging, whole
$G$-invariant processing pipeline is multiplied $m$ times, whereas for our
approach term $m$ is present only in $\Sigma\Pi$ function, and the
$G$-invariant pipeline is multiplied $n$ times. Thus, we can use relatively
big neural networks in the first stages of the processing, as the number of
computations at this stage scales linearly with $n$, not $m$. Let’s consider a
simple example of generation a $G$-invariant representation using two
aforementioned methods with a single layer of neural network (the best case
for group averaging, as its processing pipeline scales with $m$ and we reduced
it to the minimum), where $n=10$, $n_{in}=2$, $n_{mid}=32$, $G=S_{5}\times
S_{5}$, $m=120^{2}$. Then number of multiplications for group averaging is
equal to $m(n\cdot n_{in}\cdot n_{mid})=120^{2}(10\cdot 2\cdot 32)=9.216\cdot
10^{6}$, whereas for our approach $n\cdot n\cdot n_{in}\cdot
n_{mid}+m\cdot(n-1)\cdot n_{mid}=10\cdot 10\cdot 2\cdot 32+120^{2}\cdot 9\cdot
32=4.1536\cdot 10^{6}$.