* Autonomous action management depends on strict or predefined communication protocol.

* Autonomous resource utilization depends on strict or predefined resource integration.

In these cases, the predefined and rule-based mechanisms serve as integrated alignment guiding and controlling the accurate operation of the dependent autonomous aspects.

Based on the findings of the taxonomic classification, in the next Section <ref>, we discuss challenges for current systems and reflect on the taxonomy's limitations and potentials.

§ DISCUSSION

This paper introduces and applies a novel comprehensive taxonomy, shedding light on the ways autonomous LLM-powered multi-agent systems manage the dynamic interplay between autonomy and alignment within their architectures.
When interpreted through the lens of our taxonomy, we encounter challenges and development potentials for current LLM-powered multi-agent systems, which are discussed in Section <ref>.
Moreover, in Section <ref>, we reflect on limitations and further potentials of the taxonomy itself.

§.§ Challenges for Current Systems

Our analysis of architectural dynamics inherent to current LLM-powered multi-agent systems, as detailed in Section <ref>, reveals a number of challenges regarding the interplay between autonomy and alignment. In accordance with [84], we recognize challenges related to the adaptability of agent collaboration. Moreover, our exploration indicates potentials for user-centric alignment options and controlling high-autonomy aspects.

Agent Collaboration. Among the systems analyzed, we especially observe limitations regarding collaboration modes and role-playing capabilities, as well as risks tied to prompt-driven collaboration techniques.

* Adaptability of Communication Protocols:
As discussed in Section <ref>, the collaboration between agents is mainly characterized by restricted communication protocols between predefined task-execution agents, such as instructor-and-executor relationships, or sequential or multi-cycle processes with predefined execution chains. Employing LLM-powered agents to manage and adapt the constellation of the agent network as well as their collaboration modes could pave the way for more creative problem-solving methods in task execution.

* Dynamic Role-Playing: In particular, we also see development potentials via the flexible collaboration between self-organizing role agents, such as for simulating the complex interplay within a certain application domain. As far as observable, the potential of engaging multiple perspectives through different roles and standpoints has not yet been fully sounded.

* Robustness of Prompt-driven Collaboration:
Collaboration between LLM-powered agents basically relies on prompt-driven message exchange, such as by delegating tasks, asking questions, or evaluating task results. This communication mechanism, founded on a sequence of prompts, heavily relies on the quality of LLM responses, which are susceptible to errors in terms of incorrect or hallucinated results [45, 30].
However, without the integration of comprehensive and robust control mechanisms to check the quality of these responses, the system is vulnerable to inaccuracies, misunderstandings, and inefficiencies [28].

User-Centric Alignment.
Within the scope of analyzed systems, user-centric alignment options are very rare. Alignment mechanisms are predominantly integrated into the system architecture (see Section <ref>). Drawing from this limitation, we see potentials in certain user-guided and real-time responsive alignment options.

* User-Guided Alignment Options: The options for users to access and influence the internal workings of the system are very limited. The internal composition and collaboration of the agents are mostly opaque to the user, which reduces transparency of the system operation. Exception to this represents the runtime documentation of agents' reflection and planning, provided by certain systems (see Section <ref>).
The customization of internal mechanisms is mostly not provided to users. Besides agent generation and role definition (offered by a few systems), there is potential for user modifications related to communication protocols, task orchestration, or result synthesis.
Corresponding to the aspect adaptability for LLM-powered agents (see above), modifying these internal mechanisms would enable the user in exploring alternative problem-solving ways.

* Real-Time Responsiveness:
The obvious lack of real-time adjustment capabilities can be seen founded in the nature of autonomous agent systems, which is accomplishing the user-prompted goal without further human intervention.
However, as elaborated on in Section <ref>, autonomy and alignment can be understood as complementary aspects. The absence of user interaction and control during runtime restricts the potential for dynamic alignment, thereby limiting the system's flexibility in response to changes in the operational context.
As detailed in Section <ref>, the interaction layer allows the integration of interceptor mechanisms. This not only allows real-time monitoring, addressing key concerns of explainable AI [63, 96], but also to implement effective feedback and intervention options [40, 27].
Collaborative environments fostering hybrid teamwork, comprising autonomous agents (or agents systems) and human co-workers are essentially built upon such real-time responsiveness, ensuring dynamic realignment while working towards shared goals [34, 54, 89].

Controlling High-Autonomy Aspects.
Besides prompting-related flaws such as inaccurate or hallucinated responses (see above), our engagement with the analyzed multi-agent systems has revealed additional operational issues.
Occasionally, we witness non-terminating activities, where the system falls into infinite loops.
For instance, this can manifest via solutions continually fine-tuned under the premise of improvement, or the system operation is stuck in a never ending dialogue between two LLM-powered agents.
Conversely, system operations might terminate in a dead end when encountering a task that requires competencies or resources that are either unavailable or inaccessible.
Obviously, the corresponding control mechanisms (integrated alignment) applied in such systems are ill-equipped to efficiently catch these kinds of exceptions. This insufficiency proves particularly concerning, as it undermines the reliability and effectiveness of these systems.
However, besides this symptomatic treatment, the reasons for these problems can be seen founded in architectural complexities, such as high-autonomy levels not adequately aligned or intertwined dependencies resulting from varying levels of autonomy (refer to Section <ref>).

§.§ Limitations and Potentials of the Taxonomy

For engineering the taxonomic system, we chose a pragmatic and technical perspective (see Section <ref>) and explored its utility by the exemplary classification of seven selected LLM-powered multi-agent systems (see Section <ref>). However, departing from this exploration, certain limitations and further potentials become evident.

Taxonomic System.
Our taxonomy conceptualizes autonomy and alignment not as binary extremes in a one-dimensional continuum, but as interacting and synergistic aspects. This distinctions allows forming a two-dimensional matrix (see Section <ref>) combining hierarchic levels of autonomy (from automated mechanisms to self-organizing agents) and alignment (from system-integrated to real-time responsive). This structure reflects the aforementioned triadic relationship between the key decision-making entities in the system (i.e., human users, rules and mechanisms, as well as LLM-powered agents) and their dynamic interplay (i.e., alignment, system operation, and collaboration), as illustrated in Fig. <ref>. Augmenting this, we map this matrix onto different characteristic aspects derived from four applied architectural viewpoints (see Section <ref>).

* Autonomy Scope:
Within this, we reference high autonomy to the agents' self-organization capabilities for decision-making and further operational impact (see Section <ref>). However, it's essential to consider that autonomy can span beyond this definition, encompassing facets like an agent's ability for self-enhancement and proactive agency.

* Alignment Scope:
In turn, the alignment dimension employed by the taxonomy reflects two key aspects, i.e., the origin of the alignment, and the moment of its communication to the system (see Section <ref>). In combination with the architectural dimension, we also reflect the architectural or functional scope of the alignment technique in terms of the viewpoint-specific aspects.
However, one must note that this dimension does not reflect the quality, efficacy, or depth of the applied techniques.

* Scope of Architectural Aspects:
As detailed in Section <ref>, the taxonomy adopts 12 architectural aspects inherent to the four architectural viewpoints characteristic for LLM-powered multi-agent systems. The viewpoints are oriented to Kruchten's viewpoint model for software architecture [38], a recognized standard in this field. However, as there exist more viewpoint models reflecting further concerns and perspectives on software systems, there might also be further architectural aspects possibly relevant to autonomous LLM-powered multi-agent systems. Considering the ongoing evolution in the field, these adaptions become crucial.

Expressiveness of Taxonomic Classification.
The scope of the taxonomic structure forms the foundation for the taxonomy's analytical power enabling conclusions about the classified systems under analysis.

* Levels as Strengths and Weaknesses:
It is important to understand that higher levels in autonomy and alignment, termed as user-responsive autonomy (see Table <ref>), might not always be the optimal system configuration for every scenario. Indeed, high autonomy can deviate from the intended goal and therefore needs to be aligned accordingly. In certain situations, a system with modest autonomy could be considered the best choice. Given the intention to automate a repetitive set of routine tasks with predictable variables and contextual requirements, a static autonomy with predefined rules and mechanisms would not be just sufficient, but also provide a higher reliability. If there is no need to include user-specific information, a combination with an integrated alignment can be seen as best choice (rule-driven automation).

* System Efficiency and Accuracy:
As previously elaborated, our taxonomy focuses on the architectural complexities driven by the dynamics between autonomy and alignment, rather than evaluating functional performance metrics like operational efficiency or accuracy.
Neither recent surveys in the field [84, 30] do measure the systems' performance, such as in terms of efficiency, accuracy, or scalability.
However, while engaging with the analyzed systems, we observed substantial differences among them, reflecting the exploratory state and the ongoing rapid evolution of the domain.
For measuring their functional performance, benchmarks and methods could be adopted similar to those presented in [13].

* Balancing Techniques:
As reported in Section <ref>, we have identified different balancing strategies across the system architectures. In this context, it is important to notice that aspects marked as unbalanced (for example, combining high-autonomy and low-alignment levels) might be actually controlled or balanced via automated mechanisms applied by another aspect (static autonomy and integrated alignment). Within the analyzed systems, user-centric alignment options are barely applied to curb the wildness of high-autonomy aspects. It would be interesting, to investigate and compare in detail, how integrated alignment techniques are employed to deal with the challenges and complexities of agent-driven autonomy.

