# Controlling Resource Allocation using Blockchain-Based Delegation

Shantanu Pal∗, Ambrose Hill∗∗, Tahiry Rabehaja§, Michael Hitchens§§ ∗School of
Computer Science, Queensland University of Technology, Brisbane, QLD 4000,
Australia
∗∗School of Computer Science and Engineering, University of New South Wales,
Sydney, NSW 2052, Australia
§Risk Frontiers, Sydney, NSW 2065, Australia
§§Department of Computing, Macquarie University, Sydney, NSW 2109, Australia
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Allocation of resources and their control over multiple organisations is
challenging. This is especially true for a large-scale and dynamic system like
the Internet of Things (IoT). One of the core issues in such a system is the
provision of secure access control. In particular, transfer of access rights
from one entity to another in a secure, flexible and fine-grained manner. In
this paper, we present a multi-organisational delegation framework using
blockchain. Our framework takes advantage of blockchain smart contracts to
define the interactions and resource allocation between the consortium of
organisations. We show the feasibility of our solution in a real-world
scenario using the allocation of transportation credits in a multi-level
organisational setting as a use-case. We provide proof of implementation of
the proposed framework using the Hyperledger Fabric blockchain platform. Our
results indicate that the proposed framework is efficient and can be used for
city-wide transport, potentially even scale country-wide with a shared
blockchain with complex access control rules. It also bestows better
transparency to the delegation of access rights and control over the
employees’ transportation access for the organisations.

##  I Introduction

In an increasingly digitised and decentralised environment, groups of users
will wish to access, employ and expend resources in ways that are both co-
operative and dynamic. Groups of users will draw on common resources (e.g.,
digital currency), to which they have authorised access [1]. However, even
with pre-existing authorisation, the extent and nature of the use they make of
the resource may not be known in detail in advance. Limiting each user to an
average portion of the resource may not be an efficient use of the resource,
as some users will wish for greater than average access, some for less than
average. Allowing each user access to a greater than average share of the
resource risks over use. For example, a group of users, may be able to access
100 units of a resource between them. Say there are 10 members of the group.
An average allowance would be 10 units. However, if not all users access this
much, some of the resource goes to waste. Allowing all users access to more
than 10 units risks over-allocation. While, in centralised systems, this
situation can be easily handled, in distributed environments, where resources
are supplied by multiple providers and accessed by users external to that
provider, ensuring efficient access without over-committing the resource is a
more complex issue [2]. In such situations, the providers and consumers of
resources may not want to be at a disadvantage in terms of the control of the
relationship. That is, they may want the relationship supported by an
infrastructure that treats all participants equally.

In situations such as these the issue of access control delegation is
significant [3]. In such an environment, multiple attributes possessed by an
entity need to be validated by multiple different authorities that regulate
the access control policies. Delegation denotes the transfer of access rights
from one entity to another that is governed by a set of access control
policies and associated conditions to access a resource [4]. That said, the
delegation of access rights determines the level of access that must be
transferred from one entity to another, governed by the set of access control
policies and associated access conditions. In a closed environment, such
delegation may be controlled by a central entity employed to perform this
function. But when the system grows, for example, in a multi-organisational
context, the multi-level delegation needs to be performed over a distributed
system spanning across multiple jurisdictions. Given the scale, dynamic
nature, and massive network complexity of interconnected devices, users,
applications, and services (e.g., in an Internet of Things (IoT) setting [5]),
this becomes a challenging task, in particular, to control resources allowing
access only to the authorised users.

###  I-A Motivation and Problem Statement

Consider the challenge of shared resources discussed above. Suppose an
organisation wants to create an automated credit system to maintain and manage
costs associated with the transportation-related expenses of employees. This
is achieved through the use of a pool that provides flexibility and efficiency
in credit management. Employees access the credit pool through delegation
which has its root in access control systems. The delegated access to the pool
can then be attached with conditions and tree-like hierarchies which provides
an expressive and flexible platform upon which granular and complex rules can
be written. Through delegation, employees have access to the credit pool under
given and specific conditions that are automatically verified. For our
purpose, we call this a transportation credit. Transportation credit can be
seen as an amount of money (virtual) that an employee can spend in a certain
period of time to perform some specific tasks. For instance, an employee can
travel by bus, train, or flight to join a business meeting, perform remote
operational tasks or simply commute in-between work sites. In general, the
conditions can use spatio-temporal properties as well as other aspects such as
employee ranks or mode of transportation. The company purchases an amount of
transportation credit and allocates access to employees where the sum of the
access can exceed total purchased. This allows flexibility to meet individual
work requirements while still maintaining an overall budget.

Figure 1: A conceptual view of the delegation process in multi-organisations.

The organisation contacts a preferred transport company (or several transport
companies) to buy some transportation credit (in exchange for crypto or fiat
currency). After evaluation of the request and successful payment, the
transportation company sends the appropriate credit to the organisation. Upon
receipt, the organisation allocates the credits based on the access control
policies and enforceable conditions. The access rights are delegated to the
intended departments, and the department further delegates access rights (with
more conditions, so as to ensure monotonicity) to the employees working within
that department. In Fig. 1, we illustrate a conceptual view of such a
delegation process. Note, there may be multiple organisations and multiple
transport companies present in the system. There is a ‘channel’ between the
organisations and transportation companies to mutually agree on the services
and the associated costs. That is, the transportation credit has some top-
level access control between the organisation and consortium of transportation
companies (different companies managing the various transportation services).
For each organisation, there may be many employees working in various
departments. Effectively, each organisation can purchase a certain amount of
credit, store them in a ‘pool’ (controlled by the organisation), and then
allow employees to access them on demand, as long as the access control rules
are satisfied. Employees, once their company has joined the network and
purchased some amount of transportation credit, can then request to use, and
access these credits in near-real-time. Access to these transportation credits
(i.e., resources) would be, for example, via a mobile application that will
allow the employees to request, check and use the credits. Note, we use the
term company to show the business, and the term organisation to show a large-
scale business. In essence, they can be interchangeable, and we use these two
separate terms for ease of reading.

The example just described is an example of the broader situation described
above, that is, one where we may have an overall budget, and multiple entities
that can access that budget, but where a precise pre-allocation of resources
is non-optimal. To provide fine-grained access control delegation for
controlling resource allocation, several mechanisms can be used [6] [7]. For
example, Role Based Access Control (RBAC) can provide fine-grained access
control over the resources explicitly using user-to-role mappings. However, in
RBAC, for every access to a resource, there is a need to define separate user-
to-permission relations. Moreover, RBAC is highly centralised in nature,
limiting its scalability for large-scale dynamic systems. Attribute Based
Access Control (ABAC) uses attributes to improve the policy management rather
than depending upon the concrete unique identity of individual entities.
However, ABAC does not, for example, support mechanisms for grouping together
policies with different attribute requirements that allow access to a single
resource or policies with the same attribute requirements that allow access to
different resources. That said, ABAC requires a policy management mechanism,
especially when the number of policies rises significantly [8]. Capability
Based Access Control (CapBAC) provides flexible access control by distributing
capability tokens that contain access rights or privileges (along with
additional conditions) validated at the edge IoT devices at the time of access
to a resource. However, most of the CapBAC systems are centralised for policy
storing and their management [9]. Therefore, these access control mechanisms
can not provide scalable, robust, and trustworthy delegation supporting the
decentralisation of resources.

We argue that managing such resource delegation in a multi-level scenario
involving various dynamic and large-scale systems requires scalable,
efficient, lightweight, trustworthy, and robust policy enforcement mechanisms
[10]. The delegation process should scale with the system through
decentralisation. At the same time, there is a need to establish trust between
the various entities within the system to delegate access rights [11].

Blockchains have the potential to address these issues and overcome the
limitations of traditional access control mechanisms in a more efficient and
fine-grained way for large-scale IoT systems spanning multiple jurisdictions
[12]. The distributed platform of blockchain allows an apparent balance of
power where no participating entity has sole control of the system. This means
that agreement must be achieved by parties regarding any addition, deletion,
or update of contract and payments for every transaction. This creates a
balanced atmosphere for the clients and service suppliers through an open
marketplace platform where supply and demand are dynamic. In addition, using
blockchain as a base delivers new opportunities by providing distributed
storage and computational framework on which programs can be executed, which
ultimately leads to efficiency and automation. Several properties of the
blockchain (e.g., no central authority and trusted third-party, consensus
mechanism, immutable, irreversible and tamper-proof, accessibility,
auditability, etc.) offer secure and safe foundations to record and track a
list of transactions for a large number of devices in a highly transparent,
auditable and efficient way [13]. Moreover, our use of Hyperledger enables the
segmentation of the market into channels where private interactions between an
organisation and multiple transport suppliers is supported on top of the
underlying global blockchain. This means that, even though the native payment
system is universal to all parties, secure and private interactions can be
established dynamically while inheriting the aforementioned blockchain
properties.

###  I-B Contributions

We employ blockchain to provide granular and fine-grained decentralised
management of access control delegation to resources within a multi-
organisational establishment. This includes an entity-centric delegation
tailored to various system granularities spanning over multiple timescales.
The main contributions of the paper can be summarised as follows:

  * •

We propose a framework that can manage resources owned by a consortium of
entities, and assists allocation of these resources through access control
delegation.

  * •

We present the system design along with a detailed framework of the proposed
delegation model. We develop a distributed and decentralised delegation
framework for fine-grained access rights transfer using blockchain.

  * •

We provide a detailed proof of concept prototype implementation in the
Hyperledger Fabric blockchain platform to show the feasibility of our system.

The rest of the paper is organised as follows. In Section II, we discuss
system components, system functionality, and communication protocol of the
proposed delegation framework. In Section III, we present system
implementation and evaluation of the achieved results. Section IV includes
related works. Finally, we conclude the paper with direction to the future
work in Section V.

##  II Proposed Delegation Framework

In this section, we discuss (i) the various components of the proposed
delegation framework, (ii) the system functionality, and (ii) show the
communication protocol between the various components of the framework.