Practical Implications.
Drawing from the information value provided by the classification results, we can distinguish considerations regarding the practical utility and relevance of the taxonomy.

* Analysis Purposes:
The analysis and understanding of these dynamic architectural complexities can serve different purposes, such as:

* Comparing, selecting, and applying available multi-agent systems in the context of given scenarios with certain requirements for autonomy and alignment.

* Reasoning about architectural design options for the development of novel multi-agent systems.

* Scrutinizing and rethinking strategies for balancing levels of autonomy and alignment.

* Building a foundational framework for additional analysis techniques or complementing them, such as measuring the functional system capabilities (see above).

* Ongoing Evolution:
As underscored by recent surveys [84, 95], the field of autonomous LLM-powered multi-agent systems is characterized by an ongoing rapid evolution showcasing a dynamically growing number of approaches featuring diverse architectures and a wide spectrum of system-maturity levels.
While designed to abstract from concrete system specifics, the taxonomic system might need periodic updates to accommodate this dynamically evolving landscape.

* Broader Applicability.
Tailored to address the characteristics of autonomous LLM-powered multi-agent architectures (refer to Section <ref>), the foundational principles of our taxonomy, however, seem to be transferable to other AI systems. Certain segments of the taxonomic structure can be seen as universally applicable across AI architectures. Conversely, facets specifically tailored to multi-agent systems, such as the aspects inherent to the agent composition and multi-agent collaboration viewpoints, would require corresponding adjustments.

§ CONCLUSION

In this paper, we have introduced a comprehensive multi-dimensional taxonomy engineered to analyze how autonomous LLM-powered multi-agent systems balance the dynamic interplay between autonomy and alignment across their system architectures.
For this purpose, the taxonomy employs a matrix that combines hierarchical levels of autonomy and alignment. This matrix is then mapped onto various architectural aspects organized by four architectural viewpoints reflecting different complementary concerns and perspectives.
The resulting taxonomic system enables the assessment of interdependent aspect configurations in a wide spectrum, ranging from simple configurations, such as predefined mechanisms combined with system-integrated alignment techniques (rule-driven automation), to sophisticated configurations, such as self-organizing agency responsive to user feedback and evolving conditions (user-responsive autonomy).
Applied to 12 distinct architectural aspects inherent to viewpoints, such as goal-driven task management, multi-agent collaboration, agent composition, and context interaction, this taxonomy allows for a nuanced analysis and understanding of architectural complexities within autonomous LLM-powered multi-agent systems.

Through our taxonomy's application to seven selected LLM-powered multi-agent systems, its practical relevance and utility has been illustrated.
In particular, it has been shown that a combined assessment of autonomy and alignment levels across the architectural aspects of each multi-agent system allows for identifying system profiles that can indicate certain strategies for balancing the dynamic interplay between autonomy and alignment.
This exploration of exemplary current systems also revealed several challenges.
Most prominently, we observed a lack of user-centric alignment options across all systems, with little user-guided alignment, but no real-time responsive alignment at all.
Moreover, the systems exhibit high autonomy levels mostly for certain aspects, such as the goal decomposition, the action management, or the utilization of contextual resources.
In contrast, other key aspects of the system operation show limited autonomy; aspects such as managing the communication protocol, memory usage, or agent network are largely static, leaning heavily on predefined mechanisms.

Based on these and further findings, we especially see two promising avenues for the evolution of autonomous LLM-powered multi-agent systems.
Firstly, by employing adaptable and self-organizing communication protocols and agent networks, the systems' role-playing capabilities could be enhances, which enables them to better simulate complex multi-perspective environments. By reflecting and weighing up diverse standpoints and strategies, this could also pave the way for more in-depth inter-agent discussions and creativity in problem solving.
Secondly, the exploration of real-time responsive systems, which can adapt to evolving conditions as well as to user feedback during runtime, would foster dynamic collaboration and hybrid teamwork between LLM-powered agents and human users.

Departing from an exploratory stage, the field of autonomous LLM-powered multi-agent systems is rapidly evolving, resulting in a growing number of promising approaches and innovative architectures.
With their current capabilities and inherent potentials, such as multi-perspective domain simulations or collaborative environments of autonomous agents and human coworkers, these systems could significantly contribute to the progression towards advanced stages of artificial intelligence, such as AGI or ASI.
From a pragmatic perspective, there are numerous opportunities for combining LLMs as general purpose technology with the specifics of various application domains. LLM-based multi-agent systems can serve as foundation for developing corresponding domain-specific application layers.
The architectural complexities resulting from the dynamic interplay between autonomy and alignment can be seen as one of the key challenges in such systems.
By providing a systematic framework for analyzing these complexities, our taxonomy aims to contribute to these ongoing efforts.

For our subsequent endeavors, we aim at developing a comprehensive overview and comparison of existing autonomous LLM-powered multi-agent systems, complementing existing literature reviews in the field [84, 95].
To this end, we intend to analyze and classify available systems using our taxonomy.
The identified system profiles and balancing strategies resulting from this analysis will then be combined with further investigations of functional system capabilities.
In addition, driven by the potentials identified during the taxonomic classification of selected systems, we currently explore the development of an LLM-powered multi-agent system that aims at combining high levels of agency with real-time user-centric control mechanisms.

Building on the foundation of our taxonomy, future initiatives could venture into the following areas:
A dedicated exploration, assessment, and systematization of alignment techniques, particularly tailored for LLM-based interaction and application layers, could serve as reference for future systems.
Moreover, the conception of a methodological framework with instruments and benchmarks for measuring the functional capabilities of LLM-powered multi-agent systems could provide a structured template to evaluate key metrics like efficiency, accuracy, and scalability of these systems.

§ ACKNOWLEDGEMENTS

The author gratefully acknowledges the support from the "Gesellschaft für Forschungsförderung (GFF)" of Lower Austria, as this research was conducted at Ferdinand Porsche Mobile University of Applied Sciences (FERNFH) as part of the "Digital Transformation Hub" project funded by the GFF.

[1]
D. Amodei, C. Olah, J. Steinhardt, P. Christiano, J. Schulman, and D. Mané.
Concrete problems in AI safety.
arXiv preprint arXiv:1606.06565, 2016.

[2]
A. B. Arrieta, N. Díaz-Rodríguez, J. Del Ser, A. Bennetot, S. Tabik,
A. Barbado, S. García, S. Gil-López, D. Molina, R. Benjamins, et al.
Explainable artificial intelligence (XAI): Concepts, taxonomies,
opportunities and challenges toward responsible AI.
Information fusion, 58:82–115, 2020.

[3]
A. Askell, Y. Bai, A. Chen, D. Drain, D. Ganguli, T. Henighan, A. Jones,
N. Joseph, B. Mann, N. DasSarma, et al.
A general language assistant as a laboratory for alignment.
arXiv preprint arXiv:2112.00861, 2021.

[4]
L. Bass, P. Clements, and R. Kazman.
Software architecture in practice.
Addison-Wesley Professional, 2003.

[5]
D. Batory.
Feature models, grammars, and propositional formulas.
In 9th International Software Product Line Conference, pages
7–20, 2005.

[6]
J. M. Beer, A. D. Fisk, and W. A. Rogers.
Toward a framework for levels of robot autonomy in human-robot
Journal of human-robot interaction, 3(2):74, 2014.

[7]
S. D. Bird.
Toward a taxonomy of multi-agent systems.
International Journal of Man-Machine Studies, 39(4):689–704,

[8]
B. W. Boehm and P. N. Papaccio.
Understanding and controlling software costs.
IEEE transactions on software engineering, 14(10):1462–1477,

[9]
R. Bommasani, D. A. Hudson, E. Adeli, R. Altman, S. Arora, S. von Arx, M. S.
Bernstein, J. Bohg, A. Bosselut, E. Brunskill, et al.
On the opportunities and risks of foundation models.
arXiv preprint arXiv:2108.07258, 2021.

[10]
N. Bostrom.
Dunod, 2017.

[11]
T. Brown, B. Mann, N. Ryder, M. Subbiah, J. D. Kaplan, P. Dhariwal,
A. Neelakantan, P. Shyam, G. Sastry, A. Askell, et al.
Language models are few-shot learners.
Advances in neural information processing systems,
33:1877–1901, 2020.

[12]
J. C. Brustoloni.
Autonomous agents: Characterization and requirements.
Carnegie Mellon University, 1991.

[13]
S. Bubeck, V. Chandrasekaran, R. Eldan, J. Gehrke, E. Horvitz, E. Kamar,
P. Lee, Y. T. Lee, Y. Li, S. Lundberg, et al.
Sparks of artificial general intelligence: Early experiments with
arXiv preprint arXiv:2303.12712, 2023.

[14]
H. Chase.
<https://github.com/langchain-ai/langchain>, 2022.

[15]
A. Chowdhery, S. Narang, J. Devlin, M. Bosma, G. Mishra, A. Roberts, P. Barham,
H. W. Chung, C. Sutton, S. Gehrmann, et al.
Palm: Scaling language modeling with pathways.
arXiv preprint arXiv:2204.02311, 2022.