###  II-A Components

In Fig. 2, we illustrate the proposed framework. It is composed of the
following major components:

  * •

Employee: Who works within the company and wants to access transportation
credit. We assume that all employees have a smart device that can be used to
access a resource, as well as able to perform the communication between the
various entities within the organisation.

  * •

Organisation: Where a group of people works together for a particular purpose
in pursuing dedicated objectives to e.g., a business, institution, or an
association. There may be various departments within a company within which
groups of people function.

  * •

Blockchain Network: A dedicated distributed infrastructure spanning over the
entire network to provide ledger and smart-contract services autonomously. We
select a private blockchain network as all participating organisations can be
identified, and to restrict access only to members of those organisations.

  * •

Transportation Company: A dedicated infrastructure (or business) that provides
transportation services to move people or goods e.g., bus, train, taxi, or
flights. It also provides a chain of services from scheduling timetables,
managing ticketing, and control the logistics process.

Figure 2: Layer view of the proposed blockchain-based delegation framework.

###  II-B System Functionality

The blockchain network interfaces between businesses wishing to organise
transportation credits for their employees, and the transportation companies
that facilitate those solutions. We call the overall network a transport
chain. We then setup private channels on the transport chain for each
participating organisation. A channel here is another distributed ledger that
sits on top of the larger blockchain but is only maintained by a subset of the
participants. For this use case each organisation would create their own
channel and include any transport companies they want to conduct business
with. With this design, privacy is guaranteed between organisations. Transport
companies uses a token smart contract on the transport chain to sell
transportation credits (maybe in terms of tokens, tickets, and passes) to the
organisations. As noted above, the currency used can be any crypto or fiat
currency, however, the participants must agree on the currency. Using a crypto
currency would allow the financial transactions to take place on the transport
chain via the smart contracts. Transport companies would join channels with
any organisation looking to purchase transportation credits for that transport
type.

The organisation would also use the smart contract to purchase the
transportation credits. However, once they have been purchased the
tokens/tickets/etc. can be accessed through access control rules defined by
another smart contract deployed and controlled by the organisation. Employees,
once their company has joined the transport chain network and purchased some
amount of transportation credits, can then request to use and access these
tokens in near-real-time. They would have access to the transport chain via a
mobile app that will allow them to request, check and use these credits. Note,
when an employee requests transportation credits, the access control smart
contract can automatically check the access request against the access rules.
The rules can be based on many metrics including amount, time, role, location,
or transport type.

In other words, when an employee requests access to transportation credits via
the organisation’s access control smart contract – the access request validity
and whether the organisation has enough credits is checked and stored on
blockchain network via a transaction to the token smart contract. The employee
can then use the credits at the point of transport, which once used will send
confirmation back to the token smart contract, finalising the trip and using
up the required amount of credits. The reason two smart contracts are used is
so that the organisations have control and privacy over the access control
rules but they are still on the blockchain to automate the checking process.
Transport companies can guarantee that employees have the right to use credits
without seeing what made them eligible.

###  II-C Communication

In Fig. 3, we illustrate the steps each entity in our system takes to
communicate with and use the system. To give a more fine-grained view of the
interaction, it is split up into three parts, (i) purchase transportation
credit, (ii) access control setup, and (iii) use transportation credit. These
could be generalised in the obvious fashion if a different resource was being
managed. A detailed description for each of them is as follows:

  * •

Step 1: The organisation and the transportation company will negotiate a price
for transport credit (in terms of tokens) that can be used with that
particular transportation company. This happens off-chain (i.e., outside the
blockchain) and there is no time limit as the deal will need to be in the best
interest of both parties.

  * •

Step 2a: Once a price has been agreed upon by both parties, then the
blockchain is updated. First, the transportation company will initialise a
token smart contract with the price and submit a transaction that places the
agreed amount of tokens in escrow (i.e., a financial and legal agreement).

  * •

Step 2b: The organisation will send payment, either via another token or off-
chain with a receipt being put on-chain, to the smart contract.

  * •

Step 3: The contract will wait for both the tokens and payment before
releasing the tokens. There is also a check here to ensure that the amount of
tokens and amount paid matches the proposal. This is done as there is an
initialisation step to the contract that requires the parameters of the
proposal to be entered. If any of the transactions do not match the proposal
the transaction is rolled back and a new contract will have to be deployed.

  * •

Step 4 (a and b): Once the payment and tokens have been received the smart
contract will emit confirmation events on the channel notifying the
transportation company and organisation that the transaction is successful.

Figure 3: Communications among the different components of the framework.

  * •

Step 5: The organisation deploys an access control smart contract on the
channel. This contract will have the codified rules for accessing the tokens.
This is a completely internal process and the organisation has complete
control over which employees can access the tokens, how much they can access
for certain services, and even delegate this access control.

  * •

Step 6: When an employee wants to access those tokens i.e., use the transport
service, they will put in their transport details (start/end destination,
transport type, etc.) into their mobile app. This can be done in advance or at
the point of interaction with the transportation company.

  * •

Step 7: The system (managed by the transportation company) will then initiate
a transaction that will take confirm the trip and send it to the access
control contract.

  * •

Step 8: The smart contract will process the request by validating two values.
Firstly, it will check that the organisation has enough balance for the
transport, this could be calculated based on the final destination or just
having a maximum spending limit. It then checks that the employee passes the
access control rules. If both checks are passed, an event is emitted to the
transportation company to signal that the trip can take place.

  * •

Step 9: At the end of the trip, the employee finalises the trip on their
mobile app.

  * •

Step 10: The transportation company will also send a transaction when the trip
is complete which will allow the smart contract to automatically use up the
tokens.

##  III System Design and Evaluation

In this section, we discuss (i) the implementation details of the proposed
delegation framework, and (ii) evaluate the achieved results.

###  III-A Implementation

We use Hyperledger Fabric (HLF) to implement the proof of concept of our
system [14]. HLF is an enterprise-ready blockchain platform that contains many
of the required features (e.g., performance, scalability, and levels of trust)
that our system will use. Version 2.2 of HLF is used, and version 0.4.2 of
Hyperledger Caliper is used to benchmark the system. The tests are run on a
Dell Latitude 7490 Notebook with 8 GB of memory and an Intel Core i5
processor. The smart contracts are written in GO version 1.15.2.

Note, HLF’s inbuilt channel system is used to set up each organisation on
their own private channel that transport companies can then be added to for
price negotiation and token generation. Having separate channels for each
organisation allows for private negotiation, the delegation of contracts and
usage whilst still storing all key transactions into the blockchain state. The
channel system can be visualised as a ledger on a ledger with access control
tools placed on top. Every entity will have access to the foundation ledger
and that will store information that is public or vital for users to interact
with the system, while any of the private information will be stored on one of
the smaller ledgers, and only authorised entities will be given access to
these ledgers.

As we discussed in the previous section, the implementation consists of two
smart contracts, the token smart contract, and the access control smart
contract. There will be one access control contract per channel which the
organisation controls. This smart contract is where the organisation’s admin
can specify rules (and conditions) for the delegation and usage of the tokens
on this channel. Each transport company that wishes to interact with this
organisation must deploy a token contract which can be done before or after
the price negotiations. The price and amount of tokens for each transportation
mode can be maintained using this contract. There would be one channel per
organisation on the network in a production deployment, with each channel
having one access control contract and as many token contracts as transport
companies on that channel.

Our test network consists of two organisations and two transport companies,
each on its own channel. The transactions are generated in workloads using
caliper. To reduce strain on the test machine, the two contracts were combined
and deployed together. For testing purposes, two fewer docker containers are
needed, and it functions theoretically the same as though two contracts were
deployed. The simulation was run ten times, each time simulating over 20,000
transactions. The transactions simulated were as follows:

  * •

Request_Access: The transaction a user would send when trying to use a
transport token. The smart contract will check that this user has permission
to use tokens and that the organisation has the tokens to be used.

  * •

Finish_Trip: The transaction a transport company would send when it detects a
user has completed their trip using this service. The trip object in the
blockchain state is updated, saying it has been complete and any tokens
associated with that trip are now considered spent.

Each round of testing involved simulating different send rates for the system,
starting at 100 transactions per second (tps) and ending at 300 tps,
increasing the send rate by 50 tps each time.

###  III-B Results and Discussion

Figure 4: Studying the throughput and latency of the proposed framework.

In Fig. 4, we illustrate the achieved results of the average throughput and
latency of the system. Next, we discuss the throughput, and then the latency
in detail. We also discuss the suitability of the achieved results of the
proposed system in practical scenarios.

We observe that the system reaches throughput saturation between 175 and 200
transactions per second. Request_Access is the more computationally expensive
transaction. It is expected to have a smaller throughput than the Finish_Trip
transaction, which can be seen when the send rate is high (i.e., more than 200
tps), and the system is past saturation. Below saturation, the system is able
to process these transactions similarly. With the latency results, it is clear
to see that the latency is trivial before the system reaches saturation as it
is constantly less than 0.5 seconds. When the system does reach saturation,
there is an upwards trend in latency. However, this is expected as when the
system is under stress from many transactions, for each second there are more
transactions than the system can handle, the backlog of pending transactions
continues to grow, leading to longer wait times for confirmed transactions. At
a workload of 300 transactions per second, the latency is seen to be 10
seconds for both transactions.

With a throughput of 175 tps and a maximum latency of 10 seconds, the
prototype system is more than capable of handling a transport application of a
large size (i.e., many concurrent users). Transactions such as funding and
token generation can be processed in advance and so do not need to be taken
into account when benchmarking the system. The critical transactions, such as
requesting access, need to be handled as efficiently as possible as they will
be executed at the point of interaction between user and transportation mode.
It can be noted that depending on the size of the organisations and transport
companies, our system would be able to handle a large number of users all
requesting access and finishing trips at the same time. Moreover, if the
situation does occur where there are more than 175 requests a second, a user
would not be waiting more than 10 seconds for confirmation.