[16]
P. Clements, D. Garlan, R. Little, R. Nord, and J. Stafford.
Documenting software architectures: views and beyond.
In 25th International Conference on Software Engineering, 2003.
Proceedings., pages 740–741. IEEE, 2003.

[17]
L. M. Csepregi.
The effect of context-aware LLM-based NPC conversations on player
engagement in role-playing video games.

[18]
Y. Du, S. Li, A. Torralba, J. B. Tenenbaum, and I. Mordatch.
Improving factuality and reasoning in language models through
multiagent debate.
arXiv preprint arXiv:2305.14325, 2023.

[19]
G. Dudek, M. R. Jenkin, E. Milios, and D. Wilkes.
A taxonomy for multi-agent robotics.
Autonomous Robots, 3:375–397, 1996.

[20]
F. Fabiano, V. Pallagani, M. B. Ganapini, L. Horesh, A. Loreggia, K. Murugesan,
F. Rossi, and B. Srivastava.
Fast and slow planning.
arXiv preprint arXiv:2303.04283, 2023.

[21]
S. Franklin and A. Graesser.
Is it an agent, or just a program?: A taxonomy for autonomous agents.
In International workshop on agent theories, architectures, and
languages, pages 21–35. Springer, 1996.

[22]
C. Gao, X. Lan, Z. Lu, J. Mao, J. Piao, H. Wang, D. Jin, and Y. Li.
S3: Social-network simulation system with large
language model-empowered agents.
arXiv preprint arXiv:2307.14984, 2023.

[23]
T. R. Gruber.
Toward principles for the design of ontologies used for knowledge
International journal of human-computer studies,
43(5-6):907–928, 1995.

[24]
G. Guizzardi, H. Herre, and G. Wagner.
On the general ontological foundations of conceptual modeling.
In Conceptual Modeling—ER 2002: 21st International Conference
on Conceptual Modeling Tampere, Finland, October 7–11, 2002 Proceedings 21,
pages 65–78. Springer, 2002.

[25]
T. Haendler and G. Neumann.
Ontology-based analysis and design of educational games for software
In Computer Supported Education: 11th International Conference,
CSEDU 2019, Heraklion, Crete, Greece, May 2-4, 2019, Revised Selected
Papers, pages 602–628. Springer, 2020.

[26]
R. Hao, L. Hu, W. Qi, Q. Wu, Y. Zhang, and L. Nie.
ChatLLM network: More brains, more intelligence.
arXiv preprint arXiv:2304.12998, 2023.

[27]
J. L. Hellerstein, Y. Diao, S. Parekh, and D. M. Tilbury.
Feedback control of computing systems.
John Wiley & Sons, 2004.

[28]
S. Hong, X. Zheng, J. Chen, Y. Cheng, C. Zhang, Z. Wang, S. K. S. Yau, Z. Lin,
L. Zhou, C. Ran, et al.
MetaGPT: Meta programming for multi-agent collaborative framework.
arXiv preprint arXiv:2308.00352, 2023.

[29]
S. International.
Taxonomy and definitions for terms related to driving automation
systems for on-road motor vehicles, 2016.

[30]
Z. Ji, N. Lee, R. Frieske, T. Yu, D. Su, Y. Xu, E. Ishii, Y. J. Bang,
A. Madotto, and P. Fung.
Survey of hallucination in natural language generation.
ACM Computing Surveys, 55(12):1–38, 2023.

[31]
J. Johnson, M. Douze, and H. Jégou.
Billion-scale similarity search with GPUs.
IEEE Transactions on Big Data, 7(3):535–547, 2019.

[32]
J. Kaddour, J. Harris, M. Mozes, H. Bradley, R. Raileanu, and R. McHardy.
Challenges and applications of large language models.
arXiv preprint arXiv:2307.10169, 2023.

[33]
D. Kahneman.
Thinking, fast and slow.
Macmillan, 2011.

[34]
R. Khosla.
Engineering intelligent hybrid multi-agent systems.
Springer Science & Business Media, 1997.

[35]
G. Kiczales, J. Lamping, A. Mendhekar, C. Maeda, C. Lopes, J.-M. Loingtier, and
J. Irwin.
Aspect-oriented programming.
In ECOOP'97—Object-Oriented Programming: 11th European
Conference Jyväskylä, Finland, June 9–13, 1997 Proceedings 11,
pages 220–242. Springer, 1997.

[36]
B. A. Kitchenham, G. H. Travassos, A. Von Mayrhauser, F. Niessink, N. F.
Schneidewind, J. Singer, S. Takada, R. Vehvilainen, and H. Yang.
Towards an ontology of software maintenance.
Journal of Software Maintenance: Research and Practice,
11(6):365–389, 1999.

[37]
T. Kojima, S. S. Gu, M. Reid, Y. Matsuo, and Y. Iwasawa.
Large language models are zero-shot reasoners.
Advances in neural information processing systems,
35:22199–22213, 2022.

[38]
P. B. Kruchten.
Architectural blueprints — the “4+1” view model of software
IEEE software, 12(6):42–50, 1995.

[39]
Y. Labrou and T. Finin.
Semantics and conversations for an agent communication language.
arXiv preprint cs/9809034, 1998.

[40]
P. A. Laplante et al.
Real-time systems design and analysis.
Wiley New York, 2004.

[41]
G. Li, H. A. A. K. Hammoud, H. Itani, D. Khizbullin, and B. Ghanem.
CAMEL: Communicative agents for "mind" exploration of large scale
language model society.
arXiv preprint arXiv:2303.17760, 2023.

[42]
T. Liang, Z. He, W. Jiao, X. Wang, Y. Wang, R. Wang, Y. Yang, Z. Tu, and
S. Shi.
Encouraging divergent thinking in large language models through
multi-agent debate.
arXiv preprint arXiv:2305.19118, 2023.

[43]
B. Y. Lin, Y. Fu, K. Yang, P. Ammanabrolu, F. Brahman, S. Huang,
C. Bhagavatula, Y. Choi, and X. Ren.
SwiftSage: A generative agent with fast and slow thinking for
complex interactive tasks.
arXiv preprint arXiv:2305.17390, 2023.

[44]
P. Maes.
Artificial life meets entertainment: lifelike autonomous agents.
Communications of the ACM, 38(11):108–114, 1995.

[45]
J. Maynez, S. Narayan, B. Bohnet, and R. McDonald.
On faithfulness and factuality in abstractive summarization.
arXiv preprint arXiv:2005.00661, 2020.

[46]
B. Meyer.
Applying'design by contract'.
Computer, 25(10):40–51, 1992.

[47]
T. Mikolov, K. Chen, G. Corrado, and J. Dean.
Efficient estimation of word representations in vector space.
arXiv preprint arXiv:1301.3781, 2013.

[48]
M. Minsky.
The Society of mind.
Simon and Schuster, 1988.

[49]
H. Mintzberg.
The structuring of organizations.
Springer, 1989.

[50]
L. J. Moya and A. Tolk.
Towards a taxonomy of agents and multi-agent systems.
In SpringSim (2), pages 11–18, 2007.

[51]
Y. Nakajima.
<https://github.com/yoheinakajima/babyagi>, 2023.

[52]
K. S. Narendra and A. M. Annaswamy.
Stable adaptive systems.
Courier Corporation, 2012.

[53]
H. Naveed, A. U. Khan, S. Qiu, M. Saqib, S. Anwar, M. Usman, N. Barnes, and
A. Mian.
A comprehensive overview of large language models.
arXiv preprint arXiv:2307.06435, 2023.

[54]
M. Neef.
A taxonomy of human-agent team collaborations.
In Proceedings of the 18th BeNeLux Conference on Artificial
Intelligence (BNAIC 2006), pages 245–250, 2006.

[55]
Object Management Group.
Unified Modeling Language – version 2.5.1.
<https://www.omg.org/spec/UML/2.5.1>, Dec. 2017.

[56]
L. Ouyang, J. Wu, X. Jiang, D. Almeida, C. Wainwright, P. Mishkin, C. Zhang,
S. Agarwal, K. Slama, A. Ray, et al.
Training language models to follow instructions with human feedback.
Advances in Neural Information Processing Systems,
35:27730–27744, 2022.

[57]
C. A. O’reilly Iii and M. L. Tushman.
Ambidexterity as a dynamic capability: Resolving the innovator's
Research in organizational behavior, 28:185–206, 2008.

[58]
R. Parasuraman, T. B. Sheridan, and C. D. Wickens.
A model for types and levels of human interaction with automation.
IEEE Transactions on systems, man, and cybernetics-Part A:
Systems and Humans, 30(3):286–297, 2000.

[59]
J. S. Park, J. C. O'Brien, C. J. Cai, M. R. Morris, P. Liang, and M. S.
Generative agents: Interactive simulacra of human behavior.
arXiv preprint arXiv:2304.03442, 2023.

[60]
S. G. Patil, T. Zhang, X. Wang, and J. E. Gonzalez.
Gorilla: Large language model connected with massive APIs.
arXiv preprint arXiv:2305.15334, 2023.

[61]
C. Qian, X. Cong, C. Yang, W. Chen, Y. Su, J. Xu, Z. Liu, and M. Sun.
Communicative agents for software development.
arXiv preprint arXiv:2307.07924, 2023.

[62]
A. Rahmati, E. Fernandes, J. Jung, and A. Prakash.
IFTTT vs. Zapier: A comparative study of trigger-action programming
arXiv preprint arXiv:1709.02788, 2017.

[63]
M. T. Ribeiro, S. Singh, and C. Guestrin.
"why should i trust you?" explaining the predictions of any
In Proceedings of the 22nd ACM SIGKDD international conference
on knowledge discovery and data mining, pages 1135–1144, 2016.

[64]
N. Rozanski and E. Woods.
Software systems architecture: working with stakeholders using
viewpoints and perspectives.
Addison-Wesley, 2012.

[65]
S. Russell.
Human compatible: Artificial intelligence and the problem of
Penguin, 2019.

[66]
S. Russell.
Artificial intelligence and the problem of control.
Perspectives on Digital Humanism, page 19, 2022.

[67]
S. Russell, D. Dewey, and M. Tegmark.
Research priorities for robust and beneficial artificial
AI magazine, 36(4):105–114, 2015.

[68]
S. K. K. Santu and D. Feng.
TELeR: A general taxonomy of LLM prompts for benchmarking complex
arXiv preprint arXiv:2305.11430, 2023.

[69]
P.-Y. Schobbens, P. Heymans, J.-C. Trigaux, and Y. Bontemps.
Generic semantics of feature diagrams.
Computer networks, 51(2):456–479, 2007.

[70]
Y. Shen, K. Song, X. Tan, D. Li, W. Lu, and Y. Zhuang.
HuggingGPT: Solving AI tasks with ChatGPT and its friends in
Hugging Face.
arXiv preprint arXiv:2303.17580, 2023.

[71]
A. Shrestha, S. Subedi, and A. Watkins.
<https://github.com/reworkd/AgentGPT>, 2023.

[72]
K. Shum, S. Diao, and T. Zhang.
Automatic prompt augmentation and selection with chain-of-thought
from labeled data.
arXiv preprint arXiv:2302.12822, 2023.

[73]
M. P. Singh.
Agent communication languages: Rethinking the principles.
Computer, 31(12):40–47, 1998.

[74]
S. A. Sloman.
The empirical case for two systems of reasoning.
Psychological bulletin, 119(1):3, 1996.

[75]
J. F. Sowa.
Top-level ontological categories.
International journal of human-computer studies,
43(5-6):669–685, 1995.

[76]
R. Thoppilan, D. De Freitas, J. Hall, N. Shazeer, A. Kulshreshtha, H.-T. Cheng,
A. Jin, T. Bos, L. Baker, Y. Du, et al.
Lamda: Language models for dialog applications.
arXiv preprint arXiv:2201.08239, 2022.

[77]
Torantulino et al.
<https://github.com/Significant-Gravitas/Auto-GPT>, 2023.

[78]
P. T. Tosic and G. A. Agha.
Towards a hierarchical taxonomy of autonomous agents.
In 2004 IEEE International Conference on Systems, Man and
Cybernetics (IEEE Cat. No. 04CH37583), volume 4, pages 3421–3426. IEEE,

[79]
TransformerOptimus et al.
<https://github.com/TransformerOptimus/SuperAGI>, 2023.

[80]
E. R. Tufte.
The visual display of quantitative information, volume 2.
Graphics press Cheshire, CT, 2001.

[81]
M. Usman, R. Britto, J. Börstler, and E. Mendes.
Taxonomies in software engineering: A systematic mapping study and a
revised taxonomy development method.
Information and Software Technology, 85:43–59, 2017.

[82]
H. Van Dyke Parunak, S. Brueckner, M. Fleischer, and J. Odell.
A design taxonomy of multi-agent interactions.
In Agent-Oriented Software Engineering IV: 4th
InternationalWorkshop, AOSE 2003, Melbourne, Australia, July 15, 2003.
Revised Papers 4, pages 123–137. Springer, 2004.

[83]
G. Wang, Y. Xie, Y. Jiang, A. Mandlekar, C. Xiao, Y. Zhu, L. Fan, and
A. Anandkumar.
Voyager: An open-ended embodied agent with large language models.
arXiv preprint arXiv:2305.16291, 2023.

[84]
L. Wang, C. Ma, X. Feng, Z. Zhang, H. Yang, J. Zhang, Z. Chen, J. Tang,
X. Chen, Y. Lin, et al.
A survey on large language model based autonomous agents.
arXiv preprint arXiv:2308.11432, 2023.

[85]
L. Wang, W. Xu, Y. Lan, Z. Hu, Y. Lan, R. K.-W. Lee, and E.-P. Lim.
Plan-and-solve prompting: Improving zero-shot chain-of-thought
reasoning by large language models.
arXiv preprint arXiv:2305.04091, 2023.

[86]
Q. Wang, L. Ding, Y. Cao, Z. Tian, S. Wang, D. Tao, and L. Guo.
Recursively summarizing enables long-term dialogue memory in large
language models.
arXiv preprint arXiv:2308.15022, 2023.

[87]
W. Wang, L. Dong, H. Cheng, X. Liu, X. Yan, J. Gao, and F. Wei.
Augmenting language models with long-term memory.
arXiv preprint arXiv:2306.07174, 2023.

[88]
Z. Wang, S. Mao, W. Wu, T. Ge, F. Wei, and H. Ji.
Unleashing cognitive synergy in large language models: A task-solving
agent through multi-persona self-collaboration.
arXiv preprint arXiv:2307.05300, 2023.

[89]
J. Wei, K. Shuster, A. Szlam, J. Weston, J. Urbanek, and M. Komeili.
Multi-party chat: Conversational agents in group settings with humans
and models.
arXiv preprint arXiv:2304.13835, 2023.

[90]
J. Wei, X. Wang, D. Schuurmans, M. Bosma, F. Xia, E. Chi, Q. V. Le, D. Zhou,
et al.
Chain-of-thought prompting elicits reasoning in large language
Advances in Neural Information Processing Systems,
35:24824–24837, 2022.

[91]
J. White, Q. Fu, S. Hays, M. Sandborn, C. Olea, H. Gilbert, A. Elnashar,
J. Spencer-Smith, and D. C. Schmidt.
A prompt pattern catalog to enhance prompt engineering with
arXiv preprint arXiv:2302.11382, 2023.

[92]
Y. Wolf, N. Wies, Y. Levine, and A. Shashua.
Fundamental limitations of alignment in large language models.
arXiv preprint arXiv:2304.11082, 2023.

[93]
M. Wooldridge.
An introduction to multiagent systems.
John wiley & sons, 2009.

[94]
M. Wooldridge and N. R. Jennings.
Intelligent agents: Theory and practice.
The knowledge engineering review, 10(2):115–152, 1995.

[95]
Z. Xi, W. Chen, X. Guo, W. He, Y. Ding, B. Hong, M. Zhang, J. Wang, S. Jin,
E. Zhou, et al.
The rise and potential of large language model based agents: A
arXiv preprint arXiv:2309.07864, 2023.

[96]
F. Xu, H. Uszkoreit, Y. Du, W. Fan, D. Zhao, and J. Zhu.
Explainable AI: A brief survey on history, research areas,
approaches and challenges.
In Natural Language Processing and Chinese Computing: 8th CCF
International Conference, NLPCC 2019, Dunhuang, China, October 9–14, 2019,
Proceedings, Part II 8, pages 563–574. Springer, 2019.

[97]
E. Yudkowsky.
The AI alignment problem: why it is hard, and where to start.
Symbolic Systems Distinguished Speaker, 4, 2016.

[98]
S. Zhang, S. Roller, N. Goyal, M. Artetxe, M. Chen, S. Chen, C. Dewan, M. Diab,
X. Li, X. V. Lin, et al.
OPT: Open pre-trained transformer language models.
arXiv preprint arXiv:2205.01068, 2022.

[99]
J. Zhao.
Using dependence analysis to support software architecture
arXiv preprint cs/0105009, 2001.

[100]
W. X. Zhao, K. Zhou, J. Li, T. Tang, X. Wang, Y. Hou, Y. Min, B. Zhang,
J. Zhang, Z. Dong, et al.
A survey of large language models.
arXiv preprint arXiv:2303.18223, 2023.


Stefan<EMAIL_ADDRESS>
# Reliable Part-of-Speech Tagging of Historical Corpora
through Set-Valued Prediction

Stefan Heid  Heinz Nixdorf Institut, Paderborn University, Germany  Marcel
Wever  Heinz Nixdorf Institut, Paderborn University, Germany  Eyke Hüllermeier
Heinz Nixdorf Institut, Paderborn University, Germany

(January 2020)

###### Abstract

Syntactic annotation of corpora in the form of part-of-speech (pos) tags is a
key requirement for both linguistic research and subsequent automated natural
language processing (nlp) tasks. This problem is commonly tackled using
machine learning methods, i.e., by training a pos tagger on a sufficiently
large corpus of labeled data. While the problem of pos tagging can essentially
be considered as solved for modern languages, historical corpora turn out to
be much more difficult, especially due to the lack of native speakers and
sparsity of training data. Moreover, most texts have no sentences as we know
them today, nor a common orthography. These irregularities render the task of
automated pos tagging more difficult and error-prone. Under these
circumstances, instead of forcing the pos tagger to predict and commit to a
single tag, it should be enabled to express its uncertainty. In this paper, we
consider pos tagging within the framework of set-valued prediction, which
allows the pos tagger to express its uncertainty via predicting a set of
candidate pos tags instead of guessing a single one. The goal is to guarantee
a high confidence that the correct pos tag is included while keeping the
number of candidates small. In our experimental study, we find that extending
state-of-the-art pos taggers to set-valued prediction yields more precise and
robust taggings, especially for unknown words, i.e., words not occurring in
the training data.