These results indicate that this system could be used for city-wide transport,
potentially even country-wide, with a sharded blockchain. Even organisations
and transport companies with complex access control rules will experience
short wait times, transparency into transport usage, trusted digital history
of use, and total control over their employees’ transport access can easily be
achieved to a flexible and fine-grained manner.

##  IV Related Work

Recently, there has been significant attention on blockchain and smart
contract technology for authentication, access control and delegation of
access rights [15] [16]. Several proposals have discussed the need for
blockchain technology in transport and logistics to facilitate payments,
fulfill their tasks, and deliver goods through a secure supply chain [17] [18]
[19]. However, the application of access control delegation using blockchain
in transportation, in particular, for transportation resource allocation, is
lacking in most of these proposals.

For instance, to improve transportation infrastructures, proposal [20]
discusses a blockchain-based real-time ride-sharing service. It mainly focuses
on efficient vehicle utilisation so that the number of vehicles on the road
can be minimised, reducing traffic congestion. In [21], a blockchain-based
intelligent transportation system is discussed. Blockchain is used to
establish a decentralised autonomous platform for the transportation
ecosystem. In [22], a blockchain-based resource allocation technique is
discussed. A video analysis framework is used to improve traffic safety and
efficiency for the Internet of Autonomous Vehicles (IoAV) infrastructure.
Blockchain is used to reduce the latency of the system. While these proposals
discuss security, mobility, automation, latency, and communications issues,
they do not focus on specific resource allocation (e.g., transportation
credits) issue. Unlike these approaches, in our work, we devise a distributed
and decentralised management of transportation credits among various
organisations. This enhances the delegation issues to a more fine-grained
level for the allocation of access rights.

Proposals [23] and [24] present an ABAC model for secure distribution of
sensitive information of vehicles (e.g., location, time, speed, etc.) in an
intelligent transportation system. However, these proposals are built over a
highly centralised component for authorisation and access right delegation.
While they provide scalability to the system by enhancing attributes-based
security policies, unlike our proposal, the allocation of resources that can
be managed for individual entities is missing in these proposals.

In [25], a collaborative supply chain framework for transportation companies
is discussed. It focuses on the company’s logistic functionalities, e.g.,
order and capacity sharing. In [26], a fog-based architecture is discussed for
distribution and data processing of transport network resources at the edge
nodes. It helps seamless and faster responses and coordinates resources and
application queries in real-time. Similar to [26], proposal [27] present a
fog-based resource allocation techniques for intelligent transportation
systems. Proposal [28] presents an ‘Internet of Vehicles’ (IoV) concept from
an energy management point of view. Based on the energy, it decides to drive
customers to a particular destination. In [29], a blockchain-based renewable
energy management process is developed for electronic vehicles. It focuses on
the improvement of energy efficiency at the time of charging the vehicles. A
similar approach can be seen in proposal [30], but it uses a blockchain-
enabled crowdsensing framework. However, these proposals do not discuss the
resource allocation issue.

Our proposed framework takes advantage of blockchain technology to overcome
the limitations of the traditional approaches (e.g., RBAC, ABAC, and CapBAC)
and leverage the potential of safe, secure, and fine-grained allocation of
transportation credits among various entities without the need for a
centralised trust management system.

##  V Conclusion and Future Work

In this paper, we have discussed the allocation of resources from a multi-
organisational point of view supported by blockchain technology. We used
access control delegation to transfer, maintain, and control the
transportation credits over the employees within an organisation. The proposed
framework employed blockchain smart contracts to maintain safe and secure
interactions among transportation companies and organisations without the need
for a trusted third-party. The use of blockchain smart contracts enables the
resource exchange to occur in an open market place without an imbalance of
power between the participants. it also allows multiple providers and
consumers to participate in the market. This provides a flexible, open and
secure system leveraging off the natureof the blockchain.

The proof of implementation prototype showed that the proposed framework is
feasible to use in city-wide transport, even potentially country-wide large-
scale scenarios. HLF is an enterprise ready blockchain that can achieve a
throughput of up to 10,000 transactions per second. This indicates that a
large scale deployment using HLF would not have network bottlenecks and would
be able to provide a seamless experience for users. One of the challenges in a
large scale deployment would be how to guarantee decentralisation, i.e., how
do we ensure that no single entity is ever in control of the endorsers and
validators. A potential solution would be to have each transport company
maintain their own endorser and validator. A user can then set endorsement
policies that ensure each transport company must use at least 30% of total
nodes. This reduces the possibility that a single entity or group of entities
can control the endorsing and validating stages. A limitation of this work is
that even with separate communication channels for each organisation, there is
a security risk of confidential information leaking. Although this can be
mitigated with private data collections and having anonymous transactions
there is still the inherent risk of those transactions being broadcast. With
these solutions in place, our system could easily scale up to a large
production system without loss of efficiency or quality.

In the future, we plan to conduct more experiments to assess the security
level and see the feasibility of our framework with more complex access
control policies. We also plan to add more application features to transport
chain e.g., route planning and automatic token purchase based on patterns in
the historical transit data. Each of these features would add another aspect
of that can be seen in the traditional transport sector today, with the goal
of creating a transparent and open transport system that is truly
decentralised. We plan on assessing the effectiveness of such a transport
system and highlighting the major benefits of implementing such a system.

## References

  * [1] J. Magiera and A. Pawlak, “Security frameworks for virtual organizations,” in _Virtual Organizations_. M Camarinha-Matos, H. Afsarmanesh H., M. Ollus (eds). Springer, 2005, pp. 133–148.
  * [2] S. Pal, T. Rabehaja, M. Hitchens, V. Varadharajan, and A. Hill, “On the design of a flexible delegation model for the internet of things using blockchain,” _IEEE Transactions on Industrial Informatics_ , vol. 16, no. 5, 2019, pp. 3521–3530.
  * [3] S. Pal, _Internet of Things and Access Control: Sensing, Monitoring and Controlling Access in IoT-Enabled Healthcare Systems_. Springer Nature, 2021, vol. 37.
  * [4] M. Ghorbel-Talbi, F. Cuppens, N. Cuppens-Boulahia, and A. Bouhoula, “Managing delegation in access control models,” in _the 15th International Conference on Advanced Computing and Communications (ADCOM)_ , 2007, pp. 744–751.
  * [5] L. Atzori, A. Iera, and G. Morabito, “The Internet of Things: A survey,” _Computer Networks_ , vol. 54, no. 15, 2010, pp. 2787–2805.
  * [6] S. Ravidas, A. Lekidis, F. Paci, and N. Zannone, “Access control in internet-of-things: A survey,” _Journal of Network and Computer Applications_ , vol. 144, 2019, pp. 79–101.
  * [7] S. Pal, M. Hitchens, and V. Varadharajan, “Towards a secure access control architecture for the internet of things,” in _the 42nd Conference on Local Computer Networks (LCN)_. IEEE, 2017, pp. 219–222.
  * [8] S. Pal, M. Hitchens, V. Varadharajan, and T. Rabehaja, “Policy-based access control for constrained healthcare resources,” in _the 19th WoWMoM Conference_. IEEE, 2018, pp. 588–599.
  * [9] S. Pal, M. Hitchens, T. Rabehaja, and V. Varadharajan, “Policy-based access control for constrained healthcare resources in the context of the internet of things,” _Journal of Network and Computer Applications_ , vol. 139, 2019, pp. 57–74.
  * [10] T. Rabehaja, S. Pal, and M. Hitchens, “Design and implementation of a secure and flexible access-right delegation for resource constrained environments,” _Future Generation Computer Systems_ , vol. 99, 2019, pp. 593–608.
  * [11] S. Pal, T. Rabehaja, A. Hill, M. Hitchens, and V. Varadharajan, “On the integration of blockchain to the internet of things for enabling access right delegation,” _IEEE Internet of Things Journal_ , vol. 7, no. 4, 2019, pp. 2630–2639.
  * [12] L. Koh, A. Dolgui, and J. Sarkis, “Blockchain in transport and logistics–paradigms and transitions,” _Production Research_ , vol. 58, no. 7, 2020, pp. 2054-2062.
  * [13] M. Pournader, Y. Shi, S. Seuring, and S. Koh, “Blockchain applications in supply chains, transport and logistics: a systematic review of the literature,” _Production Research_ , vol. 58, no. 7, 2020, pp. 2063–2081.
  * [14] E. Androulaki, _et al._ , “Hyperledger fabric: a distributed operating system for permissioned blockchains,” in _Proceedings of the 13th EuroSys Conference_ , 2018, pp. 1–15.
  * [15] S. Pal, M. Hitchens, V. Varadharajan, and T. Rabehaja, “On design of a fine-grained access control architecture for securing iot-enabled smart healthcare systems,” in _Proceedings of the 14th MobiQuitous Conference_ , 2017, pp. 432–441.
  * [16] S. Pal, M. Hitchens, and V. Varadharajan, “On the design of security mechanisms for the internet of things,” in _the 11th International Conference on Sensing Technology (ICST)_. IEEE, 2017, pp. 1–6.
  * [17] V. Astarita, V. Giofrè, G. Mirabelli, and V. Solina, “A review of blockchain-based systems in transportation,” _Information_ , vol. 11, no. 1, 2020.
  * [18] M. Mollah, _et al._ , “Blockchain for the internet of vehicles towards intelligent transportation systems: A survey,” _IEEE Internet of Things Journal_ , vol. 8 no. 6, 2020, pp. 4157–4185.
  * [19] U. Lang and R. Schreiner, “Managing security in intelligent transport systems,” in _the 18th International Conference on Intelligent Transportation Systems_. IEEE, 2015, pp. 48–53.
  * [20] E. Vázquez and D. Landa-Silva, “Towards blockchain-based ride-sharing systems.” in _ICORES Conference_ , 2021, pp. 446–452.
  * [21] Y. Yuan and F. Wang, “Towards blockchain-based intelligent transportation systems,” in _the 19th International Conference on Intelligent Transportation Systems (ITSC)_. IEEE, 2016, pp. 2663–2668.
  * [22] X. Jiang, F. Yu, T. Song, and V. Leung, “Intelligent resource allocation for video analytics in blockchain-enabled internet of autonomous vehicles with edge computing,” _IEEE Internet of Things Journal_ , 2020.
  * [23] M. Gupta, J. Benson, F. Patwa, and R. Sandhu, “Dynamic groups and attribute-based access control for next-generation smart cars,” in _Data and Application Security and Privacy Conference_ , 2019, pp. 61–72.
  * [24] M. Gupta, _et al._ , “An attribute-based access control for cloud-enabled industrial smart vehicles,” _IEEE Transactions on Industrial Informatics_ , vol. 17, no. 6, 2021, pp. 4288–4297.
  * [25] L. Verdonck, A. Caris, K. Ramaekers, and G. Janssens, “Collaborative logistics from the perspective of road transportation companies,” _Transport Reviews_ , vol. 33, no. 6, pp. 700–719, 2013.
  * [26] T. Darwish and K. Bakar, “Fog based intelligent transportation big data analytics in the internet of vehicles environment: motivations, architecture, challenges, and critical issues,” _IEEE Access_ , vol. 6, pp. 2018, pp. 15679–15701.
  * [27] F. Xhafa, A. Aly, and A. Juan, “Allocation of applications to fog resources via semantic clustering techniques: With scenarios from intelligent transportation systems,” _Computing_ , vol. 103, no. 3, 2021, pp. 361–378.
  * [28] M. Gerla, E. Lee, G. Pau, and U. Lee, “Internet of vehicles: From intelligent grid to autonomous cars and vehicular clouds,” in _the world forum on internet of things (WF-IoT)_. IEEE, 2014, pp. 241–246.
  * [29] J. Zhao, C. He, C. Peng, and X. Zhang, “Blockchain for effective renewable energy management in the intelligent transportation system,” _Journal of Interconnection Networks_ , 2021.
  * [30] Z. Ning, _et al._ , “Blockchain-enabled intelligent transportation systems: A distributed crowdsensing framework,” _IEEE Transactions on Mobile Computing_ , 2021.