###### keywords:

Part-of-speech tagging, set-valued prediction, uncertainty, historic corpora

##  1 Introduction

In part-of-speech (pos) tagging, words of a corpus are assigned word classes,
also referred to as pos tags. These tags form the basis for both automated
natural language processing (nlp) procedures and for human experts who want to
analyze texts or text passages more closely. Especially in studies devoted to
the development of languages as a whole, its grammar and lexic, for which
mainly historical texts are considered, pos tagging constitutes an elementary
technique that is commonly applied as a first step, providing the basis for
any subsequent analysis.

For modern languages such as English, state-of-the-art pos tagging algorithms
based on machine learning methodology reach an accuracy as high as 97.3% [3],
so that the task can essentially be considered as solved. Historic languages,
on the other side, still impose challenges for pos tagging algorithms as well
as human experts. The reasons for this are manifold:

  * •

For such languages, the amount of data is very limited, and even the data
available is comparatively noisy, because the labels are provided by humans
who are not native speakers of that language.

  * •

In addition to noisy data, a pos tagger needs to deal with further
characteristics, such as missing regulations for orthography, and a multitude
of word classes [6], i.e., distinct labels.

  * •

The right pos tag not only depends on the considered word but also on its role
within a syntactical construction, and thus on the context in which it is
used. However, the context often cannot be easily differentiated due to a lack
of syntactic markers, since the concept of sentences usually did not yet
exist.

  * •

Last but not least, there is a risk of projecting the understanding of
contemporary speech onto the language under consideration, which is referred
to as “comparative fallacy”.

As a consequence, even experts are not entirely certain about many decisions.
In [12], the inter-annotator agreement for a historic corpus of Middle Lower
German (mlg) was reported at 92%, suggesting that there is significant room
for different interpretations. Nevertheless, words are commonly labeled with
single pos tags to keep the annotations consistent, in spite of a high risk to
introduce mistakes. As the predicted pos tags are used in many up-stream nlp
tasks, the reliability of the tagging is crucial to avoid error propagation.
By requiring pos taggers to commit only to a specific tag, errors are
deliberately enforced.

In this paper, we generalize the standard approach to pos tagging so as to
enable a tagger to express its uncertainty, thereby making pos tagging more
reliable. To this end, we build on the framework of set-valued prediction,
which has attracted increasing attention in machine learning research in
recent years [16], and integrate this framework with existing state-of-the-art
pos taggers. More precisely, for a given word and its context, we allow a pos
tagger to predict a set of candidate tags, for which it is sufficiently
confident that the ground truth tag is contained in that set. Figure 1
presents a comparison of an exemplary tagging with classical and set-valued
predictions.

Dat | is | vredebrake
---|---|---
dds | vafin | na

Dat | is | vredebrake.
---|---|---
$\\{\textsc{dds}\\}$ | $\\{\textsc{vafin},\textsc{vkfin}\\}$ | $\\{\textsc{na}\\}$

Figure 1: Example sentence taken from the mlg corpus (translation: this is
breach of peace) tagged classically on the left-hand side and with set-valued
prediction on the right. In this case it is uncertain, whether the verb is
represents a finite auxiliary verb (vafin), as it is frequently the case, or a
finite copular verb (vkfin).

Set-valued tagging does not only increase reliability, but also comes with
practical advantages. For example, the explicit handling of tagger uncertainty
can help reduce a possible propagation of errors through a pipeline of nlp
tasks, thereby increasing the reliability of down-stream tasks as well.
Furthermore, it reduces the workload of a human annotator in charge of
correcting the automatic annotations of a text, because it immediately points
to those cases that are unclear and offers a reasonable number of candidates
as options. This could be specifically useful for historic languages such as
mlg, where pos-taggers are often used to speed up the annotation process. Yet,
due to the limited amount of training data, the annotation quality is
relatively low in early stages.

In an empirical study, we demonstrate set-valued predictions to prove
beneficial at the example of a historic corpus of legal texts written in mlg
and a historical tag set comprising more than 90 word classes [6].
Furthermore, we find that the approach increases robustness of the pos-taggers
in general and specifically for unknown words, i.e., words that did not occur
in the training data.

The remainder of the paper is structured as follows. In the next section, we
start with a brief overview of related work and the state of the art in pos-
tagging, prior to introducing the problem more formally in Section 3. Our
approach of set-valued prediction for part-of-speech tagging is then presented
in Section 4 and evaluated empirically in Section 5. We conclude the paper
with a summary and an outlook on future work in Section 6.

##  2 Related Work

Pos-tagging is generally done with a maximum entropy Markov model (memm) to
exploit the sequential nature of the data. A memm is a generative model, where
a base classifier predicts the tag probability given the word and its context.
The choice of such a base classifier and the specific data representation and
provided context information vary across different approaches. One of the
earlier algorithms related to historic languages is the TreeTagger [21], which
employs a decision tree as base classifier. It was first introduced with
English language models and later on adapted to German [20] and it is still
used in current research.

[18] suggest a similar method but rely on logistic regression as a base
learner. Their work has been further refined by [14], who model the state
transitions in a different manner. [13] extend the latter, solving an issue
they refer to as label bias problem. The proposed algorithm is called
conditional random fields (crf).

Building on the work by [18], [26] refine memm models with a focus on unknown
words. [27] extend this work further by incorporating the findings of [13].
However, their suggestion to solve the label bias problem is computationally
less expensive. Instead of calculating a global model for state transitions,
they build a memm which conditions on both previous and succeeding tags,
resulting in the corenlp tagger algorithm. For a more detailed discussion of
the algorithm, we refer the interested reader to [9, ch. 5.4].

Deviating from the previously outlined approaches, [1] shows that plain hidden
Markov model (hmm)s are similarly powerful when used with trigrams and
suitable statistical smoothing. [25] propose an entirely different approach
using perceptrons. Their algorithm slightly outperforms corenlp. [3]
investigate recent neural network approaches for pos-tagging and other nlp-
tasks. [10] incorporate the bidirectional nature of crf with long short-term
memory (lstm), a specific type of recurrent neural networks, to cope with the
sequential nature of the data.

The problem of pos-tagging is generally well-studied for contemporary English.
However, it is often challenging if the data is noisy. For example, extensions
to corenlp have been proposed to enhance its performance when applied to short
messages on twitter [5]. The noise in this data is mainly caused by large
amount of unknown words, as new words emerge rapidly in the daily use of
languages.

As already said, the noise in historic corpora is due to different reasons,
including the annotator’s lack of experience and expertise as a non-native
speakers. This is often worsened by the sparsity of the data, particularly for
historic German. Despite the fact that more potent taggers have been proposed
in the recent past, TreeTagger is still used in linguistic research of
historic German [8]. Also, crf-based taggers have been used on mlg texts [12].

##  3 Problem Definition

In pos-tagging, the task is to assign each word (aka. token) $w_{i}$ of a
document, i.e., a sequence of words $D=(w_{1},\ldots,w_{n})$, a part-of-speech
tag $t_{i}$. Finally, the whole document is thus assigned a sequence of pos-
tags $\mathbf{t}=(t_{1},\ldots,t_{n})$. To put it formally, we are interested
in predicting the probability of a tag $t_{i}$ under the condition that we see
word $w_{i}$:

$P(t_{i}\mid w_{i}).$ (1)

However, the part-of-speech tag depends not only on the word $w_{i}$ itself,
but also on the context in which it is used. In modern languages, the scope of
the context is quite obvious, as it usually only encompasses the sentence in
which the word occurs. While these sentences in modern language can be clearly
distinguished by punctuation, historic languages typically lack such clear
indications and the concept of a sentence as we know it today. Still, the
context is crucial for determining the role of a word within a construction,
and therewith its part-of-speech tag. With $\mathtt{context}(w_{i})$ a
function referring to the context of the word $w_{i}$, we actually seek to
estimate the probability of a tag $t_{i}$ under the condition of the word
$w_{i}$ occurring within the context $\mathtt{context}(w_{i})$:

$P\big{(}t_{i}\mid w_{i}\land\mathtt{context}(w_{i})\big{)}.$ (2)

Let $\mathcal{W}$ be a vocabulary, $\mathcal{T}$ a tag set of size
$s:=|\mathcal{T}|$, and a context function, mapping the context of a word to a
real-valued vector $\mathbb{R}^{n}$. We aim to learn a function
$f:\mathcal{W}\times\mathbb{R}^{n}\rightarrow\mathcal{T}$, where
$\mathbb{R}^{n}$ denotes the context description of the respective word. As we
are also interested in the (un)certainty in the prediction of tag $t_{i}$ for
word $w_{i}$, we adapt the image of the function $f$ to be a vector
$\mathbf{p}=(p_{1},\ldots,p_{s})\in\left[0,1\right]^{s}$, where $p_{i}$
correspond to the probability of tag $t_{i}$. Obviously, the entries should
sum to 1, i.e., $\sum_{i=1}^{s}p_{i}=1$.

The function is induced from training data of the form
$(\mathcal{W}\times\mathcal{T})^{l}$ representing a document $D$ for which
each element $w_{i}$ is labeled with a tag $t_{i}$. Here, $l$ is the number of
words of the particular document. An important property is the sequential
order of the training data, where for $k\geq 1$ the elements $w_{i-k}$, $k\geq
1$ denote the preceding and $w_{i+k}$ the subsequent words of $w_{i}$. The
context function represents the context of a given word $w_{i}$ as provided by
these preceding and subsequent words and tags. The concrete instantiation of
this function highly depends on the respective method and has no common
signature. However, one simple example of such an instance is a binary
encoding indicating whether a specific word is present or absent in the
context.

##  4 Set-Valued Prediction for Part-of-Speech Tagging

In standard supervised learning, the goal is to induce a predictive model
$h:\,\mathcal{X}\rightarrow\mathcal{Y}$, where $\mathcal{X}$ is the so-called
instance space. To this end, the learner is given access to a set of training
data
$\\{(\boldsymbol{x}_{i},y_{i})\\}_{i=1}^{l}\subset\mathcal{X}\times\mathcal{Y}$.
In multi-class classification, the output space
$\mathcal{Y}=\\{y_{1},\ldots,y_{s}\\}$ consists of a finite number of class
labels (which correspond to the tags $t_{i}$ in pos-tagging, where
$\mathcal{Y}=\mathcal{T}$). Thus, a model $h$ (hypothetically) assigns a class
label $\hat{y}=h(\boldsymbol{x})\in\mathcal{Y}$ to each query instance
$\boldsymbol{x}\in\mathcal{X}$. The quality of a predictor is measured in
terms of its expected loss $\mathbb{E}[\ell(y,h(\boldsymbol{x}))]$, where
$\ell:\mathcal{Y}^{2}\rightarrow[0,1]$ is a loss function that compares a
prediction $\hat{y}=h(\boldsymbol{x})$ with a true outcome $y$, and the
expectation is taken with respect to an underlying (though unknown) joint
probability distribution on $\mathcal{X}\times\mathcal{Y}$.

###  4.1 Set-valued Prediction

Set-valued prediction is a generalization of the above setting, in which
predictions $h(\boldsymbol{x})$ are subsets of $\mathcal{Y}$, i.e., predictors
are now functions of the form $\mathcal{X}\rightarrow 2^{\mathcal{Y}}$. The
basic idea is to make “reliable” predictions $\hat{Y}=h(\boldsymbol{x})$ that
cover the true class label $y$ with high probability. At the same time,
$\hat{Y}$ should of course not be too large, as a prediction would otherwise
loose its value ($\hat{Y}=\mathcal{Y}$ is not very useful, despite being
correct with probability 1). These two criteria, correctness and precision,
are obviously in conflict with each other. Thus, in one way or the other, a
predictor needs to find a reasonable compromise. Theoretically, there are
different ways to learn such set-valued predictions. [16] introduce algorithms
that can calculate set-valued predictions for any probabilistic classifier,
based on the predicted class distribution for a given data sample. To this
end, they propose to generalize the notion of a loss function (or,
equivalently, utility function). More specifically, they propose a class of
utility functions of the following form:

$u(y,\hat{Y})=\underbrace{\llbracket
y\in\hat{Y}\rrbracket}_{correctness}\cdot\underbrace{g(|\hat{Y}|)}_{\mathclap{precision}}\,,$
(3)

where $\llbracket\cdot\rrbracket$ denotes the indicator function. A utility
function of that kind compares a ground truth class label $y$ with a predicted
set of candidates $\hat{Y}$. The utility is 0 in the case where
$y\not\in\hat{Y}$, i.e., if the true label is not covered by the prediction.
Otherwise, the utility depends on the cardinality of the predicted set: $g$ is
a monotone decreasing function such that $g(1)=1$, which means that the
highest utility of 1 is reached if $\hat{Y}=\\{y\\}$ is a singleton set with
the true label as its only element, and the utility decreases by adding
further candidates. An example of a utility measure, which will be used in our
experimental study later on, is the following function:

$u_{\beta}(y,\hat{Y})=\begin{cases}0&\mbox{if $y\notin\hat{Y}$}\,,\\\
1-\Big{(}\frac{|\hat{Y}|-1}{|\mathcal{Y}|-1}\Big{)}^{\beta}&\mbox{if
$y\in\hat{Y}$}\,,\end{cases}$ (4)

This function, if parameterized by $\beta\in]0,\infty]$, defines how quickly
the utility decreases when the size of the predicted set becomes larger.

Given a utility function (3) and a (conditional) probability
$P(\,\cdot\mid\boldsymbol{x})$, or at least a prediction of that probability,
a rationale prediction is a set $Y^{*}$ that maximizes the expected utility

$\displaystyle\mathbb{E}[u(\cdot,\hat{Y})]$
$\displaystyle=\sum_{y\in\mathcal{Y}}P(y\mid\boldsymbol{x})\cdot u(y,\hat{Y})$
$\displaystyle=\sum_{y\in\mathcal{Y}}P(y\mid\boldsymbol{x})\cdot\llbracket
y\in\hat{Y}\rrbracket\cdot g(|\hat{Y}|)$
$\displaystyle=g(|\hat{Y}|)\cdot\sum_{y\in\hat{Y}}P(y\mid\boldsymbol{x})\,.$

In machine learning, a prediction of that kind is referred to as a Bayes-
optimal prediction. To find this prediction efficiently, [16] propose the
Unrestricted Bayes-Optimal Prediction (ubop) algorithm. Roughly speaking, this
algorithms sorts the class labels $y_{i}$ in decreasing order of their
posterior probability $P(y_{i}\mid\boldsymbol{x})$ and successively computes
the expected utilities of the top-$k$ sets, i.e., the sets consisting of the
$k$ labels with highest probability. Starting with $k=1$, the algorithms stops
as soon as the expected utility decreases when adding another label. Under
certain technical (though not very restrictive) assumptions on the function
$g$, it can be shown that the set found in this way is indeed a Bayes-optimal
prediction.

The approach by [16] generalizes several other approaches to set-valued
prediction, which are recovered as special cases for a suitable choice of the
utility function. For example, [4] evaluate set-valued predictions in terms of
utility scores from the information retrieval community, such as precision,
recall, and the F1-measure. Other researchers call the same setting _credal_
or _cautious classification_. In a series of papers, they analyze several set-
based utility scores that reward abstention in cases of uncertainty [29, 28].
The framework of _conformal prediction_ also produces set-valued predictions,
albeit with a focus on confidence (the predicted set covers the true class
with a predefined probability) and less on utility [24]. Furthermore, set-
valued prediction can be seen as a generalization of multi-class
classification with a reject option [2, 17], where one either predicts a
single class or the complete set of classes.

###  4.2 POS-Tagging

The above framework of set-valued prediction can also be applied to pos-
tagging. In this case, the set of class labels $\mathcal{Y}$ is given by the
tag set $\mathcal{T}$, and an instance is a word $w_{i}$ together with its
context. Moreover, the utility function is of the form

$u(t,\hat{T})=\llbracket t\in\hat{T}\rrbracket\cdot g(|\hat{T}|)\,,$ (5)

and the expected utility of a subset of tags $\hat{T}$ is given by

$\displaystyle\mathbb{E}[u(\cdot,\hat{T})]=\sum_{t\in\hat{T}}P(t\mid
w_{i}\land\mathtt{context}(w_{i}))\cdot g(|\hat{T}|)\,.$

pavapavdptkzuna$0$$0.5$$1$$\\{\textsc{pavap}\\}$dposappernavvpp$0$$0.2$$0.4$$\\{\textsc{dposa},\textsc{pper},\textsc{na}\\}$
Figure 2: Visualization of ubop. The posterior distribution over tags is
converted into a set-valued prediction.

Figure 2 illustrates the application of the ubop algorithm, i.e., the
conversion from posterior probabilities to the set-valued predictions.

Recall that ubop requires the posterior probability distribution (2) as input,
and that the quality of this distribution will clearly have a strong impact on
the quality of the set-valued prediction. In principle, probability estimates
can be obtained by any probabilistic tagger whose context only depends on
surrounding words but not on tags. The TreeTagger, for example, estimates
probabilities in terms of relative frequencies of observations, which leads to
relatively coarse predictions.

As corenlp uses logistic regression, its probability estimates are better
suited for set-valued prediction. However, since the performance of pos-
taggers strongly relies on the contextual information harnessed, corenlp also
includes tags in the context. During prediction, this creates circular
dependencies, as predicting a tag for a specific word expects the contextual
tags to be set already. corenlp introduces a strategy to circumvent these
circular dependencies, which is based on a brute-force search stepping over (a
subset of) all possible contexts. When applying this approach to set-valued
targets, the contexts blow up exponentially, making the problem intractable.
Therefore, an approximation via post-processing is used in this work. To this
end, the document is first tagged in a standard way to initialize the context
information of each word, and then the tagging of every word is revised by a
set-valued prediction using the context information obtained from the first
pass. The pre-calculated context together with the word in consideration is
used to build a feature vector allowing to cast the original sequential
problem as a standard multi-class classification problem. In this way, we
enable the application of the ubop algorithm.