This article has been removed by arXiv administrators because the submitter
did not have the authority to grant a license at the time of submission.
[2022-12-20]


# Embedding Feature Selection for Large-scale Hierarchical Classification

Azad Naik and Huzefa Rangwala  Department of Computer Science
George Mason University
Fairfax, VA, United States
Email<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Large-scale Hierarchical Classification (HC) involves datasets consisting of
thousands of classes and millions of training instances with high-dimensional
features posing several big data challenges. Feature selection that aims to
select the subset of discriminant features is an effective strategy to deal
with large-scale HC problem. It speeds up the training process, reduces the
prediction time and minimizes the memory requirements by compressing the total
size of learned model weight vectors. Majority of the studies have also shown
feature selection to be competent and successful in improving the
classification accuracy by removing irrelevant features. In this work, we
investigate various filter-based feature selection methods for dimensionality
reduction to solve the large-scale HC problem. Our experimental evaluation on
text and image datasets with varying distribution of features, classes and
instances shows upto 3x order of speed-up on massive datasets and upto 45$\%$
less memory requirements for storing the weight vectors of learned model
without any significant loss (improvement for some datasets) in the
classification accuracy. Source Code:
https://cs.gmu.edu/$\sim$mlbio/featureselection.

###### Index Terms:

Feature Selection, Top-down Hierarchical Classification, Logistic Regression,
Scalability

##  I Introduction

Hierarchies (Taxonomies) are popular for organizing large volume datasets in
various application domains [1, 2]. Several large-scale online prediction
challenges such as LSHTC111http://lshtc.iit.demokritos.gr/ (webpage
classification), BioASQ222http://bioasq.org/ (PubMed documents classification)
and ILSVRC333http://www.image-net.org/challenges/LSVRC/2016/ (image
classification) revolve around the HC problem. Although, substantial amount of
data with inter-class dependencies information are beneficial for improving
HC, one of the major challenges in dealing with these datasets comprising
large-number of categories (classes), high-dimensional features and large-
number of training instances (examples) is scalability.

Many large-scale HC approaches have been developed in past to deal with the
various “big data” challenges by: (i) training faster models, (ii) quickly
predicting class-labels and (iii) minimizing memory usage. For example, Gopal
et al. [3] proposed the log-concavity bound that allows parallel training of
model weight vectors across multiple computing units. This achieves
significant speed-up along with added flexibility of storing model weight
vectors at different units. However, the memory requirements is still large
($\sim$26 GB for DMOZ-2010 dataset, refer to Table III) which requires complex
distributed hardware for storage and implementation. Alternatively, Map-Reduce
based formulation of learning model is introduced [4, 5] which is scalable but
have software/hardware dependencies that limits the applicability of this
approach.

To minimize the memory requirements, one of the popular strategy is to
incorporate the feature selection in conjunction with model training [6, 7].
The main intuition behind these approaches is to squeeze the high-dimensional
features into lower dimensions. This allows the model to be trained on low-
dimensional features only; significantly reducing the memory usage while
retaining (or improving) the classification accuracy. This is possible because
only subset of features are beneficial to discriminate between classes at each
node in the hierarchy. For example, to distinguish between sub-class
‘Chemistry’ and ‘Physics’ that belongs to class ‘Science’ features like
_chemical_ , _reactions_ and _acceleration_ are important whereas features
like _coach_ , _memory_ and _processor_ are irrelevant. HC methods that
leverage the structural relationship shows improved classification performance
but are computationally expensive [8, 5, 9].

Figure 1: Figure demonstrating the importance of feature selection for HC.
Green color (sticky note) represents the top five best features selected using
gini-index feature selection method at each internal node. Internal nodes are
represented by orange color (elliptical shape) and leaf nodes are represented
by blue color (rectangular shape).

In this paper, we study different filter-based feature selection methods for
solving large-scale HC problem. Feature selection serves as the preprocessing
step in our learning framework prior to training models. Any developed methods
for solving HC problem can be integrated with the selected features, providing
flexibility in choosing the HC algorithm of our choice along with
computational efficiency and storage benefits. Our proposed “adaptive feature
selection” also shows an improvement of $\sim$2% in classification accuracy.
Experiments on various real world datasets across different domains
demonstrates the utility of the feature selection over full set of high-
dimensional features. We also investigate the effect of feature selection in
classification performance when the number of labeled instances per class is
low.

##  II Literature Review

###  II-A Hierarchical Classification

Several methods have been developed to address the hierarchical classification
problem [4, 5, 10, 11, 12]. These methods can be broadly divided into three
major categories. (i) _Flat approach_ is one of the simplest and straight
forward method to solve the HC problem. In this method, hierarchical structure
is completely ignored and an independent one-vs-rest or multi-class
classifiers are trained for each of the leaf categories that can discriminate
it from remaining leaf categories. For predicting the label of instances, the
flat method invokes the classifiers corresponding to all leaf categories and
selects the leaf category with highest prediction score. As such, flat
approach have expensive training and prediction runtime for datasets with
large number of classes. (ii) _Local classification_ involves the use of local
hierarchical relationships during the model training process. Depending on how
the hierarchical relationships are leveraged, various local methods exist
[13]. In this paper, we have used the most popular “local classifier per
parent node” method as the baseline for evaluations. Specifically, we train a
multi-class classifier at each of the parent node to maximize the
discrimination between its children nodes. For making predictions a top-down
method (discussed in Section II-B) is followed. (iii) _Global classification_
learns a single complex model where all relevant hierarchical relationships
are explored jointly during the optimization process making these approaches
expensive for training. Label predictions is done using a similar approach
followed for flat or local methods.

###  II-B Top-Down Hierarchical Classification

One of the most efficient approach for solving large-scale HC problem is using
the top-down method [8, 14]. In this method, local or global classification
method is used for model training and the unlabeled instances are recursively
classified in a top-down fashion. At each step, best node is picked based on
the computed prediction score of its children nodes. The process repeats until
the leaf node representing a certain category (or class-label) is reached,
which is the final predicted label (refer to eq. (3)).

Top-Down (TD) methods are popular for large-scale problems owing to their
computational benefits where only the subset of classes in the relevant path
are considered during prediction phase. For example, in order to make second
level prediction provided the first level prediction is ‘Sci’ (shown in Figure
1) we only need to consider the children of ‘Sci’ class ($i.e.$, electronics,
med, crypt and space), thereby, avoiding the large number of second level
classes such as ‘Sys’, ‘Politics’, ‘Sports’, ‘graphics’, ‘autos’. In the past,
top-down methods have been successfully used to solve HC problems [11, 15,
16]. Liu et al. [8] performed classification on large-scale Yahoo! dataset and
analyzed the complexity of the top-down approach. In [17], a selective
classifier top-down method is proposed where the classifier to train at
particular node is chosen in a data-driven manner.

###  II-C Feature Selection

There have been several studies focused on feature selection methods for the
flat classification problem [18, 19, 20, 21, 22, 23]. However, very few work
emphasize on feature selection for HC problem that are limited to small number
of categories [24, 25]. Figure 1 demonstrates the importance of feature
selection for hierarchical settings where only the relevant features are
chosen at each of the decision (internal) nodes. More details about the figure
will be discussed in Section V (Case Study).

Feature selection aims to find a subset of highly discriminant features that
minimizes the error rate and improve the classifier performance. Based on the
approach adapted for selecting features two broad categories of feature
selection exist, namely, wrapper and filter-based methods. Wrapper approaches
evaluate the fitness of the selected features using the intended classifier.
Although many different wrapper-based approaches have been proposed, these
methods are not suitable for large-scale problems due to the expensive
evaluation needed to select the subset of features [18]. On the contrary,
filter approaches select the subset of features based on the certain measures
or statistical properties that does not require the expensive evaluations.
This makes the filter-based approaches a natural choice for large-scale
problem. Hence, in this paper we have focused on various filter-based
approaches for solving HC problem (discussed in Section III-C). In literature,
third category referred as embedded approaches have also been proposed which
are a hybrid of the wrapper and filter methods. However, these approaches have
not been shown to be efficient for large-scale classification [18] and hence,
we do not focus on hybrid methods.