##  5 Experimental Evaluation

We evaluate the proposed set-valued prediction approach to part-of-speech
tagging, comparing two different types of pos-taggers, and relate their
performance to a baseline, which is introduced in Section 5.3. To this end, we
compare the performances obtained by the vanilla versions with the respective
extensions producing set-valued predictions. Furthermore, we assess the
generalization behavior of the approaches as well as their robustness for
different amounts of training data.

###  5.1 Experimental Setup

Throughout our experimental evaluation, we consider three scenarios of
different levels of training data available to the pos-taggers. To this end,
as a very first step, we split each document once into 80% training and 20%
test data. This was achieved by selecting one cutting point uniformly at
random and placing the second cut with respect to the size. Independent of the
scenario, the test data portion is never used for training, even if the
approaches are not evaluated on that specific portion of the data.

The three scenarios are defined as follows. First, we evaluate the approaches
being trained and evaluated on the same document only, i.e., we use the
training data portion of one document and test on the remaining 20% of the
respective document. We refer to this scenario as in-domain performance.
Second, in a leave-one-document-out fashion, we assess the ability of the
models being transferred to unseen texts using the training portion of all but
one documents and assess the performance with respect to the test portion of
the left-out document. In the last and third scenario, we train the approaches
on the training data portions of the entire corpus and then test them on the
test data portion of every text.

Our evaluation is then carried out in two parts. In the first part we report
the accuracy of the vanilla versions of the pos-taggers and the utility and
the mean size of the predicted pos-tag sets of the set-valued prediction pos-
taggers. The parameter $\beta$ of the utility function (4) is set to 1. The
second part of our evaluation concerns the sensitivity of the approaches with
respect to the parameter choice of $\beta$. Varying the value of this
parameter, which penalizes the prediction of larger sets, we investigate the
influence on the size of the predicted sets.

All the experiments were run on a single machine equipped with 6 cores
(i7-8700k for hyperparameter optimization runs and i7-9750H for the evaluation
of the pos-taggers) and 32gb of ram. The machine operates with a Manjaro Linux
5.4.39, Python 3.8 and Java 10.

###  5.2 Corpus Description

The corpus considered in this study mainly stems from the InterGramm
project111https://www.uni-paderborn.de/forschungsprojekte/intergramm [15, 22,
23] and consists of dateable and localizable legal documents and records of
judgements ranging from the 13th to the 17th century comprising 23 documents
in total. Some texts of dataset originally stem from the ReN project [19],
which have been partially adapted to be consistent to the tagging guidelines
of the InterGramm project. The majority of the documents originate from the
Central Low German region written in a historic German dialect called Middle
Low German. The remaining corpus contains the first Early New High German
texts that were written in Low German after the change of writing language. In
the course of the InterGramm project, these texts have been annotated with
pos-tags which are considered as ground truth labels.

Since an established, commonly accepted orthography did not exist at that
time, we unified different spellings of the same words to condense the number
of different words in a reasonable way. To this end, we first applied a
clustering algorithm using the Levenshtein distance as the distance metric and
let an expert double-check the correctness of the discovered clusters. The
texts used in this study are provided (together with the code to read and
process the documents) on GitHub222https://github.com/stheid/SetPOS.

For the sake of clarity, the evaluation presented in Section 5.4 focuses on
four selected documents from the Corpus, which are representatives of
different challenges when dealing with historic corpora. The results for the
remaining corpus are provided together with the code via the GitHub
repository. The Duisburger Stadtrecht (1500) can be seen as an outlier
document, as the dialect in this text is quite different from the rest of the
corpus. Bremer Urkunden (1351–1400) on the other hand can be seen as the
medoid of the data set, as the corpus contains many other deeds from the same
time, some of which are even from Bremen as well. Bambergische
Halsgerichtsordnung (1510) is one of the most recent documents in the corpus.
Finally, we consider the Kolberger Kodex (1297), which in turn is a rather old
one. In the following, the four documents will be referred to as Duisburg,
Bremen, Bamberg, and Kołobrzeg.

###  5.3 Baseline

To compare the different algorithms on a common ground, a baseline is used to
estimate the difficulty of the data set itself. The baseline predicts the tag
with the highest probability and solely depends on the word itself. In case
the word $w_{i}$ is known, the predictor is as follows:

$t_{i}=\operatorname*{\arg\max}_{t\in\mathcal{T}}P(t\mid w_{i})$

This posterior probability is estimated by the relative word frequency:

$P(t\mid w)=\frac{\\#(t,w)}{\\#(w)}$

If the word is unknown, the baseline predicts the globally most frequent tag
via the prior:

$t_{i}=\operatorname*{\arg\max}_{t\in\mathcal{T}}P(t)$

In our corpus, this is the na tag, which represents a common noun. Aligning to
the other algorithms, this tagger can only predict tags that are known from
the training data.

Within the set-valued prediction framework, the conditional probability
distributions, or the prior in case of an unknown word, are used directly.

###  5.4 Results

Across all experiments, the TreeTagger and corenlp showed competitive results.
Generally speaking, the TreeTagger predicts smaller sets with slightly
inferior accuracy and utility compared to corenlp. The weaker performance was
generally more consistent for the utility measure. The baseline was
outperformed by both taggers in nearly every scenario and measure. The margin
was generally larger when assessing the accuracy, while performances with
respect to utility were more similar.

Figure 3: Performance numbers of the different taggers when trained and
evaluated on one document.

The results of the in-domain scenario, where the tagger was trained and
evaluated on one document, is shown in Figure 3. In this scenario, the data is
as homogeneous as possible, while providing much less training data than in
the other scenarios. The accuracy on the smaller documents such as Bremen (7.5
k tokens) and Kołobrzeg (13.2 k tokens) indicates that the TreeTagger is more
data efficient than corenlp. With the Bremen document being particularly
small, all taggers including the baseline make more than one tagging error in
five words. For the larger texts Duisburg (15.5 k tokens) and Bamberg (19.7 k
tokens), corenlp provides the best accuracy.

When comparing the accuracy with the utility, all taggers recover a lot of
their errors, as they are allowed to provide more tags on the small Bremen
document. Simultaneously, the set sizes for the Bremen document are the
largest, regardless of the tagger. However, they are only slightly larger than
for the other documents. Specifically the TreeTagger has only a slightly
increased set size, but also performs poorer than the baseline in terms of
utility.

Figure 4: Performance numbers of the different taggers when trained and
evaluated in a leave-one-document-out fashion.

Figure 4 shows the performance on the transferability scenario. Since Duisburg
has a different dialect than the other documents, none of the classifiers is
able to predict more than half of the tags correctly. The Bamberg and
Kołobrzeg texts show similar performance drops, though less severely. For the
Bremen document, the classifiers present superior accuracy as compared to the
in-domain scenario. The larger data set allows thus for a higher performance
than when training only on the homogeneous document itself.

Regardless of the text or approach, the utility measures are significantly
higher. For a difficult text such as Duisburg, the performance increase over
the accuracy comes at the cost of an increased set size. However, in a real-
world scenario, i.e., in interaction with a human annotator, such a suggestion
might still be more useful than predicting a wrong tag half of the time.

Figure 5: Performance numbers of the different taggers when trained on the
whole corpus.

Finally, Figure 5 shows the results when using the training section of the
entire corpus. Providing the classifier with additional training data as
compared to the in-domain scenario can also result in detrimental effects. For
example, the prediction performance for the Bremen document can be negatively
affected by adding portions of the Duisburg text to the training data. The
performance on the Kołobrzeg document suffers significantly in accuracy as
compared to the first scenario.

However, it is a non-trivial task to decide which data to exclude from the
training data by looking only at unlabeled evaluation data. The results of the
in-domain scenario and training on the whole corpus are comparable, however,
meaning that the classifiers are not severely affected by confusing data.
Again, the utility proves to be more robust in terms of performance. Even
though the accuracy on the Kołobrzeg text dropped when considering the whole
corpus, the utility is not affected negatively at all. For TreeTagger and
corenlp, the set size across all data sets is on average around 2, clearly
outperforming the baseline.

In this scenario, corenlp outperforms the TreeTagger in accuracy and utility,
whereas the set sizes of the TreeTagger are typically smaller. However, if it
is desirable to have smaller set sizes, this can also be enforced in the
parameterization of the ubop algorithm to force corenlp to return smaller sets
as well. Both taggers use the optimal set size for a specific posterior and
penalty function.

###  5.5 Detailed Analysis

In this section, we analyze the sensitivity of the results with respect to the
parameter $\beta$ of the utility function (Equation 4). Recall that this
parameter defines the amount of risk aversion, as it modifies the penalty
incurred by larger set sizes. As $\beta\to 0$, the classifier predicts only
singleton sets. For $\beta\to\infty$, the classifier behaves more risk averse,
preferring larger sets to ensure the correct tag to be covered with a higher
probability.

The results shown in Figure 6 are obtained by averaging all evaluations of the
third scenario, where the classifier is trained on the whole corpus. Notably,
the utility increases with larger values of $\beta$. However, values larger
than one barely increases the utility score. This is mainly because the
utility can only increase if either the penalty for a large set size is
decreased, or the recall is increased due to the increased coverage of the
posterior distribution. When investigating the average set size, we see that
the baseline always results in the largest sets and the TreeTagger provides
the smallest sets.

For the baseline, this is in agreement with the confidence of the tagger, as
it also performs the worst. However, the TreeTagger yields smaller set sizes
while showing smaller confidence as compared to corenlp. This indicates that
the probability distributions obtained through the decision tree, which are
estimated as fractions of observed frequencies of features in the training
data, are less well calibrated. This is made especially apparent by the fact
that even the baseline can outperform the TreeTagger when selecting $\beta>2$.
In contrast to this, the logistic regression model as employed by corenlp
tends to produce a more fine grained and better calibrated posterior.

Figure 6: The average utility and average set size with respect to the
parameter $\beta$. Larger values of $\beta$ result in a more risk averse
behaviour. The performance is aggregated first within each document and then
averaged again. The error bars show the standard deviation of the values.

Finally, the distribution over the predicted set sizes is analyzed in Figure
7. For this experiment, corenlp was trained on the training data of the whole
corpus and evaluated on the complete test section with $\beta=1$. For known
words, the large majority of predictions are basically singletons. The
distribution of the set sizes is decreasing almost exponentially. The
histogram over unknown words decays much slower. Still, the majority of
unknown word predictions results in a singleton prediction. Predictions of
sets containing more than 8 elements are extremely seldom in any case.

Figure 7: Distribution of the set sizes. The histogram is calculated from the
predictions on the whole corpus with corenlp fitted on the train portion of
the whole data set

##  6 Conclusion

We proposed an extension of pos-tagging, in which a tagger is allowed to
provide set-valued annotations in cases of uncertainty. To this end, we
leveraged methods for set-valued prediction as recently developed in the field
of machine learning and combined them with state-of-the-art pos taggers. In
our empirical study, in which we analyzed the specifically relevant case of
annotating texts from a historic language, we observed an improved utility as
compared to the standard pos-tagging. Another observation is that set-valued
predictions seem to be more robust with regard to the employed base learner,
while the set sizes (number of candidate tags) are still moderate on average.

In future work, we plan to elaborate on promising extensions of the approach
to reliable tagging as presented in this paper. One idea, for example, is to
take multiple potential contexts into account, i.e., different (structurally
ambiguous) readings of a text passage. For example, the current extension of
the corenlp tagger is limited to the most likely context extracted via a first
pass of the algorithm, thus completely ignoring less likely contexts. Another
interesting idea is to combine set-valued prediction with set-valued
supervision. Thus, instead of assuming deterministic annotations in the
training data, the human expert would be allowed to provide set-valued
annotations in cases where he or she feels uncertain and considers several
tags as plausible options — just like the tagger at prediction time. Learning
from “weak” supervision of that kind can be accomplished by means of
techniques for so-called superset learning [11, 7].

## References

  * [1] Thorsten Brants  “TnT: a statistical part-of-speech tagger”  In _Proceedings of the sixth conference on Applied natural language processing_ , 2000, pp. 224–231  Association for Computational Linguistics
  * [2] Chi-Keung Chow  “On optimum recognition error and reject tradeoff”  In _IEEE Transactions on information theory_ 16.1 IEEE, 1970, pp. 41–46
  * [3] Ronan Collobert et al.  “Natural language processing (almost) from scratch”  In _Journal of machine learning research_ 12.Aug, 2011, pp. 2493–2537
  * [4] Juan José Del Coz, Jorge Díez and Antonio Bahamonde  “Learning Nondeterministic Classifiers”  In _The Journal of Machine Learning Research_ 10 JMLR, 2009, pp. 2273–2293
  * [5] Leon Derczynski, Alan Ritter, Sam Clark and Kalina Bontcheva  “Twitter part-of-speech tagging for all: Overcoming sparse and noisy data”  In _Proceedings of the International Conference Recent Advances in Natural Language Processing RANLP 2013_ , 2013, pp. 198–206
  * [6] Stefanie Dipper et al.  “HiTS: ein Tagset für historische Sprachstufen des Deutschen.”  In _JLCL_ 28.1, 2013, pp. 85–137
  * [7] E. and W. Cheng  “Superset Learning Based on Generalized Loss Minimization”  In _Proceedings ECML/PKDD–2015, European Conference on Machine Learning and Knowledge Discovery in Databases_ , 2015
  * [8] Nora Echelmeyer, Nils Reiter and Sarah Schulz  “Ein PoS-Tagger für das Mittelhochdeutsche”, 2017
  * [9] Stefan Heid  “Set-Valued Prediction for Part-of-Speech Tagging”,  DOI: 10.17619/UNIPB/1-957
  * [10] Zhiheng Huang, Wei Xu and Kai Yu  “Bidirectional LSTM-CRF models for sequence tagging”, 2015  arXiv:1508.01991
  * [11] E. Hüllermeier  “Learning from imprecise and fuzzy observations: Data disambiguation through generalized loss minimization”  In _International Journal of Approximate Reasoning_ 55.7, 2014, pp. 1519–1534
  * [12] Mariya Koleva et al.  “An automatic part-of-speech tagger for Middle Low German”  In _International Journal of Corpus Linguistics_ 22.1 John Benjamins, 2017, pp. 107–140
  * [13] John Lafferty, Andrew McCallum and Fernando CN Pereira  “Conditional random fields: Probabilistic models for segmenting and labeling sequence data”, 2001
  * [14] Andrew McCallum, Dayne Freitag and Fernando CN Pereira  “Maximum Entropy Markov Models for Information Extraction and Segmentation.”, 2000
  * [15] Marie-Luis Merten, Nina Seemann and Marcel Dominik Wever  “Grammatikwandel digital-kulturwissenschaftlich erforscht. Mittelniederdeutscher Sprachausbau im interdisziplinären Zugriff”  In _Niederdeutsches Jahrbuch_ , 2019, pp. 124–146
  * [16] Thomas Mortier et al.  “Efficient Algorithms for Set-Valued Prediction in Multi-Class Classification”, 2019  arXiv:1906.08129
  * [17] Harish G. Ramaswamy, Ambuj Tewari and Shivani Agarwal  “Consistent Algorithms for Multiclass Classification with a Reject Option”  In _CoRR_ abs/1505.04137, 2015
  * [18] Adwait Ratnaparkhi  “A maximum entropy model for part-of-speech tagging”  In _Conference on Empirical Methods in Natural Language Processing_ , 1996
  * [19] ReN-Team  “Referenzkorpus Mittelniederdeutsch/Niederrheinisch (1200-1650)”  Hamburger Zentrum für Sprachkorpora, http://hdl.handle.net/11022/0000-0007-D829-8, 2019
  * [20] Helmut Schmid  “Improvements in part-of-speech tagging with an application to German”  In _Natural language processing using very large corpora_ Springer, 1999, pp. 13–25
  * [21] Helmut Schmid  “Probabilistic Part-of-Speech Tagging Using Decision Trees”  In _Conference on New Methods in Language Processing. Manchester, UK_ , 1994
  * [22] Nina Seemann et al.  “Annotation Challenges for Reconstructing the Structural Elaboration of Middle Low German”  In _Proceedings of the Joint SIGHUM Workshop on Computational Linguistics for Cultural Heritage, Social Sciences, Humanities and Literature_ Association for Computational Linguistics (ACL), 2017, pp. 40–45  DOI: 10.18653/v1/W17-2206
  * [23] Nina Seemann et al.  “Supporting the Cognitive Process in Annotation Tasks”  In _Postersession Computerlinguistik der 40. Jahrestagung der Deutschen Gesellschaft für Sprachwissenschaft_ , 2018
  * [24] G. Shafer and V. Vovk  “A Tutorial on Conformal Prediction”  In _Journal of Machine Learning Research_ 9 JMLR.org, 2008, pp. 371–421
  * [25] Libin Shen, Giorgio Satta and Aravind Joshi  “Guided learning for bidirectional sequence classification”  In _Proceedings of the 45th annual meeting of the association of computational linguistics_ , 2007, pp. 760–767
  * [26] Kristina Toutanova and Christopher D Manning  “Enriching the knowledge sources used in a maximum entropy part-of-speech tagger”  In _Proceedings of the 2000 Joint SIGDAT conference on Empirical methods in natural language processing and very large corpora: held in conjunction with the 38th Annual Meeting of the Association for Computational Linguistics-Volume 13_ , 2000, pp. 63–70  Association for Computational Linguistics
  * [27] Kristina Toutanova, Dan Klein, Christopher D Manning and Yoram Singer  “Feature-rich part-of-speech tagging with a cyclic dependency network”  In _Proceedings of the 2003 Conference of the North American Chapter of the Association for Computational Linguistics on Human Language Technology-Volume 1_ , 2003, pp. 173–180  Association for computational Linguistics
  * [28] G. Yang, S. Destercke and M. Masson  “The Costs of Indeterminacy: How to Determine Them?”  In _IEEE Transactions on Cybernetics_ 47, 2017, pp. 4316–4327
  * [29] Marco Zaffalon, Corani Giorgio and Denis Deratani Mauá  “Evaluating credal classifiers by utility-discounted predictive accuracy”  In _Int. J. Approx. Reasoning_ 53, 2012, pp. 1282–1301