To the best of our knowledge this is the first paper that performs a broad
study of filter-based feature selection methods for HC problem.

##  III Methods

###  III-A Definitions and Notations

In this paper, we use bold lower-case and upper-case letters to indicate
vector and matrix variables, respectively. Symbol $\mathcal{N}$ denotes the
set of internal nodes in the hierarchy where for each node $n\in\mathcal{N}$
we learn the multi-class classifier denoted by ${\bf{W}}_{n}$ =
$\big{[}{\bf{w}}^{n}_{c}\big{]}_{{c\in\mathcal{C}(n)}}$ to discriminate
between its children nodes $\mathcal{C}(n)$. ${\bf{w}}^{n}_{c}$ represents the
optimal model weight vectors for $c^{th}$ child of node $n$. $\mathcal{L}$
denotes the set of leaf nodes (categories) to which instances are assigned.
The total number of training instances are denoted by $N$ and $T(n)\subseteq
N$ denotes the total number of training instances considered at node $n$ which
corresponds to all instances of descendant categories at node $n$.
$\mathcal{F}$ denotes the set of total features (dimensionality) for each
instance where $i^{th}$ feature is denoted by $f_{i}$.
${S}_{\mathcal{F}}\subseteq\mathcal{F}$ denotes the subset of relevant
features selected using feature selection algorithm.
$\mathcal{D}=\big{\\{}\big{(}{\bf{x}}(i)$, $y(i)\big{)}\big{\\}}_{i=1}^{N}$
denotes the training dataset where ${\bf{x}}(i)\in\mathbb{R}^{\mathcal{F}}$
and $y(i)\in\mathcal{L}$. For training optimal model corresponding to $c^{th}$
child at node $n$ we use the binary label ${y_{c}^{n}}{(i)}\in\\{\pm 1\\}$ for
$i^{th}$ training instance where $y_{c}^{n}(i)$ = 1 iff $y(i)$ = $c$ and
$y_{c}^{n}(i)$ = -1 otherwise. Predicted label for $i^{th}$ test instance
$\hat{\bf{x}}(i)$ is denoted by $\hat{y}(i)\in\mathcal{L}$.

###  III-B Hierarchical Classification

Given a hierarchy $\mathcal{H}$, we train multi-class classifiers for each of
the internal nodes $n\in\mathcal{N}$ in the hierarchy— to discriminate between
its children nodes $\mathcal{C}(n)$. In this paper, we have used Logistic
Regression (LR) as the underlying base model for training [5, 26]. The LR
objective uses logistic loss to minimize the empirical risk and $l_{1}$-norm
(denoted by $\big{|}\big{|}\cdot\big{|}\big{|}_{1}$) or squared $l_{2}$-norm
term (denoted by $\big{|}\big{|}\cdot\big{|}\big{|}_{2}^{2}$) to control model
complexity and prevent overfitting. Usually, $l_{1}$-norm encourages sparse
solution by randomly choosing single parameter amongst highly correlated
parameters whereas $l_{2}$-norm jointly shrinks the correlated parameters. The
objective function $\Psi^{n}_{c}$ for training a model corresponding to
${c^{th}}$ child of node $n$ is provided in eq. (1).

$\scriptsize\Psi^{n}_{c}=\min_{{\bf{w}}^{n}_{c}}\Bigg{[}\lambda\sum_{i=1}^{T(n)}\log\left(1+\exp\left(-y_{c}^{n}(i)\big{(}{\bf{w}}^{n}_{c}\big{)}^{T}\mathbf{x}(i)\right)\right)+\mathcal{R}\big{(}{\bf{w}}^{n}_{c}\big{)}\Bigg{]}$
(1)

where $\lambda>0$ is a mis-classification penalty parameter and
$\mathcal{R}\big{(}.\big{)}$ denotes the regularization term given by eq. (2).

$\displaystyle\mathcal{R}\big{(}{\bf{w}}^{n}_{c}\big{)}=\left\\{\begin{aligned}
&\big{|}\big{|}{\bf{w}}^{n}_{c}\big{|}\big{|}_{1}^{1},\quad l_{1}-norm\\\
&\quad\quad\quad OR\\\
&\big{|}\big{|}{\bf{w}}^{n}_{c}\big{|}\big{|}_{2}^{2},\quad
l_{2}-norm\end{aligned}\right\\}$ (2)

For each child $c$ of node $n$ within the hierarchy, we solve eq. (1) to
obtain the optimal weight vector denoted by ${\bf{w}}^{n}_{c}$. The complete
set of parameters for all the children nodes ${\bf{W}}_{n}$ =
$[{\bf{w}}^{n}_{c}]_{c\in\mathcal{C}(n)}$ constitutes the learned multi-class
classifiers at node $n$ whereas total parameters for all internal nodes
${\bf{W}}$ = $[{\bf{W}}_{n}]_{n\in\mathcal{N}}$ constitutes the learned model
for Top-Down (TD) classifier.

For a test instance ${\hat{\bf{x}}}(i)$, the TD classifier predicts the class
label $\hat{y}(i)\in\mathcal{L}$ as shown in eq. (3). Essentially, the
algorithm starts at the root node and recursively selects the best child nodes
until it reaches a terminal node belonging to the set of leaf nodes
$\mathcal{L}$.

$\displaystyle\hat{y}(i)=\left\\{\begin{aligned} &\mathbf{initialize}\quad
p:=root\\\ &\mathbf{while}\ p\notin\mathcal{L}\\\ &\quad
p:=\mathbf{argmax}_{q\in\mathcal{C}(p)}\
\big{(}{\bf{w}}^{p}_{q}\big{)}^{T}\hat{{\bf{x}}}(i)\\\ &\mathbf{return}\
p\end{aligned}\right\\}$ (3)

###  III-C Feature Selection

The focus of our study in this paper is on filter-based feature selection
methods which are scalable for large-scale datasets. In this section, we
present four feature selection approaches that are used for evaluation
purposes.

Gini-Index \- It is one of the most widely used method to compute the best
split (ordered feature) in the decision tree induction algorithm [27].
Realizing its importance, it was extended for the multi-class classification
problem [28]. In our case, it measure the feature’s ability to distinguish
between different leaf categories (classes). Gini-Index of $i^{th}$ feature
$f_{i}$ with $\mathcal{L}$ classes can be computed as shown in eq. (4).

${\bf{Gini-
Index}}(f_{i})=1-\sum_{k=1}^{\mathcal{L}}\Big{(}p(k|f_{i})\Big{)}^{2}$ (4)

where $p(k|f_{i})$ is the conditional probability of class $k$ given feature
$f_{i}$.

Smaller the value of Gini-Index, more relevant and useful is the feature for
classification. For HC problem, we compute the Gini-Index corresponding to all
feature’s independently at each internal node and select the best subset of
features (${S}_{\mathcal{F}}$) using a held-out validation dataset.

Minimal Redundancy Maximal Relevance (MRMR) \- This method incorporates the
following two conditions for feature subset selection that are beneficial for
classification.

  1. (i)

Identify features that are mutually maximally dissimilar to capture better
representation of entire dataset and

  2. (ii)

Select features to maximize the discrimination between different classes.

The first criterion referred as “minimal redundancy” selects features that
carry distinct information by eliminating the redundant features. The main
intuition behind this criterion is that selecting two similar features
contains no new information that can assist in better classification.
Redundancy information of feature set $\mathcal{F}$ can be computed using eq.
(5).

${\mathfrak{R}_{D}}=\Bigg{[}\frac{1}{|S_{\mathcal{F}}|^{2}}\sum_{f_{i},f_{j}\in
S_{\mathcal{F}}}I(f_{i},f_{j})\Bigg{]}$ (5)

where $I(f_{i},f_{j})$ is the mutual information that measure the level of
similarity between features $f_{i}$ and $f_{j}$ [29].

The second criterion referred as “maximum relevance” enforces the selected
features to have maximum discriminatory power for classification between
different classes. Relevance of feature set $\mathcal{F}$ can be formulated
using eq. (6).

${\mathfrak{R}_{L}}=\Bigg{[}\frac{1}{|S_{\mathcal{F}}|}\sum_{f_{i}\in
S_{\mathcal{F}}}I(f_{i},\mathcal{L})\Bigg{]}$ (6)

where $I(f_{i},\mathcal{L})$ is the mutual information between the feature
$f_{i}$ and leaf categories $\mathcal{L}$ that captures how well the feature
$f_{i}$ can discriminate between different classes [20].

The combined optimization of eq. (5) and eq. (6) leads to a feature set with
maximum discriminatory power and minimum correlations among features.
Depending on strategy adapted for optimization of these two objectives
different flavors exist. The first one referred as “mutual information
difference (MRMR-D)” formulates the optimization problem as the difference
between two objectives as shown in eq. (7). The second one referred as “mutual
information quotient (MRMR-Q)” formulates the problem as the ratio between two
objectives and can be computed using eq. (8).

$\emph{MRMR-D}=\max_{S_{\mathcal{F}}\subseteq\mathcal{F}}\;({{\mathfrak{R}_{L}-\mathfrak{R}_{D}}})$
(7)
$\emph{MRMR-Q}=\max_{S_{\mathcal{F}}\subseteq\mathcal{F}}\;({{\mathfrak{R}_{L}/\mathfrak{R}_{D}}})$
(8)

For HC problem again we select the best top ${S}_{\mathcal{F}}$ features
(using a validation dataset) for evaluating these methods.

Kruskal-Wallis \- This is a non-parametric statistical test that ranks the
importance of each feature. As a first step this method ranks all instances
across all leaf categories $\mathcal{L}$ and computes the feature importance
metric as shown in eq. (9):

$KW=(N-1)\frac{\sum_{i=1}^{\mathcal{L}}{n_{i}(\bar{r_{i}}-\bar{r})^{2}}}{\sum_{i=1}^{\mathcal{L}}\sum_{j=1}^{n_{i}}n_{i}({r}_{ij}-\bar{r})^{2}}$
(9)

where $n_{i}$ is the number of instances in $i^{th}$ category, $r_{ij}$ is the
ranking of $j^{th}$ instances in the $i^{th}$ category and $\bar{r}$ denotes
the average rank across all instances.

It should be noted that using different feature results in different ranking
and hence feature importance. Lower the value of computed score $KW$, more
relevant is the feature for classification.

Data: Hierarchy $\mathcal{H}$, input-output pairs (${\bf{x}}(i),y(i)$)

Result: Learned model weight vectors:

${\bf{W}}$ = [${\bf{W}}_{1}$, ${\bf{W}}_{2}$, $\cdots$, ${\bf{W}}_{n}$], $n$
$\in$ $\mathcal{N}$

${\bf{W}}$ = $\phi$;

/* 1st subroutine: Feature Selection */

for  _$f_{i}\in$ $\mathcal{F}$_ do

Compute score (relevance) corresponding to feature $f_{i}$ using feature
selection algorithm mentioned in Section III-C;

end for

Select top $k$ features based on score (and correlations) amongst features
where best value of $k$ is tuned using a validation dataset

/* 2nd subroutine: Model Learning using Reduced Feature Set */

for  _n $\in$ $\mathcal{N}$_ do

/* learn models for discriminating child at node $n$ */

Train optimal multi-class classifiers ${\bf{W}}_{n}$ at node $n$ using reduced
feature set as shown in eq. (1);

/* update model weight vectors */

${\bf{W}}$ = [${\bf{W}}$, ${\bf{W}}_{n}$];

end for

return _${\bf{W}}$_

Algorithm 1 Feature Selection (FS) based Model Learning for Hierarchical Classification (HC) TABLE I: Dataset Statistics Dataset | Domain | # Leaf Node | # Internal Node | Height | # Training | # Testing | # Features | Avg. # children
---|---|---|---|---|---|---|---|---
(per internal node)
NG | Text | 20 | 8 | 4 | 11,269 | 7,505 | 61,188 | 3.38
CLEF | Image | 63 | 34 | 4 | 10,000 | 1,006 | 80 | 2.56
IPC | Text | 451 | 102 | 4 | 46,324 | 28,926 | 1,123,497 | 5.41
DMOZ-SMALL | Text | 1,139 | 1,249 | 6 | 6,323 | 1,858 | 51,033 | 1.91
DMOZ-2010 | Text | 12,294 | 4,928 | 6 | 128,710 | 34,880 | 381,580 | 3.49
DMOZ-2012 | Text | 11,947 | 2,016 | 6 | 383,408 | 103,435 | 348,548 | 6.93

###  III-D Proposed Framework

Algorithm 1 presents our proposed method for embedding feature selection into
the HC framework. It consist of two independent main subroutines: (i) a
feature selection algorithm (discussed in Section III-C) for deciding the
appropriate set of features at each decision (internal) node and (ii) a
supervised learning algorithm (discussed in Section III-B) for constructing a
TD hierarchical classifier using reduced feature set. Feature selection serves
as the preprocessing step in our framework which provides flexibility in
choosing any HC algorithm.

We propose two different approaches for choosing relevant number of features
at each internal node $n\in\mathcal{N}$. The first approach which we refer as
“global feature selection (Global FS)” selects the same number of features for
all internal nodes in the hierarchy where the number of features are
determined based on the entire validation dataset performance. The second
approach, referred as “adaptive feature selection (Adaptive FS)” selects
different number of features at each internal node to maximize the performance
at that node. It should be noted that adaptive method only uses the validation
dataset that exclusively belongs to the internal node $n$ ($i.e.$, descendant
categories of node $n$). Computationally, both approaches are almost identical
because model tuning and optimization requires similar runtime which accounts
for the major fraction of computation.

##  IV Experimental Evaluations

###  IV-A Dataset Description

We have performed an extensive evaluation of various feature selection methods
on a wide range of hierarchical text and image datasets. Key characteristics
about the datasets that we have used in our experiments are shown in Table I.
All these datasets are single-labeled and the instances are assigned to the
leaf nodes in the hierarchy. For text datasets, we have used the word-
frequency representation and perform the tf-idf transformation with
$l_{2}$-norm to the word-frequency feature vector.
Text Datasets
NEWSGROUP (NG)444http://qwone.com/$\sim$jason/20Newsgroups/ \- It is a
collection of approximately 20,000 news documents partitioned (nearly) evenly
across twenty different topics such as ‘baseball’, ‘electronics’ and
‘graphics’ (refer to Figure 1).
IPC555http://www.wipo.int/classifications/ipc/en/ \- Collection of patent
documents organized in International Patent Classification (IPC) hierarchy.
DMOZ-SMALL, DMOZ-2010 and DMOZ-2012666http://dmoz.org \- Collection of
multiple web documents organized in various classes using the hierarchical
structure. Dataset has been released as the part of the
LSHTC777http://lshtc.iit.demokritos.gr/ challenge in the year 2010 and 2012.
For evaluating the DMOZ-2010 and DMOZ-2012 datasets we have used the provided
test split and the results reported for this benchmark is blind prediction
obtained from web-portal interface888http://lshtc.iit.demokritos.gr/node/81.
Image Datasets
CLEF [30] \- Dataset contains medical images annotated with Information
Retrieval in Medical Applications (IRMA) codes. Each image is represented by
the 80 features that are extracted using local distribution of edges method.

###  IV-B Evaluation Metrics

We have used the standard set based performance measures Micro-$F_{1}$ and
Macro-$F_{1}$ [31] for evaluating the performance of learned models.
Micro-$F_{1}$ ($\mu$$F_{1}$) \- To compute $\mu$$F_{1}$, we sum up the
category specific true positives $(TP_{l})$, false positives $(FP_{l})$ and
false negatives $(FN_{l})$ for different leaf categories and compute the
$\mu$$F_{1}$ score as follows:

$\displaystyle
P=\frac{\sum_{l\in\mathcal{L}}TP_{l}}{\sum_{l\in\mathcal{L}}(TP_{l}+FP_{l})},R=\frac{\sum_{l\in\mathcal{L}}TP_{l}}{\sum_{l\in\mathcal{L}}(TP_{l}+FN_{l})}$
$\displaystyle\mu F_{1}=\frac{2PR}{P+R}$ (10)

where, P and R are the overall precision and recall values for all the classes
taken together.
Macro-$F_{1}$ ($M$$F_{1}$) \- Unlike $\mu$$F_{1}$, M$F_{1}$ gives equal weight
to all the categories so that the average score is not skewed in favor of the
larger categories. It is defined as follows:

$\displaystyle
P_{l}=\frac{TP_{l}}{TP_{l}+FP_{l}},R_{l}=\frac{TP_{l}}{TP_{l}+FN_{l}}$
$\displaystyle
MF_{1}=\frac{1}{|\mathcal{L}|}\sum_{l\in\mathcal{L}}\frac{2P_{l}R_{l}}{P_{l}+R_{l}}$
(11)

where $|\mathcal{L}|$ denotes the set of leaf categories, $P_{l}$ and $R_{l}$
are the precision and recall values for leaf category $l$ $\in$ $\mathcal{L}$.

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

(i)

(j)

(k)

(l)

Figure 2: Performance comparison of LR + $l_{1}$-norm models with varying
percentage (%) of features selected using different feature selection (global)
methods on text and image datasets.

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

(i)

(j)

(k)

(l)

Figure 3: Performance comparison of LR + $l_{2}$-norm models with varying
percentage (%) of features selected using different feature selection (global)
methods on text and image datasets.

###  IV-C Experimental Details

For all the experiments, we divide the training dataset into train and small
validation dataset in the ratio 90:10. The train dataset is used to train TD
classifiers whereas the validation dataset is used to tune the parameter. The
model is trained for a range of mis-classification penalty parameter
($\lambda$) values in the set {0.001, 0.01, 0.1, 1, 10, 100, 1000} with best
value selected using a validation dataset. Adopting the best parameter, we
retrain the models on the entire training dataset and measure the performance
on a separate held-out test dataset. For feature selection, we choose the best
set of features using the validation dataset by varying the number of features
between 1$\%$ and 75$\%$ of all the features. Our preliminary experiments
showed no significant improvement after 75$\%$ hence we bound the upper limit
to this value. We performed all the experiments on ARGO cluster
(http://orc.gmu.edu) with dual Intel Xeon E5-2670 8 core CPUs and 64 GB
memory. Source code implementation of the proposed algorithm discussed in this
paper is made available at our
website999https://cs.gmu.edu/$\sim$mlbio/featureselection for repeatability
and future use.

TABLE II: Performance comparison of adaptive and global approach for feature
selection based on Gini-Index with all features. LR + $l_{1}$-norm model is
used for evaluation

Dataset | Metric | Adaptive FS | Global FS | All Features
---|---|---|---|---
NG | $\mu F_{1}$ | 76.16$\vartriangle$ | 76.39$\vartriangle$ | 74.94
$MF_{1}$ | 76.10$\vartriangle$ | 76.07$\vartriangle$ | 74.56
CLEF | $\mu F_{1}$ | 72.66 | 72.27 | 72.17
$MF_{1}$ | 36.73$\blacktriangle$ | 35.07$\vartriangle$ | 33.14
IPC | $\mu F_{1}$ | 48.23$\blacktriangle$ | 46.35 | 46.14
$MF_{1}$ | 41.54$\blacktriangle$ | 39.52 | 39.43
DMOZ-SMALL | $\mu F_{1}$ | 40.32$\vartriangle$ | 39.52 | 38.86
$MF_{1}$ | 26.12$\blacktriangle$ | 25.07 | 24.77
DMOZ-2010 | $\mu F_{1}$ | 35.94 | 35.40 | 34.32
$MF_{1}$ | 23.01 | 21.32 | 21.26
DMOZ-2012 | $\mu F_{1}$ | 44.12 | 43.94 | 43.92
$MF_{1}$ | 23.65 | 22.18 | 22.13

  * •

$\blacktriangle$ (and $\vartriangle$) indicates that improvements are
statistically significant with 0.05 (and 0.1) significance level.

##  V Results Discussion

###  V-A Case Study

To understand the quality of features selected at different internal nodes in
the hierarchy we perform case study on NG dataset. We choose this dataset
because we have full access to feature information. Figure 1 demonstrates the
results of top five features that is selected using best feature selection
method $i.e.$, Gini-Index (refer to Figure 2 and 3). We can see from the
figure that selected features corresponds to the distinctive attributes which
helps in better discrimination at particular node. For example, the features
like _Dod (Day of defeat or Department of defense)_ , _Car_ , _Bike_ and
_Team_ are important at node ‘Rec’ to distinguish between the sub-class
‘autos’, ‘motorcycles’ and ‘Sports’ whereas other features like _Windows_ ,
_God_ and _Encryption_ are irrelevant. This analysis illustrates the
importance of feature selection for TD HC problem.

One important observation that we made in our study is that some of the
features like _Windows_ , _God_ and _Team_ are useful for discrimination at
multiple nodes in the hierarchy (associated with parent-child relationships).
This observation conflicts with the assumption made in the work by Xiao et al.
[6], which attempts to optimize the objective function by necessitating the
child node features to be different from the features selected at the parent
node.

TABLE III: Comparison of memory requirements for LR + $l_{1}$-norm model Dataset | Adaptive FS | Global FS | All Features
---|---|---|---
# parameters | size | # parameters | size | # parameters | size
NG | 982,805 | 4.97 MB | 908,820 | 3.64 MB | 1,652,076 | 6.61 MB
CLEF | 4,715 | 18.86 KB | 5,220 | 20.89 KB | 6,960 | 27.84 KB
IPC | 306,628,256 | 1.23 GB | 331,200,000 | 1.32 GB | 620,170,344 | 2.48 GB
DMOZ-SMALL | 74,582,625 | 0.30 GB | 85,270,801 | 0.34 GB | 121,815,771 | 0.49 GB
DMOZ-2010 | 4,035,382,592 | 16.14 GB | 4,271,272,967 | 17.08 GB | 6,571,189,180 | 26.28 GB
DMOZ-2012 | 3,453,646,353 | 13.81 GB | 3,649,820,382 | 14.60 GB | 4,866,427,176 | 19.47 GB

###  V-B Classification Performance Comparison

Global FS \- Figures 2 and 3 shows the $\mu F_{1}$ and M$F_{1}$ comparison of
LR models with $l_{1}$-norm and $l_{2}$-norm regularization combined with
various feature selection methods discussed in Section III-C respectively. We
can see that all feature selection method (except Kruskal-Wallis) show
competitive performance results in comparison to the full set of features for
all the datasets. Overall, Gini-Index feature selection method has slightly
better performance over other methods. MRMR methods have a tendency to remove
some of the important features as redundant based on the minimization
objective obtained from data-sparse leaf categories which may not be optimal
and negatively influences the performance. The Kruskal-Wallis method shows
poor performance because of the statistical properties that is obtained from
data-sparse nodes [32].

On comparing the $l_{1}$-norm and $l_{2}$-norm regularized models of best
feature selection method (Gini-Index) with all features, we can see that
$l_{1}$-norm models have more performance improvement (especially for M$F_{1}$
scores) for all datasets whereas for $l_{2}$-norm models performance is almost
similar without any significant loss. This is because $l_{1}$-norm assigns
higher weight to the important predictor variables which results in more
performance gain.

Since, feature selection based on Gini-Index gives the best performance, in
the rest of the experiments we have used the Gini-Index as the baseline for
comparison purpose. Also, we consider $l_{1}$-norm model only due to space
constraint.

Adaptive FS \- Table II shows the LR + $l_{1}$-norm models performance
comparison of adaptive and global approaches for feature selection with all
features. We can see from the table that adaptive approach based feature
selection gives the best performance for all the datasets (except $\mu F_{1}$
score of NG dataset which has very few categories). For evaluating the
performance improvement of models we perform statistical significance test.
Specifically, we perform sign-test for $\mu F_{1}$ [33] and non-parametric
wilcoxon rank test for $MF_{1}$. Results with 0.05 (0.1) significance level is
denoted by $\blacktriangle$ ($\vartriangle$). Tests are between models
obtained using feature selection methods and all set of features. We cannot
perform test on DMOZ-2010 and DMOZ-2012 datasets because true predictions and
class-wise performance score are not available from online web-portal.

Statistical evaluation shows that although global approach is slightly better
in comparison to full set of features they are not statistically significant.
On contrary, adaptive approach is much better with an improvement of $\sim$2%
in $\mu F_{1}$ and M$F_{1}$ scores which are statistically significant.

###  V-C Memory Requirements

Table III shows the information about memory requirements for various models
with full set of features and best set of features that are selected using
global and adaptive feature selection. Upto 45$\%$ reduction in memory size is
observed for all datasets to store the learned models. This is a huge margin
in terms of memory requirements considering the models for large-scale
datasets (such as DMOZ-2010 and DMOZ-2012) are difficult to fit in memory.

It should be noted that optimal set of features is different for global and
adaptive methods for feature selection hence they have different memory
requirements. Overall, adaptive FS is slightly better because it selects small
set of features that are relevant for distinguishing data-sparse nodes present
in CLEF, IPC and the DMOZ datasets. Also, we would like to point out that
Table III represents the memory required to store the learned model parameters
only. In practice, 2-4 times more memory is required for temporarily storing
the gradient values of model paramaters that is obtained during the
optimization process.

TABLE IV: Feature selection preprocessing time (in minutes)($\downarrow$) Dataset | Feature Selection Method
---|---
Gini-Index | MRMR-D | MRMR-Q | Kruskal-Wallis
NG | 2.10 | 5.33 | 5.35 | 5.42
CLEF | 0.02 | 0.46 | 0.54 | 0.70
IPC | 15.24 | 27.42 | 27.00 | 23.24
DMOZ-SMALL | 23.65 | 45.24 | 45.42 | 34.65
DMOZ-2010 | 614 | 1524 | 1535 | 1314
DMOZ-2012 | 818 | 1824 | 1848 | 1268

###  V-D Runtime Comparison

Preprocessing Time \- Table IV shows the preprocessing time needed to compute
the feature importance using the different feature selection methods. The
Gini-index method takes the least amount of time since it does not require the
interactions between different features to rank the features. The MRMR methods
are computationally expensive due to the large number of pairwise comparisons
between all the features to identify the redundancy information. On other
hand, the Kruskal-Wallis method has overhead associated with determining
ranking of each features with different classes.

Model Training \- Table V shows the total training time needed for learning
models. As expected, feature selection requires less training time due to the
less number of features that needs to be considered during learning. For
smaller datasets such as NG and CLEF improvement is not noticeable. However,
for larger datasets with high-dimensionality such as IPC, DMOZ-2010 and
DMOZ-2012 improvement is much higher (upto 3x order speed-up). For example,
DMOZ-2010 dataset training time reduces from 6524 minutes to mere 2258
minutes.

Prediction Time \- For the dataset with largest number of test instances,
DMOZ-2012 it takes 37 minutes to make predictions with feature selection as
opposed to 48.24 minutes with all features using the TD HC approach.

In Figure 4 we show the training and prediction time comparison of large
datasets (DMOZ-2010 and DMOZ-2012) between flat LR and the TD HC approach with
(and without) feature selection. The flat method is comparatively more
expensive than the TD approach ($\sim$6.5 times for training and $\sim$5 times
for prediction).

TABLE V: Total training time (in minutes)($\downarrow$) Dataset | Model | Feature Selection | All Features
---|---|---|---
(Gini-Index)
NG | LR + $l_{1}$ | 0.75 | 0.94
LR + $l_{2}$ | 0.44 | 0.69
CLEF | LR + $l_{1}$ | 0.50 | 0.74
LR + $l_{2}$ | 0.10 | 0.28
IPC | LR + $l_{1}$ | 24.38 | 74.10
LR + $l_{2}$ | 20.92 | 68.58
DMOZ-SMALL | LR + $l_{1}$ | 3.25 | 4.60
LR + $l_{2}$ | 2.46 | 3.17
DMOZ-2010 | LR + $l_{1}$ | 2258 | 6524
LR + $l_{2}$ | 2132 | 6418
DMOZ-2012 | LR + $l_{1}$ | 8024 | 19374
LR + $l_{2}$ | 7908 | 19193

Figure 4: Training and prediction runtime comparison of LR + $l_{1}$-norm
model (in minutes). TABLE VI: Performance comparison of LR + $l_{1}$-norm
model with varying training size (# instances) per class on NG dataset

Dataset | Train size | Feature Selection | All Features
---|---|---|---
Distribution | (per class) | (Gini-Index) |  |
|  | $\mu F_{1}$ | M$F_{1}$ | $\mu F_{1}$ | M$F_{1}$
| 5 |  27.44 $\blacktriangle$ |  26.45 $\blacktriangle$ | 25.74 | 24.33
| (0.4723) | (0.4415) | (0.5811) | (0.6868)
| 10 |  37.69 $\vartriangle$ |  37.51 $\blacktriangle$ | 36.59 | 35.86
Low | (0.2124) | (0.2772) | (0.5661) | (0.3471)
Distribution | 15 |  43.14 $\vartriangle$ |  43.80 $\vartriangle$ | 42.49 | 42.99
| (0.3274) | (0.3301) | (0.1517) | (0.7196)
| 25 |  52.12 $\blacktriangle$ |  52.04 $\blacktriangle$ | 50.33 | 50.56
| (0.3962) | (0.3011) | (0.4486) | (0.5766)
| 50 | 59.55 | 59.46 | 59.52 | 59.59
| (0.4649) | (0.1953) | (0.3391) | (0.1641)
| 100 | 66.53 | 66.42 | 66.69 | 66.60
High | (0.0346) | (0.0566) | (0.7321) | (0.8412)
Distribution | 200 | 70.60 | 70.53 | 70.83 | 70.70
| (0.6068) | (0.5164) | (0.7123) | (0.6330)
| 250 | 72.37 | 72.24 |  73.06 $\vartriangle$ | 72.86
| (0.4285) | (0.4293) | (0.4732) | (0.4898)

  * •

Table shows mean and (standard deviation) in bracket across five runs.
$\blacktriangle$ (and $\vartriangle$) indicates that improvements are
statistically significant with 0.05 (and 0.1) significance level.

###  V-E Additional Results

Effect of Varying Training Size \- Table VI shows the classification
performance on NG dataset with varying training dataset distribution. We have
tested the models by varying the training size (instances) per class ($t_{c}$)
between 5 and 250. Each experiment is repeated five times by randomly choosing
$t_{c}$ instances per class. Moreover, adaptive method with Gini-Index feature
selection is used for experiments. For evaluating the performance improvement
of models we perform statistical significance test (sign-test for $\mu F_{1}$
and wilcoxon rank test for $MF_{1}$). Results with 0.05 (0.1) significance
level is denoted by $\blacktriangle$ ($\vartriangle$).

We can see from Table VI that for low distribution datasets, the feature
selection method performs well and shows improvements of upto 2$\%$
(statistically significant) over the baseline method. The reason behind this
improvement is that with low data distribution, feature selection methods
prevents the models from overfitting by selectively choosing the important
features that helps in discriminating between the models of various classes.
For datasets with high distribution, no significant performance gain is
observed due to sufficient number of available training instances for learning
models which prevents overfitting when using all the features.

Levelwise Analysis \- Figure 5 shows the level-wise error analysis for CLEF,
IPC and DMOZ-SMALL datasets with or without feature selection. We can see that
at topmost level more error is committed compared to the lower level. This is
because at higher levels each of the children nodes that needs to be
discriminated is the combination of multiple leaf categories which cannot be
modeled accurately using the linear classifiers. Another observation is that
adaptive feature selection gives best results at all levels for all datasets
which demonstrates its ability to extract relevant number of features at each
internal node (that belongs to different levels) in the hierarchy.

Figure 5: Level-wise error analysis of LR + $l_{1}$-norm model for CLEF, IPC
and DMOZ-SMALL datasets.

##  VI Conclusion and future work

In this paper we compared various feature selection methods for solving large-
scale HC problem. Experimental evaluation shows that with feature selection we
are able to achieve significant improvement in terms of runtime performance
(training and prediction) without affecting the accuracy of learned
classification models. We also showed that feature selection can be
beneficial, especially for the larger datasets in terms of memory
requirements. This paper presents the first study of various information
theoretic feature selection methods for large-scale HC.

In future, we plan to extend our work by learning more complex models at each
of the decision nodes. Specifically, we plan to use multi-task learning
methods where related tasks can be learned jointly to improve the performance
on each task. Feature selection gives us the flexibility of learning complex
models due to reduced dimensionality of the features, which otherwise have
longer runtime and larger memory requirements.

## Acknowledgement

NSF Grant #1252318 and #1447489 to Huzefa Rangwala and Summer Research
Fellowship from the office of provost, George Mason University to Azad Naik.

## References

  * [1] M. Ashburner, C. A. Ball, J. A. Blake, D. Botstein, H. Butler, J. M. Cherry, A. P. Davis, K. Dolinski, S. S. Dwight, J. T. Eppig _et al._ , “Gene ontology: tool for the unification of biology,” _Nature genetics_ , vol. 25, no. 1, pp. 25–29, 2000.
  * [2] J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei, “Imagenet: A large-scale hierarchical image database,” in _CVPR_ , 2009, pp. 248–255.
  * [3] S. Gopal and Y. Yang, “Distributed training of large-scale logistic models.” in _ICML_ , 2013, pp. 289–297.
  * [4] A. Naik and H. Rangwala, “A ranking-based approach for hierarchical classification,” in _IEEE DSAA_ , 2015, pp. 1–10.
  * [5] S. Gopal and Y. Yang, “Recursive regularization for large-scale classification with hierarchical and graphical dependencies,” in _ACM SIGKDD_ , 2013, pp. 257–265.
  * [6] L. Xiao, D. Zhou, and M. Wu, “Hierarchical classification via orthogonal transfer,” in _ICML_ , 2011, pp. 801–808.
  * [7] B. Heisele, T. Serre, S. Prentice, and T. Poggio, “Hierarchical classification and feature reduction for fast face detection with support vector machines,” _Pattern Recognition_ , vol. 36, no. 9, pp. 2007–2017, 2003.
  * [8] T. Liu, Y. Yang, H. Wan, H. Zeng, Z. Chen, and W. Ma, “Support vector machines classification with a very large-scale taxonomy,” _ACM SIGKDD Explorations Newsletter_ , vol. 7, no. 1, pp. 36–43, 2005.
  * [9] L. Cai and T. Hofmann, “Hierarchical document categorization with support vector machines,” in _CIKM_ , 2004, pp. 78–87.
  * [10] A. Naik and H. Rangwala, “Inconsistent node flattening for improving top-down hierarchical classification,” in _IEEE DSAA_ , 2016.
  * [11] S. Dumais and H. Chen, “Hierarchical classification of web content,” in _ACM SIGIR_ , 2000, pp. 256–263.
  * [12] N. Cesa-Bianchi, C. Gentile, and L. Zaniboni, “Incremental algorithms for hierarchical classification,” _Journal of Machine Learning Research_ , vol. 7, no. Jan, pp. 31–54, 2006.
  * [13] C. Silla Jr and A. Freitas, “A survey of hierarchical classification across different application domains,” _Data Mining and Knowledge Discovery_ , vol. 22, no. 1-2, pp. 31–72, 2011.
  * [14] D. Koller and M. Sahami, “Hierarchically classifying documents using very few words,” in _ICML_ , 1997, pp. 170–178.
  * [15] N. Holden and A. A. Freitas, “A hybrid particle swarm/ant colony algorithm for the classification of hierarchical biological data,” in _SIS_ , 2005, pp. 100–107.
  * [16] T. Li and M. Ogihara, “Music genre classification with taxonomy,” in _IEEE International Conference on Acoustics, Speech, and Signal Processing_ , vol. 5, 2005, pp. v–197.
  * [17] A. Secker, M. N. Davies, A. A. Freitas, J. Timmis, M. Mendao, and D. R. Flower, “An experimental comparison of classification algorithms for the hierarchical prediction of protein function,” _Expert Update (the BCS-SGAI Magazine)_ , vol. 9, no. 3, pp. 17–22.
  * [18] J. Tang, S. Alelyani, and H. Liu, “Feature selection for classification: A review,” _Data Classification: Algorithms and Applications_ , p. 37, 2014\.
  * [19] M. Dash and H. Liu, “Feature selection for classification,” _Intelligent data analysis_ , vol. 1, no. 3, pp. 131–156, 1997.
  * [20] H. Peng, F. Long, and C. Ding, “Feature selection based on mutual information criteria of max-dependency, max-relevance, and min-redundancy,” _TPAMI_ , vol. 27, no. 8, pp. 1226–1238, 2005.
  * [21] Z. Zheng, X. Wu, and R. Srihari, “Feature selection for text categorization on imbalanced data,” _ACM SIGKDD Explorations Newsletter_ , vol. 6, no. 1, pp. 80–89, 2004.
  * [22] T. Joachims, “Text categorization with support vector machines: Learning with many relevant features,” in _ECML_ , 1998, pp. 137–142.
  * [23] R. Kohavi and G. H. John, “Wrappers for feature subset selection,” _Artificial intelligence_ , vol. 97, no. 1, pp. 273–324, 1997.
  * [24] P. Ristoski and H. Paulheim, “Feature selection in hierarchical feature spaces,” in _DS_. Springer, 2014, pp. 288–300.
  * [25] W. Wibowo and H. E. Williams, “Simple and accurate feature selection for hierarchical categorisation,” in _Proceedings of the ACM symposium on Document engineering_ , 2002, pp. 111–118.
  * [26] A. Naik, A. Charuvaka, and H. Rangwala, “Classifying documents within multiple hierarchical datasets using multi-task learning,” in _ICTAI_ , 2013, pp. 390–397.
  * [27] H. Ogura, H. Amano, and M. Kondo, “Feature selection with a measure of deviations from poisson in text categorization,” _Expert Systems with Applications_ , vol. 36, no. 3, pp. 6826–6832, 2009.
  * [28] W. Shang, H. Huang, H. Zhu, Y. Lin, Y. Qu, and Z. Wang, “A novel feature selection algorithm for text categorization,” _Expert Systems with Applications_ , vol. 33, no. 1, pp. 1–5, 2007.
  * [29] C. Ding and H. Peng, “Minimum redundancy feature selection from microarray gene expression data,” _Journal of bioinformatics and computational biology_ , vol. 3, no. 02, pp. 185–205, 2005.
  * [30] I. Dimitrovski, D. Kocev, S. Loskovska, and S. Džeroski, “Hierarchical annotation of medical images,” _Pattern Recognition_ , vol. 44, no. 10, pp. 2436–2449, 2011.
  * [31] Y. Yang, “An evaluation of statistical approaches to text categorization,” _Information retrieval_ , vol. 1, no. 1-2, pp. 69–90, 1999.
  * [32] C. Strobl and A. Zeileis, “Danger: High power! – exploring the statistical properties of a test for random forest variable importance,” in _COMPSTAT_ , 2008.
  * [33] Y. Yang and X. Liu, “A re-examination of text categorization methods,” in _ACM SIGIR_ , 1999, pp. 42–49.